Алгоритм Евклида
Ключевые слова: теория чисел, лекции, примеры решений задач.
Пусть даны два числа a и b ; a ≥ 0, b ≥ 0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание.
Алгоритм:
1. Ввести a и b .
2. Если b = 0 , то Ответ: а . Конец .
3. Заменить r := "остаток от деления а на b ", а := b , b := r .
4. Идти на 2.
В современной буквенной записи алгоритм Евклида выглядит так: a > b; a, b ∈ Z .
Пусть даны два числа a и b ; a ≥ 0, b ≥ 0, считаем, что a > b . Символом := в записи алгоритма обозначаем присваивание.
Алгоритм:
1. Ввести a и b .
2. Если b = 0 , то Ответ: а . Конец .
3. Заменить r := "остаток от деления а на b ", а := b , b := r .
4. Идти на 2.
В современной буквенной записи алгоритм Евклида выглядит так: a > b; a, b ∈ Z .
Имеем: b > r1 > r2 >... > rn > 0, следовательно процесс оборвется максимум через b шагов.
Пример. Пусть а = 525, b = 231. Алгоритм Евклида: (ниже приводится запись деления уголком, и каждый раз то, что было в уголке, т.е. делитель, приписывается к остатку от деления с левой стороны, а остаток, как новый делитель, берется в уголок)
Запись того же самого в виде цепочки равенств:
Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:
Похожие материалы:
Примеры решений задач
Готовые работы