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

Материал из CustisWiki

Версия от 03:43, 24 августа 2005; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Это снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений.
Перейти к: навигация, поиск

Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД, в англоязычной литературе - GCD - Greatest Common Divisor) двух целых чисел. Для упрощения, ниже будем считать, что .

Реализация на языке Python и пример выполнения:

 def gcd(a, b):
    print a,b
    if a == 0:
            return b
    return gcd(b % a, a)
Calculating gcd( 123456 , 6122256 ):
123456 6122256
72912 123456
50544 72912
22368 50544
5808 22368
4944 5808
864 4944
624 864
240 624
144 240
96 144
48 96
0 48
gcd( 123456 , 6122256 )= 48


Время работы алгоритма Евклида составляет O(log a +log b) арифметических операций над натуральными числами.


Внимание! Эта статья была создана путем автоматического реплицирования из внутренней базы знаний компании Заказные Информ Системы. Любые правки этой статьи могут быть перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».