Re: [請益] loop invariant ?

看板C_and_CPP (C/C++)作者cplusplus (C++:ID暗藏玄機)時間19年前 (2006/01/23 12:06)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串1/1

※ 引述《hardcover (精裝版喔)》之銘言： : 請問一下 : loop invariant是指什麼? : 看半天看不懂 XD : 書上寫得像在講數學歸納法也是可以這麼說啦 XD : wikipedia上寫得更神奇 : 到底在講什麼啊? : thanks 簡單說就是在程式中的loop 如果有某loop invariant LI 嘖每loop一次都可保持滿足LI裡的某種條件(條件不變=>invariant) 當跑完n次loop結束以後這個條件或是狀態還是會滿足不變式的定義那個定出來的不變式通常就是我們想要的結果比如說如果有個迴圈的LI是跑完第i次loop 在陣列a中的前i個element由小到大排好那這個迴圈跑n次(loop n次) 那陣列中前n個element就小到大排好如果n等於陣列大小那陣列就等於是由小到大排序好... 像是bubblesort的loop invariant就可能是跑完第i次loop 前i大的element會被配置在陣列尾端i個位置尚且由小到大排列好 insertion sort就可能是最上面題的例子... 如果能證明某個loop可達成某LI 就可以證明跑完loop結果會滿足LI裡面的條件定義所以通常拿來證明某個演算法是否正確只要能保持某LI直到最後就可證明是正確的所以說像是數學歸納法應該是因為拿來證明了吧? 證明第n步對 n+1也對所以blahblah ----- 有錯請指正~ 謝謝 :p -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.115.217.14 ※ 編輯: cplusplus 來自: 140.115.217.14 (01/23 12:22)