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

Материал из CustisWiki

Версия от 12:55, 4 августа 2008; WikiSysop (обсуждение | вклад) (1 версия)

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

Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД, в англоязычной литературе - 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) арифметических операций над натуральными числами.


Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.