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

  • Презентации учебные
  • pptx
  • 26.03.2017
Публикация в СМИ для учителей

Публикация в СМИ для учителей

Бесплатное участие. Свидетельство СМИ сразу.
Мгновенные 10 документов в портфолио.

Пусть 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.
Иконка файла материала 0003c511-f69a80e9.pptx

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

Наибольший общий делитель (НОД) двух чисел 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)=?

Пример. Пусть а = 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. Поэтому извлекать НОД надо именно в этот момент.

БЛОК-СХЕМА

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

ПРОГРАММА

Алгоритм Евклида
в задачах ЕГЭ

ЕГЭ №20

Получив на вход число 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.

ОТВЕТЫ
Пример: 130
№77 106
№78 109
№79 120
№80 117
№81 125
№82 108
№83 128

Используемые источники:
1. Алгоритм Евклида http://learnpascal.ru/algoritmy/algoritm-evklida-1.html
2. Сайт Полякова К.Ю. http://kpolyakov.spb.ru/school/ege.htm
3. Евклид http://pobedpix.com/evklid-kartinka