现在的位置: 首页 > 综合 > 正文

大数/高精度加减乘除取模[收藏]

2013年12月02日 ⁄ 综合 ⁄ 共 7288字 ⁄ 字号 小 中 大 ⁄ 评论关闭
Cpp代码
  1. #include <iostream>   
  2. #include <string>   
  3. using namespace std;   
  4.   
  5. inline int compare(string str1, string str2)   
  6. {   
  7.       if(str1.size() > str2.size()) //长度长的整数大于长度小的整数   
  8.             return 1;   
  9.       else if(str1.size() < str2.size())   
  10.             return -1;   
  11.       else  
  12.             return str1.compare(str2); //若长度相等，从头到尾按位比较，compare函数：相等返回0，大于返回1，小于返回－1   
  13. }   
  14. //高精度加法   
  15. string ADD_INT(string str1, string str2)   
  16. {   
  17.       string MINUS_INT(string str1, string str2);   
  18.       int sign = 1; //sign 为符号位   
  19.       string str;   
  20.       if(str1[0] == '-') {   
  21.            if(str2[0] == '-') {   
  22.                  sign = -1;   
  23.                  str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));   
  24.            }else {   
  25.                  str = MINUS_INT(str2, str1.erase(0, 1));   
  26.            }   
  27.       }else {   
  28.            if(str2[0] == '-')   
  29.                  str = MINUS_INT(str1, str2.erase(0, 1));   
  30.            else {   
  31.                  //把两个整数对齐，短整数前面加0补齐   
  32.                  string::size_type l1, l2;   
  33.                  int i;   
  34.                  l1 = str1.size(); l2 = str2.size();   
  35.                  if(l1 < l2) {   
  36.                        for(i = 1; i <= l2 - l1; i++)   
  37.                        str1 = "0" + str1;   
  38.                  }else {   
  39.                        for(i = 1; i <= l1 - l2; i++)   
  40.                        str2 = "0" + str2;   
  41.                  }   
  42.                  int int1 = 0, int2 = 0; //int2 记录进位   
  43.                  for(i = str1.size() - 1; i >= 0; i--) {   
  44.                        int1 = (int(str1[i]) - 48 + int(str2[i]) - 48 + int2) % 10;  //48 为 '0' 的ASCII 码   
  45.                        int2 = (int(str1[i]) - 48 + int(str2[i]) - 48 +int2) / 10;   
  46.                        str = char(int1 + 48) + str;   
  47.                  }   
  48.                  if(int2 != 0) str = char(int2 + 48) + str;   
  49.           }   
  50.      }   
  51.      //运算后处理符号位   
  52.      if((sign == -1) && (str[0] != '0'))   
  53.           str = "-" + str;   
  54.      return str;   
  55. }   
  56.   
  57.   
  58. //高精度减法   
  59. string MINUS_INT(string str1, string str2)   
  60. {   
  61.      string MULTIPLY_INT(string str1, string str2);   
  62.      int sign = 1; //sign 为符号位   
  63.      string str;   
  64.      if(str2[0] == '-')   
  65.             str = ADD_INT(str1, str2.erase(0, 1));   
  66.      else {   
  67.             int res = compare(str1, str2);   
  68.             if(res == 0) return "0";   
  69.             if(res < 0) {   
  70.                   sign = -1;   
  71.                   string temp = str1;   
  72.                   str1 = str2;   
  73.                   str2 = temp;   
  74.             }   
  75.             string::size_type tempint;   
  76.             tempint = str1.size() - str2.size();   
  77.             for(int i = str2.size() - 1; i >= 0; i--) {   
  78.                  if(str1[i + tempint] < str2[i]) {   
  79.                        str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1);   
  80.                        str = char(str1[i + tempint] - str2[i] + 58) + str;   
  81.                  }   
  82.                  else  
  83.                        str = char(str1[i + tempint] - str2[i] + 48) + str;   
  84.             }   
  85.            for(iint  i = tempint - 1; i >= 0; i--)   
  86.                 str = str1[i] + str;   
  87.      }   
  88.      //去除结果中多余的前导0   
  89.      str.erase(0, str.find_first_not_of('0'));   
  90.      if(str.empty()) str = "0";   
  91.      if((sign == -1) && (str[0] != '0'))   
  92.           str = "-" + str;   
  93.      return str;   
  94. }   
  95.   
  96. //高精度乘法   
  97. string MULTIPLY_INT(string str1, string str2)   
  98. {   
  99.      int sign = 1; //sign 为符号位   
  100.      string str;   
  101.      if(str1[0] == '-') {   
  102.            sign *= -1;   
  103.            str1 = str1.erase(0, 1);   
  104.      }   
  105.      if(str2[0] == '-') {   
  106.            sign *= -1;   
  107.            str2 = str2.erase(0, 1);   
  108.      }   
  109.      int i, j;   
  110.      string::size_type l1, l2;   
  111.      l1 = str1.size(); l2 = str2.size();   
  112.      for(i = l2 - 1; i >= 0; i --) {  //实现手工乘法   
  113.            string tempstr;   
  114.            int int1 = 0, int2 = 0, int3 = int(str2[i]) - 48;   
  115.            if(int3 != 0) {   
  116.                   for(j = 1; j <= (int)(l2 - 1 - i); j++)   
  117.                         tempstr = "0" + tempstr;   
  118.                   for(j = l1 - 1; j >= 0; j--) {   
  119.                         int1 = (int3 * (int(str1[j]) - 48) + int2) % 10;   
  120.                         int2 = (int3 * (int(str1[j]) - 48) + int2) / 10;   
  121.                         tempstr = char(int1 + 48) + tempstr;   
  122.                   }   
  123.                   if(int2 != 0) tempstr = char(int2 + 48) + tempstr;   
  124.            }   
  125.            str = ADD_INT(str, tempstr);   
  126.      }   
  127.      //去除结果中的前导0   
  128.      str.erase(0, str.find_first_not_of('0'));   
  129.      if(str.empty()) str = "0";   
  130.      if((sign == -1) && (str[0] != '0'))   
  131.            str = "-" + str;   
  132.      return str;   
  133. }   
  134. //高精度除法   
  135. string DIVIDE_INT(string str1, string str2, int flag)   
  136. {   
  137.      //flag = 1时,返回商; flag = 0时,返回余数   
  138.      string quotient, residue; //定义商和余数   
  139.      int sign1 = 1, sign2 = 1;   
  140.      if(str2 == "0") {  //判断除数是否为0   
  141.            quotient = "ERROR!";   
  142.            residue = "ERROR!";   
  143.            if(flag == 1) return quotient;   
  144.            else return residue;   
  145.      }   
  146.      if(str1 == "0") { //判断被除数是否为0   
  147.            quotient = "0";   
  148.            residue = "0";   
  149.      }   
  150.      if(str1[0] == '-') {   
  151.            str1 = str1.erase(0, 1);   
  152.            sign1 *= -1;   
  153.            sign2 = -1;   
  154.      }   
  155.      if(str2[0] == '-') {   
  156.            str2 = str2.erase(0, 1);   
  157.            sign1 *= -1;   
  158.      }   
  159.      int res = compare(str1, str2);   
  160.      if(res < 0) {   
  161.            quotient = "0";   
  162.            residue = str1;   
  163.      }else if(res == 0) {   
  164.            quotient = "1";   
  165.            residue = "0";   
  166.      }else {   
  167.            string::size_type l1, l2;   
  168.            l1 = str1.size(); l2 = str2.size();   
  169.            string tempstr;   
  170.            tempstr.append(str1, 0, l2 - 1);   
  171.            //模拟手工除法   
  172.            for(int i = l2 - 1; i < l1; i++) {   
  173.                  tempstr = tempstr + str1[i];   
  174.                  for(char ch = '9'; ch >= '0'; ch --) { //试商   
  175.                        string str;   
  176.                        str = str + ch;   
  177.                        if(compare(MULTIPLY_INT(str2, str), tempstr) <= 0) {   
  178.                               quotient = quotient + ch;   
  179.                               tempstr = MINUS_INT(tempstr, MULTIPLY_INT(str2, str));   
  180.                               break;   
  181.                        }   
  182.                  }   
  183.            }   
  184.            residue = tempstr;   
  185.      }   
  186.      //去除结果中的前导0   
  187.      quotient.erase(0, quotient.find_first_not_of('0'));   
  188.      if(quotient.empty()) quotient = "0";   
  189.      if((sign1 == -1) && (quotient[0] != '0'))   
  190.      quotient = "-" + quotient;   
  191.      if((sign2 == -1) && (residue[0] != '0'))   
  192.      residue = "-" + residue;   
  193.      if(flag == 1) return quotient;   
  194.      else return residue;   
  195. }   
  196.   
  197. //高精度除法,返回商   
  198. string DIV_INT(string str1, string str2)   
  199. {   
  200.       return DIVIDE_INT(str1, str2, 1);   
  201. }   
  202. //高精度除法,返回余数   
  203. string MOD_INT(string str1, string str2)   
  204. {   
  205.       return DIVIDE_INT(str1, str2, 0);   
  206. }   
  207.                      
  208. int main()   
  209. {   
  210.       char ch;   
  211.       string s1, s2, res;   
  212.       while(cin >> ch) {   
  213.            cin >> s1 >> s2;   
  214.            switch(ch) {   
  215.                 case '+':  res = ADD_INT(s1, s2); break;   //高精度加法   
  216.                 case '-':  res = MINUS_INT(s1, s2); break; //高精度减法   
  217.                 case '*':  res = MULTIPLY_INT(s1, s2); break; //高精度乘法   
  218.                 case '/':  res = DIV_INT(s1, s2); break; //高精度除法, 返回商   
  219.                 case 'm':  res = MOD_INT(s1, s2); break; //高精度除法, 返回余数   
  220.                 default :  break;   
  221.            }   
  222.            cout << res << endl;   
  223.       }   
  224.       return(0);   
  225. }  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞