https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0 2026-05-03T04:53:44Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0&diff=873&oldid=prev 2008-10-23T16:47:53Z

<p>1 версия</p> <p><b>Новая страница</b></p><div>Алгоритм Евклида предназначен для нахождения наибольшего общего делителя (НОД, в англоязычной литературе - GCD - ''Greatest Common Divisor'') двух целых чисел.<br /> Для упрощения, ниже будем считать, что &lt;m&gt;a \leq b&lt;/m&gt;. <br /> <br /> Реализация на языке [[Python]] и пример выполнения:<br /> <br /> &lt;code-python&gt;<br /> def gcd(a, b):<br /> print a,b<br /> if a == 0:<br /> return b<br /> return gcd(b % a, a)<br /> &lt;/code-python&gt;<br /> <br /> Calculating gcd( 123456 , 6122256 ):<br /> 123456 6122256<br /> 72912 123456<br /> 50544 72912<br /> 22368 50544<br /> 5808 22368<br /> 4944 5808<br /> 864 4944<br /> 624 864<br /> 240 624<br /> 144 240<br /> 96 144<br /> 48 96<br /> 0 48<br /> gcd( 123456 , 6122256 )= 48<br /> <br /> <br /> Время работы алгоритма Евклида составляет ''O(log a +log b)'' арифметических операций над натуральными числами.<br /> <br /> [[Category:Алгоритмы]]<br /> {{replicate-from-custiswiki-to-lib}}</div>

WikiSysop