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

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

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

Код программы на 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.

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

Алгоритм Евклида. Метод деления 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.

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

Источник :