高精度计算.docx

高精度计算.docx

《高精度计算.docx》由会员分享，可在线阅读，更多相关《高精度计算.docx（26页珍藏版）》请在冰点文库上搜索。

高精度计算

高精度计算

一、数据输入

先将要计算的数据输入到内存中一般是按位存到数组中，按位对齐。

定义：

第一位表示个位，n表示最高位。

１、利用字符串输入：

先以字符串方式输入，再存入数组。

对非法输入可以作检查，处理小数、有符号数比较方便。

但需要对字符串操作比较熟悉。

字符串的输入和转换可用如下语句：

inta[100]={0},b[100]={0};

intka,kb,kc;

chara1[100],b1[100];

scanf（“%s”,a1）;/*也可用gets（a1）;*/

scanf（“%s”,b1）;

ka=strlen（a1）;kb=strlen（b1）;

for（i=0;i

for（i=0;i

字符串类型操作：

连接函数strcat（str1,str2）;

求字符串长度函数strlen（str1）

２、带小数、正负号问题

①利用查找函数查找小数点（.）、正负号（＋、－）

②记录小数点的位置和正负号。

③处理符号位。

３、位数对齐问题

①无小数位对齐：

以个位对齐

②有小数位对齐：

以小数点对齐

４、存储问题

①一位一存储②四位一存储

二、估算结果位数

高精度计算的结果位数要估算好，以便赋初值和控制循环次数。

设A、B为两个高精度数，结果为C，用LA、LB、LC分别表示A、B、C的位数。

加法：

C=A+BLC=MAX（LA,LB）+1是最长的位数加1

减法：

C=A-BLC=MAX（LA,LB）是最长的位数

乘法：

C=A*BLC=LA+LB

除法：

问题比较复杂，求商、余数、小数、可以不可以除尽，精确到小数点后几位。

一般取较大的位数作为结果位数。

阶乘、乘方的位数可以用对数求出。

1、XN的位数为计算

由数学知识可知：

一个自然数的位数基本等于这个数的常用对数取整加1。

由此可知对于XN来说它的位数为=（int）n*log10（x）+1

2、N!

的位数计算

N！

=N×（N-1）×（N-2）……×3×2×1

Log10（n!

）=（int）（log10（n）+log10（n-1）+……+log10

（2）+log10

（1））+1

可用如下程序段求Ｎ！

的位数：

inti,n,j;

doublek=0;

scanf（"%d",&n）;

for（i=1;i<=n;i++）k+=log10（i）;

j=（int）k+1;

三、计算和进位问题

高精度计算要求自己来编写进位。

进位存放在CI中。

加法：

一位存储，CI=AI+BI+CI，若CI>10，则CI=CI-10，CI+1=1

四位存储，CI=AI+BI+CI，若CI>10000，则CI=CI-10000，CI+1=1

减法：

保证大数减小数。

一位存储，CI=AI-BI，若CI<0，则CI=CI+10，AI+1=AI+1-1

四位存储，CI=AI-BI，若CI>0，则CI=CI+10000，AI+1=AI+1-1

乘法：

一位存储，Y=AI*BI+C，C=Y整除10，AI=Y取模10

四位存储，Y=AI*BI+C，C=Y整除10000，AI=Y取模10000

除法比较复杂

1、A、B两数都为高精度数，利用减法求解。

2、A、B其中A为高精度数、B不是，可以利用除法。

3、A、B其中A不是高精度数、B是高精度数，利用除法减法求解。

4、A、B两数都不是高精度数，可以利用除法。

精确到小数点后几位，判断循环小数。

乘法的控制：

for（i=0;i

for（j=0;j

{C[i+j]=C[i+j]+A[i]*B[j];

C[i+j+1]:

=C[i+j+1]+C[i+j]/10;

C[i+j]=C[i+j]%10;

}

四、输出问题

可以直接输出数组、或字符串。

注意小数点位置，首尾的零。

五、优化程序

每个数组位置存四位整数逢10000进位，减少计算次数，提高运行速度。

六、高精度习题

问题1.编程实现两个高精度实数加、减法，两数分别由键盘输入，均不超过２４０位。

1、加法运算a+b=c

算法：

先确定a和b中的最大位数k，然后依照由低至高位的顺序进行加法运算。

注意进位，若高位有进位，则c的长度为k+1。

源程序如下：

#include

main（）

{

inta[240]={0},b[240]={0},c[241]={0};

inti,ka,kb,k;

chara1[240],b1[240];

gets（a1）;ka=strlen（a1）;

gets（b1）;kb=strlen（b1）;

if（ka>=kb）k=ka;

elsek=kb;

for（i=0;i

for（i=0;i

for（i=0;i

{

c[i]=a[i]+b[i]+c[i];

c[i+1]=c[i+1]+c[i]/10;

c[i]=c[i]%10;

}

if（c[k]）k++;

for（i=k-1;i>=0;i--）printf（"%d",c[i]）;

}

当然也可把a+b的值直接存在a中，请大家在此基础上作出出修改。

2、减法运算a-b→a（a>b）

算法：

依照由低位至高位的顺序进行减法运算。

在每次位运算中，若出现不够减的情况，则向高位借位。

在进行了la的减法后，若最高位为零，则a的长度减1。

源程序如下：

#include

main（）

{

inta[240]={0},b[240]={0};

inti,ka,kb;

chara1[240],b1[240];

gets（a1）;ka=strlen（a1）;

gets（b1）;kb=strlen（b1）;

for（i=0;i

for（i=0;i

for（i=0;i

{

if（a[i]

{

a[i+1]--;

a[i]+=10;

}

a[i]=a[i]-b[i];

}

while（!

a[ka-1]）

{

ka--;

if（!

ka）{printf（"0"）;break;}

}

for（i=ka-1;i>=0;i--）printf（"%d",a[i]）;

}

若A、B大小未知，则需先判断大小。

问题2.一个正整数的数字的乘积Ｎ的定义是：

这个正整数中非零数字的乘积。

例如：

整数９９数字乘积为９＊９即８１，８１的数字乘积为８＊１即８。

一个正整数的数字乘积根Ｎ是这样得到的：

反复取该整数的数字乘积，直到得到一位数字为止。

如：

上题中９９的数字乘积根为８。

编写一个程序，对于任意不超过７０位数字的正整数，打印出计算其数字乘积根的每一步结果。

例如：

输入一个１０位数９９９９９９９９９９，则输出如下：

９９９９９９９９９９

３４８６７８４４０１

５１６０９６

１６２０

１２

２

算法：

将正整数保存在数组中，高位在前、低位在后，首先去掉末位的‘0’，然后从第二位开始依次往前乘，低位在前、高位在后，完成一遍后，处理进位和去掉最高位的‘0’，最后再按正常顺序排放，重复上述过程直到仅一位为止。

源程序如下：

#include

main（）

{

inta[100]={0};

inti,j,k,m,n,l,temp;

chara1[100];

printf（"InputN:

\n"）;

gets（a1）;

k=strlen（a1）;

for（i=0;i

if（k==1）printf（"%d\n",a[k-1]）;

while（k!

=1）

{

while（a[k-1]==0）k--;

for（i=1;i

{

for（j=0;j

{

while（a[i]==0）

{

for（m=i;m

a[k-1]=0;

k--;

}

a[j]=a[i]*a[j];

}

for（n=0;n

{

a[n+1]=a[n+1]+a[n]/10;

a[n]=a[n]%10;

}

a[i]=a[i-1]/10;

a[i-1]=a[i-1]%10;

if（a[i]==0）

{

for（n=i;n

a[k-1]=0;

k--;

i--;

}

}

while（a[k-1]==0）k--;

for（i=0;i

{

temp=a[i];

a[i]=a[k-i-1];

a[k-i-1]=temp;

}

for（i=0;i

printf（"\n"）;

}

}

问题3.用高精度计算出s=1!

+2!

+3!

+…+n!

。

（n≤50）其中“！

”表示阶乘，例如５！

＝５·４·３·２·１。

输入正整数n，输出计算结果s。

算法：

首先要确定结果的位数k，然后定义数组的大小，这一过程可单独做，并不需放在程序中。

将阶乘的结果存放在数组并累加到S数组中，最后输出结果。

源程序如下：

#include

#include

#defineN66

main（）

{

ints[N]={0},a[N]={0};

inti,j,k,n,digit=1;

printf（"InputN:

"）;

scanf（"%d",&n）;

a[0]=1;

s[0]=1;

if（n==1）printf（"s=%d",s[0]）;

for（k=2;k<=n;k++）

{

for（j=0;j

for（j=0;j

{

if（a[j]>=10）

{

a[j+1]+=a[j]/10;

a[j]=a[j]%10;

if（j==digit-1）digit++;

}

}

for（i=0;i

for（i=0;i

{

if（s[i]>=10）

{

s[i+1]+=s[i]/10;

s[i]=s[i]%10;

if（i==digit-1）digit++;

}

}

}

for（i=digit-1;i>=0;i--）printf（"%d",s[i]）;

}

问题4.编程完成以下的高精度计算：

①高精度乘以低精度；

算法：

将多位数存入数组，低位在前、高位在后，然后用一位数去乘数组的各位，考虑进位，最后按按正常顺序输出。

源程序如下：

#include

#defineN200

main（）

{

inta[N]={0};

inti,j,k,m;

charb[N]={0};

printf（"Inputtwonumbers:

\n"）;/*初始化*/

scanf（"%d",&m）;

scanf（"%s",b）;

k=strlen（b）;

for（i=0;i

a[0]=a[0]*m;/*乘积运算、进位*/

for（i=1;i

{

a[i]=a[i]*m;

a[i]=a[i]+a[i-1]/10;

a[i-1]=a[i-1]%10;

}

while（a[k-1]>=10）

{

k++;

a[k-1]=a[k-2]/10;

a[k-2]=a[k-2]%10;

}

for（i=k-1;i>=0;i--）printf（"%d",a[i]）;/*输出*/

}

②高精度除以低精度；

算法：

按照从高位到低位的顺序，逐位相除。

在除到第j位时，该位在接受了来自第j+1位的余数后与除数相除，如果最高位为零，则商的长度减一。

源程序如下：

#include

#defineN500

main（）

{

inta[N]={0},c[N]={0};

inti,k,d,b;

chara1[N];

printf（"Input除数:

"）;

scanf（"%d",&b）;

printf（"Input被除数:

"）;

scanf（"%s",a1）;

k=strlen（a1）;

for（i=0;i

d=0;

for（i=k-1;i>=0;i--）

{

d=d*10+a[i];

c[i]=d/b;

d=d%b;

}

while（c[k-1]==0&&k>1）k--;

printf（"商="）;

for（i=k-1;i>=0;i--）printf（"%d",c[i]）;

printf（"\n余数=%d",d）;

}

③高精度乘以高精度（要求用尽可能少的存储单元）；

算法：

用数组保存两个高精度数，然后逐位相乘，注意考虑进位和总位数。

源程序如下：

#include

main（）

{

inta[240]={0},b[240]={0},c[480]={0};

inti,j,ka,kb,k;

chara1[240],b1[240];

gets（a1）;

ka=strlen（a1）;

gets（b1）;

kb=strlen（b1）;

k=ka+kb;

for（i=0;i

for（i=0;i

for（i=0;i

for（j=0;j

{

c[i+j]=c[i+j]+a[i]*b[j];

c[i+j+1]=c[i+j+1]+c[i+j]/10;

c[i+j]=c[i+j]%10;

}

if（!

c[k]）k--;

for（i=k-1;i>=0;i--）printf（"%d",c[i]）;

}

④高精度除以高精度（要求用尽可能少的存储单元）；

算法：

用计算机模拟手算除法，把除法试商转化为连减。

#include

#defineN500

intbj（inta[],intb[],intk1,intk2）/*比较大小函数*/

{

inti,t,flag;/*flag作标志位*/

if（k1

flag=0;/*被除数小于除数返回0*/

elseif（k1>k2）

flag=1;/*被除数大于除数返回1*/

else

{/*被除数和除数位数相等则逐位进行比较*/

i=k1;

t=0;

while（t==0&&i>0）

{

if（a[i]>b[i]）{t=1;flag=1;}

elseif（a[i]==b[i]）i--;

else{t=1;flag=0;}

}

if（i==0&&t==0）flag=2;/*被除数等于除数返回2*/

}

returnflag;

}

intjf（inta[],intb[],intk1,intk2）/*减法运算*/

{

inti,k,d[N];

for（i=0;i

for（i=k2;i

k=k1-k2-1;/*计算减法起始位置*/

if（k<0）k=0;

if（k>0）

{

for（i=k2-1;i>=0;i--）d[i+k]=d[i];/*移动减数位数与被减数对齐*/

for（i=0;i

}

for（i=0;i

{

if（a[i]>=d[i]）a[i]-=d[i];

else

{

a[i+1]=a[i+1]-1;

a[i]=10+a[i]-d[i];

}

}

returnk;

}

main（）

{

inta[N]={0},b[N]={0},c[N]={0},d[N]={0};

inti,ka,kb,m,t,t1,t2,k,x,kd,kk;

chara1[N],b1[N];

printf（"Input被除数:

"）;

scanf（"%s",a1）;

ka=strlen（a1）;

for（i=0;i

printf（"Input除数:

"）;

scanf（"%s",b1）;

kb=strlen（b1）;

for（i=0;i

kd=ka;/*保存被除数位数*/

t2=bj（a,b,ka,kb）;

m=0;

do

{

while（a[ka-1]==0）ka--;

t=bj（a,b,ka,kb）;

if（t>=1）

{

k=jf（a,b,ka,kb）;

c[k]++;

if（k>m）m=k;

t1=0;

for（i=k;i<=m;i++）

{

x=c[i]+t1;

c[i]=x%10;

t1=x/10;

}

if（t1>0）{m++;c[m]=t1;}

}

}while（t==1）;

if（t2==0）

{

printf（"商=0"）;

printf（"\n余数="）;

for（i=kd-1;i>=0;i--）printf（"%d",a[i]）;

exit

（1）;

}

if（t2==2）

{

printf（"商=1"）;

printf（"\n余数=0"）;

exit

（1）;

}

kk=kd;

while（!

c[kd-1]）kd--;

printf（"商="）;

for（i=kd-1;i>=0;i--）printf（"%d",c[i]）;

while（!

a[kk]）kk--;

printf（"\n余数="）;

if（kk<0）

{

printf（"0"）;

exit

（1）;

}

for（i=kk;i>=0;i--）printf（"%d",a[i]）;

}

⑤Ｎ！

，要求精确到Ｐ位（０〈Ｐ〈１０００〉。

算法：

结果用数组a保存，开始时a[0]=1，依次乘以数组中各位，注意进位和数组长度的变化。

源程序如下：

#include

#defineM1000

main（）

{

inta[M],i,n,j,flag=1;

printf（"n="）;

scanf（"%d",&n）;

printf（"n!

="）;

a[0]=1;

for（i=1;i

for（j=2;j<=n;j++）

{

for（i=0;i

for（i=0;i