如何找到循環不變

我知道循環不變是爲了證明問題的正確性，但我無法完全理解如何提出一個問題，無論問題多麼微不足道。下面是一個例子，有人能指出我應該考慮採取哪一步來提出一個步驟。我知道循環中所有正在變化的值都必須包含在我的不變量中。請指導我解決這個問題，我也必須找到後期條件。一個解釋將不僅僅是一個答案;請幫忙。如何找到循環不變

{M > 0 and N >= 0 } 

a = M; 
b = N; 
k = 1; 

while (b > 0) { 
    if (b % 2 == 0) { 
     a = a * a; 
     b = b/2 
    } else { 
     b = b – 1; 
     k = k * a; 
    } 
} 

{ ? ? }

來源

2015-10-19 Bobby

[我也面臨同樣的問題，希望這個解釋會給你的想法]（http://stackoverflow.com/questions/2935295/what-is-the-best-way-of-determining-a -loop-invariant） –

謝謝你，我會看看那個，希望它能幫助你 – Bobby

關於循環不變量的棘手部分是沒有算法（我意識到）會始終保證「正確」的答案。

作爲開始，對於您的問題中的算法，請嘗試通過程序進行跟蹤並找出算法的目標（提示：指數很有趣）。追蹤跟蹤變量a，b和k。

例如，使用M = 2和N = 1,2,3,...。在N的幾個值之後，你會注意到變量a，b和k之間的關係會開始發展。

一旦你發現循環不變，後置條件應該很簡單。

希望這會讓你的球滾動！

來源

2015-10-25 20:18:34 Amous

那麼，你會有點落後。如你所說，循環不變的目的是幫助你證明程序的正確性。我想你沒有編寫這個程序 - 否則你會知道它是什麼，並且在編寫循環之前你會想出循環不變的，因爲這是理解循環是正確的關鍵。

那麼...該程序是什麼？你怎麼知道這是正確的？循環不變將成爲你對第二個問題的答案的一部分。

聽起來像這樣：在每次迭代的開始和結束時，k = ... b ....在循環之後，b == 0，所以....和程序是正確的。

我不想拼出答案，因爲這可能是作業，如果你自己想出來，你只會學習它。

來源

2015-10-25 21:05:42

如何找到循環不變

回答

相關問題