Персональные инструменты
 

Алгоритм Евклида — различия между версиями

Материал из CustisWiki

Перейти к: навигация, поиск
м (обновление данных)
м (Содержимое страницы заменено на «#REDIRECT [[discopal:{{PAGENAME}}]]»)
 
(не показана 1 промежуточная версия 1 участника)
Строка 1: Строка 1:
Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД, в англоязычной литературе - GCD - ''Greatest Common Divisor'') двух целых чисел.
+
#REDIRECT [[discopal:{{PAGENAME}}]]
Для упрощения, ниже будем считать, что <m>a \leq b</m>.
+
 
+
Реализация на языке [[Python]] и пример выполнения:
+
 
+
<code-python>
+
def gcd(a, b):
+
    print a,b
+
    if a == 0:
+
            return b
+
    return gcd(b % a, a)
+
</code-python>
+
 
+
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)''  арифметических операций над натуральными числами.
+
 
+
[[Category:Алгоритмы]]
+
{{replicate-from-custiswiki-to-lib}}
+

Текущая версия на 20:42, 13 июня 2011

  1. REDIRECT discopal:Алгоритм Евклида