ループ不変条件を取得し、次のアルゴリズムでそれを証明するにはどうすればよいですか。
power(x,y):
z = 1
m = 0
while m < y:
z = z*x
m = m+1
return z
ループ不変条件を取得し、次のアルゴリズムでそれを証明するにはどうすればよいですか。
power(x,y):
z = 1
m = 0
while m < y:
z = z*x
m = m+1
return z
まず、z = z * xを意味すると思います。特定のループに対してループ不変条件を表示するには、反復の開始時と終了時に変更されないステートメントを考え出す必要があります。その不変条件を使用して、プログラムが終了したときに関数が機能することを証明します。あなたの関数力は基本的にx^yを行おうとしています。
ループ不変条件を構築しましょう:Z = x^m。これは、ループの最初と最後の両方で当てはまることがわかります。
また、ループはnot(m = y、またはm =y)の場合にのみ終了できることも知っています。
したがって、Z = x ^ mの場合、終了時にm=yです。次に、Z = x^yです。
したがって、このプログラムは部分的に正しいことがわかります。