Алгоритм Евклида для натуральных чисел: заменять большее из двух заданных чисел на их разность до тех пор, пока они не станут равны. Полученное число и есть их НОД.

Этот вариант алгоритма работает довольно медленно, если одно из чисел значительно меньше другого, например для пары чисел 2 и 2014. Значительно быстрее выполняется улучшенный (модифицированный) алгоритм Евклида.

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

Мы видим, что здесь тоже нужно выполнять некоторые операции несколько раз, причём сколько раз — заранее неизвестно. Но нас выручит цикл с условием, ведь мы знаем, когда нужно остановиться — когда какое-нибудь из двух чисел станет равно нулю.

Запишите условие, которое означает «одно из значений переменных а или b равно нулю». После этого запишите обратное условие.

Теперь мы готовы записать цикл:

Обратите внимание, что цикл содержит только один условный оператор, поэтому слова begin и end, ограничивающие тело цикла в программе на Паскале, можно не писать.

Остаётся вывести результат — ненулевое значение переменной а или b.

Запишите условный оператор, который выводит результат, проверяя одну из переменных на равенство нулю.

Из двух переменных, а и b, одна равна нулю, а вторая — не ноль. Запишите арифметическое выражение, которое всегда равно второй (ненулевой) переменной.

Количество шагов такого цикла заранее неизвестно и зависит от исходных данных. Дополним программу так, чтобы она считала ещё и количество сделанных шагов цикла. Для этого нужно ввести переменную-счётчик целого типа. Перед началом цикла счётчик обнуляется (в него записывается ноль), и на каждом шаге цикла значение счётчика увеличивается на единицу:

Вместо многоточия нужно вставить условный оператор, как и в предыдущем варианте программы. В цикле теперь находятся два оператора, поэтому в программе на Паскале нужно использовать составной оператор, ограниченный служебными словами begin и end.

Следующая страница Циклы в других языках программирования

Cкачать материалы урока

Уроки 35 - 41§ 20. Программирование циклических алгоритмов

Содержание урока

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

Уроки 35 - 41
§ 20. Программирование циклических алгоритмов