首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

大数运算解决办法

2012-06-14 
大数运算#include iostream#includeString.husing namespace stdstruct Node// 定义一个双向链表用来

大数运算
#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);} 

热点排行