Help me!!!
Автор: Aferist (---.eltech.ru)
Дата:   24 Апр 2002 13:28

Норад никто не знает расширенный Алгоритм Евклида??
Если кто нить хоть чтонибудь знает напишите плизззззззззз.
Срочно надо.Заранее спасибо.
 Re: Help me!!!
Автор: Agent (---.cell.ru)
Дата:   24 Апр 2002 14:13

Наибольший общий делитель двух целых чисел (алгоритм Евклида):

Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое делит эти два числа. По определению НОД(0,0)=0.

Данный алгоритм вычисления НОД двух целых чисел a и b состоит в следующем: если хотя бы одно из чисел равно нулю, то НОД(a,b)=|a+b|, в других случаях последовательно находятся остатки ri от делений:

a на b-a=bq1+r1,
b на r1-b=r1q2+r2,
r1 на r2-r1=r2q3+r3,
. . . . . .
и т.д., пока rn+1 не станет равно нулю. Тогда НОД(a,b)=НОД(b,r1)=НОД(r1 ,r2)=...=НОД(rn-1 ,rn )=rn.


--------------------------------------------------------------------------------

Наибольший общий делитель двух целых чисел (бинарный алгоритм Евклида):

Данный алгоритм вычисления НОД(a,b) основан на бинарном алгоритме Евклида. Вычисления проводятся на основании следующих свойств НОД:

НОД(2m,2n)=2 НОД(m,n),
НОД(2m,2n+1)= НОД(m,2n+1),
НОД(-m,n)= НОД(m,n).

--------------------------------------------------------------------------------

Наибольший общий делитель двух целых чисел (расширенный алгоритм Евклида):

Алгоритм, кроме поиска НОД двух целых чисел a,b также находит величины x,y, т.ч. ax+by=НОД(a,b). Алгоритм включает в себя алгоритм Евклида и похож на алгоритм решения диофантового уравнения.


http://vmk.hut.ru/index.php?id=8&bk=002&cp=01#exteucl