大数运算
#include <iostream>
#include<String.h>
using namespace std;
struct Node // 定义一个双向链表用来存贮结果
{
char data; // 数据*定义为字符的原因：要显示负号
Node *next; // 尾指针
Node *ahead; // 首指针
};
char *findend(char *numa)
{
numa+=strlen(numa);
return numa;
}
//返回值说明:0是alongblong ; 2是along=blong
int abigerb(char *numa, char *numb) //比较两个数最高位那一个大
{
int along=(int)strlen(numa); //标记数字a的长度；
int blong=(int)strlen(numb); //标记数字b的长度；
char *pna = numa; //指向数A的最高位，
char *pnb = numb; //指向数B的最高位，
if (along>blong) return 1;
if (along==blong)
{
while(*pna) //比较两个数那一个大
{
if(*pna>*pnb)return 1;
else if(*pna<*pnb)return 0 ;
else if(*pna==*pnb){pna++;pnb++;} //1111与1112
}
return 2; //这表明找到最后了还是全相等;
}
return 0 ;
}
//大数乘法
void multiply(char *numa, char *numb ,char *result)//用来储结果的)//计算乘积
{
char *pna = findend(numa);//指向numa的一个指针。point numa pna 指向乘数的最低位，
char *pnb = findend(numb);//指向numb的一个指针 //pnb 指向被乘数的最低位，
int along=(int)strlen(numa);//标记数字a的长度；
int blong=(int)strlen(numb);//标记数字b的长度；
int carry=0,temp_result;//存贮进位 和临时结果的
Node *head, // 用于存贮头指针
*pstart, // 用于存贮计算时的首指针
*pnew, //作于申请新结点
*pgo; //作为每计算完一行时，回到下一行起始节点用,移位标致来用
head = pstart =new Node;//初始化首结点和头结点。
pstart -> data = 0;
pstart -> next = NULL;
pstart -> ahead = NULL;
while (along--)
{
pgo = pstart;//保存进位点
blong = (int)strlen(numb);//初始化长度
pnb = findend(numb); //初始化指针
while ((blong-- && (blong>=0))|| carry != 0)
{ if(!pstart->next)//如果当前为空结点，则申请新结点
{ pnew = new Node;
pnew -> data = 0;
pnew -> next = NULL;
pnew -> ahead = pstart;
pstart -> next = pnew;
}
if(blong<0)temp_result = carry ;//处理只有进位的情况
else temp_result =(pstart->data+(*pna-48)*(*pnb-48)+carry);//自身值+新值+进位作为新值
pstart -> data = temp_result%10; //存贮个位
carry = temp_result/10; //存贮进位
pstart = pstart -> next; //结点移动
pnb--; //指针移向被乘数高位
}
pstart = pgo->next; //前进一个位置；
pna--; //指针移向乘数高位
}
pstart =head;//寻找链表的结尾点
while(pstart->next != 0)
{
pstart->data += 48;//!!<<<因为我们的输出是字符。所以再此加上48>>>> 逆顺输出
pstart = pstart->next ; }
int tip = 0;//转为字符串用
pstart = pstart->ahead ;//找有效字
while(pstart != 0)//输出正序的结果；
{
result[tip++] = pstart->data;
pstart = pstart->ahead ;
}
result[tip] = '\0';
pstart =head; //释放空间
while(pstart->next != 0)
{
pnew = pstart->next ;
delete pstart;
pstart =pnew;
}
return ;
}
//大数减法
void subtract(char *numa, char *numb,char *result)//计算减
{ char *pna = findend(numa);//指向numa的一个指针。point numa pna 指向减数的最低位，
char *pnb = findend(numb);//指向numb的一个指针 //pnb 指向被减数的最低位，
int along=(int)strlen(numa);//标记数字a的长度；
int blong=(int)strlen(numb);//标记数字b的长度；
int times = 0; // 标记要计算多少次。
int carry=0; //存贮借位
int clear0=0; //消除结果最前面无用的'0' 13-5 = 08 的效果！！
int isnegative=0; //用来加上被减数大于减数时补上最后一个负号
Node *head, // 用于存贮头指针
*pstart, // 用于存贮计算时的首指针
*pnew; //作于申请新结点
head = pstart =new Node;//初始化首结点和头结点。
pstart -> data = 0;
pstart -> next = NULL; pstart -> ahead = NULL;
if (abigerb(numa ,numb))
times = strlen(numa);//比较两个字符串长度，以大的作为循环次数
else //交换位置以降低难度
{
times = strlen(numb);//让数（字符串）长的减去数（字符串）短的
pna = findend(numb);//交换指针
pnb = findend(numa);
along=(int)strlen(numb);//标记数字a的长度；
blong=(int)strlen(numa);//标记数字b的长度；
isnegative=1;//标记最后要加上负号
}
while ((times-- && (times>=0))|| carry != 0)//carry != 0 说没有借位时
{
if(!pstart->next)//如果当前为空结点，则申请新结点
{ pnew = new Node;
pnew -> data = 0;
pnew -> next = NULL;
pnew -> ahead = pstart;
pstart -> next = pnew;
}
if(times<0)//如果计算完之后，借位等于1，，说明必然为负值;
{ pstart -> data = -3 ;//让它等于负号 '-'//-3来源于负号与0相差3。。
break; }
else
{
if ( *pna == *pnb )//减数等于被减数时。结果等于直截相减的结果；并置借位为0
{
if(carry==0)pstart -> data = (*pna-48)-(*pnb-48); //111-11的情况
else
{
pstart->data = (*pna-48)-(*pnb-48)+10 -carry;//1121-1112
carry=1;
}
}
if( *pna > *pnb )//减数大于被减数时。结果等于直截相减的结果；并置借位为0
{
pstart -> data = (*pna-48)-(*pnb-48)-carry; //存贮个位
carry=0;
}
else if( *pna < *pnb )//说明被减数大于减数，让结果加10，相当于借位 (carry)为1
{
if(times>0)
pstart->data = (*pna-48)-(*pnb-48)+10 -carry;//13-5的情况作为新值
else
pstart->data = (*pnb-48)-(*pna-48) -carry; //3-5 作为当前的新值
carry=1;
}
}
pstart = pstart -> next; //结点移动
blong--;
if(blong>0)pnb--;//指针移向被减数高位
else *pnb=48;//之后相减就变为了0不作任何运算，其实可以优化的。但代码会长！而且还需要重新开结点。所以放弃；
pna--;//被数指针移动，
}
if(isnegative==1)////加上负号处理。增加一长度并置为负号
{ pnew = new Node;
pnew -> data = 0;
pnew -> next = NULL;
pnew -> ahead = pstart;
pstart -> next = pnew;
pstart->data=-3;//因为寻找链表的结尾点要统一加48。又因为‘-’是45。所以等于‘-3’
}
pstart =head;//寻找链表的结尾点
while(pstart->next != 0)
{ pstart->data += 48;//!!<<<因为我们的输出是字符。所以再此加上48>>>> 逆顺输出
pstart = pstart->next ;
}
int tip = 0;//转为字符串用
clear0=0;// 消除结果最前面无用的'0' 13-5 = 08 的效果 ..>>修改字符串的首指针
pstart = pstart->ahead ;//找有效字 while(pstart != 0)//输出正序的结果；
{
if (clear0==0 && ((int)pstart->data)==48&&pstart->ahead!=0);// 消除结果最前面无用的'0'
//不输出任何东西
else
result[tip++] = pstart->data;
if(((int)pstart->data)!=48&&((int)pstart->data)!=45)
clear0=1;//'－'号
pstart = pstart->ahead ;
}
result[tip] = '\0';
pstart =head; //释放空间
while(pstart->next != 0)
{
pnew = pstart->next ;
delete pstart; pstart =pnew;
}
return ;
}
void power (char *numa, char *numb,char *result) //计算幂
{
char one[]="1"; //临时字符串....
char one2[]="1";
char zero[]="0";
char numb2[6048];
char remainder[6048];
strcpy(result,one); //给结果初值为1
strcpy(numb2,numb);
subtract(numb,one ,remainder); //B自减1
strcpy(numb,numb2);
strcpy(numb2,numb);
multiply(result,numa,result ); //A自己乘自己
strcpy(numb,numb2);
while(strcmp(remainder,zero)>0) //A大于相等B时 就是numb不等于0时
{
strcpy(numb2,numb);
multiply(result,numa,result ); //A自己乘自己
strcpy(numb,numb2);
strcpy(one,one2);
subtract(remainder,one ,remainder); //B减一
}
return ;
}
int main()
{
char a[20];
char b[20];
char c[40];
gets(a);
gets(b);
subtract(a,b,c);
cout<<"a-b="<<c<<endl;
multiply(a,b,c);
cout<<"a*b="<<c<<endl;
power(a,b,c);
cout<<"a^b="<<c<<endl;
return 0;
}
为什么测试结果不对？是不是char *findend(char *numa) 有问题
[解决办法]
仅供参考
- C/C++ code
#include <iostream>#include <string>using namespace std;inline int compare(string str1, string str2) { if(str1.size() > str2.size()) //长度长的整数大于长度小的整数 return 1; else if(str1.size() < str2.size()) return -1; else return str1.compare(str2); //若长度相等，从头到尾按位比较，compare函数：相等返回0，大于返回1，小于返回－1}string ADD_INT(string str1, string str2) {//高精度加法 string SUB_INT(string str1, string str2); int sign = 1; //sign 为符号位 string str; if(str1[0] == '-') { if(str2[0] == '-') { sign = -1; str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1)); } else { str = SUB_INT(str2, str1.erase(0, 1)); } } else { if(str2[0] == '-') str = SUB_INT(str1, str2.erase(0, 1)); else { //把两个整数对齐，短整数前面加0补齐 string::size_type l1, l2; int i; l1 = str1.size(); l2 = str2.size(); if(l1 < l2) { for(i = 1; i <= l2 - l1; i++) str1 = "0" + str1; } else { for(i = 1; i <= l1 - l2; i++) str2 = "0" + str2; } int int1 = 0, int2 = 0; //int2 记录进位 for(i = str1.size() - 1; i >= 0; i--) { int1 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) % 10; int2 = (int(str1[i]) - '0' + int(str2[i]) - '0' +int2) / 10; str = char(int1 + '0') + str; } if(int2 != 0) str = char(int2 + '0') + str; } } //运算后处理符号位 if((sign == -1) && (str[0] != '0')) str = "-" + str; return str;}string SUB_INT(string str1, string str2) {//高精度减法 string MUL_INT(string str1, string str2); int sign = 1; //sign 为符号位 string str; int i; if(str2[0] == '-') str = ADD_INT(str1, str2.erase(0, 1)); else { int res = compare(str1, str2); if(res == 0) return "0"; if(res < 0) { sign = -1; string temp = str1; str1 = str2; str2 = temp; } string::size_type tempint; tempint = str1.size() - str2.size(); for(i = str2.size() - 1; i >= 0; i--) { if(str1[i + tempint] < str2[i]) { str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1); str = char(str1[i + tempint] - str2[i] + ':') + str; } else str = char(str1[i + tempint] - str2[i] + '0') + str; } for(i = tempint - 1; i >= 0; i--) str = str1[i] + str; } //去除结果中多余的前导0 str.erase(0, str.find_first_not_of('0')); if(str.empty()) str = "0"; if((sign == -1) && (str[0] != '0')) str = "-" + str; return str;}string MUL_INT(string str1, string str2) {//高精度乘法 int sign = 1; //sign 为符号位 string str; if(str1[0] == '-') { sign *= -1; str1 = str1.erase(0, 1); } if(str2[0] == '-') { sign *= -1; str2 = str2.erase(0, 1); } int i, j; string::size_type l1, l2; l1 = str1.size(); l2 = str2.size(); for(i = l2 - 1; i >= 0; i --) { //实现手工乘法 string tempstr; int int1 = 0, int2 = 0, int3 = int(str2[i]) - '0'; if(int3 != 0) { for(j = 1; j <= (int)(l2 - 1 - i); j++) tempstr = "0" + tempstr; for(j = l1 - 1; j >= 0; j--) { int1 = (int3 * (int(str1[j]) - '0') + int2) % 10; int2 = (int3 * (int(str1[j]) - '0') + int2) / 10; tempstr = char(int1 + '0') + tempstr; } if(int2 != 0) tempstr = char(int2 + '0') + tempstr; } str = ADD_INT(str, tempstr); } //去除结果中的前导0 str.erase(0, str.find_first_not_of('0')); if(str.empty()) str = "0"; if((sign == -1) && (str[0] != '0')) str = "-" + str; return str;}string DIVIDE_INT(string str1, string str2, int flag) {//高精度除法 //flag = 1时,返回商; flag = 0时,返回余数 string quotient, residue; //定义商和余数 int sign1 = 1, sign2 = 1; if(str2 == "0") { //判断除数是否为0 quotient = "ERROR!"; residue = "ERROR!"; if(flag == 1) return quotient; else return residue; } if(str1 == "0") { //判断被除数是否为0 quotient = "0"; residue = "0"; } if(str1[0] == '-') { str1 = str1.erase(0, 1); sign1 *= -1; sign2 = -1; } if(str2[0] == '-') { str2 = str2.erase(0, 1); sign1 *= -1; } int res = compare(str1, str2); if(res < 0) { quotient = "0"; residue = str1; } else if(res == 0) { quotient = "1"; residue = "0"; } else { string::size_type l1, l2; l1 = str1.size(); l2 = str2.size(); string tempstr; tempstr.append(str1, 0, l2 - 1); //模拟手工除法 for(int i = l2 - 1; i < l1; i++) { tempstr = tempstr + str1[i]; tempstr.erase(0, tempstr.find_first_not_of('0'));//zhao4zhong1添加 if(tempstr.empty()) tempstr = "0";//zhao4zhong1添加 for(char ch = '9'; ch >= '0'; ch --) { //试商 string str; str = str + ch; if(compare(MUL_INT(str2, str), tempstr) <= 0) { quotient = quotient + ch; tempstr = SUB_INT(tempstr, MUL_INT(str2, str)); break; } } } residue = tempstr; } //去除结果中的前导0 quotient.erase(0, quotient.find_first_not_of('0')); if(quotient.empty()) quotient = "0"; if((sign1 == -1) && (quotient[0] != '0')) quotient = "-" + quotient; if((sign2 == -1) && (residue[0] != '0')) residue = "-" + residue; if(flag == 1) return quotient; else return residue;}string DIV_INT(string str1, string str2) {//高精度除法,返回商 return DIVIDE_INT(str1, str2, 1);}string MOD_INT(string str1, string str2) {//高精度除法,返回余数 return DIVIDE_INT(str1, str2, 0);}int main() { char ch; string s1, s2, res; while(cin >> ch) { cin >> s1 >> s2; switch(ch) { case '+': res = ADD_INT(s1, s2); break; case '-': res = SUB_INT(s1, s2); break; case '*': res = MUL_INT(s1, s2); break; case '/': res = DIV_INT(s1, s2); break; case '%': res = MOD_INT(s1, s2); break; default : break; } cout << res << endl; } return(0);}