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

Алгоритм Евклида

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

Пусть a и b - это целые числа, тогда верны следующие утверждения:
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. Поэтому извлекать НОД надо именно в этот момент.

Получив на вход число x, этот алгоритм печатает число M. Известно, что 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.

№77 Получив на вход число x, этот алгоритм печатает число M. Известно, что 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.

№ 78 Получив на вход число x, этот алгоритм печатает число 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.

№ 79 Получив на вход число x, этот алгоритм печатает число 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.

№ 80 Получив на вход число x, этот алгоритм печатает число 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.

№81 Получив на вход число x, этот алгоритм печатает число M. Известно, что 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.

№82 Получив на вход число x, этот алгоритм печатает число M. Известно, что 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.

№83 Получив на вход число x, этот алгоритм печатает число M. Известно, что 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.