首页 > 代码库 > 大整数的加减乘除
大整数的加减乘除
多项式的加减乘除可以利用多项式的加减乘除进行运算，所以以下程序采用了多项式的加减乘除。多项式运算已经在《算法导论》第30章有简要的介绍，具体的请参考数学书。
大整数加法：(利用书上公式轻松得出)
//多项式加法-大数加法
#include <iostream>
#include <time.h>
using namespace std;
#define m1 4
#define m2 5
//a[0]=x^0 a[1]=x^1....a[n]=x^n的关于x的多项式系数
//b[0]=x^0 b[1]=x^1....b[n]=x^n表示另一关于x的多项式系数
//多项式的系数也可以看做每位上的数字
const int k=m1<m2?m2:m1;
void Simple_Large_int_add(int a[],int b[],int c[])
{
for (int i=0;i<=k;i++)
{
c[i]+=a[i]+b[i];
if (c[i]>=10)
{
c[i+1]=c[i]/10;
c[i]%=10;
}
}
}
void main()
{
srand( (unsigned)time( NULL ) );
int a[k+1]={4,2,5,1,7};//12345X12345=152399025
int b[k+1]={6,2,1,4,0,0};
int c[k+1]={0};
for (int i=m1;i>=0;i--)
{
//a[i]=rand()%10;
cout<<a[i];
}
cout<<" + ";
for ( i=m2;i>=0;i--)
{
//b[i]=rand()%10;
cout<<b[i];
}
cout<<"=";
Simple_Large_int_add(a,b,c);
for ( i=k;i>=0;i--)
{
if (i==k&&c[i]==0)
{
continue;
}
cout<<c[i];
}
cout<<endl;
}大整数减法：(和加法类似)
//多项式减法-大数减法
#include <iostream>
#include <time.h>
using namespace std;
#define m1 1000
#define m2 898
//a[0]=x^0 a[1]=x^1....a[n]=x^n的关于x的多项式系数
//b[0]=x^0 b[1]=x^1....b[n]=x^n表示另一关于x的多项式系数
//多项式的系数也可以看做每位上的数字
const int k=m1<m2?m2:m1;
void Simple_Large_int_Sub(int a[],int b[],int c[])
{
for (int i=0;i<=k;i++)
{
if (k==m1)
{
if (a[i]<b[i])
{
c[i]+=a[i]+10-b[i];
a[i+1]=a[i+1]-1;
}
else c[i]+=a[i]-b[i];
}
else
{
if (b[i]<a[i])
{
c[i]+=b[i]+10-a[i];
b[i+1]=b[i+1]-1;
}
else c[i]+=b[i]-a[i];
}
}
}
void main()
{
srand( (unsigned)time( NULL ) );
int a[k+1]={0};//12345X12345=152399025
int b[k+1]={0};
int c[k+1]={0};
for (int i=m1;i>=0;i--)
{
a[i]=rand()%10;
cout<<a[i];
}
cout<<" - ";
for ( i=m2;i>=0;i--)
{
b[i]=rand()%10;
cout<<b[i];
}
cout<<" = ";
Simple_Large_int_Sub(a,b,c);
int temp=k;
if (k==m2)
{
temp=k;
c[temp]=-c[temp];
while (c[temp]==0)
{
--temp;
c[temp]=-c[temp];
if (c[temp]!=0)
{
break;
}
}
}
for ( i=temp;i>=0;i--)
{
cout<<c[i];
}
cout<<endl;
}大整数的乘法：(利用书上的公式轻松得出)
//多项式乘法-大数乘法
#include <iostream>
#include <time.h>
using namespace std;
#define m1 300
#define m2 400
#define n m1+m2
//a[0]=x^0 a[1]=x^1....a[n]=x^n的关于x的多项式系数
//b[0]=x^0 b[1]=x^1....b[n]=x^n表示另一关于x的多项式系数
//多项式的系数也可以看做每位上的数字
void Simple_Large_int_multiplication(int a[],int b[],int c[])
{
for (int j=n-1;j>=0;j--)
{
int i=n-1-j;
for (int k=0;k<=j;k++)
{
c[i]+=a[k]*b[j-k];
}
if (c[i]>=10)
{
c[i+1]=c[i]/10;
c[i]%=10;
}
}
}
void main()
{
srand( (unsigned)time( NULL ) );
int a[n+1]={0};//12345X12345=152399025
int b[n+1]={0};
int c[n+1]={0};
for (int i=0;i<m1;i++)
{
a[i]=rand()%10;
cout<<a[i];
}
cout<<" X ";
for ( i=0;i<m2;i++)
{
b[i]=rand()%10;
cout<<b[i];
}
cout<<" = ";
Simple_Large_int_multiplication(a,b,c);
for ( i=n;i>0;i--)
{
if (i==n&&c[i]==0)
{
continue;
}
cout<<c[i];
}
cout<<endl;
}大整数的除法：(可以由大整数减法得出，算是比较复杂的一个四则运算了)
参考资料：超大整数除法 但是这个链接里的代码有3点需要说明：1，当被除数与除数相同时，会产生错误，比如701/101返回的是1，而不是6. 2,这个代码用了string数组，我和他不太一样，我用的是int数组，所以代码还是有区别的。3，还有一点需要说明，他的代码用了 itoa系统函数，这个函数在VS2013编译器已经被废弃了。
//*************************超长整数除法*******************************///*核心思想是程序中使用了int数组存放大整数的每一位,扩大除数的倍数使其*///*位数与被除数位数相同，然后被除数与除数每循环一次，就比较一次。*****///*如果被除数＜除数，不进行大整数的减法，除数减少1位继续下一次循环****///*如果被除数＞除数，进入大整数的循环减法操作直到被除数小于除数，*****///*而后同样进行下一层循环。这样经过数次循环直到被扩大倍数的除数位*****///*数减少到初始除数位数为止这样可以同时得到余数和商完成大整数除法操作*///*例如10480÷45扩大100倍=>10480÷45000减少1位=>10480÷4500发现能减2次///*1048÷4500缩小1位=>1048÷450发现能减3次=>130÷450减少1位=>130÷45**///*发现能减2次=>40÷45除数为初始除数循环结束，除法结束 最终余数40商232///*这除法运行时间是对于β位的大整数需要O(β^2)时间********************/#include <iostream>#include <time.h>using namespace std;#define m1 500#define m2 150//a[0]=x^0 a[1]=x^1....a[n]=x^n的关于x的多项式系数//b[0]=x^0 b[1]=x^1....b[n]=x^n表示另一关于x的多项式系数//多项式的系数也可以看做每位上的数字const int k = m1<m2 ? m2 : m1;int len1 = m1, len2 = m2;//被除数大于除数的辅助大整数减法函数void help1(int a[], int b[], int c[])//O(β) 对于β位整数来说{ int j = k; while (j >= 0)c[j--] = 0; for (int i = 0; i <= k; i++) { if (a[i]<b[i]) { c[i] += a[i] + 10 - b[i]; a[i + 1] = a[i + 1] - 1; } else c[i] += a[i] - b[i]; a[i] = c[i]; } while (!a[len1]) --len1;}//大整数的减法int Simple_Large_int_Sub(int a[], int b[], int c[])//O(β) 对于β位整数来说{ if (len1 == len2) { int i = len1; while (a[i] == b[i]) i--; if (a[i]>b[i]) { help1(a, b, c); return 1; } else return -1; } else { if (len2<len1) { help1(a, b, c); return 1; } else return -1; }}int divide(int a[], int b[], int c[]){ int res[k + 1] = { 0 }, temp = 0, flag = 0;//res数组是存放商的数组 if (len2 == 0 && b[0] == 0) { cout << "除数不能为0！" << endl; return 0; } if (len1<len2) { return 1; } else { if (len1 == len2) { int i = len1; while (a[i] == b[i])i--; if (a[i] < b[i])return 1; } while (!b[len2])len2--;//00xxx...化简为xxx，第一个非0数字之前的所有0全部去掉后计算大整数的实际位数 while (!a[len1])len1--;//同上,如果不进行随机生成大整数的话，那么这两个循环可以省略掉 int p = len1 - len2; int j = len2, q = len2; int i = (len2 += p); while (i >= 0)//这个循环是给除数末尾补0使其与被除数位数一样， { if (j<0) { b[i--] = 0; continue; } b[i] = b[j]; --i; --j; } while (p >= 0)//O(cβ^2) {//O(β1-β2)=O(β)最外层循环执行次数就是2个整数的差值，最大可能到β位(因为β位-1位=β位) int t = 0; int q2 = len2;//q2至少为1 while (Simple_Large_int_Sub(a, b, c) >= 0)//O(cβ)每次计算大整数相减，都要进行β次循环 t++;//t<10=>O(c) 最多循环9次，所以这层循环只需花费常数时间 res[p] = t; if (res[p] != 0 && flag == 0){ temp = p; flag = 1; } p--; //len2--; int i = 0; q2 -= len1;//计算len2减少的实际位数 if (q2 == 0)q2 = 1; len2 -= q2; while (i <= k&&len2>q - 1) { if (i>len2) { b[i++] = 0; continue; } b[i] = b[i + q2]; i++; } if (len2 <= q - 1){ break; }//如果经过X10加倍的除数减少到小于等于原来的除数-1，那么除法结束跳出循环 while (q2>1)//如果q2减少的位数超过1位，那么需要给商补0 { res[p--] = 0; q2--; } } cout << "商="; for (j = temp; j >= 0; j--) { cout << res[j]; } return 2; }//除数长度大于被除数长度}void main(){ srand((unsigned)time(NULL)); int a[k + 1] = { 0 }; int b[k + 1] = { 0 }; int c[k + 1] = { 0 };//c为临时数组 for (int i = m1; i >= 0; i--) { a[i]=rand()%10; cout << a[i]; } cout << " ÷ "; for ( i = m2; i >= 0; i--) { b[i] = rand() % 10; cout << b[i]; } cout << " = "; int p = divide(a, b, c); if (p == 1) { cout << "商=" << "0" << endl; cout << "余数="; for (int i = m1; i >= 0; i--) { cout << a[i]; } } else if (p == 2) { cout << "余数="; int i = k; while (!a[i]&&i!=0)--i; for (int j = i; j >= 0; j--) { cout << a[j]; } } else cout << "输入错误！" << endl; cout << endl;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。