算法————大数减法，大数除法
算法————大数减法，大数除法
文章目录
- 算法————大数减法，大数除法
- 一.前言
- 二.前置函数
- 1.置后函数
- 2.输出函数
- 3.比较函数
- 三.大数减法
- 1.思想
- 2.代码实现
- 3.包装
- 四.大数除法
- 1.思想
- 2.代码实现
- 3.减法的改动
一.前言
在之间的时候，写了另一篇大数相关的算法：，后来一直忙于其他事，没有继续写大数其他的算法，现在就来看看大数其他算法的实现。
在之前的数据结构相关的博客里，一直都是用c语言实现的，现在处于面试已经方面的考虑，之后算法的实现都改为java。
二.前置函数
1.置后函数
作用：将数字字符串改为数组，并将字符串放在数组尾部。这样做是方便减法和除法的处理。
例:将"123456",8–>00’1’‘2’‘3’‘4’‘5’‘6’.
/*** 置后函数* @param str 需要置后的字符串* @param n 申请单数组空间大小* @return 置后的数组*/public static char[] postpone(String str,int n) { char[] a = new char[n];int al = str.length();for (int i = 0; i < al; i++) {a[n - al + i] = str.charAt(i);}return a;}
2.输出函数
作用：将存放结果的数组，去掉前面多余的’0’和0,并将结果转换成字符串。
例：00’1’‘2’‘3’‘4’‘5’‘6’–>“123456”.
/*** 转换函数* @param a 需要输出的数组* @return*/public static String eliminate(char a[]) { int n = a.length;StringBuilder sb = new StringBuilder();int i;for (i = 0; (a[i] == 0 || a[i] == '0') && i < n; i++) {}for (; i < n; i++) {sb.append(a[i]);}return sb.toString();}
3.比较函数
作用：比较数字字符串a，b的大小
返回：a>b–>1 ,a==b–>0,a< b–>-1
/*** 比较函数* @param a* @param b* @return*/public static int compare(String a, String b) { //比较两个数的大小if (a.length() > b.length()) {return 1;} else if (a.length() < b.length()) {return -1;} else {for (int i = 0; i < a.length(); i++) {if (a.charAt(i) > b.charAt(i)) {return 1;} else if (a.charAt(i) < b.charAt(i)) {return -1;}}}return 0;}
三.大数减法
1.思想
大数减法的思想和加法类似。只不过在计算前，先比较两个数的大小，保证是大数减小数。
在具体减的过程中，要考虑借位的情况，就是模拟具体的手工减法的过程。
例 193 - 79 （c存储结果，f表示借位）
1.0 f = 0
1.1 num = 3 - 9 + 0 = -6
1.2 c[3] =-6+10 = 4,f = -1
2.0 f = -1
2.1 num = 9 - 7 + -1=1
2.2 c[2] = 1,f=0
3.0 f = 0
3.1 num = 1-0+0 =1
3.2 c[1] = 1,f=0
结果：114
2.代码实现
/*** 大数 - 小数 （a - b = c）* @param a 被减数和减数中大者* @param b 被减数和减数中小者* @param n 申请单数字长度* @param c 存放结果的数组*/private static void subtraction(char a[], char b[],int n, char c[]) {int num, fi = 0;for (int i = n - 1; a[i] != 0 || b[i] != 0 || fi != 0; i--) {a[i] = a[i] == 0 ? '0' : a[i];b[i] = b[i] == 0 ? '0' : b[i];num = (a[i] - '0') - (b[i] - '0') + fi;//System.out.println("i=" + i + " a[i]=" + a[i] + " b[i]=" + b[i] + " fi =" + fi + " num=" + num);if (num >= 0) {c[i] = (char) (num + '0');fi = 0;} else {c[i] = (char) (num + 10 + '0');fi = -1;}}}
3.包装
处理小数 - 大数，以及字符串和数组之间的转换
/*** 减法* @param a 减数* @param b 被减数* @return 商*/
public static String subtraction(String a, String b) {int alen = a.length();int blen = b.length();int n = alen > blen ? alen + 2 : blen + 2;int result = compare(a, b);if (result == 0) {return "0";} else if (result == 1) {char[] c = new char[n];subtraction(Util.postpone(a,n), Util.postpone(b,n),n,c); //转换并调用上面的函数return Util.eliminate(c); //转换结果}else {char[] c = new char[n];subtraction(Util.postpone(b,n), Util.postpone(a,n),n,c); //转换并调用上面的函数return "-"+Util.eliminate(c);//转换结果}}
四.大数除法
1.思想
大数减法的思想也很简单，就是不停的调用减法，每成功减一次，就对商+1.
但时间成本有些太高，比如9999/1,就要进行9999次除法。所以进行改进。
9999 先减1000，减9次，结果为999，再减100，减9次，直到最后减9次1.计算出结果。
例：
9876/ 1000 = 9
876 /100 = 8
76 /10 = 7
6 /1 = 6
最终的结果：9876
2.代码实现
这个在调用减法是对上面减法的改进，当被减数 < 减数时返回0
public static String division(String a, String b) {int alen = a.length();int blen = b.length();int n = alen > blen ? alen + 2 : blen + 2;if(b.equals("0")){return "除0错误";}char[] result = new char[alen - blen+1];for (int i= 0 ;i<alen-blen+1;i++){StringBuilder c = new StringBuilder(b);for (int j = i; j < alen-blen; j++) {c.append('0');}int num = 0;while (Util.compare(a,c.toString())>=0){a = subtraction(a,c.toString()); //调用减法num++;}result[i]= (char) (num+'0');//System.out.println("a = "+a+" b="+b+" c="+c +" num="+num +" result="+ new String(result));}return Util.eliminate(result);}
3.减法的改动
public static String subtraction(String a, String b) {int alen = a.length();int blen = b.length();int n = alen > blen ? alen + 2 : blen + 2;int result = Util.compare(a, b);if (result == 0) {return "0";} else if (result == 1) {char[] c = new char[n];subtraction(Util.postpone(a,n), Util.postpone(b,n),n, c);return Util.eliminate(c);} else {return "0"; // 被减数 小于减数时 返回0}}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！