大整数(25000位)的四则运算C语言源程序 -

/**************************************************************
*功能：实现大整数的加减乘除四则运算，最大位长为MAX-1,1为符号位
*思路：利用数组实现，尽量将四则运算封装成函数；
* 1.开始菜单；数组初始化，避免影响第二次运算结果接收数据；提示信息
* 2.接收数据
* 3.先判断进行哪种运算(加减乘除退出),再判断输入的两个数据是否为0
* (加减时，若ab都为0,则直接输出结果0;乘时,则ab任一为0,则直接输出结果0;
* 除时,b为0,则输出提示“输入错误”,b不为0a为0，则直接输出结果0);
* 4.再判断a和b的符号
* 加时:同号相加则调加;+-相加则将-变+再调减;-+相加,将-变+,再调换成+-,再调减
* 减时:++相减则调减;+-相减则将-变+再调加;-+相减则将+变-再调加;--相减，将-变+再交换ab值,再调减
* 乘时:异号相乘结果添'-'号,同号相乘不处理;ab符号皆调正，子函数不处理符号位
* 除时:异号相除结果添'-'号,同号相乘不处理;ab符号皆调正，子函数不处理符号位;若有小数则,则用余数形式显示。
* 5.调用子函数处理数据
* 5.输出结果
*注意!!:数组定义大小要注意，计算结果有的比最大位数大1,有的大2倍+1;
* 因内存限制了数组下标，MAX最大值为25001，本程序运行正常;超出此值，程序运行将出现问题!!!
*测试数据:加法：0+0=0;0+5=5;5+0=5;5+5=10;5+(-8)=-3;(-8)+5=-3;(-5)+(-5)=-10
* 11+12=23;11+123=134;123+11=134; -11+12=1;-11+123=112;-123+11=-112
* 80848+36678623=36759471;-2998602+(-44953)=-3043555;-8+39639213=39639205
* 减法：0-0=0;0-5=-5;5-0=5;5-5=0;5-(-8)=13;(-8)-5=-13;(-5)-(-5)=0
* 11-12=-1;11-123=-112;123-11=112; -11-12=-23;-11-123=-134;-123-11=-134;
* -5429891960-(5838364)=-5435730324;5039-(-41490954)=41495993
* 乘法：0*0=0;0*5=0;5*0=0;5*5=25;5*(-8)=-40;(-8)*5=-40;(-5)*(-5)=25
* 11*12=132;11*123=1353;123*11=1353; -11*12=-132;-11*123=-1353;-123*11=-1353;
* -49*(-128)=6272 4268*13197386=56326443448
* 除法：0/0=--;0/5=0;5/0=--;5/5=1;5/(-8)=-0……5;(-8)/5=-1……3;(-5)/(-5)=1
* 11/12=0……11;11/123=0……11;123/11=11……2; -11/12=-0……11;-11/123=-0……11;-123/11=-11……2;
* 043714/956540=0(输入数据不规范)默认数据最高位非0
* 7425776/338=21969……254
* 8784015415/3545=2477860……1715
* 将#define MAX 25001 改为 #define MAX 5;再将a=b=9999，分别进行加减乘除，结果分别为19998、0、99980001、1
* 验证最大位数计算正确与否再将a=b=-9999，分别进行加减乘除，结果分别为-19998、0、99980001、1
* 验证结束后，根据实际情况，改其值再将a=9999,b=-9999，分别进行加减乘除，结果分别为0、19998、-99980001、-1
* 再将a=-9999,b=9999，分别进行加减乘除，结果分别为0、-19998、-99980001、-1
**************************************************************/
#include <stdio.h>
#define MAX 25001 // 大数的最大位数,包括一位符号位，实际数字位数为MAX-1
/*****************************************
*功能说明：打印菜单函数
* 仅提示用户选择何种运算
* 不接收不判断数据
*****************************************/
void menu() //菜单
{
printf("===============大整数(最大数字位数25000位)计算器==================\n");
printf("1.加法 2.减法 3.乘法 4.除法 0.退出\n");
printf("请从0~4中选择:");
}
/*****************************************
*功能说明: 读入所要计算的数值，数据初始化
*参数说明: a[]第一个数值, b[]第二个数值
* *p1第一个数值长度(包括符号位)
* *p2第二个数值长度(包括符号位)
*其他说明: 参数传递都采用传地址的方式,
* 调用本函数前，需要提前定义好相关变量
* 数组存储数据为大端方式：
* 即：数值-12在数组中的下标依次为0,1,2
* 数组第0位为符号位,0为正，非0为负
*****************************************/
void init(int a[], int b[], int *p1, int *p2) // 输入
{
int i,j;
char r,s;
for(i=0;i<MAX;i++) // 数组清零，以确保第二次之后的运行结果不受影响
{
a[i]=0;
b[i]=0;
}
printf("请输入(0123456789+-)中的任意字符\n请输入第一个(a)数值："); // 默认输入正确，不进行判断
r=getchar();
if(r=='-') // "-" 输入负数
{
a[0]=r;
for(i=1;(r=getchar())!='\n';i++)
a[i]=r-48;
}
else // 输入正数
{
a[1]=r-48;
for(i=2;(r=getchar())!='\n';i++)
a[i]=r-48;
}
*p1=i;
printf("请输入第二个(b)数值："); // 默认输入正确，不进行判断
s=getchar();
if(s=='-')
{
b[0]=s;
for(j=1;(s=getchar())!='\n';j++)
b[j]=s-48;
}
else
{
b[1]=s-48;
for(j=2;(s=getchar())!='\n';j++)
b[j]=s-48;
}
*p2=j;
}
/*****************************************
*功能说明: 两个同号整数相加(++、--)
*参数说明: a[]第一个数值, b[]第二个数值
* c[]第一二数值相加的结果
* 返回值i为c[]数组的长度，即结果的实际长度
* m第一个数值长度(包括符号位)
* n第二个数值长度(包括符号位)
*其他说明: 数组参数传递采用传地址的方式,
* 调用本函数前，需要提前定义好相关变量
* a[],b[],c[]数组存储数据为大端方式：
* 即：数值-12在数组中的下标依次为0,1,2
* d[]数组存储数据为小端方式：
* 即：数值-12在数组中的下标依次为2,1,0
*****************************************/
int plus(int a[], int b[], int c[], int m, int n) //加法运算
{
int d[MAX+1]={0},i,j,k; // 和比最大位数可能长1位
if(a[1]==0) // 处理a+b时，有a为0的情况
{
for(i=0;i<n;i++)
c[i]=b[i];
return(i);
}
if(b[1]==0) // 处理a+b时，有b为0的情况
{
for(i=0;i<m;i++)
c[i]=a[i];
return(i);
}
for(i=m-1,j=n-1,k=1;i>0&&j>0;i--,j--,k++) // 处理a+b时，有a,b都不为0的情况
{
d[k]=a[i]+b[j]+d[k];
if(d[k]>9) // 处理和进位的情况
{
d[k+1]=1;
d[k]=d[k]-10;
}
}
while(i>0) // 处理a+b时, a长度>b长度的情况
{
d[k]=d[k]+a[i];
if(d[k]>9)
{
d[k+1]=1;
d[k]=d[k]-10;
}
k++;
i--;
}
while(j>0) // 处理a+b时, a长度<b长度的情况
{
d[k]=d[k]+b[j];
if(d[k]>9)
{
d[k+1]=1;
d[k]=d[k]-10;
}
k++;
j--;
}
d[0]=a[0]+b[0];
c[0]=d[0];
if(d[k]==0) // 数值和最高位没有进位
k--;
for(i=1;k>0;i++,k--)
c[i]=d[k];
return(i);
}
/*****************************************
*功能说明: 两个正整数相减 (++)
*参数说明: a[]第一个数值, b[]第二个数值
* c[]第一二数值相减的结果
* 返回值i为d[]数组的长度，即结果的实际长度
* m第一个数值长度(包括符号位)
* n第二个数值长度(包括符号位)
*其他说明: 数组参数传递采用传地址的方式,
* 调用本函数前，需要提前定义好相关变量
* a[],b[],c[]数组存储数据为大端方式：
* 即：数值-12在数组中的下标依次为0,1,2
* d[]数组存储数据为小端方式：
* 即：数值-12在数组中的下标依次为2,1,0
*****************************************/
int minus(int a[], int b[], int c[], int m, int n) //减法运算
{
int d[MAX+1]={0},i,j,k,T; // 多一位可能存在的借位位
if (m<n) // a<b 位
{
a: T=m;
m=n;
n=T;
for(i=m-1,j=n-1,k=1;i>0&&j>0;i--,j--,k++)
{
if(d[k]<0||b[i]<a[j]) // 有借位情况
{
d[k]=d[k]+b[i]-a[j];
if(d[k]<0)
{
d[k]+=10;
d[k+1]=-1;
}
}
else // 无借位情况
d[k]=b[i]-a[j];
}
while(i>0)
{
d[k]=d[k]+b[i];
if(d[k]<0)
{
d[k]+=10;
d[k+1]--;
}
k++;
i--;
}
d[k]=b[i]+d[k];
while(d[k]<=0&&k>0)
k--;
for(i=1;k>0;i++)
c[i]=d[k--];
c[0]=45;
return(i);
}
if(m>n) // a>b 位
{
b: for(i=m-1,j=n-1,k=1;i>0&&j>0;i--,j--,k++)
{
if(d[k]<0||a[i]<b[j]) // 有借位情况
{
d[k]=d[k]+a[i]-b[j];
if(d[k]<0)
{
d[k]+=10;
d[k+1]=-1;
}
}
else // 无借位情况
d[k]=a[i]-b[j];
}
while(i>0)
{
d[k]=d[k]+a[i];
if(d[k]<0)
{
d[k]+=10;
d[k+1]--;
}
k++;
i--;
}
d[k]=a[i]+d[k];
while(d[k]<=0&&k>0)
k--;
for(i=1;k>0;i++)
c[i]=d[k--];
return(i);
}
// a==b 位数
{
for(i=1; i<m; i++)
{
if(a[i]>b[i]) // a>b 数值
goto b;
else if(a[i]<b[i]) // a<b 数值
goto a;
}
c[0]=0; //a=b
c[1]=0;
return 2;
}
}
/*****************************************
*功能说明: 两个整数相乘
*注：函数运算过程中未处理符号
*参数说明: a[]第一个数值, b[]第二个数值
* c[]第一二数值相乘的结果
* 返回值k为c[]数组的长度，即结果的实际长度(包括符号位)
* m第一个数值长度(包括符号位)
* n第二个数值长度(包括符号位)
*其他说明: 数组参数传递采用传地址的方式,
* 调用本函数前，需要提前定义好相关变量
* a[],b[],c[]数组存储数据为大端方式：
* 即：数值-12在数组中的下标依次为0,1,2
* d[]数组存储数据为小端方式：
* 即：数值-12在数组中的下标依次为2,1,0
*★ Comba 乘法（Comba Multiplication）原理实现
* Comba 乘法以（在密码学方面）不太出名的 Paul G. Comba 得名。
* 和普通的笔算乘法很类似，只是每一次单精度乘法只是单纯计算乘法，不计算进位，进位留到每一列累加后进行。
* Comba 乘法无需进行嵌套进位来计算乘法,时间复杂度和基线乘法一样
* Comba 乘法则按列计算，先累加，然后传递进位，减少了计算量，所以速度快。
************************************************************/
int multi(int a[], int b[], int c[], int m, int n) //正整数乘法运算
{
int d[2*MAX+1]={0},i,j,k,s;
for(i=0;i<MAX;i++)
c[i]=0;
if(m<=n) // a位数大于等于b位数
{
for(i=m-1,s=1;i>0;i--,s++) // 单纯计算乘法，不计算进位
{
for(j=n-1,k=1*s;j>0;j--,k++)
{
d[k]=a[i]*b[j]+d[k];
}
}
for(i=1;i<k;i++) // 处理进位
{
if(d[i]>9)
{
d[i+1]=d[i+1]+d[i]/10;
d[i] = d[i]%10;
}
}
if(d[i]==0) // 数值和最高位没有进位
i--;
for(k=1;i>0;k++,i--)
c[k]=d[i];
return k;
}
else // a位数大于b位数
{
for(i=n-1,s=1;i>0;i--,s++) // 单纯计算乘法，不计算进位
{
for(j=m-1,k=1*s;j>0;j--,k++)
{
d[k]=b[i]*a[j]+d[k];
}
}
// 处理进位
for(i=1;i<k;i++)
{
if(d[i]>9)
{
d[i+1]=d[i+1]+d[i]/10;
d[i] = d[i]%10;
}
}
if(d[i]==0) // 数值和最高位没有进位
i--;
for(k=1;i>0;k++,i--)
c[k]=d[i];
return k;
}
}
/*****************************************
*功能说明: 用长度为len1的大整数p1减去长度为len2的大整数p2
* 结果存在p1中，返回值代表结果的长度
* 不够减：返回-1 ，正好够：返回0
*数组数值为：p1,p2小端
*其他说明: 数组参数传递采用传地址的方式,
* 调用本函数前，需要提前定义好相关变量
* 本函数的作用仅与Division函数结合实现除法
*****************************************/
int SubStract(int *p1, int len1, int *p2, int len2)
{
int i;
if(len1 < len2)
return -1;
if(len1 == len2 )
{ // 判断p1 > p2
for(i = len1-1; i >= 0; i--)
{
if(p1[i] > p2[i]) // 若大，则满足条件，可做减法
break;
else if(p1[i] < p2[i]) // 否则返回-1
return -1;
}
}
for(i = 0; i <= len1-1; i++) // 从低位开始做减法
{
p1[i] -= p2[i]; // 相减
if(p1[i] < 0) // 若是否需要借位
{ // 借位
p1[i] += 10;
p1[i+1]--;
}
}
for(i = len1-1; i >= 0; i--) // 查找结果的最高位
{
if( p1[i] ) //最高位第一个不为0
return (i+1); //得到位数并返回
}
return 0; //两数相等的时候返回0
}
/*****************************************
*功能说明: 大数除法---结果不包括小数点
**注：函数运算过程中未处理符号
*参数说明: a[]被除数 b[]除数
* c[]第一二数值相除的结果即：a/b=c
* 返回值len为c[]数组的长度，即结果的实际长度
* m第一个数值长度(包括符号位)
* n第二个数值长度(包括符号位)
* *p表示余数的位数，位数大于0时,表示有余数；否则无余数
* num_a[]保存最后余数的
*其他说明: 数组参数传递采用传地址的方式,
* 调用本函数前，需要提前定义好相关变量
* a[],b[],c[],num_a[]数组存储数据为大端方式：
* 即：数值-12在数组中的下标依次为0,1,2
*****************************************/
int Division(int a[], int b[], int c[] , int m, int n, int *p, int num_a[])
{
int i, j;
int len=0;
int nTimes; //两大数相差位数
int nTemp; //Subtract函数返回值
int num_b[MAX] = {0}; //除数
int num_c[MAX+1] = {0}; //商
if( m < n ) //如果被除数小于除数，直接返回-1，表示结果为0……a
{
return -1;
}
if(m==n)
{
for(i=1; i<m; i++)
{
if(a[i]>b[i]) // 够减一次否
break;
}
if(i==m && a[m-1]<b[m-1]) // 包含符号位
return -1; // 如果被除数小于除数，直接返回-1，表示结果为0……a
}
nTimes = m - n; //相差位数
//翻转保存的数据
for( j = 1, i = m-1; i >= 0; j++, i-- )
num_a[j] = a[i];
for( j = 1, i = n-1; i >= 0; j++, i-- )
num_b[j] = b[i];
for ( i=m-1; i>=0; i-- ) //将除数扩大，使得除数和被除数位数相等
{
if ( i>=nTimes )
num_b[i] = num_b[i-nTimes];
else //低位置0
num_b[i] = 0;
}
n=m;
for( j=0; j<=nTimes; j++ ) //重复调用，同时记录减成功的次数，即为商
{
while((nTemp = SubStract(num_a,m,num_b + j,n - j)) >= 0)
{
m = nTemp; //结果长度
num_c[nTimes-j]++;//每成功减一次，将商的相应位加1
}
}
if(nTemp<0)
*p=m; // 有余数
else
*p=0; //无余数
// 计算商的位数，并将商放在c数组中
for(i = MAX-1; num_c[i] == 0 && i >= 0; i-- ); //跳过高位0，获取商的位数
if(i >= 0)
len = i + 1; // 保存位数
for(j = 1; i >= 0; i--, j++) // 将结果复制到c数组中
{
c[j] = num_c[i];
}
return len+1; // 返回商的位数
}
//功能说明：主函数，调用其余函数，计算相应功能的值并输出
int main()
{
//积的位数最多是因数位数的两倍
int a[MAX]={0}, b[MAX]={0}, c[2*MAX+1]={0}, Temp[MAX]={0};
int m,n;
int *p1,*p2;
int i, j;
int select;
int len;
int remainder;
p1=&m;
p2=&n;
while(1)
{
for(i=0;i<MAX;i++) // 初始化0,避免影响下一次运行
{
a[i]=0;
b[i]=0;
c[i]=0;
Temp[i]=0;
}
for(;i<2*MAX+2;i++) // 初始化0,避免影响下一次运行
{
c[i]=0;
}
menu(); // 仅输出提示信息
select=getchar(); // 获得四则运算中的一个(1加2减3乘4除0退出)
getchar(); // 处理选择时候的回车，避免第二次运行无法重新选择0~4
if(select =='0')
return 0; // 退出程序
else if(!(select>'0'&&select<'5'))
{
printf("输入错误!\n请从0~4中选择一个数输入!!\n\n");
continue;
}
init(a,b,p1,p2); // 获取两个数值
switch(select)
{
case '1':
{
if(a[1]==0&&b[1]==0) // 两0相加
{
printf("a+b=0\n\n");
break;
}
printf("a+b=");
if(a[0]==b[0]) // 同号相加则调加
{
j=plus(a, b, c, m, n); //加法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
if(a[0]==0 && b[0]!=0) // +-相加则将-变+再调减
{
b[0]=0; // 将b的符号变为+
j=minus(a, b, c, m, n); //减法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
// -+相加,将-变+,再调换成+-,再调减
{
a[0]=0; // 将-变+
// 交换a，b数值
for(i=1; i<(m>n?m:n); i++)
{
Temp[i]=a[i];
a[i]=b[i];
b[i]=Temp[i];
}
// 交换a，b位数
i=m;
m=n;
n=i;
j=minus(a, b, c, m, n); //减法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
}
case '2':
{
if(a[1]==0&&b[1]==0) // 两0相减
{
printf("a-b=0\n\n");
break;
}
printf("a-b=");
if(a[0]==0&&b[0]==0) // ++相减则调减
{
j=minus(a, b, c, m, n); //减法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
if(a[0]==0&&b[0]!=0) // +-相减则将-变+再调加
{
b[0]=0; // 将b的符号变为+
j=plus(a, b, c, m, n); //加法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
if(a[0]!=0&&b[0]==0) // -+相减则将+变-再调加
{
b[0]='-'; // 将b的符号变为-
j=plus(a, b, c, m, n); //加法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
// --相减，将-变+再交换ab值,再调减
{
a[0]=0; // 将-变+
b[0]=0;
// 交换a，b数值
for(i=1; i<(m>n?m:n); i++)
{
Temp[i]=a[i];
a[i]=b[i];
b[i]=Temp[i];
}
// 交换a，b位数
i=m;
m=n;
n=i;
j=minus(a, b, c, m, n); //减法运算
if(c[0]!=0)
printf("-");
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
}
case '3':
{
if(a[1]==0||b[1]==0) // 任意个0相乘
{
printf("a*b=0\n\n");
break;
}
printf("a*b=");
if((a[0]==0&&b[0]!=0)||(a[0]!=0&&b[0]==0)) // 异号相乘结果添'-'号，ab符号设为+，运算中符号不起作用
printf("-");
a[0]=0;
b[0]=0;
j=multi(a, b, c, m, n); //正整数乘法运算
for(i=1;i<j;i++)
printf("%d",c[i]);
printf("\n\n");
break;
}
case '4':
{
if(b[1]==0) // 除数为0
{
printf("输入错误!!\n除数不能为0!!!\n\n");
break;
}
else if(a[1]==0) //被除数为0
{
printf("a÷b=0\n\n");
break;
}
printf("a÷b=");
if((a[0]==0&&b[0]!=0)||(a[0]!=0&&b[0]==0)) // 异号相除结果添'-'号，ab符号设为+，运算中符号不起作用
printf("-");
len = Division(a, b, c, m, n, &remainder, Temp);
//输出结果
if( len>0 )
{
for(i = 1; i < len; i++ )
printf("%d", c[i]);
if(remainder>0) // 有余数，输出余数
{
printf("……");
for(i=remainder-1; i>0; i--)
printf("%d", Temp[i]);
}
}
else
{
printf("0……");
for(i = 1; i < m; i++ )
printf("%d", a[i]);
}
printf("\n\n");
break;
}
}
}
return 0;
}

复制代码