2

したがって、次のコードがある場合:

public int sumSquares(int n){
   int sum = 0;
   for(int i = 1; i <=n; i++){
      sum += i*i;
   }
   return sum;
}

ここで、ループ不変条件を見つけなければなりません。このようなループの場合、Y = i^2 の不変式はループ不変式と見なされると言われましたが、それがループ不変式であることを証明する方法がわからないのです。Y は単なるものであるため、ループの前、ループ中、およびループ後は常に true です。これは、i*i が何であれ ... それが不変式であることの有効な証拠ですか?

また、不変式を使用してアルゴリズムを証明する場合、合計 = i*i (または Y、ループ不変式) の 1 から n までの合計 = n(n+1)(2n+1 )/6

それでは、帰納法を使ってそれが正しいことを示しますか? アルゴリズムを証明するためにループ不変式を適切に使用していますか?

助けていただければ幸いです:)

4

1 に答える 1

1

不変条件は、ループの入り口にある必要がありますi。

sum = 0 + 1*1 + 2*2 + ... + (i-1)*(i-1)

上の主張は帰納法で証明できます。sumをループの先頭の変数、ループの末尾の変数とするsum'と、次のようになります。

sum' = sum + i*i = 0 + 1*1 + ... + i*i

これにより、さらに、ループが終了i=n+1すると、プログラムが終了すると次のようになるという事実を使用できます。

sum = 0 + 1*1 + ... + n*n
于 2015-09-17T06:12:52.910 に答える