1.1.18 #
解答 #
其实就是一种快速乘法的实现，换成乘号之后就变成了快速乘幂。
例如对于乘法 $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 \newline 2^4 = 2^2 \times 2^2\newline 2^8 = 2^4 \times 2^4 $$
这样时间复杂度就从 $O(n)$ 变为了 $O(log n)$ 。
代码 #
using System;
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
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
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;
}