Презентация, доклад Алгоритм Евклида в задачах ЕГЭ

наибольшее целое число, которое делит их оба. Пример:
НОД(25, 5) = 5
НОД(12, 18) = 6

утверждения:
1. Все общие делители пары a и b являются также общими делителями пары a - b, b;
2. И наоборот, все общие делители пары a - b и b являются также общими делителями пары a и b;
3.НОД(A,  B) = НОД(A — B, B) ,
если A > B;
4. НОД(A, 0) = A.

большее на разность до тех пор, пока одно из чисел не обратится в нуль. Тогда оставшееся ненулевое число - наибольший общий делитель.

Пример. Пусть а = 82 и b = 60.
Найти НОД по алгоритму Евклида
НОД(82, 60)=?

= НОД(22, 60) = НОД(22, 38) = НОД(22, 16) = НОД(6, 16) = НОД(6, 10) = НОД(6, 4) = НОД(2, 4) = НОД(2, 2) = НОД(2, 0) = 2.
На предпоследнем шаге алгоритма, перед появлением 0, оба числа равны, иначе не мог возникнуть 0. Поэтому извлекать НОД надо именно в этот момент.

while a <> b do
if a > b then a := a - b
else b := b - a;
writeln('NOD = ', a);
end.

ПРОГРАММА

что x > 100. Укажите наименьшее такое (т.е. большее 100) число x, при вводе которого алгоритм печатает 26.
var x, L, M: integer;
begin
readln(x);
L := x;
M := 65;
if L mod 2 = 0 then M := 52;
while L <> M do { * }
if L > M then { * }
L := L – M { * }
else { * }
M := M – L; { * }
writeln(M);
end.

Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 2.
var x, L, M: integer;
begin
readln(x);
L := x-12;
M := x+12;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 11.

var x, L, M: integer;
begin
readln(x);
L := x-21;
M := x+12;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 35.

var x, L, M: integer;
begin
readln(x);
L := x-15;
M := x+20;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

M. Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 9.

var x, L, M: integer;
begin
readln(x);
L := x-18;
M := x+36;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 35.

var x, L, M: integer;
begin
readln(x);
L := x-20;
M := x+15;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 4.

var x, L, M: integer;
begin
readln(x);
L := x-16;
M := x+32;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

Известно, что x > 100. Укажите наименьшее такое (т. е. большее 100) число x, при вводе которого алгоритм печатает 16.

var x, L, M: integer;
begin
readln(x);
L := x-16;
M := x+16;
while L <> M do
if L > M then
L := L - M
else
M := M – L;
writeln(M);
end.

125
№82 108
№83 128

Евклид http://pobedpix.com/evklid-kartinka