PTT數位生活區 / Programming

[問題] 作業題目求助...

看板Programming作者 (可樂嘎)時間13年前 (2012/04/26 01:57), 編輯推噓5(5推 0噓 20→)
留言25則, 5人參與, 最新討論串1/1
請問以下 C/C++程式的目的為何？寫下loop invariant，並利用loop invariant 給予證明或說明。 // a[0..99] is an integer array int m = 0; int k = 0; while (k < 100) { if (a[k]%2 == 1) m = m + 1; k = k + 1; } 拜託版上大神幫忙了.... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.127.186.2
推
04/26 10:49, , 1F
應該是k<100 and m<100吧
04/26 10:49, 1F
→
04/26 10:50, , 2F
算奇數有幾個....??
04/26 10:50, 2F
→
04/26 10:52, , 3F
m只是計數用
04/26 10:52, 3F
推
04/26 11:35, , 4F
作業? 迴圈不變量是演算法最基本證明法
04/26 11:35, 4F
推
04/26 11:36, , 5F
那應該是k<100 and m<= k
04/26 11:36, 5F
→
04/26 11:38, , 6F
..大家應該都知道我想表達什麼吧? ((嘆
04/26 11:38, 6F
→
04/26 11:38, , 7F
迴圈不變量跟數學歸納法相似，利用一個
04/26 11:38, 7F
→
04/26 11:39, , 8F
已知且恆亙不變的事實，去推倒往後的Y
04/26 11:39, 8F
→
04/26 11:39, , 9F
事實也會相同。
04/26 11:39, 9F
→
04/26 11:42, , 10F
分初始(得到某事實)維持(迴圈結果相同)
04/26 11:42, 10F
→
04/26 11:42, , 11F
結束(演算法結束後結果與目的相同)
04/26 11:42, 11F
→
04/26 14:28, , 12F
這樣講反而難懂,不變量既然不變,如何往後推?
04/26 14:28, 12F
→
04/26 16:13, , 13F
改稱不變「項」比較容易理解。
04/26 16:13, 13F
推
04/26 16:49, , 14F
因為出來的結果是確定的 不變的
04/26 16:49, 14F
→
04/26 16:52, , 15F
不對= =+ 我講錯了 <(_ _)>
04/26 16:52, 15F
推
04/26 16:55, , 16F
疑? 對耶 沒錯 XD 我沒講錯 是結果不變
04/26 16:55, 16F
→
04/26 16:55, , 17F
因為迴圈結果不變 所以我們可以得知
04/26 16:55, 17F
→
04/26 16:55, , 18F
演算法的正確性~
04/26 16:55, 18F
→
04/26 16:56, , 19F
所以迴圈不變量是利用先證明出迴圈的
04/26 16:56, 19F
→
04/26 16:56, , 20F
不變量，然後利用這個不變量去說明
04/26 16:56, 20F
→
04/26 16:56, , 21F
演算法的正確性。
04/26 16:56, 21F
→
04/26 16:57, , 22F
這種方式只能利用再主體是迴圈的演算法
04/26 16:57, 22F
→
04/26 16:57, , 23F
如果主體是遞迴，就必須使用遞迴樹之類
04/26 16:57, 23F
→
04/26 17:31, , 24F
唉唷,相對於invariant當然是variant和guard.
04/26 17:31, 24F
→
04/26 20:15, , 25F
（推文跳過）嘗試寫下m和k的精準關係吧～
04/26 20:15, 25F
‣ 更多 smallc7023 的文章
文章代碼(AID): #1Fc3iVCf (Programming)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 smallc7023 的文章
文章代碼(AID): #1Fc3iVCf (Programming)