循環不變式（loop invariant）主要來幫助我們來理解算法的正確性。

對于循環不變式，必需證明它的三個性質：

初始化：它在循環的第一輪迭代開始之前，應該是正確的。

保持：如果在循環的某一次迭代開始之前它是正確的，那么，在下一次迭代開始之前，它也應該保持正確。

終止:當循環結束時，不變式給了我們一個有用的性質，它有助于表明算法是正確的。?

關循環不變式與數學歸納法有些類似，但是與它的常見用法不同：在歸納法中，歸納的步驟是無窮地使用的；而在這兒，當循環結束時， 即終止“歸納”。

?

霍納規則的正確性：

以下代碼片段實現了用于計算多項式?

?的霍納規則

1?y=0
2?i=n
3?while?i>=0
4?????do?y=a(i)+x*y
5????????i=i-1

?

?

以下給出的是針對第3~5行中while循環的一個循環不變式：

?

初始化：當循環第一次的時候，n=n-1,y=a(n)

保持：當i=n-j與i=n-j-1 的時候，y(n-j-1)=a(n-j-1)+x*y(n-j)

終止： 當循環結束的時候，

?

?

?

?

?

?

?

?

?

?

轉載于:https://www.cnblogs.com/iwuyudong/archive/2010/09/13/2234122.html

總結

以上是生活随笔為你收集整理的循环不变式及其运用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。