算法的正确性

Question

该算法旨在为任何正整数 m、n 计算 m^n。如何通过对 n.

的归纳来证明该算法的正确性

long exp(long m, int n) {

if(n == 0) return 1;

if(n == 1) return m;

if(n % 2 == 0) return exp(m*m, n/2); 

else return exp(m*m, n/2) * m;

}

Answer 1

设P(i)为语句：

exp(m, i) computes mⁱ for any integer m

对于基本情况，很明显 P(0) 是正确的，因为我们有 exp(m, 0) = 1 = m^0。

对于归纳步​​骤，我们假设P(0), P(1), ..., P(k-1)都为真，我们声明P(k)也为真。我们不得不考虑以下三种情况：

1.) 如果 k = 1，那么 P(1) 显然为真，因为我们有 exp(m, 1) = m = m^1;

2.) 如果 k > 1 和 k % 2 == 0，那么根据 exp 的定义我们有：

exp(m, k) = exp(m * m, k / 2)

根据归纳假设，我们有 exp(m * m, k / 2) = (m * m)^(k / 2) = m^k，因此 P(k) 在这种情况下为真。

3.) 如果 k > 1 和 k % 2 == 1，那么根据 exp 的定义我们有：

exp(m, k) = exp(m * m, k / 2) * m

根据归纳假设，我们有exp(m * m, k / 2) = (m * m)^(k / 2)。由于 k % 2 == 1，我们有 k / 2 = (k - 1) / 2。因此我们有：

exp(m * m, k / 2) = (m * m)^(k / 2) = (m * m)^((k-1) / 2) = m^(k-1)

因此：

exp(m, k) = exp(m * m, k / 2) * m = m^k

所以P(k)在这种情况下也是如此。