§. ПМ Алгоритм Евклида в Python
Выполните приведённую выше программу в любой доступной вам среде программирования на языке Python 3. Протестируйте программу на последовательности из пяти чисел: 16, 32, 40, 80 и 128. Верно ли работает программа?
Решение
В примере процедура nod(a, b) применяет алгоритм Евклида вычитанием и записывает найденный НОД в глобальную переменную x. Основная программа начинает с первого числа, затем по очереди присоединяет остальные. Для проверки введём сначала количество чисел , затем , , , , .
| Шаг |
Текущее x |
Следующее число |
Новое x |
| Начало |
|
— |
|
|
|
|
НОД(, ) = |
|
|
|
НОД(, ) = |
|
|
|
НОД(, ) = |
|
|
|
НОД(, ) = |
Например, для пары и вычитаем , , : при равенстве НОД равен . В цикле for i in range(, k) при k = получается четыре вызова, как раз для чисел после первого. Значит будет напечатано НОД= . Число делит все пять чисел, а большего общего делителя у и нет, так что результат верен.
Ответ
Да. Программа выводит «НОД= ».
