程序员面试金典-面试题 08.05. 递归乘法

题目:

递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。

示例1:

输入:A = 1, B = 10
输出:10
示例2:

输入:A = 3, B = 4
输出:12

分析:

我们将A看做被乘数,如果A为偶数的话则multiply(A , B) = multiply(A>>1 , B) << 1 ,也就是A/2*B的二倍。

如果A为奇数数的话则multiply(A , B) = multiply(A>>1 , B) << 1 + B ,也就是(A-1)/2*B*2 + B。

程序:

class Solution {
    public int multiply(int A, int B) {
        return helper(A, B);
    }
    public int helper(int A, int B) {
        if(A == 1)
            return B;
        if(A % 2 == 0)
            return helper(A >> 1, B) << 1;
        else
            return (helper(A >> 1, B) << 1) + B;
    }
}

 

上一篇:AcWing 1050. 鸣人的影分身 整数划分问题


下一篇:单向环形链表解决约瑟夫环问题(Java实现)