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)もまた真であると主張します。次の 3 つのケースを考慮する必要があります。

1.) もしk = 1, thenP(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)この場合もそうです。