C语言的高精度算法Word文档格式.docx
- 文档编号:5907746
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:20
- 大小:19.75KB
C语言的高精度算法Word文档格式.docx
《C语言的高精度算法Word文档格式.docx》由会员分享,可在线阅读,更多相关《C语言的高精度算法Word文档格式.docx(20页珍藏版)》请在冰点文库上搜索。
for(i=max;
i--)
if(s[i]>
'
9'
)
{
s[i]-=10;
s[i-1]++;
if(s[0]=='
for(i=0;
i<
=max;
i++)
c[i-1]=s[i];
c[i-1]='
\0'
c[i]=s[i];
c[i]='
free(s);
}
二.减法
先考虑减数大于被减数的情况。
也是先对齐,再相减,接赋值,最后是处理借位问题(判断每位上的数是否小于0)。
如果减数小于被减数的话,可以用被减数减去减数。
最后在结果的前面加个负号就可以了。
源代码:
voidsubtract(char*a,char*b,char*c)
inti,j,ca,cb;
ca=strlen(a);
cb=strlen(b);
if(ca>
cb||(ca==cb&
&
strcmp(a,b)>
=0))
for(i=ca-1,j=cb-1;
i--,j--)
a[i]-=(b[j]-'
);
for(i=ca-1;
if(a[i]<
{
a[i]+=10;
a[i-1]--;
i=0;
while(a[i]=='
i++;
if(a[i]=='
c[0]='
c[1]='
for(j=0;
a[i]!
='
i++,j++)
c[j]=a[i];
c[j]='
b[j]-=(a[i]-'
for(j=cb-1;
j--)
if(b[j]<
b[j]+=10;
b[j-1]--;
j=0;
while(b[j]=='
j++;
i=1;
c[0]='
-'
b[j]!
c[i]=b[j];
c[i]='
}
三.乘法
注意乘积的最大位数是两个数的位数之和。
先相乘,再处理进位问题。
ca;
i++)//相乘
for(j=0;
j<
cb;
j++)
c[i+j+1]+=(a[i]-'
)*(b[j]-'
);
voidmultiply(char*a,char*b,char*c)
inti,j,ca,cb,*s;
s=(int*)malloc(sizeof(int)*(ca+cb));
ca+cb;
s[i]=0;
for(j=0;
s[i+j+1]+=(a[i]-'
for(i=ca+cb-1;
=10)
s[i-1]+=s[i]/10;
s[i]%=10;
while(s[i]==0)
c[j]=s[i]+'
c[j]='
四.除法
高精度的除法最后的结果整数部分和余数。
其中被除数一般是计算机可以表示的整数。
intdividor(char*a,intb,char*c)
inti,j,temp=0,n;
char*s;
n=strlen(a);
s=(char*)malloc(sizeof(char)*(n+1));
temp=temp*10+a[i]-'
s[i]=temp/b+'
temp%=b;
s[i]='
s[i]=='
s[i]!
i++);
if(s[i]=='
c[0]='
c[1]='
c[j]=s[i];
returntemp;
例1(ZOJ-1205):
在22世纪,科学家发现有外星人的存在。
他们十分喜欢数学。
每年他们都举行ACM比赛。
题目是计算2个100位数的和。
谁用的时间最少,谁就获胜。
今年他们邀请我们去参加他们的比赛。
而你幸运的成为我们的代表去参赛。
现在你唯一的问题是编写一个小程序去计算2个数的和。
但是他们的数是20进制。
他们的数由0-9和a-j(代表10-19)表示。
输入:
成对的给出一些他们用20进制表示的数,每个数占一行。
而且每个数不会超过100位。
输出:
对每一对数,在一行上输出他们的和(还是用20进制表示)。
分析:
两数相加,对齐后,从最后一位开始。
先把各个位上的数转化成10进制的数,再相加。
最后把各个位上的数转化成20进制的数。
注意2个数的和,最后位数可能跟较长的数相同,可能大1。
intmain()
inti,min,max,j;
chara[101],b[101],c[102],*pmin,*pmax;
while(scanf("
%s%s"
a,b)==2)//判断输入是否结素
if(a[0]=='
b[0]=='
)//可能有点多余
printf("
0\n"
else
101;
min=strlen(a);
/*
max=strlen(b);
求每个数的长度
if(min<
=max)把较长的数的地址赋给pmax
{较短的赋给pmin
pmin=a;
这样可以节省考虑的情况
pmax=b;
*/
i=min;
min=max;
max=i;
i=j=max;
c[max+1]='
for(min--,max--;
min>
i--,min--,max--)/*
{先将2个数从最后一位对齐
if(pmin[min]>
a'
)在从最后一位开始相加
{在相加的时候把20进制的
if(pmax[max]>
)数转化成10进制的数
c[i]=pmax[max]-'
+pmin[min]-'
+20+'
一直加到较短那个数的
else最高位为止
c[i]=pmin[min]-'
+pmax[max]+10;
if(pmax[max]>
c[i]=pmax[max]-'
+pmin[min]+10;
+pmin[min];
for(;
max>
max--,i--)/*
)把较长的数未相加的数赋给C
+10+'
注意转换进制
else*/
c[i]=pmax[max];
for(i=j;
i--)/*
if(c[i]>
+20)再把相加的每一位置上的数
{从10进制转换成20进制
c[i]=c[i]-20;
c[i-1]++;
+10)
c[i]=c[i]-'
-10+'
i=0;
while(c[i]=='
)/*
i++;
最后判断2个输相加后,
while(c[i]!
)得到的数的位数会不会比
%c"
c[i++]);
较长的数的位数长
\n"
return0;
例2(ZOJ-1962):
考虑Fibonacci数,
f1:
=1
f2:
=2
fn:
=fn-1+fn-2(n>
=3);
给你a,b两个整数,要你计算在a,b间的Fibonacci数有多少个[a,b]。
有多组测试,每组测试有2个非负的整数。
当a=b=0是输入结束。
而且a<
=b<
=10^100。
对于每组数据,在单独一行输出满足条件的Fibonacci数的个数。
注意:
其中要用到线性表(属于动态规划内容)。
首先将0-10^100之间的Fibonacci数保存在数组P里。
在计算Fibonacci数的时候用开线性表的方法,否则会超时。
对于输入的a,b先在P里找到第一个大于等于a的Fibonacci数,并标记此位置为j。
再找第一个大于等于b的Fibonacci数,标记为k。
则a,b间的Fibonacci数为k-j.
//高精度加法
intadd(char*a,char*b,char*c)
free(s);
returnmax;
returnmax+1;
intn,i,j,k;
charp[1000][102],min[101],max[101];
p[0][0]='
1'
首先开线性表,把在0-10^100的数
p[0][1]='
都求出来,记录在P里。
p[1][0]='
2'
p[1][1]='
n=1;
for(i=2;
n<
n=add(p[i-1],p[i-2],p[i]);
scanf("
min,max);
while(min[0]!
||max[0]!
)//判断a,b是否等于0
j=strlen(min);
k=strlen(max);
for(i=0;
i++)//查找第一个大于等于a的Fibonacci数
n=strlen(p[i]);
if(n>
=j)
if(n==j)
if(strcmp(p[i],min)>
=0)
break;
break;
j=i;
i++)//查找第一个大于等于b的Fibonacci数
n=strlen(p[i]);
if(n>
=k)
if(n==k)
if(strcmp(p[i],max)>
0)
k=i;
printf("
%d\n"
k-j);
scanf("
例3(ZOJ-1923):
定义一种整数的连乘规则:
给出一个数,它的各个位上的数的乘积,得到一个新的数。
这个数在做这种运算,直到最后得到的数是一位的为止。
如:
679->
378->
168->
48->
32->
6。
我们说679要经过5次这样的运算得到是一位数。
假定一位数运算这种规则所要用的次数是0。
现在你要解决的问题是:
求最小的数经过一次这种乘法运算得到结果是给出的已知的数。
每一组测试是一个十进制的数,它的位数最多1000位。
以-1作为测试结束的条件。
对于每一组测试,输出满足条件的数。
如果这个数存在,输出“Thereisnosuchnumber”。
1
18
51
768
-1
10
11
29
Thereisnosuchnumber.
2688
首先发现,一个数经过这种运算之后,要么是等于由2-9之间的数的乘积,要么为0。
所以判断一个数能不能进行这种规则的逆运算,至需判断它素因子只有2,3,5或7。
如果能进行逆运算,找满足条件的最小的数,只须从9开始判断能不能被整除,能的话就除以9,再看能不能被9整除,直到不能被整除,并标记能除以9的次数。
接着考虑8,
一直到2。
最后把这些能整除的数从低向高排列就可以了。
如768,不能被9整除,考虑8,能整除,且次数2;
接着是6,次数1;
最后是2,次数1。
所以768可以分解成2,6,8,8,要求的数就是2688。
不过要注意特殊情况的出现,如果输入的数是一位的话。
那满足条件的数,是在它的前面加1,就可以了。
(因为满足条件的数必须经过最少经过一次这种运算。
所以要求的数最少是2位数,而在2位数里只有10几是最小的)
//判断一个数能不能整除另一个数
booljudge(char*s,intn)
intm,i;
for(i=0,m=0;
m=m*10+s[i]-'
if(m>
=n)
m=m%n;
if(m==0)
returntrue;
returnfalse;
inti,j,k,temp,p[8];
charsa[1001],sb[1001];
%s"
sa);
while(sa[0]!
{//分2种情况讨论
if(sa[1]=='
)//输入的是一位数
1%c\n"
sa[0]);
else//其他的情况
8;
i++)/*
p[i]=0;
满足条件的数的求法是:
for(i=9;
=2;
)给出的数一定要能被分解if(judge(sa,i))成2-9的乘积。
否则无解。
{求最小的满足条件的数,
temp=0;
只须从9开始判断能不能
for(j=0;
sa[j]!
j++)整除。
能整除的并纪录
{能整除的次数。
最后把
temp=temp*10+sa[j]-'
这些能整除的数,从低
sb[j]=temp/i+'
向高排列,就是所求的
temp%=i;
数。
}*/
sb[j]='
sb[j]=='
j++);
for(k=0;
sb[j]!
j++,k++)
sa[k]=sb[j];
sa[k]='
p[i-2]++;
i--;
if(strcmp(sa,"
1"
)==0)
if(p[i]>
for(k=0;
k<
p[i];
k++)
printf("
%d"
i+2);
}
printf("
Thereisnosuchnumber.\n"
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言 高精度 算法