回 帖 发 新 帖 刷新版面

主题:高精度除法

最近在网上查了一下高除,但都是c语言,好不容易得了个Pascal的,但是看不懂,望大虾们能够提供一种易懂的方法解释一下。

回复列表 (共7个回复)

沙发

这样,你把那段C的贴过来,翻译比写要容易的多。

板凳

#i nclude <cstdio>
#i nclude <cstring>

#define K 4
#define N 1024
#define UP 10000
//将字符串转换为按四位存储的整数 
void strToInt(char *x,int *y)
{
 int i,k,m,cnt,wgt;
 cnt = strlen(x);
 i = cnt - 1;
 m = y[0] = (cnt + K - 1) / K;
    while(m > 0)
 {
  k = 0;
  wgt = 1;
  y[m] = 0;
  while(i >= 0 && k < K)
  {
   y[m] += (x[i] - 48) * wgt;
   wgt *= 10;
   i --,k ++;
  }
  m --;
 }
}
//过滤数字前面的0 
void skipZero(int *x)
{
 int i,k;
 for(i = 1;i <= x[0];i ++)
  if(x[i])  break;
 if(i > x[0])  i --;
 for(k = i;k <= x[0];k ++)
  x[k - i + 1] = x[k];
 x[0] = x[0] - i + 1;
}
//将按四位存储的结果还原 
void highToLow(int *high,bool flag)
{
 int i,j,k,n,p,cnt,sgn;
 sgn = high[high[0] + 1];
 cnt = high[0] * K;
 p = k = cnt;
    for(i = high[0];i > 0;i --)
 {
  j = k;
  n = high[i];
  while(n)
  {
   high[j --] = n%10;
   n /= 10;
  }
  while(j > k - K)
      high[j --] = 0;
  k -= K;
 }
 high[0] = p;
 if(flag)  skipZero(high);
 high[high[0] + 1] = sgn;
}
//比较两个大整数的大小关系 
int compare(int *x,int *y)
{
 int i = 1;
 if(x[0] > y[0])  return 1;
 if(x[0] < y[0])  return -1;
    while(i <= x[0])
 {
  if(x[i] > y[i])  return 1;
  if(x[i] < y[i])  return -1;
  i ++;
 }
 return 0;
}
//两数相减 
void subtract(int *x,int *y,int *ans)
{
 int tmp[N];
 int i,j,p,s,t,res,sub,sgn;
 sgn = 1;
 p = compare(x,y);
    if(p < 0)
    { 
        sgn = 0;
  for(i = 0;i <= x[0];i ++)  tmp[i] = x[i];
        for(i = 0;i <= y[0];i ++)  x[i] = y[i];
        for(i = 0;i <= tmp[0];i ++)  y[i] = tmp[i];
    }
 sub = 0;
    i = ans[0] = x[0];
 j = y[0];
    while(i > 0)
    {
        t = 0,s = x[i];
        if(j > 0)  t = y[j --];
        res = s - t - sub;
        sub = 0;
        if(res < 0)  { res += UP; sub = 1; }
        ans[i --] = res;
    }
 skipZero(ans);
 ans[ans[0] + 1] = sgn;
}
void singleMultiply(int *x,int n,int *ans)
{
 int i,k,l,s,inc = 0;
    i = l = x[0];
    ans[0] = k = l + 1;
    while(i > 0)
    {
        s = x[i --] * n + inc;
        inc = s / UP;
        ans[k --] = s % UP;
    }
 ans[k] = inc;
 skipZero(ans);
}
//二分查找试除的结果 
int finds(int *x,int *y)
{
 int res[N];
 int l,m,h,p,sgn;
 l = 0;
 h = UP - 1;
 while(l <= h)
 {
  m = (l + h) / 2;
  singleMultiply(y,m,res);
  sgn = compare(x,res);
  if(sgn >= 0)  { p = m; l = m + 1; }
  else  h = m - 1;
 }
 return p;
}
void divide(int *x,int *y,int prec,int *res,int *ans)
{
 int i,k;
 int tmp[N],tmp1[N],tmp2[N],tmp3[N];
 for(i = 0;i <= x[0];i ++)
  tmp1[i] = x[i];
 for(i = 0;i <= y[0] ;i ++)
  tmp2[i] = y[i];
 i = 1;
 while(i < tmp1[0] && i < tmp2[0])  
 {
  tmp[i] = tmp1[i];
  i ++;
 }
 ans[0] = 0;
 tmp[0] = i - 1;
 while(i <= tmp1[0])
 {
  tmp[0] ++;
  tmp[tmp[0]] = tmp1[i ++];
  skipZero(tmp);
  k = 0;
  if(tmp[0] >= tmp2[0])
      k = finds(tmp,tmp2);
  ans[++ ans[0]] = k;
  if(k)
  {
      singleMultiply(y,k,tmp3);
      subtract(tmp,tmp3,tmp);
        }
    }
 for(i = 0;i <= tmp[0] + 1;i ++)
  res[i] = tmp[i];
 highToLow(res,true);
 ans[ans[0] + 1] = 1;
}
int ans[N];
int main()
{
 int i,w[N],x[N],y[N];
 char cx[N],cy[N];
 while(scanf("%s%s",cx,cy) == 2)
 {
  strToInt(cx,x);
  strToInt(cy,y);
  divide(x,y,-1,w,ans);
  highToLow(ans,true);
  if(ans[ans[0] + 1] == 0)
   printf("-");
  for(i = 1;i <= ans[0];i ++)
   printf("%d",ans[i]);
  printf("\n");
 }
    return 0; 
}
这是C语言
program highprecision3_multiply1;
const
fn_inp='hp5.inp';
fn_out='hp5.out';
maxlen=100; { max length of the number }
type
hp=record
len:integer; { length of the number }
s:array[1..maxlen] of integer
{ s[1] is the lowest position
s[len] is the highest position }
end;
var
x,y:hp;
z,w:integer;

procedure printhp(const p:hp);
var i:integer;
begin
for i:=p.len downto 1 do write(p.s);
end;

procedure init;
var
st:string;
i:integer;
begin
assign(input,fn_inp);
reset(input);
readln(st);
x.len:=length(st);
for i:=1 to x.len do { change string to hp }
x.s:=ord(st[x.len+1-i])-ord('0');
readln(z);
close(input);
end;

procedure divide(a:hp;b:integer;var c:hp;var d:integer);
{ c:=a div b ; d:=a mod b }
var i,len:integer;
begin
fillchar(c,sizeof(c),0);
len:=a.len;
d:=0;
for i:=len downto 1 do { from high to low }
begin
d:=d*10+a.s;
c.s:=d div b;
d:=d mod b;
end;
while(len>1) and (c.s[len]=0) do dec(len);
c.len:=len;
end;

procedure main;
begin
divide(x,z,y,w);
end;

procedure out;
begin
assign(output,fn_out);
rewrite(output);
printhp(y);
writeln;
writeln(w);
close(output);
end;

begin
init;
main;
out;
end.

这是Pascal,但是不是很懂

3 楼

怎么没人?大虾们呢?

4 楼

……
那段C的太猥琐了,实在没法翻了。
那个PAS的编译过不了,改改能过,但是貌似不是乘法。所以还是把我早先写的一份贴过来吧。
这个比较乱,凑合着看吧。

unit HP;
 interface
  type
    HPN=record
          n:string;{数字主体}
          s:boolean;{符号,值为true时是正数}
          d:integer;{点的位置}
        end;
  Function  StrToHPN(s:string;var a:HPN):boolean;
  {将字符串转换为高精度类型}
  Function  StrInput(s:string):string;
  {输入,格式为字符串类型}
  Procedure HPNInput(s:string;var a:HPN);
  {输入,格式为高精度类型}
  Function  HPNToStr(a:HPN):string;
  {将高精度类型转换为字符串}
  Function  HPNComp (a,b:HPN):shortint;
  {高精度类型比较大小,返回值1为">",0为"=",-1为"<"}
  Function  StrComp (a,b:string):shortint;
  {字符串类型比较大小,返回值1为">",0为"=",-1为"<"}
  Procedure HPNEvaluate(a:HPN;var b:HPN);
  {赋值,a给b}
  Procedure HPNSwap (var a,b:HPN);
  {交换a,b}
  Procedure HPNPlus (a,b:HPN;var c:HPN);
  {高精度类型加法}
  Function  StrPlus (a,b:string):string;
  {字符串类型加法}
  Procedure HPNMinus(a,b:HPN;var c:HPN);
  {高精度类型减法,a被减数,b为减数}
  Function  StrMinus(a,b:string):string;
  {字符串类型减法,a被减数,b为减数}
  Function  StringOfChar(c:Char;l:byte):String;
  {返回包含一个字符重复指定次数的字符串}
  Procedure HPNMultiplication(a,b:HPN;var c:HPN);
  {高精度类型乘法}
  Function  StrMultiplication(a,b:string):string;
  {字符串类型乘法}
  Procedure HPNdivison(a,b:HPN;var c:HPN;u:byte);
implementation
  Function StringOfChar;
    var
      i:byte;t:String;
  begin
    t:='';for i:=1 to l do t:=t+c;
    StringOfChar:=t;
  end;
  Function StrToHPN;
    var
      i:byte;
  begin
    a.s:=s[1]<>'-';if s[1] in ['+','-'] then delete(s,1,1);
    a.d:=pos('.',s)-1;
    if a.d=-1 then a.d:=length(s);
    delete(s,a.d+1,1);
    StrToHPN:=true;
    if length(s)=0 then StrToHPN:=false;
    while (s[1]='0') and (s<>'') do begin
        delete(s,1,1);
        a.d:=a.d-1;
    end;
    for i:=length(s) downto 1 do
      if s[i]='0' then delete(s,i,1) else break;
    a.n:=s;
    for i:=1 to length(a.n) do
     if not (a.n[i] in ['0'..'9'])
      then StrToHPN:=false;
  end;
  Procedure HPNInput;
    var
      t:string;
      f:boolean;
  begin
    f:=false;
    repeat
      if f then writeln('Input Error!');
      write(s);
      readln(t);
      f:=true;
    until StrToHPN(t,a);
  end;
  function StrInput;
    var
      a:HPN;
  begin
    HPNInput(s,a);
    StrInput:=HPNToStr(a)
  end;
  function HPNToStr;
    var
      i:integer;
      s:string;
  begin
    s:='';
    if not a.s then s:=s+'-';
    if a.d<=0 then begin
      s:=s+'0';
      if a.n<>'' then begin
        s:=s+'.';
        s:=s+StringOfChar('0',a.d+2);
        s:=s+a.n;
      end;
    end else begin
      if a.d<=length(a.n) then s:=s+(copy(a.n,1,a.d));
      if a.d<length(a.n) then begin
        s:=s+'.';
        s:=s+(copy(a.n,a.d+1,length(a.n)-a.d))
      end;
      if a.d>length(a.n) then begin
        s:=s+(a.n);
        s:=s+StringOfChar('0',a.d-length(a.n));

5 楼

end;
    end;
    HPNToStr:=s;
  end;
  function HPNComp;
    var
      i,l:byte;
  begin
    if (a.n=b.n) and (a.s=b.s) and (a.d=b.d) then HPNComp:=0 else begin
      if a.s<>b.s then HPNComp:=2*Ord(a.s)-1 else
       if a.d<>b.d then HPNComp:=2*Ord((a.d>b.d)=a.s)-1
       else begin
         for i:=1 to l do if a.n[i]<>b.n[i] then break;
         HPNComp:=2*Ord((a.n[i]>b.n[i])=a.s)-1;
       end;
    end;
  end;
  function StrComp;
    var
      m,n:HPN;
  begin
    StrToHPN(a,m);StrToHPN(b,n);
    StrComp:=HPNComp(m,n)
  end;
  Procedure HPNEvaluate;
  begin
    b.n:=a.n;b.s:=a.s;b.d:=a.d;
  end;
  Procedure HPNSwap;
    var
      c:HPN;
  begin
    HPNEvaluate(a,c);
    HPNEvaluate(b,a);
    HPNEvaluate(c,b);
  end;
  procedure HPNPlus;
    var
      i,k:integer;
      f:boolean;
      s:string;
  begin
    if a.d<b.d then begin
      a.n:=StringOfChar('0',b.d-a.d)+a.n;a.d:=b.d;
    end else if a.d>b.d then begin
      b.n:=StringOfChar('0',a.d-b.d)+b.n;b.d:=a.d;
    end;
    c.d:=a.d;
    if length(a.n)<length(b.n)
     then a.n:=a.n+StringOfChar('0',length(b.n)-length(a.n))
     else b.n:=b.n+StringOfChar('0',length(a.n)-length(b.n));
    k:=0;c.n:='';
    if a.s=b.s then begin
      c.s:=a.s;
      for i:=length(a.n) downto 1 do begin
        k:=k+ord(a.n[i])+ord(b.n[i])-96;
        c.n:=chr(k mod 10+48)+c.n;
        k:=k div 10
      end;
      if k<>0 then begin
        c.n:=chr(k+48)+c.n;
        c.d:=c.d+1
      end;
    end else begin
      f:=a.s;a.s:=true;b.s:=true;
      if HPNComp(a,b)=-1 then begin
        f:=not f;
        HPNSwap(a,b)
      end;
      c.s:=f;
      for i:=length(a.n) downto 1 do begin
        k:=ord(a.n[i])-ord(b.n[i])+k;
        c.n:=chr(48+(k+10) mod 10)+c.n;
        if k<0 then k:=-1 else k:=0
      end
    end;
    s:=HPNToStr(c);
    if not StrToHPN(s,c) then write('')
  end;
  function StrPlus;
    var
      m,n,c:HPN;
  begin
    StrToHPN(a,m);StrToHPN(b,n);
    HPNPlus(m,n,c);
    StrPlus:=HPNToStr(c)
  end;
  procedure HPNMinus;
  begin
    b.s:=not b.s;
    HPNPlus(a,b,c)
  end;
  function StrMinus;
  begin
    if b[1]='-' then b:=copy(b,2,length(b)-1) else b:='-'+b;
    StrMinus:=StrPlus(a,b)
  end;
  Procedure HPNMultiplication;
    var
      i,j:byte;
      d:HPN;
  begin
    with c do begin
      n:='0';d:=0;s:=true
    end;
    for i:=1 to length(a.n) do begin
      for j:=1 to ord(a.n[i])-48 do begin
        d:=b;d.d:=d.d+a.d-i;
        HPNPlus(c,d,c);
      end;
    end;
  end;
  function StrMultiplication;
    var
      m,n,c:HPN;
  begin
    StrToHPN(a,m);StrToHPN(b,n);
    HPNMultiplication(m,n,c);
    StrMultiplication:=HPNToStr(c)
  end;
  procedure HPNdivison;
  begin
  end;
end.

6 楼

翻译!

7 楼

加油

我来回复

您尚未登录,请登录后再回复。点此登录或注册