1.1.18

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

其实就是一种快速乘法的实现,换成乘号之后就变成了快速乘幂。

例如对于乘法 $2 \times 4$ ,可以用 $2 + 2 + 2 + 2$ 做四次加法计算;也可以变为 $ (2 + 2) \times 2 = (2 + 2) + (2 + 2) $ 的形式,用两次加法就可以完成(先计算 $ 2 + 2 $ 的值,再计算 $ 4 + 4 $ 的值)。

同理对于乘幂 $ 2^8 $ ,既可以用 $ 2\times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 $ 做 8 次乘法,也可以只用三次乘法就计算出来:

$$
2^2 = 2 \times 2 \\
2^4 = 2^2 \times 2^2\\
2^8 = 2^4 \times 2^4
$$
这样时间复杂度就从 $ O(n) $ 变为了 $ O(log n) $ 。

代码

static void Main(string[] args)
{
    Console.WriteLine($"mystery(2, 25): {mystery(2, 25)}");
    Console.WriteLine($"mystery(3, 11): {mystery(3, 11)}");

    Console.WriteLine($"mysteryChanged(2, 8): {mysteryChanged(2, 8)}");
    Console.WriteLine($"mysteryChanged(3, 2): {mysteryChanged(3, 2)}");
}

//mystery(a, b) = a * b
//利用等式:a * b = 2a * b/2 = (2a * (b-1) / 2) + a
//示例:
//mystery(2, 25) =
//mystery(2 + 2, 12) + 2 =
//mystery(4 + 4, 6) + 2 =
//mystery(8 + 8, 3) =
//mystery(16 + 16, 1) + 16 + 2 =
//mystery(32 + 32, 0) + 32 + 16 + 2 =
//0 + 32 + 16 + 2 =
//50
public static int mystery(int a, int b)
{
    if (b == 0) return 0;
    if (b % 2 == 0) return mystery(a + a, b / 2);
    return mystery(a + a, b / 2) + a;
}

//mysteryChanged(a, b) = a ^ b
//同理(乘方与乘法,乘法与加法之间具有类似的性质)
//a ^ b = (a ^ 2) ^ (b / 2) = (a ^ 2) ^ ((b - 1) / 2) * a
public static int mysteryChanged(int a, int b)
{
    if (b == 0) return 1;
    if (b % 2 == 0) return mysteryChanged(a * a, b / 2);
    return mysteryChanged(a * a, b / 2) * a;
}
上一题 下一题