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

Алгоритм Евклида Наибольший общий делитель (НОД) двух чисел 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