proof - ループ不変条件とアルゴリズムの証明

Question

ループ不変条件を取得し、次のアルゴリズムでそれを証明するにはどうすればよいですか。

power(x,y):
   z = 1
   m = 0
   while m < y:
       z = z*x
       m = m+1
   return z

Answer 1

まず、z = z * xを意味すると思います。特定のループに対してループ不変条件を表示するには、反復の開始時と終了時に変更されないステートメントを考え出す必要があります。その不変条件を使用して、プログラムが終了したときに関数が機能することを証明します。あなたの関数力は基本的にx^yを行おうとしています。

ループ不変条件を構築しましょう：Z = x^m。これは、ループの最初と最後の両方で当てはまることがわかります。

また、ループはnot（m = y、またはm =y）の場合にのみ終了できることも知っています。

したがって、Z = x ^ mの場合、終了時にm=yです。次に、Z = x^yです。

したがって、このプログラムは部分的に正しいことがわかります。