算法 - 如何确定将X评估为30的最小乘法次数？

Question

在面试官的算法中,有一个问题:

您如何确定将X评估为30的最小乘法次数？

谁能告诉我这个问题意味着什么？

什么意思是"评估X到30的功率"？

我想有两种可能的含义:

1. 我们有一个X,然后这个问题问我"我需要多少次乘法来计算X ^ 30？".
2. 我们有一个X,然后它问我"你是什么y y 30 = X,你需要多少乘法来计算y？"

我不知道我认为哪个是正确的,或者它具有第三个含义？

谢谢

Answer 1

这个问题假设有一种写函数的方法:

int f(int x) { return pow(x, 30); }

仅使用乘法.

实际上,有一种方法如下:

int f(int x)
{
    int y = 1;
    for (int i = 0; i < 30; i++)
        y *= x;
    return y;
}

这使用30次乘法.

但考虑一下:

int f(int x)
{
    int z = x*x;
    int y = 1;
    for (int i = 0; i < 15; i++)
        y *= z;
    return y;
}

这使用16次乘法.

所以问题是询问可能的最小乘法数是多少？

这是6次乘法,可能是采访者理想的解决方案:

int f(int x)
{
    x_3 = x * x * x;
    x_6 = x_3 * x_3;
    x_12 = x_6 * x_6
    x_24 = x_12 * x_12
    return x_24 * x_6
}

这更像是一个脑筋急转弯而不是编程问题.真正的幂函数不使用乘法(或者至少不是问题隐含的方式)