В общем, есть одна задача, умножение длинных чисел. В начале дается число N (0<N<11), затем N чисел (максимум – 500-значные). Нужно умножить все числа и написать результат.
Решал на Pascal (число дано в файле Input):
var row,p:array[1..20000] of smallint; col:array[1..500] of smallint; nr,res,nc,dp,n,i,b,x,y,k,j,cr,cc,l:integer; c:char; carry,sum:longint;
procedure PrintResult;
begin
k:=0;
while (dp<high(row)) do begin
if (k=0) and (row[dp]=0) and (res<>0) then inc(dp) else
if res=0 then begin writeln(0); dp:=high(row)+1; end else begin
write(char(row[dp]+48));
inc(dp); k:=1;
end; end;
end;
procedure make(a,b:longint);
begin
while (a<>0) do begin
row[b]:=a mod 10;
a:=a div 10;
dec(b);
end;
inc(b);
end;
procedure Multiplying;
begin
dp:=high(row); cr:=nr; cc:=nc;
carry:=0;
while (cc>0) do begin
i:=cr; j:=cc; sum:=carry;
while (i<=nr) and (j>=1) do begin
sum:=sum+row[i]*col[j];
inc(i); dec(j);
end;
row[dp]:=sum mod 10; dec(dp);
carry:=sum div 10;
if cr>1 then dec(cr) else dec(cc);
end;
make(carry,dp);
for i:=1 to 20001-dp do p[i]:=row[dp+i-1];
for l:=1 to i do row[l]:=p[l];
nr:=i; cr:=i;
end;
procedure Multiplying1;
begin
dp:=high(row); cr:=nr; cc:=nc;
carry:=0;
while (cc>0) do begin
i:=cr; j:=cc; sum:=carry;
while (i<=nr) and (j>=1) do begin
sum:=sum+row[i]*col[j];
inc(i); dec(j);
end;
row[dp]:=sum mod 10; dec(dp);
carry:=sum div 10;
if cr>1 then dec(cr) else dec(cc);
end;
nr:=i;
make(carry,dp);
end;
begin
res:=1;
assign(input,'input.txt');
reset(input);
readln(n);
c:=#0;
read(c);
nr:=0;
while (c in ['0'..'9']) do begin
inc(nr); row[nr]:=ord(c)-48;
read(c);
end;
if (nc=1) and (row[1]=0) then res:=0;
readln;
for k:=2 to n do begin
for b:=1 to 500 do col[b]:=0;
read(c);
nc:=0;
while (c in ['0'..'9']) do begin
inc(nc); col[nc]:=ord(c)-48;
read(c);
end;
if (nc=1) and (col[1]=0) then res:=0;
if i<>n then Multiplying else Multiplying1;
readln;
end;
assign(output,'output.txt'); rewrite(output);
PrintResult;
end.
почему-то не всегда решает правильно!!
Можно еще и решение на C, но я не пробовал.
Пожалуйста!
31 декабря 2009 в 22:05
в нете много есть реализаций длинной арифметики, вот и есть там длинное умножение)