C语言的高精度算法
- 格式：doc
- 大小：92.50 KB
- 文档页数：18
1 高精度计算
一． 加法
先判断出两个数哪个较长，两个数从个位对齐后，从个位数开始相加，先不考虑进位的问题，相加直到较短的数的最高位。接着把较长的数未相加的部分进行赋值。最后在处理进位问题（判断每位上的数是否大于等于10）。
其中要注意的是两数相加，得到的和的位数是否比较长的数的位数大1。和进位问题的处理。
代码：
# include
# include
# include
void add(char* a,char* b,char* c)
{
int i,j,k,max,min,n,temp;
char *s,*pmax,*pmin;
max=strlen(a);
min=strlen(b);
if (max
temp=max;
max=min;
min=temp;
pmax=b;
pmin=a;
}
else
{
pmax=a;
pmin=b;
}
s=(char*)malloc(sizeof(char)*(max+1));
s[0]='0';
for (i=min-1,j=max-1,k=max;i>=0;i--,j--,k--)
s[k]=pmin[i]-'0'+pmax[j];
for (;j>=0;j--,k--)
s[k]=pmax[j];
for (i=max;i>=0;i--)
if (s[i]>'9')
{
s[i]-=10; 3 s[i-1]++;
}
if (s[0]=='0')
{
for (i=0;i<=max;i++)
c[i-1]=s[i];
c[i-1]='\0';
}
else
{
for (i=0;i<=max;i++)
c[i]=s[i];
c[i]='\0';
}
free(s);
}
二． 减法
先考虑减数大于被减数的情况。也是先对齐，再相减，接赋值，最后是处理借位问题（判断每位上的数是否小于0）。
如果减数小于被减数的话，可以用被减数减去减数。最后在结果的前面加个负号就可以了。 4
源代码：
# include
# include
# include
void subtract(char* a,char* b,char* c)
{
int i,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;j>=0;i--,j--)
a[i]-=(b[j]-'0');
for (i=ca-1;i>=0;i--)
if (a[i]<'0')
{
a[i]+=10;
a[i-1]--;
}
i=0;
while (a[i]=='0')
i++;
if (a[i]=='\0')
{
c[0]='0';
c[1]='\0';
}
else
{
for (j=0;a[i]!='\0';i++,j++)
c[j]=a[i];
c[j]='\0';
}
}
else
{
for (i=ca-1,j=cb-1;i>=0;i--,j--)
b[j]-=(a[i]-'0');
for (j=cb-1;j>=0;j--)
if (b[j]<'0')
{ 5 b[j]+=10;
b[j-1]--;
}
j=0;
while (b[j]=='0')
j++;
i=1;
c[0]='-';
for (;b[j]!='\0';i++,j++)
c[i]=b[j];
c[i]='\0';
}
}
三．乘法
注意乘积的最大位数是两个数的位数之和。先相乘，再处理进位问题。
for (i=0;i
for (j=0;j
c[i+j+1]+=(a[i]-'0')*(b[j]-'0')；
源代码：
# include
# include
# include
void multiply(char* a,char* b,char* c)
{
int i,j,ca,cb,* s;
ca=strlen(a);
cb=strlen(b);
s=(int*)malloc(sizeof(int)*(ca+cb));
for (i=0;i
s[i]=0;
for (i=0;i
for (j=0;j
for (i=ca+cb-1;i>=0;i--)
if (s[i]>=10)
{
s[i-1]+=s[i]/10;
s[i]%=10;
}
i=0;
while (s[i]==0)
i++;
for (j=0;i
c[j]=s[i]+'0';
c[j]='\0';
free(s);
}
四． 除法
高精度的除法最后的结果整数部分和余数。其中被除数一般是计算机可以表示的整数。
源代码：
# include
# include
# include
int dividor(char* a,int b,char* c)
{
int i,j,temp=0,n;
char* s;
n=strlen(a); 7 s=(char*)malloc(sizeof(char)*(n+1));
for (i=0;a[i]!=0;i++)
{
temp=temp*10+a[i]-'0';
s[i]=temp/b+'0';
temp%=b;
}
s[i]='\0';
for (i=0;s[i]=='0'&&s[i]!='\0';i++);
if (s[i]=='\0')
{
c[0]='0';
c[1]='\0';
}
else
{
for (j=0;s[i]!='\0';i++,j++)
c[j]=s[i];
c[j]='\0';
}
free(s);
return temp; 8 }
例1（ ZOJ-1205）：
在22世纪，科学家发现有外星人的存在。他们十分喜欢数学。每年他们都举行 ACM比赛。题目是计算2个100位数的和。谁用的时间最少，谁就获胜。
今年他们邀请我们去参加他们的比赛。而你幸运的成为我们的代表去参赛。现在你唯一的问题是编写一个小程序去计算2个数的和。但是他们的数是20进制。他们的数由0-9和a-j（代表10-19）表示。
输入：
成对的给出一些他们用20进制表示的数，每个数占一行。而且每个数不会超过100位。
输出：
对每一对数，在一行上输出他们的和（还是用20进制表示）。
分析：
两数相加，对齐后，从最后一位开始。先把各个位上的数转化成10进制的数，再相加。最后把各个位上的数转化成20进制的数。注意2个数的和，最后位数可能跟较长的数相同，可能大1。
源代码： 9 # include
# include
int main()
{
int i,min,max,j;
char a[101],b[101],c[102],*pmin,*pmax;
while (scanf("%s %s",a,b)==2) //判断输入是否结素
{
if (a[0]=='0'&&b[0]=='0') //可能有点多余
printf("0\n");
else
{
for (i=0;i<101;i++)
c[i]='0';
min=strlen(a); /*
max=strlen(b)； 求每个数的长度
if (min<=max) 把较长的数的地址赋给pmax
{ 较短的赋给pmin
pmin=a; 这样可以节省考虑的情况
pmax=b; */
}
else
{
i=min;
min=max;
max=i;
pmin=b;
pmax=a;
}
i=j=max;
c[max+1]='\0';
for (min--,max--;min>=0;i--,min--,max--) /*
{ 先将2个数从最后一位对齐
if (pmin[min]>='a') 在从最后一位开始相加
