主题:高精度除法
w75317
[专家分:530] 发布于 2010-03-07 17:26:00
最近在网上查了一下高除,但都是c语言,好不容易得了个Pascal的,但是看不懂,望大虾们能够提供一种易懂的方法解释一下。
回复列表 (共7个回复)
沙发
小田甜 [专家分:3910] 发布于 2010-03-08 18:34:00
这样,你把那段C的贴过来,翻译比写要容易的多。
板凳
w75317 [专家分:530] 发布于 2010-03-08 20:45:00
#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 楼
w75317 [专家分:530] 发布于 2010-03-13 13:56:00
怎么没人?大虾们呢?
4 楼
小田甜 [专家分:3910] 发布于 2010-03-13 18:02:00
……
那段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 楼
小田甜 [专家分:3910] 发布于 2010-03-13 18:02:00
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 楼
CVN-70 [专家分:0] 发布于 2010-06-08 21:49:00
翻译!
7 楼
小勇士来了 [专家分:220] 发布于 2010-06-27 22:40:00
加油
我来回复