浅谈一下大数相除有关思路(图解)与用java代码具体解决方案
PS:接上篇大数相乘博客。两数的正负情况在这就不谈了,只要加一个标记就可以了。此文阅读前提:需在解决了大数相加减和大数相乘的基础上进行。
在完成了大数相乘的程序后,很自然地想到了在不使用javaAPI的情况下,如何实现两个数相除,两数可以是大数和小数的任意组合,如大数/大数,大数/小数。
思路图解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;
}
③panduan(String):boolean // 因为①②中包含了,所以在此解释一下
/*
大整数判断函数
*/
public static boolean panduan(String data) { // 判断data是否为0
int z=0,num=data.length(),count = 0;
while(num>=0) {
if(data.charAt(count)!=0) {
z++;
}
num--;
}
if(z==0) {
return true;
}else {
return false;
}
}
结束语:
自己的想法和代码如上,如果您觉得想法赞,或者对上述有不理解的地方,再或者有更好的想法,欢迎留言,大家相互交流提高。
分享到:
相关推荐
写了一个完整的大数相除,不是代码片段,可以完整的看明白,节省时间
java代码-使用java求辗转相除法分解质因数的源代码 ——学习参考资料:仅用于个人学习使用!
大数赋值、相加、相减、相乘、相除、求模与生成
两数相除(java代码).docx
利用辗转相除法求两个数的最大公约数。要求能接受用户的输入,输出最大公约数。 辗转相除法原理: 已知a,b,c为正整数,若a除以b余c,则(a,b)=(b,c),其中用(a,b)来表示a和b的最大公约数。(证明过程请参考其它...
c++编写的辗转相除法代码,可输入数字进行辗转相除运算(具有详细步骤),便于对辗转相除运算问题进行验证求解。
计算辗转相除辗转相除计算辗转相除计算辗转相除计算辗转相除计算辗转相除计算计算
辗转相除法,也称为欧几里德算法,是一种用于求解两个整数的最大公约数的方法。该算法基于以下原理:两个整数a和b的最大公约数等于b和a除以b的余数的最大公约数。通过反复应用这个原理,可以逐步缩小两个整数的范围...
辗转相除法证明辗转相除法证明辗转相除法证明辗转相除法证明
20位左右的大数相乘算法解析,用一个整型数组表示一个大数,数组的每个元素储存大数的一位数字,则实际的大数d表示为: d=a[k]*10的k-1次幂+a[k-1]*10的k-2次幂+......+a[2]*10+a[1] 其中a[0]保存该大数的位数. ...
面向公钥密码体系的大数相除快速算法
很古老的数学问题,文件里包含完整的工程文件..其实很简单,问题主要表现在算法里,希望对各位有用...
辗转相除法求最大公约
主要介绍了Java中使用辗转相除法求最大公约数,本文直接给出代码实例,需要的朋友可以参考下
C#中辗转相除法的多种实现方式,内有完整源码.rar
主要为大家详细介绍了C++使用string的大数除法运算,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
辗转相除(当然按二进制做),本代码不求完美,只是在学习过程中练习和学习一下,希望各位朋友们指点!
其中包括分解质因数,打印完数,企业利润分析,辗转相除法解决问题,猴子摘桃问题,乒乓球比赛等许多基础典型的题目,带你熟练java语法,入门java思维,作为一个由 c到java的一个过渡性学习。相信能够帮助到大家
这是基于java的求最大公约数,使用的是最节省内存的辗转相除法
辗转相除法求最大公约