当前位置：文档库 › 大整数运算C++编程

大整数运算C++编程

#include
#include
#include
#include
#include
#include

using namespace std;

const int Max = 1000; //可根据用户的需要适当修改大数上限

class BigFigure
{
public:
int Substract(int *, int *, int, int); //大数除法需要调用的减法函数
string addition(string &, string &); //大数加法
string subtration(string &, string ); //大数减法
string multiplication(string &, string &); //大数乘法
string division(string &, string &); //大数除法
string remainder(string &, string &); //大数取余
string power(string &, string &); //大数求幂
void showResult(); //输出结果
private:
string outcome; //结果存储
};
/*******************大数加法******************/
string BigFigure::addition(string &str1, string &str2)
{
int i,j,flag = 0;
string str;
vector num1(Max+10);
vector num2(Max+10);
if(str1[0] == '-'&&str2[0] == '-')
{
flag = 1;
str1.erase(0,1);
str2.erase(0,1);
}
else if(str1[0] == '-'&&str2[0] != '-')
{
str1.erase(0,1);
outcome = subtration(str2,str1);
return outcome;
}
else if(str1[0] != '-'&&str2[0] == '-')
{
str2.erase(0,1);
outcome = subtration(str1,str2);
return outcome;
}

j = 0;
for(i = str1.size()-1; i >= 0; i--)
num1[j++] = str1[i]-'0'; //num1[0]存的是个位

j = 0;
for(i = str2.size()-1; i >= 0; i--)
num2[j++] = str2[i]-'0';

for(i = 0; i <= Max; i++)
{
num1[i] += num2[i];
if(num1[i]>=10) //如果某位的数大于9，则将这一位减10，然后将高位加1
{
num1[i] -= 10;
num1[i+1]++;
}
}
bool isBeginOutput = false;
for(i = Max; i >= 0; i--)
{
if(num1[i] != 0) //找到第一个不为0的数，然后令isBeginOutput为true
isBeginOutput = true;
if(isBeginOutput) //当isBeginOutput为true时，将大数存入字符串str
str += num1[i]+48;
}
if(!isBeginOutput) //找不到不为0的数，直接将str置为0
str = "0";
if(flag) //若标记flag=1，则将结果之前插入一个负号
str.insert(0,"-");
outcome = str;
return outcome;
}
/*******************大数减法******************/
string BigFigure::subtration(string &str1, string str2)
{
string str;
int i, j;
vector num1(Max+10);
vector num2(Max+10);
int flag = 0;

if(str1[0] == '-'&&str2[0] == '-')
{
str1.erase(0,1);
str2.erase(0,1);
outcome = subtration(str2,str1);

return outcome;
}
else if(str1[0] == '-'&&str2[0] != '-')
{
str1.erase(0,1);
outcome = addition(str1,str2);
outcome.insert(0,"-");
return outcome;
}
else if(str1[0] != '-'&&str2[0] == '-')
{
str2.erase(0,1);
outcome = addition(str1,str2);
return outcome;
}

if((str1.size() < str2.size())||((str1.size() == str2.size())&&(str1 < str2)))
{ //如果被减数小于减数进行交换，flag记为1
flag = 1;
string temp;
temp = str1;
str1 = str2;
str2 = temp;
}

j = 0;
for(i = str1.size()-1; i >= 0; i--)
num1[j++] = str1[i]-'0';

j = 0;
for(i = str2.size()-1; i >= 0; i--)
num2[j++] = str2[i]-'0';

for(i = 0; i <= Max; i++)
{
num1[i] -= num2[i];
if(num1[i]<0) //如果某位的数小于0，则将这一位加10，然后将高位减1
{
num1[i] += 10;
num1[i+1]--;
}
}

bool isBeginOutput = false;
for(i = Max; i >=0; i--)
{
if(num1[i] != 0)
isBeginOutput = true;
if(isBeginOutput)
str += num1[i]+48;
}
if(flag) //若标记flag=1，则将结果之前插入一个负号
str.insert(0,"-");
outcome = str;
if(!isBeginOutput)
outcome = "0";
return outcome;
}
/*******************大数乘法******************/
string BigFigure::multiplication(string &str1, string &str2)
{
string str;
int i, j;
vector num1(Max+10);
vector num2(Max+10);
vector c(2*Max);

if(str1[0] == '-'&&str2[0] == '-')
{
str1.erase(0,1);
str2.erase(0,1);
}
else if(str1[0] == '-'&&str2[0] != '-')
{
str1.erase(0,1);
outcome = multiplication(str1,str2);
outcome.insert(0,"-");
return outcome;
}
else if(str1[0] != '-'&&str2[0] == '-')
{
str2.erase(0,1);
outcome = multiplication(str1,str2);
outcome.insert(0,"-");
return outcome;
}

j = 0;
for(i = str1.size()-1; i >= 0; i--)
num1[j++] = str1[i]-'0';

j = 0;
for(i = str2.size()-1; i >= 0; i--)
num2[j++] = str2[i]-'0';

for(i = 0; i < Max; i++)
for(j = 0; j < Max; j++)
c[i+j] += num1[j]*num2[i]; //两数第i, j 位相乘，累加到结果的第i+j位上

for(i = 0; i < 2*Max; i++) //下面统一处理进位问题
if(c[i]>=10)
{
c[i+1] += c[i]/10; //从低位到高位依次进行进位
c[i] %= 10;
}

bool isBeginOutput = false;
for(i = 2*Max-1; i >= 0 ; i--)
{
if(c[i] != 0)
isBeginOutput = true;
if(isBeginOutput)
str += c[i]+

48;
}
if(!isBeginOutput)
outcome = "0";

outcome = str;
return outcome;
}
/************大数除法需要调用的减法函数*************/
int BigFigure::Substract( int * p1, int * p2, int Len1, int Len2)
{ //返回值为结果长度
int i;
if(Len1 < Len2)
return -1;

if(Len1 == Len2)
{
for(i = Len1-1; i >= 0; i--)
{
if(p1[i] > p2[i])
break;
else if(p1[i] < p2[i])
return -1; //如果不够减返回-1
}
}
for(i = 0; i < Len1; 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;
}
/*******************大数除法******************/
string BigFigure::division(string &str1, string &str2)
{
string str;
int an1[Max + 10];
int an2[Max + 10];
int result[Max + 10];
int i, j;
memset( an1, 0, sizeof(an1)); //置数组元素全为0
memset( an2, 0, sizeof(an2));
memset( result, 0, sizeof(result));

if(str2 == "0")
{
str.insert(0,"error!");
outcome = str;
return outcome;
}

if(str1[0] == '-'&&str2[0] == '-')
{
str1.erase(0,1);
str2.erase(0,1);
}
else if(str1[0] == '-'&&str2[0] != '-')
{
str1.erase(0,1);
outcome = division(str1,str2);
if(outcome != "0")
outcome.insert(0,"-");
return outcome;
}

else if(str1[0] != '-'&&str2[0] == '-')
{
str2.erase(0,1);
outcome = division(str1,str2);
if(outcome != "0")
outcome.insert(0,"-");
return outcome;
}

int Len1 = str1.length();
int Len2 = str2.length();

j = 0;
for(i = Len1 - 1; i >= 0; i--)
an1[j++] = str1[i] - '0';

j = 0;
for(i = Len2 - 1; i >= 0; i--)
an2[j++] = str2[i] - '0';
if(( Len1 < Len2 )||((Len1==Len2)&&(str1 < str2))) //如果被除数大于除数，结果为0
{
outcome = "0";
return outcome;
}
else if( (Len1==Len2)&&(str1==str2) ) //如果被除数等于除数，结果为1
{
outcome = "1";
return outcome;
}
else
{
int nTimes = Len1 - Len2;
for(i = Len1 -1; i >= 0; i--) //将 an2 乘以10 的某次幂，使得结果长度和 an1 相同
{
if(i >= nTimes)
an2[i] = an2[i-nTimes];
else
an2[i] = 0;
}
Len2 = Len1;
//一直减到不够减为止
//先减去若干个 an2×(10 的 nTimes 次方)，

//不够减了，再减去若干个 an2×(10 的 nTimes-1 次方)，......
int nTmp;
for(j = 0; j <= nTimes; j++)
{
while( (nTmp = Substract(an1, an2+j, Len1, Len2-j)) >= 0 )
{
Len1 = nTmp;
result[nTimes-j]++; //每成功减一次，则将商的相应位加1
}
}
bool isBeginOutput = false;
for(i = Max; i >= 0; i--)
{
if(result[i] != 0)
isBeginOutput = true;
if(isBeginOutput)
str += result[i]+48;
}
outcome = str;
}
return outcome;
}
/*******************大数取余******************/
string BigFigure::remainder(string &str1, string &str2)
{
string str;
int an1[Max + 10];
int an2[Max + 10];
int i, j;
int Len1 = str1.length();
int Len2 = str2.length();
memset( an1, 0, sizeof(an1));
memset( an2, 0, sizeof(an2));

if(str2 == "0")
{
str.insert(0,"error!");
outcome = str;
return outcome;
}

j = 0;
for(i = Len1 - 1; i >= 0; i--)
an1[j++] = str1[i] - '0';

j = 0;
for(i = Len2 - 1; i >= 0; i--)
an2[j++] = str2[i] - '0';

if((Len1 < Len2)||(Len1==Len2)&&(str1 < str2))
{
outcome = str1;
return outcome;
}

if((Len1==Len2)&&(str1==str2))
{
outcome = "0";
return outcome;
}
else
{

int nTimes = Len1 - Len2;
for(i = Len1 -1; i >= 0; i--)
{
if(i >= nTimes)
an2[i] = an2[i-nTimes];
else
an2[i] = 0;
}

Len2 = Len1;
for(j = 0; j <= nTimes; j++)
{
int nTmp;
while( (nTmp = Substract(an1, an2+j, Len1, Len2-j)) >= 0 )
Len1 = nTmp;
}
bool isBeginOutput = false;
for(i = Max; i >= 0; i--)
{
if(an1[i] != 0)
isBeginOutput = true;
if(isBeginOutput)
str += an1[i]+48;
}
if(!isBeginOutput)
str = "0";
outcome = str;
}
return outcome;
}
/*******************大数求幂******************/
string BigFigure::power(string &str1, string &str2)
{
int flag = 0;
string str = str1;
if(((str2[str2.size()-1]-48)%2 != 0)&&(str1[0]=='-'))
flag = 1;

if(str1 == "0")
{
outcome = "0";
return outcome;
}
if(str2 == "0")
{
outcome = "1";
return outcome;
}
while(str2 != "1")
{
str = multiplication(str, str1);
str2 = subtration(str2, "1");
}
if(flag){ str.insert(0,"-"); }
outcome = str;
return outcome;
}
/*******************输出函数******************/
void BigFigure::showResult()
{
cout << outcome << endl;
}

int main()
{
cout<<"\n\n";
cout<<" ***************************************************************************\n";
cout<<" * 欢迎使用大整数四则运算程序！！ *\n";
cout<<" * 请稍后 . . . *\n";
cout<<" ***************************************************************************\n\n";
Sleep(1500);
system("cls");
cout<<" ╭━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╮\n";
cout<<" ┃ ║使用说明║ ┃\n";
cout<<" ┃ 1. 输入形式为：A[空格或换行]OB。 ┃\n";
cout<<" ┃ 2. 1中A、B为大数，O为运算符如输入:(123456789 /246776787)。 ┃\n";
cout<<" ┃ 3. 可根据用户的需要适当修改大数上限 ┃\n";
cout<<" ┃ 5. 本程序也可以进行负数的加减乘除及幂运算。 ┃\n";
cout<<" ┃ 6. 用户输入“0 00”时退出程序。 ┃\n";
cout<<" ╰━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╯\n\n";
cout<<"运算开始：\n";
string str1;
string str2;
BigFigure a;
char operation;
while(cin >> str1 >> operation >> str2)
{
cout << "= ";
switch(operation)
{
case '+': a.addition(str1,str2); a.showResult();break;
case '-': a.subtration(str1,str2); a.showResult();break;
case '*': a.multiplication(str1,str2);a.showResult();break;
case '/': a.division(str1,str2); a.showResult();break;
case '%': a.remainder(str1,str2); a.showResult();break;
case '^': a.power(str1,str2); a.showResult();break;
case '0': cout<<"欢迎您的使用，安全退出。"<default : cout << "您输入的格式有误，请您重新输入！" << endl;
}
cout << endl;
}
return 0;
}