Алгоритм Евклида. Два варианта решения Программирование. Сочетание циклов и ветвлений. 9 класс Евклид Александрийский ( род. 330 г. до н. э.) - известный. - презентация

1 Алгоритм Евклида. Два варианта решения Программирование. Сочетание циклов и ветвлений. 9 класс Евклид Александрийский ( род. 330 г. до н. э.) - известный древнегреческий математик, автор первого из дошедших до нас теоретического трактата по математике Учитель информатики : Грынина Т. Ю.

2 Наибольший общий делитель Когда говорят « число делиться », то имеют в виду, что оно делиться без остатка. Так A делиться на B, лишь в том случае, если остаток от их деления равен нулю. На этом свойстве основывается понятие наибольшего общего делителя ( НОД ). НОД двух чисел это наибольший из всех их общих делителей.

3 Алгоритм Евклида. Метод вычитания Найти НОД двух целых чисел немного проще используя операцию вычитания. Для этого потребуется следовать такому условию : если A=B, то НОД найден и он равен одному из чисел, иначе необходимо большее из двух чисел заменить разностью его и меньшего.

4 Код программы на Pascal ( вычитание ): program AlgEvklid 2; var A, B: integer; { алгоритм Евклида. Вычитание. Функция } function NOD(A, B: integer): integer; begin while A<>B do if A>B then A:=A-B else B:=B-A; NOD:=A; end; { основной блок программы } begin write( Введите A '); read(A); write(' Введите B '); read(B); write(' НОД (', A, ', ', B, ')=', NOD(A, B)); end. program AlgEvklid 1; var A, B: integer; { алгоритм Евклида. Вычитание } begin write( Введите A '); read(A); write(' Введите B '); read(B); while A<>B do begin if A>B then A:=A-B else B:=B-A; NOD:=A; end; write(' НОД (', A, ', ', B, ')=', NOD); end. program AlgEvklid 1; var A, B: integer; { алгоритм Евклида. Вычитание } begin write( Введите A '); read(A); write(' Введите B '); read(B); while A<>B do begin if A>B then A:=A-B else B:=B-A; NOD:=A; end; write(' НОД (', A, ', ', B, ')=', NOD); end.

5 Алгоритм Евклида. Метод деления Второй способ отличается от первого тем, что в основной части программы операция вычитания заменяется на операцию деления, а точнее на взятие остатка от деления большого числа на меньшее. Этот способ предпочтительнее предыдущего, так как он в большинстве случаев эффективнее, требует меньше времени. На конкретных примерах продемонстрируем работу каждого из видов реализации алгоритма. Начнем с того, в основе которого лежит операция взятия остатка от деления. Имеем два числа : 112 и 32. Первое больше второго – заменим его остатком от деления 112 на 32. Новая пара чисел включает 16 и 32. Второе больше, поэтому также заменим его остатком от деления 32 на 16, т. е. нулем. В результате получаем НОД =16. Таблично это выглядит так : То же методом вычитания : Выигрыш в быстродействии

6 Алгоритм Евклида. Метод деления program AlgEvklid; var A, B: integer; { алгоритм Евклида. Деление. Функция } function NOD(a, B: integer): integer; begin while (A<>0) and (B<>0) do if A>B then A:=A mod B else B:=B mod A; NOD:=A+B end; { основной блок программы } begin write( Введите A '); read(A); write(' Введите B '); read(B); write(' НОД (', A, ', ', B, ')=', NOD(A, B)); end. program AlgEvklid; var A, B: integer; { алгоритм Евклида. Деление. Функция } function NOD(a, B: integer): integer; begin while (A<>0) and (B<>0) do if A>B then A:=A mod B else B:=B mod A; NOD:=A+B end; { основной блок программы } begin write( Введите A '); read(A); write(' Введите B '); read(B); write(' НОД (', A, ', ', B, ')=', NOD(A, B)); end.

7 Самостоятельная работа Написать программу нахождения наибольшего общего делителя методом деления без использования процедуры - функции program AlgEvklid; … end. program AlgEvklid; … end. Тест : Входные данные : Выходные данные : НОД (51,119)=17 Тест : Входные данные : Выходные данные : НОД (51,119)=17

8 Источник :