递归乘法
- 1 题目描述
- 2 思路一(返璞归真版)
- 3 思路二(二进制乘法器版)
- 4 思路三(变态版)
- Thanks♪(・ω・)ノ谢谢阅读
- 下一篇文章见!!!
1 题目描述
来看题目描述,真可谓大道至简的描述啊。让我们不使用 *
来实现乘法运算。
2 思路一(返璞归真版)
首先我就想到了乘法的加法表示:A * B = B 个 A 相加。
也可得到递推公式:
A * B = A * (B - 1) + A
我们很容易就可以构造出递归算法
int multiply(int A, int B){
//B 为 1 直接返回B
if(B == 1) return A;
return A + multiply(A , B - 1);
}
来看运行效果:
3 思路二(二进制乘法器版)
接下来我们换一种方法,大家一定记得小时候计算乘法的时候,在纸上打草稿的那种竖式。这其实乘法器的思路。
来看代码:
int multiply(int A, int B){
//乘法器
//二进制运算
//B 为乘数 不为零才继续
if(B)
{
if(B & 1)//B 末位是1
{
// A 左移(放大 因为下一位乘数进位)
//使用 long long 类型防止 A 超出范围
return multiply((long long)A << 1, B >> 1) + A;
}
else//B 为零 就不加 A
{
return multiply((long long)A << 1 , B >> 1);
}
}
//B 为 0 直接返回 0
else
return 0;
}
运行效果:
4 思路三(变态版)
该思路也是使用了二进制乘法器的思路
巧妙的使用了三目运算符简化if语句。
来看代码:
int multiply(int A, int B){
return B ? multiply((long long)A << 1,B >> 1) +((B & 1)? A:0) : 0 ;
}
来看效果: