【刷题】 leetcode 面试题 08.05.递归乘法

• 算法结构

在这里插入图片描述

递归乘法

  • 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) + A;
        }
        else//B 为零 就不加 A
        {
            return multiply((long long)A <> 1);
        }
    }
    //B 为 0 直接返回 0 
    else 
        return 0;
}

运行效果：

在这里插入图片描述

4 思路三（变态版）

该思路也是使用了二进制乘法器的思路

巧妙的使用了三目运算符简化if语句。

来看代码：

int multiply(int A, int B){
	return B ? multiply((long long)A <> 1) +((B & 1)? A:0) : 0 ;
}

来看效果：

在这里插入图片描述

Thanks♪(･ω･)ﾉ谢谢阅读

下一篇文章见！！！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=4qjiwoelvomd

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/d951ecc797.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐