#5 31.10.06 22:02
Re: Насчет лаб по информатике
какой адский код
не осилил )
Пока малое больше нуля, повторяй:
НОД ему временно ты приравняй,
И большое на малое ты раздели,
И остаток ты малым теперь назови,
А большим НОД назови ты теперь
И к началу вернись, и в Евклида ты верь!
Исправлено xaver (31.10.06 22:06)
Offline
#6 31.10.06 22:04
Re: Насчет лаб по информатике
Наибольший общий делитель двух целых чисел (алгоритм Евклида)
Наибольшим общим делителем (НОД) двух целых чисел называется такое наибольшее по модулю число, которое нацело делит эти два числа. По определению НОД(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.
А вот как этот алгоритм описан в книге Д.Э. Кнута "Искусство программирования".
1) [Проверка] Если a<b, то a<->b.
2) [Нахождение остатка] Разделим a на b, и пусть остаток от деления будет равен r (где 0<=r<b).
3) [Сравнение с нулем] Если r=0, то выполнение алгоритма прекращается; b - искомое значение.
4) [Замещение] Присвоить a<-b, b<-r и вернуться к шагу 1.
реализация данного алгоритма на Паскале:
function nod(a,b: integer):integer;
begin
if a<b then begin
a := a xor b;
b := a xor b;
a := a xor b;
end;
while not ((a=0) or (b=0)) do
if a >= b then a := a mod b else b := b mod a;
if a = 0 then result := b else result := a;
end;
Offline
#7 31.10.06 22:46
Re: Насчет лаб по информатике
xaver написал(а):
function nod(a,b: integer):integer;
begin
if a<b then begin
a := a xor b;
b := a xor b;
a := a xor b;
end;
while not ((a=0) or (b=0)) do
if a >= b then a := a mod b else b := b mod a;
if a = 0 then result := b else result := a;
end;
клёво! ))
только зачем нужно лишнюю перестановку (if a<b then ...XOR....) выполнять, если здесь (if a >= b then a := a mod b else b := b mod a;) уже есть сравнение
?
Offline
#9 01.11.06 13:53
Re: Насчет лаб по информатике
Смайлек, xaver, ацццццкие какие-то алгоритмы :(((
Код::
if(a==0||b==0)
return a+b;
a = a>0?a:-a;
b = b>0?b:-b;
while(a!=b)
{
if( a>b )
{
a = a-b;
}
else
{
b = b-a;
}
}
return a;за ненадобностью можно оставить тока один цикл.
Где нашел не знаю, но почему то его предваряет описание алгоритма Эвклида с делениями.
Offline
