Алгоритм Евклида как сведение к меньшей задаче
Алгоритм Евклида сохраняет общие делители двух целых чисел, заменяя более крупную задачу парой с остатком, которая быстро уменьшается.
Почему замена a и b на b и остаток сохраняет их наибольший общий делитель?
- Чтение remainder как следующего состояния задачи
- Определение инварианта общего делителя между вызовами
- Прослеживание точного целочисленного процесса до нулевого базового случая
- Сравнение уменьшающейся последовательности вызовов с итоговым ответом
Если число делит как a, так и b, оно также делит остаток от деления a на b. Обратное утверждение также верно, поэтому пара меняется, тогда как ее наибольший общий делитель остается прежним.
Каждый вызов заменяет (a, b) на (b, remainder(a, b)). Когда второе значение достигает нуля, первое значение является сохраненным наибольшим общим делителем. После рекурсивного вызова не остается отложенных арифметических действий.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает 2. Вторая программа возвращает 21.
Проследите за (206, 40), (40, 6), (6, 4), (4, 2) и (2, 0). Второй аргумент строго уменьшается до тех пор, пока базовый случай не раскроет инвариантный ответ.
Измените программу и сравните результат.
Запустите euclid со значениями 1999 и 97. Запишите каждую пару аргументов перед тем, как открыть итоговый наибольший общий делитель.
Показать подсказку
Примените remainder к текущей паре и переместите прежнее второе значение на первую позицию.