[理工] 資結 交大100 loop invariant相關問題

看板Grad-ProbAsk作者 (co)時間8年前 (2016/01/16 17:35), 8年前編輯推噓7(7推 0噓 13→)
留言20則, 6人參與, 最新討論串1/1
交大100年第11題 http://imgur.com/1fKqr5B
答案是A C B 什麼是loop invariant呢?? 查了好多資料 還是完全搞不懂意思 請高手幫忙解惑 和對此題解說一下 感謝~~ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.230.135 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1452936951.A.975.html
推
01/16 19:30, , 1F
為什麼 loop invariant 是 code?
01/16 19:30, 1F
F大我不知道Q___Q 話說F大 能順便問你有關複雜度的問題嗎?? ※ 編輯: iam30719 (61.230.230.135), 01/16/2016 19:48:15
推
01/16 21:28, , 2F
可以啊 但是為什麼要指名我回答？？
01/16 21:28, 2F
→
01/16 22:19, , 3F
很直觀的就答出來了誒 但不會解釋
01/16 22:19, 3F
→
01/16 22:22, , 4F
你可以看一下42.43題 應該會幫助理解觀念
01/16 22:22, 4F
→
01/16 23:00, , 5F
是一種結果可以被預測的概念，比方說你執行 bubble sort
01/16 23:00, 5F
→
01/16 23:00, , 6F
假如已經知道輸入那麼你就可以預測每一回合迴圈輸出的
01/16 23:00, 6F
→
01/16 23:00, , 7F
結果而不必等執行完才知道
01/16 23:00, 7F
→
01/16 23:00, , 8F
這是我的理解，有錯麻煩指正
01/16 23:00, 8F
就是說只要可以提前預測結果的話 表示演算法中沒有會讓結果變得無法預測的片段 所以此演算法即有loop invariant特性嗎??
→
01/17 00:34, , 9F
因為我看了以前版上很多複雜度文章 F大的回文都超神的
01/17 00:34, 9F
※ 編輯: iam30719 (61.230.230.135), 01/17/2016 00:45:21
→
01/17 00:47, , 10F
希望F大能幫看一下我前一篇問的複雜度問題 想看怎麼求的
01/17 00:47, 10F
推
01/17 01:06, , 11F
你把loop invariant打上google看stackoverflow那篇
01/17 01:06, 11F
→
01/17 01:06, , 12F
我覺得那例子很好
01/17 01:06, 12F
好 我等等來看看 謝G大
推
01/17 01:38, , 13F
我看了 但是版友都給了答案了 我也沒有什麼特別的解法
01/17 01:38, 13F
所以我問的那題無法用F大解這題#1BAA2uNc時的做法嗎?? ※ 編輯: iam30719 (42.72.217.83), 01/17/2016 10:33:44
推
01/17 17:28, , 14F
就不會隨著iteration數更動而變化的性質 不就這樣XD
01/17 17:28, 14F
有點FU 謝大大~~
推
01/17 18:49, , 15F
是可以啊 但是版友已經說了 這一看就知道是什麼算法
01/17 18:49, 15F
→
01/17 18:49, , 16F
既然算法已經知道了 複雜度在課本上也分析過了
01/17 18:49, 16F
→
01/17 18:49, , 17F
就不用浪費時間重新算一次..
01/17 18:49, 17F
推
01/17 20:37, , 18F
我想你的問題應該是看不出來這是什麼演算法
01/17 20:37, 18F
→
01/17 20:38, , 19F
技巧是要宏觀的看 想看看這段 code 是想要維護什麼
01/17 20:38, 19F
→
01/17 20:38, , 20F
loop invariant 而不是一行一行的去 trace..
01/17 20:38, 20F
OK 謝謝F大 ※ 編輯: iam30719 (42.72.26.2), 01/18/2016 18:37:53 ※ 編輯: iam30719 (42.72.26.2), 01/18/2016 18:43:09
‣ 更多 iam30719 的文章
文章代碼(AID): #1McWxtbr (Grad-ProbAsk)