QuickCalculators запускает алгоритм Евклида для двух неотрицательных целых чисел, печатая каждое частное и остаток до тех пор, пока НОД не станет последним ненулевым остатком. Введите пару в любом порядке; в таблице шагов показана форма деления, поэтому каждую строку можно проверить вручную.
Найдите НОД повторным делением
Алгоритм Евклида находит наибольший общий делитель, разделив большее число на меньшее и заменив большее на остаток, а затем повторив. Когда появляется остаток от нуля, делителем этого шага является НОД. Калькулятор алгоритма Евклида записывает каждое деление, поэтому цепочку можно проверить.
Для 816 и 2260 начните с 2260 ÷ 816. Частное равно 2, а остаток равен 628. Далее 816 ÷ 628 оставляет остаток 188. Продолжайте до тех пор, пока нулевой остаток не остановит цепочку. Последний ненулевой остаток, это НОД исходной пары.
Прочитайте таблицу шагов
В таблице шагов указаны делимое, делитель, частное и остаток для каждого раунда. Чтение столбца остатка показывает последовательность сокращения, которая заканчивается нулем. QuickCalculators выравнивает эти столбцы, чтобы копия блокнота могла проверить, что a × b + r равно предыдущему делимому в каждой строке.
Компактный эскиз для 48 и 18:
| Дивиденды | Делитель | частное | Остаток |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
Последний ненулевой остаток равен 6, поэтому НОД(48, 18) = 6.
Избегайте этой распространенной ошибки
Форма вычитания и форма деления имеют один и тот же алгоритм. Деление, это многократное вычитание, сжатое в одно частное. Студенты иногда рассматривают их как конкурирующие методы с разными ответами. Оба заканчиваются в одном и том же НОД при правильном применении. Вычитание 18 из 48 дважды дает 12, а это именно то, что частное 2 кодирует в одной строке.
Предпочтение деления экономит время на записи, не меняя математический путь, описанный Евклидом.
Поймите, почему алгоритм всегда завершает работу
Каждый остаток представляет собой неотрицательное целое число, строго меньшее предыдущего делителя, поэтому последовательность остатков не может убывать вечно. Конечный спуск приводит к нулевому остатку после конечного числа шагов. Эта гарантия распространяется на все неотрицательные целочисленные входные данные, которые принимает страница.
Пары наихудшего случая, связанные с числами Фибоначчи, требуют больше шагов, чем типичные примеры в классе, но все же заканчиваются. Количество шагов растет примерно с логарифмом входных данных для обычных случайных пар, поэтому метод Евклида масштабируется за пределы факторов листинга.
Часто задаваемые вопросы
Что такое алгоритм Евклида?
Алгоритм Евклида, это метод нахождения наибольшего общего делителя двух неотрицательных целых чисел путем многократного деления с остатком. Последний ненулевой остаток, это НОД. Калькулятор распечатывает каждый из этих шагов деления.
Как алгоритм Евклида находит НОД?
Алгоритм Евклида находит НОД, заменяя большее число остатком после деления на меньшее число, повторяя это до тех пор, пока остаток не станет равным нулю. Делителем, используемым на последнем этапе с ненулевым остатком, является НОД.
Что такое НОД у 816 и 2260?
НОД из 816 и 2260 находится путем запуска алгоритма Евклида для этой пары и чтения последнего ненулевого остатка из таблицы шагов. Введите оба целых числа на этой странице, чтобы увидеть все частное и остаток по порядку.
Почему алгоритм Евклида работает?
Алгоритм Евклида работает, потому что любой общий делитель a и b также является общим делителем b и mod b. Замена пары меньшим числом и остатком сохраняет НОД до тех пор, пока остаток не достигнет нуля.
Сколько шагов занимает алгоритм Евклида?
Количество шагов, которые выполняет алгоритм Евклида, зависит от входных данных; каждый остаток меньше предыдущего делителя, поэтому процесс конечен. Пары типа Фибоначчи требуют больше шагов, чем в среднем, но типичные числа в классе заканчиваются быстро.
В чем разница между формами вычитания и деления?
Форма вычитания многократно вычитает меньшее из большего; форма деления вычитает массово, используя частное. Обе формы вычисляют один и тот же НОД. Деление, это просто повторяющееся вычитание, записанное компактно.
Краткое резюме
Калькулятор алгоритма Евклида находит НОД путем повторного деления и отображает каждое частное и остаток в пошаговой таблице. Такие пары, как 48 и 18, заканчиваются на остатке 6, что соответствует НОД(48, 18). Формы вычитания и деления выполняются по одному и тому же алгоритму на разных уровнях сжатия. Остатки строго уменьшаются, поэтому процесс всегда завершается для неотрицательных целых чисел.