※ 引述《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)