循环迭代程序正确性示例-循环不变式和程序终止

我需要帮助来证明迭代程序的正确性:

def term_ex_2(x,y):
 ''' Pre: x and y are natural numbers '''
 a = x
 b = y
 while a >= 0 or b >= 0:
     if a > 0:
         a -= 1
     else:
         b -= 1
 return x * y

我知道我需要以某种方式找到循环不变式,并通过对循环的归纳来证明这一点。问题在于,这里的if / else语句使我困惑于如何提出一个。

我还必须证明程序在那之后是否终止。

我对逐步的过程有一个大致的了解,但是我不知道从家庭作业开始该示例的位置。

任何建议将不胜感激。

coo1cool798 回答:循环迭代程序正确性示例-循环不变式和程序终止

请注意,在外部while循环的次迭代中,ab都会减少1。

由于xy被假定为自然数,因此它们最初都是> 0

循环不变式: a >= 0(可能还有其他可能性!)

此外,程序不会终止,这从上面的循环不变式中可以明显看出,因为它强制while循环始终求值为true

证明草图:只要a > 0,循环就不断递减a直到到达0。然后else条件开始执行,随着b使a == 0循环一次又一次地循环,该条件将永远递减while

经典用法是将循环不变本身置于循环终止条件中,以使循环 loop 无限!

本文链接:https://www.f2er.com/1233915.html

大家都在问