Recursive Multiply: Write a recursive function to multiply two positive integers without using the * operator.You can use addition, subtraction, and bit shifting, but you should minimize the number of those operations.
Hints: #166, #203, #227, #234, #246, #280
解法1
用加法：
1
2
3
4
5
6
7
8
9
|
public int multiply(int a, int b) {
int num = Math.max(a, b);
int factor = Math.min(a, b);
int res = 0;
for (int i = 0; i < factor; i++) {
res += num;
}
return res;
}
|
解法2
用加法，用f(a, b)代表a * b，拿8 * 9举例：
1
2
3
|
f(8, 9) = double(f(4, 9))
= double(f(2, 9))
= double(f(1, 9))
|
如果是 7 * 9：
1
2
|
f(7, 9) = double(f(3, 9)) + 9
= double(f(1, 9)) + 9
|
每次double实际上就是自己加自己，是一次加法操作，那么f(8, 9)的加法次数是3，f(7, 9)的加法次数是4，比解法1好多了。
所以f(m, n)的算法复杂度是：O(logm)，m < n。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public int multiply(int a, int b) {
if (a > b) {
return multiplyInternal(b, a);s
}
return multiplyInternal(a, b);
}
// a <= b
public int multiplyInternal(int a, int b) {
if (a == 1) {
return b;
}
int res = multiplyInternal(a >> 1, b);
res += res;
if (a & 1 == 1) {
// 如果a是奇数
res += b;
}
return res;
}
|
评论