首页 > 代码库 > 高精度算法

高精度算法

2024-07-18 02:08:07   225人阅读

以下标程均为十进制，如改为10n进制可提高n倍速度。

建议不要使用operator对运算符进行重载，虽然用起来很方便，但是NOIP中不一定能用，速度也会慢一些。

高精度数大小比较

function a_dy_b(a,b:arr):boolean;var i:integer;begin  i:=a[0];  if a[0]<>b[0] then a_dy_b:=a[0]>b[0]    else begin      while (a[i]=b[i])and(i>0) do dec(i);      a_dy_b:=a[i]>b[i];    end;end;

高精度+低精度

procedure add_h_l(a:arr;b:integer; var c:arr);var i:integer;begin  a[1]:=a[1]+b;  for i:=1 to a[0] do    begin      a[i+1]:=a[i+1]+a[i] div 10;      a[i]:=a[i] mod 10;    end;  c:=a;c[0]:=max(c[0],19);  while c[c[0]]=0 do dec(c[0]);end;

高精度+高精度

procedure add_h_h(a,b:arr; var c:arr);var i,j:integer;begin  fillchar(c,sizeof(c),0);  if a[0]>b[0] then j:=a[0] else j:=b[0];  for i:=1 to j do c[i]:=a[i]+b[i];  for i:=1 to j do    begin      c[i+1]:=c[i+1]+c[i] div 10;      c[i]:=c[i] mod 10;    end;  c[0]:=j+1;  if c[c[0]]=0 then dec(c[0]);end;

高精度-低精度(高精度数大于低精度数且低精度数小于1*109)

procedure jian_h_l(a:arr; b:longint; var c:arr);//arr为基类型是longintvar i,j:integer;begin  if a[0]>=10 then begin dec(a[10]);a[1]:=a[1]+1000000000;end   else begin    dec(a[a[0]]);    j:=1;    for i:=1 to a[0]-1 do  j:=j*10;    a[1]:=a[1]+j;  end;  a[1]:=a[1]-b;  for i:=1 to a[0]-1 do    begin      a[i+1]:=a[i+1]+a[i] div 10;  a[i]:=a[i] mod 10;    end;  while a[a[0]]=0 do dec(a[0]);  c:=a;end;

高精度-高精度

procedure jian_h_h(a,b:arr; var c:arr);//确保a>bvar i:integer;begin  for i:=a[0] downto 2 do begin dec(a[i]); a[i-1]:=a[i-1]+10;end;  for i:=1 to a[0] do c[i]:=a[i]-b[i];  for i:=1 to a[0]-1 do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10;end;  c[0]:=a[0];  while c[c[0]]=0 do dec(c[0]);  if c[0]<1 then c[0]:=1;end;

高精度*低精度

procedure cheng_h_l(a:arr; b:integer; var c:arr);var i:integer;begin  fillchar(c,sizeof(c),0);  for i:=1 to a[0] do c[i]:=a[i]*b;  for i:=1 to a[0]+11 do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10;end;  c[0]:=a[0]+11;  while c[c[0]]=0 do dec(c[0]);end;

高精度*高精度

procedure cheng_h_h(a,b:arr; var c:arr);var i,j:integer;begin  fillchar(c,sizeof(c),0);  for i:=1 to a[0] do    for j:=1 to b[0] do c[i+j-1]:=c[i+j-1]+a[i]*b[j];  for i:=1 to a[0]+b[0] do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10;end;  c[0]:=a[0]+b[0];  while c[c[0]]=0 do dec(c[0]);end;

 高精度/低精度

procedure chu_h_l(a:arr;b:integer; var c:arr; var d:integer);var i:integer;begin  fillchar(c,sizeof(c),0);d:=0;  for i:=a[0] downto 1 do begin d:=d*10+a[i]; c[i]:=d div b; d:=d mod b;end;  c[0]:=a[0];  while c[c[0]]=0 do dec(c[0]); if c[0]<1 then c[0]:=1;end;

高精度/高精度(not ok)

用减法代替除法运算：不断比较A[1..n]与B[1..n]的大小，如果A[1..n]>=B[1..n]则商C[1..n]+1→C[1..n]，然后就是一个减法过程：A[1..n]-B[1..n]→A[1..n]。由于简单的减法速度太慢，故必须进行优化。设置一个商的位置值J，当A[1..n]>B[1..n]时。B[1..n]左移→B[0..n]，j:=j+1，即令B[1..n]增大10倍。这样就减少了减法的次数。当j>0且A[1..n]<B[0..n]时，B[0..n]右移→B[0..n]，j:=j-1，即令B[1..n]缩小10倍。

function a_dy_b(a,b:arr):boolean;var i:integer;begin  i:=a[0];  if a[0]<>b[0] then a_dy_b:=a[0]>b[0]  else begin    while (a[i]=b[i])and(i>0) do dec(i);    a_dy_b:=a[i]>b[i];  end;end;procedure kuoda(a:arr;var b:arr);//将a扩大10倍var i:integer;begin  fillchar(b,sizeof(b),0);  b[0]:=a[0]+1;  for i:=1 to a[0] do b[i+1]:=a[i];end;procedure suoxiao(a:arr;var b:arr);//将a缩小10倍var i:integer;begin  fillchar(b,sizeof(b),0);  for i:=2 to a[0] do b[i-1]:=a[i];  b[0]:=a[0]-1;end;procedure jian_h_h(a,b:arr; var c:arr);//确保a>bvar i:integer;begin  for i:=a[0] downto 2 do begin dec(a[i]); a[i-1]:=a[i-1]+10;end;  for i:=1 to a[0] do c[i]:=a[i]-b[i];  for i:=1 to a[0]-1 do begin c[i+1]:=c[i+1]+c[i] div 10; c[i]:=c[i] mod 10;end;  c[0]:=a[0];  while c[c[0]]=0 do dec(c[0]);  if c[0]<1 then c[0]:=1;end;procedure chu_h_h(a,b:arr;var c,d:arr);//主要子程序，a：被除数，var i,j:integer;    //b：除数；c：商；d：余数begin  c[0]:=a[0];  d:=b;//复制备份除数  while a_dy_b(a,d) do//被除数仍然比除数大则循环  begin    b:=d;j:=1;    while a_dy_b(a,b) do begin inc(j);   kuoda(b,b);end;    //扩大除数,最后一次循环后被除数已比除数小    suoxiao(b,b);dec(j);//将除数缩小10倍以正好能除    while a_dy_b(a,b) do begin inc(c[j]);  jian_h_h(a,b,a);end;//求得当前位的商  end;  d:=a;//a中保存的正好是小于除数的余数  while c[c[0]]=0 do dec(c[0]);if c[0]<1 then c[0]:=1;end;


联系
我们