|
|
| Строка 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}} | + | |
