递归 2 练习中使用的乘法次数。找到了2个不同的答案

Question

首先让我说这是我的离散结构的问题class。我不确定我是否应该 post 在这里或数学溢出。

How does the number of multiplications used by the algorithm in Exercise 24 compare to the number of multiplications used by Algorithm 2 to evaluate a^2^n ? Just to be clear: the order of evaluation is 2^n; then raise a to that power.

首先让我陈述练习24和算法2。

ex 24: Devise a recursive algorithm to find a^2^n, where a is a real number and n is a positive integer. [Hint:Use the equality a^2^(n+1) = (a^2^n)^2.]

The answer is:
procedure twopower(n: positive integer, a: real number)
if n=1 return a^2
else
    return twopower(n-1, a)^2
ALGORITHM 2 A Recursive Algorithm for Computing a^n.
procedure power (a: nonzero real number, n: nonnegative integer)
if n= 0 then return 1
else return a * power (a, n−1)
{输出为a^n}

我从 Chegg 教科书解决方案和解决方案手册中找到了两种不同的解决方案。我不确定作者是如何想出每一个的，我不确定他们是否都正确。 > 算法 2 使用 a 的 2^n 次乘法，乘积 a^2^n 中的每个因子一次练习 24 中的算法基于平方，仅使用 n 次乘法（每个其中是一个数字本身的乘法）。例如，要计算 a^2^4= a^16，该算法将计算 a*a= a^2（一次乘法），然后计算 a^2。 a^2 = a^4（第二次乘法），然后是 a^4。 a^4 = 作为（三分之一），最后作为。 as = a^16（第四次乘法）。（解决方案手册） >

Chegg 解决方案指出 ex 24 使用 2^n 次乘法；对于算法 2，它表示使用的乘法次数为 n。预先感谢您的帮助。

Answer 1

两种解决方案都是正确的——当使用正确的参数调用时。第一个计算 a^2^n 给定 a 和 n。它通过对数字 n 次求平方来实现。

算法2可以return得到相同的结果，但必须用a和2^n调用。是的，它执行 n 乘法——但它不一样 n.

需要追溯操作吗？如果是这样，只需将这两种算法转换为您喜欢的语言，在每个算法中添加一个跟踪打印语句，然后运行它们。

递归 2 练习中使用的乘法次数。找到了2个不同的答案

Recursion the number of multiplications used in 2 exercise. Have found 2 different answers

recursion

discrete-mathematics