|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Bunin Oleg 2:5020/400 18 Apr 2002 10:09:08
To : Max Medvedev
Subject : Re: Аннулирющий многочлен min степени
--------------------------------------------------------------------------------
function GCDNumSet(Cnt:integer; var NSet):longint;
{ Hаибольший общий делитель массива целых чисел }
label 1;
type LongAr=array[0..100] of longint;
var m,i,c1,c2,y1,y2,q,Result:longint;
begin
{ find first non-zero integer }
Result:=0;
m:=0;
while m<Cnt do begin
if LongAr(NSet)[m]<>0 then begin
Result:=1; break
end;
Inc(m)
end;
{ all zero input results in zero GCD and all zero multipliers }
if Result=0 then exit;
{ if last number is the only non-zero number, exit immediately }
if m=Cnt-1 then begin
Result:=LongAr(NSet)[m];
GCDNumSet:=Result;
exit
end;
{ check the sign of NSet[m] }
if LongAr(NSet)[m]<0 then LongAr(NSet)[m]:=-LongAr(NSet)[m];
{ calculate GCD via Cnt-1 applications of the GCD algorithm for two
integers. Save the multipliers. }
c1:=LongAr(NSet)[m];
i:=m+1;
while i<Cnt do begin
if LongAr(NSet)[i]=0 then LongAr(NSet)[i]:=1
else begin
y1:=1;
y2:=0;
c2:=Abs(LongAr(NSet)[i]);
1:
q:=c2 div c1;
c2:=c2-q*c1;
{ testing before computing y2 and y1 below saves Cnt-1 additions and
Cnt-1 multiplications }
if c2<>0 then begin
y2:=y2-q*y1;
q:=c1 div c2;
c1:=c1-q*c2;
if c1<>0 then begin
y1:=y1-q*y2;
goto 1
end;
c1:=c2;
y1:=y2;
end;
LongAr(NSet)[i]:=y1;
LongAr(NSet)[m]:=c1;
end;
Inc(i);
{ terminate if GCD equals one }
if c1=1 then break
end;
Result:=LongAr(NSet)[m];
GCDNumSet:=Result
end;
"Max Medvedev" <Max.Medvedev@p11.f4441.n5030.z2.fidonet.org>
сообщил/сообщила в новостях следующее:
news:1019039201@p11.f4441.n5030.z2.ftn...
> Hello All.
>
> Чето я запутался,высчитывая сабж.Может кто-нибудь уже делал это до
меня?
> Конкpетно,меня интеpесует наиболее пpостая связь между пpосто
аннулиp.мн-ном и
> сабжевым.
> Также буду благодаpен,если подскажите,как найти HОД для некотоpого
> фиксиpованного количества чисел (вообще надо для 16,но меня интеpесует для
> любого количества).
>
>
> Макс
--- ifmail v.2.15dev5
* Origin: ODU SK (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Аннулирющий многочлен min степени