8.5Recursive Multiply

2024-01-04 19:18

文章标签 8.5 recursive multiply

本文主要是介绍8.5Recursive Multiply，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Write a recursive function to multiply two positive integers without using the * operator (or / operator). You can use addition, subtraction, and bit shifting, but you should
minimize the number of those operations.

Solution

首先考虑一下做乘法意味着什么。思考一件事情到底意味着什么通常是很有用的，即使是在非常明显的情况下。

来看一下进行8 * 7，可以通过8个7相加或者7个8相加得到结果。我们也可以它认为是一个8 * 7的网格中方块的个数。

Solution1

　　我们如何计算一个网格中方块的个数？最简单的方法就是一个个去数。但是，这真的很慢。
　　我们还可以数一半的方块的个数，然后将它加倍（通过将它和自己相加）。为了计算一半方块的个数，我们重复同样的过程。
　　当然，只有当方块的个数是偶数时，上述算法才能工作。当方块个数是奇数时，我们需要从头来做。

int minProductHelper(int smaller,int bigger)
{if(smaller == 0)//0*bigger = 0return 0;else if(smaller == 1)//1*bigger = biggerreturn bigger;int halfSmaller = smaller >> 1;int side1 = minProductHelper(halfSmaller,bigger);int side2 = side1;if(smaller %2 == 1)side2 = minProductHelper(smaller - halfSmaller,bigger);return side1 + side2;
}int minProduct(int a,int b)
{int bigger = a < b?b:a;int smaller = a < b?a:b;return minProductHelper(smaller,bigger);}

Solution2

　　如果我们观察递归如何进行，就会发现我们做了很多重复工作。考虑下面的例子：
　　这里写图片描述
对minProduct(4,23)的第二次调用不知道之前的调用，所以做了重复的工作做。我们可以缓存这些结果。

int minProductHelper(int smaller,int bigger,vector<int>& memo)
{if(smaller == 0)//0*bigger = 0return 0;else if(smaller == 1)//1*bigger = biggerreturn bigger;else if(memo[smaller] > 0)return memo[smaller];int halfSmaller = smaller >> 1;int side1 = minProductHelper(halfSmaller,bigger,memo);int side2 = side1;if(smaller %2 == 1)side2 = minProductHelper(smaller - halfSmaller,bigger,memo);memo[smaller] = side1 + side2;return memo[smaller];
}int minProduct(int a,int b)
{int bigger = a < b?b:a;int smaller = a < b?a:b;vector<int> memo(smaller+1,-1);return minProductHelper(smaller,bigger,memo);}

Solution3

　　当我们看前面的代码时我们会发现使用偶数来调用minProduct的速度要比使用奇数来调用要快得多。例如，如果我们调用minProduct(30,35)，那么我们只需要计算minProduct(15,35)然后将它翻倍就行了。但是，如果我们要计算minProduct(31,35)，那么我们就需要调用minProduct(15,35)和minProduct(16,35)。
　　这不是必须的。相反，我们可以这样做：
　　minProduct(31,35) = 2*minProduct(15,35) + 35
因为31 = 2*15 + 1，所以31 *35 = 2 *15 *35 + 35。
　　最后这个解法的逻辑就是：偶数时，我们将smaller除以2，将递归调用的结果翻倍；奇数时，我们与偶数时的操作相同，但是要加上bigger之后作为最后的结果。
　　这样做，还带来了另一个好处。我们的minProduct一直向下递归，每次都是用更小的数调用。因为不会出现重复调用的情况，所以没有缓存信息的需要。
　　

int minProductHelper(int smaller,int bigger)
{if(smaller == 0)//0*bigger = 0return 0;else if(smaller == 1)//1*bigger = biggerreturn bigger;int halfSmaller = smaller >> 1;int side1 = minProductHelper(halfSmaller,bigger);int side2 = side1;if(smaller %2 == 1)side2+=bigger;return side1 + side2;
}int minProduct(int a,int b)
{int bigger = a < b?b:a;int smaller = a < b?a:b;return minProductHelper(smaller,bigger);}