当简单的计算遇上了大数,其实大数运算也很简单

t3138011 8年前
   <h3><strong>一、说三道四</strong></h3>    <p>用代码实现简单的加减乘除运算会不会?只要你是个coder,我想这个答案都是肯定的吧!</p>    <p>但是,今天我想说的是,当我们的运算遇到了大数,用原本的int、long、float、double数值类型</p>    <p>都无法表示出来的时候,你们想过该如果解决这一类型的问题了吗?</p>    <p>在这,你们可以先不用看卤煮撸的代码,想想如果自己遇到这个问题,该如果解决,也许你的想法</p>    <p>很新颖,思路以及在算法的实现上更清晰。希望能够在广大的博友的集思广益下,大数的运算能够有</p>    <p>一套更好的解决方案。不说了,咱们先撸代码吧。毕竟这才是主题!!!</p>    <h3><strong>二、大数运算之加法运算</strong></h3>    <pre>  <code class="language-java">  package com.linjm.work;    public class Add {        public String forAdd(String p, String q) {          String x = p;          String y = q;                    int len = 0;          String res = "";                    len = (x.length() > y.length()) ? x.length() : y.length();                              if (len == x.length())    y = Tools.fillZero(y, x.length() - y.length());          if (len == y.length())    x = Tools.fillZero(x, y.length() - x.length());                    x = Tools.reverse(x);          y = Tools.reverse(y);                    //m,n用于循环遍历时截取字符串x,y的每一位          //flag用于标识m和n的每一次相加是否需要进位          int m, n, flag = 0;                    //遍历x、y,对应位相加          for (int i = 0; i < len; i++) {              int sum;                            m = Integer.parseInt(x.substring(i, i + 1));              n = Integer.parseInt(y.substring(i, i + 1));              sum = m + n;                            if (flag == 1) {                      sum = sum + 1;                  flag = 0;              }                            if (sum >= 10) {                  flag = 1;                  sum = sum - 10;              }                            res += sum;          }                    if (flag == 1)    //最高位相加后还大于10,则须进位              res += "1";                    return Tools.reverse(res);      }                        public static void main(String[] args) {          Add add = new Add();          System.out.println(add.forAdd("555555555555555555", "5555555555555555551"));      }  }    大数相加</code></pre>    <p>思路分析:</p>    <p>大数的相加主要是通过字符串的相加来实现的。两个大数相加,找出位数较大的那个大数获取对应的长度,</p>    <p>然后对较小的那个数进行左补0直至长度和较大的那个数的位数一样,最后循环累加两个大数的每一位的数值,</p>    <p>遇到需要进位的需要设一个标识位标识。</p>    <h3><strong>三、大数运算之减法运算</strong></h3>    <pre>  <code class="language-java">  package com.linjm.work;    public class Sub {            public String forSub(String p, String q) {          String x = p;          String y = q;                    int len = 0;          String res = "";                    int sign = 0;    //0: x >= y、1: x < y           sign = Tools.forMax(x, y) ? 0 : 1;                    if (sign == 1) {              x = q;              y = p;          }                    len = x.length();                    y = Tools.fillZero(y, x.length() - y.length());                    int m, n, flag = 0, num = 0;    //num标识出现0的次数,防止结果中高位出现多个0的情况                    for (int i = len; i > 0; i--) {              int dif;                            m = Integer.parseInt(x.substring(i - 1, i));              n = Integer.parseInt(y.substring(i - 1, i));                            dif = m - n;                            //标志位如果等于1,说明存在借位              if (flag == 1) {                  dif = dif - 1;                  flag = 0;    //重置标志位              }                            //判断是否需要借位              if (dif < 0) {                  flag = 1;    //标记                  dif = dif + 10;              }                            if (dif == 0) {                  num ++;              } else {                  num = 0;              }                            res += dif;          }                    if (Tools.isZero(res))              return "0";            if (num > 0) {              res = res.substring(0, res.length() - num);    //截取掉高位出现的连续num个0          }                    return (sign == 1) ? "-" + Tools.reverse(res) : Tools.reverse(res);      }                        public static void main(String[] args) {          Sub sub = new Sub();          System.out.println(sub.forSub("100000000", "1"));      }  }    大数相减</code></pre>    <p>思路分析:</p>    <p>大数相减在实现上和大数相加异曲同工,也是通过循环遍历大数的每一位,对其进行数值相减,在遇到需要借位的数值,</p>    <p>设立一个标识位进行标识。当遇到被减数比减数小的时候,先用减数减去被减数,用标识位标识被减数比减数小,最后结果</p>    <p>根据标识变量判断是否需要在结果上加上"-"。</p>    <h3><strong>四、大数运算之乘法运算</strong></h3>    <pre>  <code class="language-java">  package com.linjm.work;    public class Mul {        public String forMul(String p, String q) {          String x = Tools.maxNum(p, q);          String y = Tools.minNum(p, q);                    if (y.length() > 15) {              return "ERROR:两位数中必须有一个数的长度要小于15";          }                        String sum = "0";                    Add add = new Add();          Sub sub = new Sub();                    while (Long.parseLong(y) > 0) {              sum = add.forAdd(sum, x);              y = sub.forSub(y, "1");          }                    return sum;      }                        public static void main(String[] args) {          Mul mul = new Mul();          System.out.println(mul.forMul("1000", "20000"));      }  }    大数相乘</code></pre>    <p>思路分析:</p>    <p>大数相乘在算法的实现上个人表示有点不太满意,虽然实现了功能,但还是觉得代码的实现上和思路都很挫。</p>    <p>乘法的最终思路就是多个数值的加法运算。所以大数的乘法就是多个大数的加法运算。但是遇到两个数值都是大数的情况下,</p>    <p>运行速度会非常的慢。</p>    <h3><strong>五、大数运算之除法运算</strong></h3>    <pre>  <code class="language-java">  package com.linjm.work;    public class Div {        public String forDiv (String p, String q) {          String x = p;          String y = q;                    String res = "0";          String remain = "0";    //余数                    if (!Tools.forMax(x, y)) {              return x + "的值要大等于" + y;           }                    Add add = new Add();          Sub sub = new Sub();                    while (true) {              x = sub.forSub(x, y);              res = add.forAdd(res, "1");                            if (!Tools.forMax(x, y)) {                  remain = x;                  break;              }          }                    if (!Tools.isZero(remain))              res = res + "……" +remain;                    return res;      }                        public static void main(String[] args) {          Div div = new Div();          System.out.println(div.forDiv("222222222222222222222", "222222222222222222221"));      }  }    大数相除</code></pre>    <p>思路分析:</p>    <p>除法运算的实质也就是减法,让被除数一直减去除数,直到减不动了为止,统计下减了多少次除数,这个值就是商咯。</p>    <p>但是存在的问题还是和大数的乘法是一样的,有待优化。</p>    <h3><strong>六、大数运算之工具类</strong></h3>    <pre>  <code class="language-java">  package com.linjm.work;    public class Tools {        /**       * @param s num       * @Desc 字符串左补num个0       * @return String       * */      public static String fillZero(String s, int num) {          String res = "";                    for (int i = 0; i < num; i++) {              res += "0";          }                    return res + s;      }            /**       * @param s       * @Desc 反转字符串       * @return String       * */      public static String reverse(String s) {          String res = "";                    for (int i = s.length(); i > 0 ; i--) {              res +=  s.substring(i - 1, i);          }                    return res;      }            /**       * @param x n(n最小值为1)       * @Desc 获取字符串的n个字符       * @return int       * */      public static int numAt(String x, int n) {          return Integer.parseInt(x.substring(n - 1, n));      }                  /**       * @param x y       * @Desc 获取两个大数中较大的数       *     注:此方法不对两个数是否是数字进行校验       * @return String       * */      public static String maxNum(String x, String y) {          String max = "";                    if (x.length() > y.length()) {              max = x;          } else if (x.length() == y.length()) {              for (int i = 1; i <= x.length(); i++) {                  if (numAt(x, i) != numAt(y, i)) {                      max = (numAt(x, i) > numAt(y, i)) ? x : y;                  } else if (i == x.length()) {                      max = x;                  }              }          } else if (x.length() < y.length()) {              max = y;          } else {              return "ERROR";          }          return max;      }                  /**       * @param x y       * @Desc 获取两个大数中较小的数       *     注:此方法不对两个数是否是数字进行校验       * @return String       * */      public static String minNum(String x, String y) {          String min = "";                    if (x.length() > y.length()) {              min = y;          } else if (x.length() == y.length()) {              for (int i = 1; i <= x.length(); i++) {                  if (numAt(x, i) != numAt(y, i)) {                      min = (numAt(x, i) > numAt(y, i)) ? y : x;                  } else if (i == x.length()) {                      min = x;                  }              }          } else if (x.length() < y.length()) {              min = x;          } else {              return "ERROR";          }          return min;      }                  /**       * @param x y       * @Desc 大数x是否大于大数y       * @return true/false       * */      public static boolean forMax(String x, String y) {          if (x.length() > y.length()) {              return true;          } else if (x.length() == y.length()) {              for (int i = 1; i <= x.length(); i++) {                  if (numAt(x, i) != numAt(y, i)) {                      return (numAt(x, i) > numAt(y, i)) ? true : false;                  } else if (i == x.length()) {                      return true;                  }              }          } else if (x.length() < y.length()) {              return false;          } else {              System.out.println("ERROR!!!");          }          return false;      }                        /**       * @param x       * @Desc 判断x是否是0或000……       * @return true/false       * */      public static boolean isZero(String x) {          boolean flag = true;                    for (int i = 1; i <= x.length(); i++) {              if (Tools.numAt(x, i) != 0) {                  return false;              }          }                    return flag;      }        }    工具类</code></pre>    <h3><strong>七、卤煮有话说</strong></h3>    <p>算法的实现上可以会多多少少存在点瑕疵,第一遍写出来的代码不是最好的,但我们要尽我们所能去优化和改善我们的代码。</p>    <p>大家有什么想法都可以说出来,我们一起来探讨大数的加减乘除,这样让这么有意义的事可以得到最后的解决方案。</p>    <p>想是一回事,做又是另一回事。让我们脑洞大开,集思广益一起来探讨吧!!!</p>    <p>如果你觉得博文写的不错,就点下【 推荐一下 】或【 打赏 】 卤煮一杯奶茶吧!!!</p>    <p> </p>    <p>来自:http://www.cnblogs.com/JimLy-BUG/p/5965487.html</p>    <p> </p>