Даны натуральные числа m и n найти такие натуральные p и q не имеющие общих делителей что p q m n

TURBO PASCAL

Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (НОД) двух целых неотрицательных чисел.

Алгоритм Евклида нахождения НОД основан на следующих свойствах этой величины. Пусть x и y одновременно не равные нулю целые неотрицательные числа и пусть x>=y, тогда если y = 0, то НОД(x, y) = x, а если y не равен 0, то для чисел x, y и r, где r — остаток от деления x н аy выполняется равенство НОД(x, y) = НОД(y, r).

Например, пусть x = 48, а y = 18, найдем их наибольший общий делитель.

X	Y	Результаты
48	18
48 mod 8 = 12	18	x>y	НОД(48, 18) = НОД(12, 18)
12	18 mod 12 = 6	x<y	НОД(48, 18) = НОД(12, 6)
12 mod 6 = 0	6	x>y	НОД(12, 6) = НОД(0, 6)
0	6	x=0	НОД(0, 6) = 6

Таким образом, НОД(48, 18) = 6.

Пример

Написать программу нахождения наибольшего общего делителя (НОД) двух неотрицательных чисел.

Для решения данной задачи воспользуемся циклом с постусловием:

Пример

Даны натуральные числа x и y, неравные нулю одновременно. Найти d = НОД(x, y) и такие целые q и w, что d=q*x + w*y.

Добавим в алгоритм Евклида переменные p, q, r, s, m и n такие, что m = p*a + q*b, n = r*a + s*b, где первоначально m = a = x, n = b = y.

Рассмотрим решение задачи для чисел 48 и 18.

M	N	P	Q	R	S	Результаты
48	18	1	0	0	1	48 = 481 + 180, 18 = 480 + 181
48 mod 8 = 12	18	1	-2	0	0	m>n	12 = 481 + 18(-2)
12	18 mod 12 = 6	1	-2	-1	3	m<n	6 = 181 + 12(-1) =, 48(-1) + 183
12 mod 6 = 0	6	3	-8	-1	3	m>n	0 = 121 + 6(-2)=, 483 + 18(-8)
0	6	m = 0	d = n e = r w = s

Итак, d = НОД(48, 18) = 6 и 6 = 48*(-1) + 18*3.

Значения переменных p, q, r, s изменяются следующим образом:

как только значение переменной m уменьшается на k*n, значение p уменьшается на k*r, а q уменьшается на k*s;

аналогично, как только значение n уменьшается на k*m, значения переменных r и s уменьшаются соответственно на k*p и на k*q.

Учитывая всё, что сказано выше, составим программу:

Program Example_12;
Var x,y: Integer; <исходные данные>
p,q,r,s,m,n: Integer; <введённые вспомогательные переменные>
k: Integer; <для изменения значений p,q,r,s>
d: Integer; <значение наибольшего общего делителя>
Begin
Read(x,y);
m:=x; n:=y; p:=1; q:=0; r:=0; s:=1;
Repeat
If m>n Then Begin
k:=m Div n; m:=m Mod n;
p:=p-k*r; q:=q-k*s
End
Else Begin
k:=n Div m; n:=n Mod m; r:=r-k*p; s:=s-k*q End;
Until (m=0) Or (n=0);
If m=0 Then Begin
d:=n; q:=r; w:=s; End
Else Begin d:=m; q:=p; w:=q; End
Writeln(d,’=’,q,’*’,x,’+’,w,’*’,y);
End.

Примечание. НОД(a, b, c)= НОД(НОД(a, b), c)

НОК(n, m) = n * m / НОД (n, m).

Примечание. Воспользуйтесь алгоритмом, описанным в примере 2.

НОД(2a, 2b) = 2НОД(a, b);

НОД(2a, b) = НОД(a, b), при нечётном b,

не включающий деления с остатком, использующий лишь деление на 2 и проверку чётности.

Даны натуральные числа m и n найти такие натуральные p и q не имеющие общих делителей что p q m n

Профиль
Группа: Участник
Сообщений: 11
Регистрация: 13.4.2007

Репутация: нет
Всего: нет

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 12.6.2007

Репутация: нет
Всего: нет

Код

#include<iostream.h>
#include<conio.h>

Мож кто придумает проще?)

M
Pakshin A. S.

Не забываем выделять код специальными тегами!

Это сообщение отредактировал(а) Pakshin A. S. — 18.6.2007, 18:38

Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 97

Для четвёртой, наверное, ввел бы систему координат и запоминал пройдённые точки, затем каждый раз проверял, была ли такая точка. Через дерево, наверное, тоже можно. Составить его маршрут в виде дерева: корень — конец марщрута, при составлении "взвешивать его", по завершению составления можно найти наикротчайший маршрут и получить нужную строку.

Добавлено @ 17:29

Цитата(PIvO @ 9.6.2007, 19:09 )

1. Даны натуральные числа m и n. Найти такие числа m1 и n1, не имеющие общих делителей, что m1/n1=m/n. Числа m и n ввести с клавиатуры.

m1n=n1m, подбираем такие натуральные m1 и n1 и проверяем наличие общих делителей. По идее, не сложно, если не изощряться.

Добавлено @ 17:37

Цитата(PIvO @ 9.6.2007, 19:09 )

Сейчас думать некогда, но пришла такая идея. Подбором — слишком долго и просто. Есть 2 неизвестных, стало быть нужно получить >=2-х уравнений.

m div n = p div q
m mod n = p mod q

p = (m div n) * q
m mod n = ( (m div n) * q) mod q

Отсюда, по идее, можно выразить q.
А потом найти p.

Нужно проверить, не уверен, что пашет. Вечером или завтра код набью.

Это сообщение отредактировал(а) powerfox — 18.6.2007, 17:52

Профиль
Группа: Участник Клуба
Сообщений: 5056
Регистрация: 16.2.2003

Репутация: нет
Всего: 61

!
Pakshin A. S.

PIvO, не стоит создавать дубликаты темы; для решение проблем достаточно создать одну тему.

Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 97

Цитата(powerfox @ 18.6.2007, 18:27 )

Через дерево, наверное, тоже можно. Составить его маршрут в виде дерева: корень — конец марщрута, при составлении "взвешивать его", по завершению составления можно найти наикротчайший маршрут и получить нужную строку.

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 4
Всего: 401

Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 97

Цитата(SelenIT @ 21.6.2007, 22:46 )

Имхо, первая задача — это, фактически, обычное сокращение дроби: нужно найти наибольший общий делитель m и n (например, алгоритмом Евклида) и разделить оба числа на него.

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 4
Всего: 401

Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 97

SelenIT,
допустип числа 11 и 7.
У них нет общего делителя.
11 22
— = — здесь нарушается условие, что числа не должны иметь делителя, а очевидно, что делитель 2. Но можно подобрать такие, что будет выполняться
7 14

Твоё решение будет работать, только если дробь будет сократима (как раз найти наибольший делитель и поделить на него).

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 4
Всего: 401

Профиль
Группа: Комодератор
Сообщений: 3990
Регистрация: 1.10.2005
Где: Санкт-Петербург

Репутация: нет
Всего: 97

Цитата(SelenIT @ 22.6.2007, 00:15 )

owerfox, имхо, если дробь несократима, единственное решение задачи — сами m и n (по-моему, условие этого не запрещает). Любые другие пары чисел, удовлетворяющих пропорции, непременно будут иметь общий делитель. Разве не так?

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 4
Всего: 401

Код

function main(n) < // основная ф-ция
var s=[], d; // вспомогательные переменные — буфер вывода и НОД
var p=1, q=parseInt(n); // инициализация
while (p*n <= (n — 1)*q) // реальный интервал, очевидно, от 1/n до (n-1)/n
<
s.push(p + '/' + q); // вывод в "буфер" (у меня это массив — так удобнее)
for (var i=n; i>=1; i—) // ищем ближайшую след. дробь, сократимую до подходящего знаменателя
<
d = nod(p*i + 1, q*i);
if (q*i <= n*d)
<
p = (p*i + 1) / d;
q = q*i / d;
break;
>
>
>
document.getElementById('oo').innerHTML =
'<div style="float: left; width: 6em;">' +
s.join('</div><div style="float: left; width: 6em;">') +
'</div>'; // вывод "буфера"
>

Полагаю, перевести логику на C++ не проблема, тем более синтаксис похож — у меня в MS VC++ 2005 заработало, хотя я вообще C++ не знаю. 😉

Зато, в отличие от варианта Melarosы, оно выводит дроби по возрастанию (в соответствии с ТЗ) и не оставляет вещей типа 4/6.

P.S. Небольшое пояснение: т.к. знаменатель по условию не может превосходить n, то разность соседних дробей p1/q1 — p0/q0 ≥ 1/(n*q0) ≥ 1/(n*(n-1)) > 1/n² (например, при n=9, первые дроби — 1/9 и 1/8 — различаются на 1/72). Алгоритм ищет минимальную разность (т.е. максимальный общий знаменатель), при котором следующая дробь сократима до подходящего (не превышающего n) знаменателя, перебирая потенциально допустимые общие знаменатели по убыванию. Чувствую, что его можно еще изрядно оптимизировать.

Это сообщение отредактировал(а) SelenIT — 2.7.2007, 02:11

Профиль
Группа: Завсегдатай
Сообщений: 3996
Регистрация: 17.10.2006
Где: Pale Blue Dot

Репутация: 4
Всего: 401

Цитата

P/M = x/(2 в степени n) ≤ 1, Q/N = y/(2 в степени m) ≤ 1

Цитата

Q/M = x/(2 в степени n) ≤ 1, P/N = y/(2 в степени m) ≤ 1

где x, y, m и n — натуральные числа. Соответственно, у решения будут 2 ветви, каждая из которых опять же сводится к сокращению 2-х дробей и проверке знаменателя на принадлежность к ряду степеней двойки (по идее, можно битовыми операциями).

Что же до минимально нужного числа шагов, по-видимому, оценка нижней границы равна m+n. Насколько реальное количество шагов больше (сколько раз придется разгибать) — видимо, нужно анализировать x и y. есть интуитивная пока непроверенная догадка, что нужно считать нули в их двоичной записи.

Это сообщение отредактировал(а) SelenIT — 24.6.2007, 19:17

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 2
Всего: 18

Цитата

2. Дано натуральное число n. Напечатать в порядке возрастания все простые несократимые дроби, заключенные между 0 и 1, знаменатели которых не привышают n. Дроби выводить в формате p/q. Число n задать с клавиатуры.

Эту задачу можно решить безо всяких gcd и оптимизаций.
Гуглим по "ряд Фарея" — и будет вам алгоритм за линейное (относительно количества дробей в ответе) время.

Вообще, давать такие задачи на олимпиаде по программированию — плохой стиль. Кто-то, кто знает ряд Фарея или подобную систему Штерна-Броко, решит её за 5 минут, а другой может думать 2 часа и не придумать — это совсем не тривиальный алгоритм. (Если, конечно, там не маленькие ограничения на N были даны)

Это сообщение отредактировал(а) maxdiver — 20.12.2008, 09:45

Профиль
Группа: Завсегдатай
Сообщений: 1568
Регистрация: 18.7.2006
Где: Ivory tower

Репутация: нет
Всего: 37

Код

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

struct SCoord <
SCoord(int _x, int _y)
<
x = _x; y = _y;
>
bool operator== (const SCoord &rhs)
<
return (x == rhs.x && y == rhs.y);
>
int x, y;
>;

vector<SCoord> makeTraceFromString(string str)
<
vector<SCoord> vTrace;
vector<SCoord>::iterator iter;
SCoord current(0, 0);
int direction = 0; /* Direction */
int dx[] = <0, 1, 0, -1>;
int dy[] = <1, 0, -1, 0>;

string makeStringFromTrace(vector<SCoord> vTrace)
<
string str;
SCoord current(0, 0);

Информатика ЕГЭ 15 задание разбор

15 задание ЕГЭ «Основные законы алгебры логики»

15-е задание: «Основные законы алгебры логики»
Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 5 минут.

Проверяемые элементы содержания: Знание основных понятий и законов математической логики

Плейлист видеоразборов задания на YouTube:

Задания с множествами

Элементами множества А являются натуральные числа. Известно, что выражение

истинно (т. е. принимает значение 1) при любом значении переменной х .

Определите наименьшее возможное значение суммы элементов множества A .

Ответ: 12

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем пересечение (умножение) двух множеств Q и P . То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
Сумма элементов:

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Элементами множества А являются натуральные числа. Известно, что выражение

истинно (т. е. принимает значение 1) при любом значении переменной х .

Определите наименьшее возможное значение суммы элементов множества A .

Ответ: 18

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем пересечение (умножение) двух множеств Q и P . То есть необходимо выбрать элементы, которые встречаются в обоих множествах одновременно:
Сумма элементов:

Элементами множеств А , P , Q являются натуральные числа, причём P = <2, 4, 6, 8, 10, 12, 14, 16, 18, 20>, Q = <3, 6, 9, 12, 15, 18, 21, 24, 27, 30>. Известно, что выражение

истинно (т. е. принимает значение 1) при любом значении переменной х .

Определите наибольшее возможное количество элементов в множестве A .

Ответ: 7

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем разность двух множеств Q и P . То есть это новое множество, элементы которого принадлежат P , но не принадлежат Q :
Количество элементов = 7

Элементами множества А являются натуральные числа. Известно, что выражение

истинно (т. е. принимает значение 1) при любом значении переменной х .

Определите наименьшее возможное количество элементов множества A.

Ответ: 1

Введем обозначения:
Выполним преобразования:
Разделим выражение на две части — известную часть и неизвестную. Чтобы неизвестная часть ( А ) была непременно истинной, необходимо, чтобы известная часть была ложна:
То есть получаем:
Таким образом имеем пересечение двух множеств Q и P :
Количество элементов = 1

Задания с отрезками на числовой прямой

Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

Укажите наибольшую возможную длину отрезка А, для которого формула

тождественно ложна, то есть принимает значение 0 при любом значении переменной x.

Ответ: 4

Упростим формулу, избавившись от ‘x ϵ‘:
Теперь преобразуем импликацию в скобках:

решение 15 задания егэ по информатике

✎ Решение 2 (программирование):
Внимание! этот способ подходит НЕ для всех заданий с отрезками!
Python:

def f(a1,a2,x): return((44<=x<=48)<=(23<=x<=35))and(a1<=x<=a2) maxim = 0 for a1 in range (1,200): for a2 in range (a1+1,200): if all(f(a1,a2,x)==0 for x in range (1,200)):# если все ложны if a2-a1>maxim: maxim=a2-a1 print(a1,a2, a2-a1) # сами точки отрезка и длина

PascalABC.net:

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].

Укажите наибольшую возможную длину отрезка A, для которого формула

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Ответ: 10

Упростим выражение, введя обозначения:
Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
Избавимся от импликации:
Используем закон Де Моргана для последующего преобразования:
А — наше неизвестное, а выделенную часть формулы можно найти. Необходимо, чтобы А = 1. Значит предположим, что ¬А = 0, тогда P ∧ ¬Q = 1 (если P ∧ ¬Q = 0, то ¬А может равняться и 0 и 1, так как имеет место операция логического сложения ∨)
Значит, имеем P ∧ ¬Q = 1. Кроме того, в данном случае имеет место операция конъюнкция, которую проще вычислить, если выражение равно 1 (так как для конъюнкции существует один единственный случай истинности: 1 & 1 = 1). Таким образом имеем утверждения:
Т.е. A истинно (=1) на промежутке пересечения отрезков P и ¬Q.
Отобразим отрезки на числовой прямой, чтобы найти искомое значение:

решение 15 задания ЕГЭ с числовой прямой

Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].

Укажите наибольшую возможную длину отрезка A, для которого формула

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Ответ: 8

Упростим выражение, введя обозначения:
Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
Избавимся от импликации:

Далее возможно 2 способа решения.

15 задание ЕГЭ отрезки

✎ 2 способ:
После того, как мы избавились от импликации, имеем:

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Отрезки на числовой прямой:

На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].

Укажите наибольшую возможную длину отрезка A, для которого формула

тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

Ответ: 19

Упростим выражение, введя обозначения:
Запишем формулу с новыми обозначениями, учитывая, что по условию она должна быть тождественно истинной:
Избавимся от импликации:
А — наше неизвестное, тогда как выделенную часть формулы можно найти. Введем предположение, что А = 1. Значит, ¬А = 0 (т.е. А = 1), тогда ¬(P

Задания с ДЕЛ

Поиск наибольшего А, известная часть Дел ∨ Дел = 1

Для какого наибольшего натурального числа А формула

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 8

Введем обозначения:

Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):

Избавимся от импликации:

Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:

В полученной формуле необходимо, чтобы искомая часть с A в конечном счете было истинно.

Далее можно решать задание либо с помощью кругов Эйлера, либо с помощью логических рассуждений.

Решение с помощью логических рассуждений:

Решение с помощью кругов Эйлера:

Результат: 8

✎ Решение 2 (программирование):
Python:

for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 40 == 0) or (x % 64 == 0))<=(x % A== 0) if OK: print( A )

PascalABC.net:

begin for var A := 1 to 500 do begin var ok := 1; for var x := 1 to 1000 do begin if (((x mod 40 = 0) or (x mod 64 = 0)) <= (x mod A = 0)) = false then begin ok := 0; break; end; end; if (ok = 1) then print(A) end; end.

Результат: 8

Поиск наименьшего А, известная часть Дел ∧ ¬Дел = 1

Для какого наименьшего натурального числа А формула

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 3

Избавимся от импликации:

✎ Решение 2 (программирование). Язык Python, Pascal:

Из общего выражения:

for A in range(1,50): OK = 1 for x in range(1,1000): OK *= (x % A == 0) <= ((x % 28 != 0) or (x % 42== 0)) if OK: print( A ) break

begin for var A := 1 to 50 do begin var ok := 1; for var x := 1 to 1000 do begin if (x mod A = 0) <= ((x mod 28 <> 0)or (x mod 42 = 0)) = false then begin ok := 0; break; end; end; if (ok = 1) then begin print(A); break; end end; end.

Результат: 3

Для какого наименьшего натурального числа А формула

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 285

Введем обозначения:

Перепишем исходную формулу, согласно введенным обозначениям. Укажем, что формула должна быть тождественно истинна (по условию):

Избавимся от импликации:

Разделим данную формулу на две части: в одной из них — искомое A, а в другой — часть формулы с x, которую можно найти:

Начнем с известной части — части 2 формулы. В ней находится операция конъюнкция, которую проще найти, когда все ее операнды равны 1 (единственный случай для конъюнкции: 1 ∧ 1 = 1).

Вторая часть общей формулы может равняться только1, когда ¬A = 0 (если ¬A = 1, то вторая часть может равнять 0, а нам нужно 1) :

Т.е. получаем:

Таким образом, имеем:

Очевидно, что наименьшим x можем взять число 285 (15 * 19 = 285): ДЕЛ(285, 19) и ДЕЛ(285, 15)

Поскольку мы ищем наименьшее A, такое что: ДЕЛ(x, A) и при этом ДЕЛ(x, 19) и ДЕЛ(x, 15), то нам необходимо найти наименьшее делимое чисел 19 и 15:

A должно быть таким числом, при котором x принимает единственно возможное (наименьшее) значение 285:

Таким наименьшим A является само число 285 .

✎ Решение 2 (программирование):
Python:
Из общего выражения:

for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 19 != 0) or (x % 15 != 0))<= (x % A!= 0) if OK: print( A )

Задания с поразрядной конъюнкцией

Для какого наименьшего неотрицательного целого числа A формула

тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?

Ответ: 3

Рассмотрим один из вариантов решения:

Удалим из формулы X&, чтобы сократить ее запись:

Обратим внимание, что внешней операцией является конъюнкция — логическое умножение:

Разделим общее выражение на две части относительно внешней операции. Первая часть — неизвестная, искомая, а вторая — известная, ее можно вычислить:

Выполним некоторые преобразования во второй части формулы:

Зная свойство импликации, преобразуем формулу (избавимся от импликации в скобках):

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Для какого наибольшего неотрицательного целого числа A формула

тождественно истинна (то есть принимает значение 1 при любом неотрицательном значении переменной X)?

Ответ: 38

Результат: 38

Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение

тождественно ложно (то есть принимает значение 0 при любом натуральном значении переменной х)?

Ответ: 48

Кратко изложенное решение *:

Результат: 48

Определите набольшее натуральное число A, такое что выражение

тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?

Ответ: 8

Для упрощения восприятия введем обозначения:

Таким образом, получим следующее выражение:

Упростим выражение по свойству импликации для второй скобки:

Упростим левую часть, используя свойство 2 ( Z_k + Z_m = Z_{k and m} ):

То есть получили z26 ∨ z13 = z8

По правилу импликации: все единичные биты двоичной записи результата (z78 ∨ A) должны входить во множество единичных битов двоичной записи z8.

Рассмотрим:

Для А единичными битами должны быть общие единичные биты для z8 (1000₂). Т.е. в нашим случае — это один бит — 3-й:

Результат: 8

Задания на поиск наибольшего или наименьшего числа А

Поиск наибольшего или наименьшего числа А:

Для какого наибольшего целого числа А формула
alt=»демоверсия егэ 2018 решение 15 (18) задания» width=»500″ height=»42″ />
тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

Ответ: 99

begin for var A := 200 downto -100 do begin var OK := 1; for var x := 0 to 100 do for var y := 0 to 100 do if ((x <= 9) <= (x * x <= A)) and ((y * y <= A) <= (y <= 9)) = false then begin OK := 0; break; end; if OK = 1 then begin print(A); break end; end; end.

for A in range(200,-100,-1): OK = 1 for x in range(0,100): for y in range(0,100): OK *= ((x<=9) <= (x*x<=A)) and((y*y<=A) <= (y<=9)) if OK: print(A) break

✎ Способ 2 (теоретическое решение):

Условно разделим исходное выражение на части:

(импликация 0 → 0 = 1)

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Поиск наибольшего или наименьшего числа А:

Укажите наименьшее значение А, при котором выражение

истинно для любых целых положительных значений x и y.

Ответ: 101

begin for var A := -100 to 200 do begin var OK := 1; for var x := 1 to 100 do for var y := 1 to 100 do if ((y+3*x<A) or (x >20)or(y>40)) = false then begin OK := 0; break; end; if OK = 1 then begin print(A); break end; end; end.

for A in range(-100,200): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (y+3*x<A) or (x > 20) or (y > 40) if OK: print(A) break

✎ Способ 2 (теоретическое решение):

Определим основные части выражения, выделив отдельно неизвестную часть — с А, и, так сказать, известную часть, то есть остальную.

Поскольку основными операциями являются операции дизъюнкции (логического сложения) и порядок их выполнения не важен, то последней, внешней, операцией будем выполнять дизъюнкцию слева, т.к. она объединяет неизвестную и известную часть.

Сначала важно рассмотреть вторую часть выражения, известную, так как от нее будет зависеть значение A. Если вторая часть истинна, то А может быть как = 1, так и = 0. Такой вариант нам не подходит:

Соответственно, рассмотрим вариант, когда вторая часть ложна, тогда часть выражения с неизвестным А будет обязательно истинной, т.е.:

Дизъюнкция ложна, когда оба операнда ложны, т.е. из второго пункта имеем:

Для того, чтобы перекрыть все x и все y, возьмем наибольшие из возможных значений: x = 20, y = 40.

Выразим А:

Поскольку требуется найти наименьшее значение А, то имеем А = 101 .

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Поиск наибольшего и наименьшего числа A:

Для какого наибольшего целого неотрицательного числа А выражение

(48 ≠ y + 2x) ∨ (A Показать решение:

Разделим общее выражение на две части. Выделим неизвестную часть красным:

Неизвестная часть должна быть истинной, она обязательно будет истинна, если известная часть — ложь:

Т.е. 48 ≠ y + 2x = 0 или y + 2x = 48. На графике это уравнение представляет линию. Из условия имеем два ограничения:(x > 0) and (y > 0). Отобразим линию для 1-й четверти, соответствующей положительным x и y:

✎ Решение 2 (программное):
Python:

for A in range(200,0,-1): OK = 1 for x in range(0,100): for y in range(0,100): OK *= (48!=y+2*x) or(A<x)or (A<y) if OK: print(A) break

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Поиск наибольшего и наименьшего числа A:

Для какого наименьшего целого числа А формула

(y + 5x 4) ∨ (y Показать решение:

Общая идея такова:
необходимо упростить формулу так, чтобы последняя операция (внешняя) выполнялась со скобкой, в которой находится искомое A. После чего разделить формулу на две части, в одной из которых находится искомое.

Избавимся от импликации, это даст нам возможность опустить общие скобки во второй части формулы:

Разделим формулу на две части таким образом, чтобы внешняя операции отделяла часть, в которой находится искомое A:

Формула по условию должна быть истинной (=1). Внешняя операция — дизъюнкция — истинна аж в трех случаях: a=1 b=0, a=0 b=1, a=1 b=1.

Если мы допустим, что первая часть истинна, то вторая, искомая часть, может быть как истинной, так и ложной. Поэтому такой вариант не подходит.

Допустим, что первая часть ложна, тогда вторая, искомая часть, должна быть только истинной:

С учетом, что в первой части формулу находится операция дизъюнкция, которая ложна только в одном случае (a=0 b=0), то выпишем утверждения, получившиеся из первой части:

Кроме того, имеем еще одно утверждение второй части:

Отобразим получившиеся уравнения прямых на плоскости:

✎ Решение 2 (программное):
Python:

for A in range(-100,100): OK = 1 for x in range(0,100): for y in range(0,100): OK *= (y+5*x<=34)<=((y-x >4)or(y<=A)) if OK: print( A ) break

begin for var A := -100 to 100 do begin var OK := true; for var x := 0 to 100 do begin for var y := 0 to 100 do begin OK := (y + 5 * x <= 34) <= ((y — x > 4) or (y <= A)); if OK = false then break; end; if OK = false then break; end; if OK then begin print(A); break; end; end; end.

Поиск наибольшего и наименьшего числа A:

Укажите наименьшее целое значение А при котором выражение

(2y + 5x 100) ∨ (3x – 2y > 70)

истинно для любых целых положительных значений x и y.

Ответ: 171

✎ Решение (программное):
Python:

for A in range(-200,200): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x — 2*y > 70) if OK: print( A ) break

begin for var A := -200 to 200 do begin var OK := true; for var x := 1 to 100 do begin for var y := 1 to 100 do begin OK := (2*y + 5*x < A) or (2*x + 4*y > 100) or (3*x — 2*y > 70); if OK = false then break; end; if OK = false then break; end; if OK then begin print(A); break; end; end; end.

📹 Видео (аналитическое решение)
📹 Видеорешение на RuTube здесь

Поиск наибольшего и наименьшего числа A:

Укажите наибольшее целое значение А при котором выражение

(3y – x > A) ∨ (2x + 3y Показать решение:

✎ Решение 1 (теоретическое):

✎ Решение 2 (программное):
Python:

for A in range(200,-200,-1): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (3*y-x>A) or (2*x+3*y<30) or (2*y-x<-31) if OK: print(A) break

Похожие публикации:

Как в ворде закрыть документ клавиатурой

Как прикреплять ссылку в ворде

Формат а6 в ворде как сделать

Где посмотреть баланс steam