浅谈一下大数相除有关思路(图解)与用java代码具体解决方案
浅谈一下大数相除有关思路(图解)与用java代码具体解决方案??????? PS:接上篇大数相乘博客。两数的正负情况在这就不谈了,只要加一个标记就可以了。此文阅读前提:需在解决了大数相加减和大数相乘的基础上进行。 ??? 在完成了大数相乘的程序后,很自然地想到了在不使用java?API的情况下,如何实现两个数相除,两数可以是大数和小数的任意组合,如大数/大数,大数/小数。 ? 思路图解1:??? 刚开始想到的思路如下,以82/4为例 Step 1:? ? ???? 想出了这个想法后,跟老师说了一下,老师说想法不错,但是缺点也很明显,此算法只支持两个大数相除和两个小数相除,对于一个大数与一个小数的情况,不能得到解决。想了想,觉得老师说得很对。按照上面的图解,被除结果即是计算机进行机械重复运算的步数,那么如果重复的步数超出了java基本类型的表示范围,即重复的步数为一个大数,就不会有正确的结果。 ??? 回去想了一天,突然间想明白了,既然问题是:重复步数可能为大数问题,那么完全可以逆向思维啊,跳出大数的框架。中心思想:补零操作。结果用另一种思路的String表示就可以了。如82/4?=?20,我们可以先输出String?型2,再输出String型0,再用’+’把0放在2后面就可以了。 思路图解 2:以100?/?3为例(大数/小数方法相同,嘿嘿,偷懒以100和3为例): Step 2:Step 3:具体代码实现:做了两个类成员方法函数,分别为①chufa(String,String):String和②chu(String,String):String ①chufa(String,String):String? ? /* 大整数除法转换函数 */ public static String chufa(String data1,String data2) { int i = 0,j = 0,x = 0,y = 0; String jieguo = ""; if(data1.charAt(0) == '-') { data1 = data1.substring(1);//去掉大整数前面的负号 x++; } if(data2.charAt(0) == '-') { data2 = data2.substring(1);//去掉大整数前面的负号 y++; } while(data1.charAt(i)=='0' && i<data1.length()-1) { i++; } data1 = data1.substring(i);//去掉大整数前面的所有无效的数字0 while(j<data2.length()-1 && data2.charAt(j)=='0') { j++; } data2 = data2.substring(j); if( panduan(data2)) { System.out.println("除数不能为0,请重新输入!"); System.exit(-1); }else { jieguo = chu(data1,data2); if(x+y==1) { jieguo = "-" + jieguo; } } return jieguo; } ②chu(String,String):String? /* 高精度除法函数 */ public static String chu(String data1,String data2) { String jieguo = ""; int num = data1.length() - data2.length(); if (!compare(data2,data1)) { num = -1; } if (num < 0) { jieguo = "0"; } else if (panduan(jianfa(data1,data2))) { jieguo = "1"; } else { while (num >= 0) { while (data1.length() > data2.length()) { data2 = data2 + "0"; } if (!compare(data2,data1)) { data1 += "0"; } for (int i = 9; i > 0; i--) { if (compare(chengfa(data2,String.valueOf(i)),data1)) { data1 = jianfa(data1,chengfa(data2,String.valueOf(i)));// 减去已经除去的字符段 jieguo += i; i = 0; } if (i == 1) { jieguo += 0; } } num--; } } return jieguo; }
|