algorithm - 算法的正确性

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)计算任何整数 m 的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)在这种情况下也是如此。