分治策略是一种设计高效算法的有力范型。该方法首先将问题划分成两个较小的子问题,每个子问题除了输入规模较小以外,其他都与原问题是一样的。然后分别解决这两子问题,最后子问题的解合并成为原问题的最终解。

 

一般地,分治算法由三步组成。

步骤1:如果问题规模较小,那么使用某种方法直接解决它;否则,划分问题成两个子问题,最好以相同的规模划分。

步骤2:对子问题使用分治算法递归地解决这两个子问题。

步骤3:合并子问题的解成为原问题的解。

 

问题描述:

按照一般方法计算大数乘法,就是按照手工算法的方式,逐位相乘,两个n位长度的数字相乘,乘法次数为O(n²)。如果减少乘法,增加加法,时间复杂度会降低,通过分治法,两个n位长度的数字相乘,乘积次数可以减少到O(nlog3)。

bignum图1

 

此时,有四次n/2长度的乘积(B*D,A*D,B*C,A*B),四次10进制位移,移动n/2位,三次加法。忽略位移,时间复杂度 T(n)。

公式1

将X*Y分解后仍然需要n²次乘法,12(logn-1)+3   次加法,忽略加法,乘积复杂度仍为O(n²)。进一步分解公式,减少乘法次数。

公式2

第二次分解之后,有三次乘积,六次加/减法,两次位移。忽略位移,时间复杂度T(n)。

公式3

这种分解方法,需要 n^log3 次乘法,3(logn-1)*6+6次加法,忽略加法,乘积复杂度降低为O(n^1.58)。

关键函数如下:
1、大整数乘法函数,输入两个字符串

public StringBuilder multi(StringBuilder x, StringBuilder y)

2、大整数加法函数

public StringBuilder addBigNums(StringBuilder n1, StringBuilder n2)

3、大整数减法函数

public StringBuilder minusBigNums(StringBuilder d, StringBuilder c)

 

运行结果如下:

运行结果

 

 

代码如下:

public class Main {
public static void main(String[] args) {
StringBuilder x = new StringBuilder();
StringBuilder y = new StringBuilder();
x.append("12345678912345678912345678989123458912345891234589123458912345");
y.append("12345678912345891234589123458912345891234589123458912345");
MultiplyLargeNums m = new MultiplyLargeNums();
System.out.print(  x + " * \n" + y + "\n = \n");
StringBuilder r = m.multiply(x, y);
System.out.println(m.getSigh()+""+r);
}
}
/**
* Created by chris on 15/5/9.
* devide and conquer 解决大整数相乘问题
* AB*CD = (A*10^(n/2)+B)(C*10^(n/2)+D) =BD+10^(n/2)((A+B)(D+C) - BD-AC) +AC*10^n
* 对每一个乘积继续分解
*/
public class MultiplyLargeNums {
private char sigh;
public char getSigh() {
return sigh;
}
public StringBuilder multiply(StringBuilder x, StringBuilder y) {
sigh = getSign(x, y);
processSign(x);
processSign(y);
return multi(x, y);
}
StringBuilder multi(StringBuilder x, StringBuilder y) {
//make sure x.length is bigger
if (y.length() > x.length())
return multi(y, x);
//凑成偶数位相乘,e.g. 123*45=>0123 * 0045
if (x.length() != 1 || y.length() != 1) {
if (x.length() % 2 == 0 && y.length() % 2 != 0 || x.length() % 2 == 0 && y.length() % 2 == 0) {
for (int i = 0; i < x.length() - y.length(); i++) {
y.insert(0, 0);
}
} else if (x.length() % 2 != 0 && y.length() % 2 == 0 || x.length() % 2 != 0 && y.length() % 2 != 0) {
x.insert(0, 0);
for (int i = 0; i < x.length() - y.length(); i++) {
y.insert(0, 0);
}
}
} else if (x.length() != 1 && y.length() == 1) {
if (x.length() % 2 == 0) {
for (int i = 0; i < x.length() - y.length(); i++) {
y.insert(0, 0);
}
} else {
x.insert(0, 0);
for (int i = 0; i < x.length() - y.length(); i++) {
y.insert(0, 0);
}
}
}
StringBuilder a = new StringBuilder();
StringBuilder b = new StringBuilder();
StringBuilder c = new StringBuilder();
StringBuilder d = new StringBuilder();
if (x.length() == 1 && y.length() == 1) {
long result = (x.charAt(0) - '0') * (y.charAt(0) - '0');
return new StringBuilder(result + "");
} else if (x.length() == 1 && y.length() > 1) {
a.append(0);
b.append(x);
c.append(y.substring(0, y.length() / 2));
d.append(y.substring(y.length() / 2) + 1);
} else if (x.length() > 1 && y.length() == 1) {
c.append(0);
d.append(x);
a.append(y.substring(0, x.length() / 2));
b.append(y.substring(x.length() / 2) + 1);
} else {
a.append(x.substring(0, x.length() / 2));
b.append(x.substring(x.length() / 2));
c.append(y.substring(0, y.length() / 2));
d.append(y.substring(y.length() / 2));
}
//BD+10^(n/2)((A+B)(D+C) - BD-AC) +AC*10^n
StringBuilder ab = multi(a, b);
StringBuilder bd = multi(b, d);
StringBuilder ac = multi(a, c);
StringBuilder aPlusb = addBigNums(a, b);
StringBuilder dPlusc = addBigNums(d, c);
StringBuilder mul = multi(aPlusb, dPlusc);
StringBuilder r = minusBigNums(minusBigNums(mul, bd), ac);
StringBuilder tmp = shift(r, x.length() / 2);
StringBuilder result = addBigNums(addBigNums(tmp, shift(ac, x.length())), bd);
return clearZero(result);
}
/**
* delete sign
*/
private int processSign(StringBuilder x) {
if (x == null || x.length() == 0)
return -1;
if (x.charAt(0) == '+' || x.charAt(0) == '-')
x.deleteCharAt(0);
return 0;
}
/**
* add 0 to simulate multiply 10
* */
private StringBuilder shift(StringBuilder r, int i) {
for (int j = 0; j < i; j++) {
r.append(0);
}
return r;
}
/**
* 大数相加
*/
public StringBuilder addBigNums(StringBuilder n1, StringBuilder n2) {
if (n1.length() < n2.length())
return addBigNums(n2, n1);
int length1 = n1.length();
int length2 = n2.length();
int carry = 0;
StringBuilder result = new StringBuilder();
while (length1 >= 1 && length2 >= 1) {
int out = (n1.charAt(--length1) - '0') + (n2.charAt(--length2) - '0') + carry;
carry = out / 10;
result.insert(0, out % 10);
}
while (length1 >= 1) {
int out = carry + n1.charAt(--length1) - '0';
carry = out / 10;
result.insert(0, out % 10);
}
if (length1 <= 0 && carry != 0) {
result.insert(0, carry);
}
return result;
}
/**
* 大数相减法,d-c
*/
public StringBuilder minusBigNums(StringBuilder d, StringBuilder c) {
d = clearZero(d);
c = clearZero(c);
int larger = compare(d, c);
char sign = larger == 1   '+' : '-';
if (larger == 0)
return new StringBuilder(0);
else if (larger > 0) {
return minus(d, c);
} else {
return minus(c, d).insert(0, sign);
}
}
/**
* delete all  prefix zero like 000123=>123
*/
private StringBuilder clearZero(StringBuilder c) {
int i = 0;
while (i < c.length() && c.charAt(i) == '0') {
i++;
}
return new StringBuilder(c.substring(i));
}
/**
* 大整数减法,大减小
*/
private StringBuilder minus(StringBuilder big, StringBuilder little) {
StringBuilder result = new StringBuilder();
int j = little.length() - 1;
for (int i = big.length() - 1; i >= 0; i--) {
if (j >= 0 && big.charAt(i) >= little.charAt(j)) {
result.append(big.charAt(i) - little.charAt(j));
j--;
} else if (j >= 0 && big.charAt(i) < little.charAt(j)) {
result.append(big.charAt(i) + 10 - little.charAt(j));
if (i - 1 >= 0 && big.charAt(i - 1) > '0') {
int replace = big.charAt(i - 1) - 1;
big.setCharAt(i - 1, (char) replace);
} else {
int k = 1;
while (i - k >= 0 && big.charAt(i - k) == '0') {
big.setCharAt(i - k, '9');
k++;
}
if (i - k >= 0 && big.charAt(i - k) != '0')
big.setCharAt(i - k, (char) (big.charAt(i - k) - 1));
}
j--;
} else {
result.append(big.charAt(i));
}
}
return clearZero(result.reverse());
}
/**
* 比较数字串d,c的大小,
* d > c return 1; d==c return 0 ;d < c return -1
*/
private int compare(StringBuilder d, StringBuilder c) {
if (d.length() > c.length())
return 1;
else if (d.length() < c.length())
return -1;
else {
int index = 0;
while (index < d.length() && d.charAt(index) == c.charAt(index))
index++;
if (index == d.length())
return 0;
else {
return d.charAt(index) > c.charAt(index)   1 : -1;
}
}
}
/**
* 两数字乘积结果正负性
*/
private char getSign(StringBuilder x, StringBuilder y) {
String a = x.toString().trim();
String b = y.toString().trim();
int signA = (a.charAt(0) > '0' && a.charAt(0) < '9' || a.charAt(0) == '+')   1 : -1;
int signB = b.charAt(0) == '-'   -1 : 1;
return signA * signB == -1   '-' : '+';
}
}


分类: Java开发算法

发表评论

电子邮件地址不会被公开。 必填项已用*标注