0 
//Precondition: n > 0
//Postcondition: returns the minimum number of decial digits
//               necessary to write out the number n

 int countDigits(int n){
1.    int d = 0;
2.    int val = n;
3.    while(val != 0){
4.        val = val / 10;     // In C++: 5 / 2 === 2
5.        d++;
6.    }
7.    return d;
}

不変: 3 行目のループ ガードを評価する直前に、右端の d 桁を削除した n は val と同じです。(数値 0 は、書き出すのに 0 桁が必要であり、書き出すのに 0 桁を必要とする唯一の数字である と仮定します)。

ループ不変式が成り立つことを帰納法を使って証明してください。

今私は常に、帰納法による証明は、方程式内の変数を k で置き換えることによって真になると仮定し、k+1 も真になることを証明しなければならないと常に考えてきました。しかし、私はこの質問で実際に方程式を与えられているわけではなく、コードのブロックだけを与えられています。これが私の基本ケースです：

3 行目のループ ガードを評価する直前では、d は 0 に等しく、2 行目では val == n であるため、n の右端の 0 桁が削除された場合、それは val です。したがって、基本ケースが成り立ちます。

k+1 を証明する方法がわからないので、この後の帰納的ステップの書き方がよくわかりません。

4

1 に答える 1

0

kロジックは、式の値をnループの反復で置き換えることを除いて、実際には式の場合と同じです。

  1. 基本的なケースは、ループの開始前にループの不変条件が保持されることです。
  2. 反復前に不変条件が成立する場合、N反復実行後も不変条件が成立することを証明する必要がNあります。

1. と 2. から、帰納法により、不変条件はループの最後 (または、実際には任意の反復の最後) で保持されると結論付けます。

EDITループが で終了するため、これは興味深いものval == 0です。不変条件 (ループの最後でも真) はn で、右端の d 桁が削除されたものは val と同じであるため、この時点で削除された桁は 0 と同じであるためn、表示に必要な桁数は正しく です。ddn

于 2014-04-24T23:40:24.017 に答える