作者smallc7023 (可樂嘎)
看板Programming
標題[問題] 作業題目求助...
時間Thu Apr 26 01:57:48 2012
請問以下 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
1F：推 yauhh:應該是k<100 and m<100吧 49.214.101.104 04/26 10:49
2F：→ snoopy0907:算奇數有幾個....?? 219.68.139.57 04/26 10:50
3F：→ snoopy0907:m只是計數用 219.68.139.57 04/26 10:52
4F：推 lovesnake:作業? 迴圈不變量是演算法最基本證明法 140.121.216.68 04/26 11:35
5F：推 yauhh:那應該是k<100 and m<= k 180.205.44.99 04/26 11:36
6F：→ lovesnake:..大家應該都知道我想表達什麼吧? ((嘆 140.121.216.68 04/26 11:38
7F：→ lovesnake:迴圈不變量跟數學歸納法相似，利用一個 140.121.216.68 04/26 11:38
8F：→ lovesnake:已知且恆亙不變的事實，去推倒往後的Y 140.121.216.68 04/26 11:39
9F：→ lovesnake:事實也會相同。 140.121.216.68 04/26 11:39
10F：→ lovesnake:分初始(得到某事實)維持(迴圈結果相同) 140.121.216.68 04/26 11:42
11F：→ lovesnake:結束(演算法結束後結果與目的相同) 140.121.216.68 04/26 11:42
12F：→ yauhh:這樣講反而難懂,不變量既然不變,如何往後推? 59.112.229.204 04/26 14:28
13F：→ MOONRAKER:改稱不變「項」比較容易理解。 118.163.12.174 04/26 16:13
14F：推 lovesnake:因為出來的結果是確定的 不變的 140.121.216.68 04/26 16:49
15F：→ lovesnake:不對= =+ 我講錯了 <(_ _)> 140.121.216.68 04/26 16:52
16F：推 lovesnake:疑? 對耶 沒錯 XD 我沒講錯 是結果不變 140.121.216.68 04/26 16:55
17F：→ lovesnake:因為迴圈結果不變 所以我們可以得知 140.121.216.68 04/26 16:55
18F：→ lovesnake:演算法的正確性~ 140.121.216.68 04/26 16:55
19F：→ lovesnake:所以迴圈不變量是利用先證明出迴圈的 140.121.216.68 04/26 16:56
20F：→ lovesnake:不變量，然後利用這個不變量去說明 140.121.216.68 04/26 16:56
21F：→ lovesnake:演算法的正確性。 140.121.216.68 04/26 16:56
22F：→ lovesnake:這種方式只能利用再主體是迴圈的演算法 140.121.216.68 04/26 16:57
23F：→ lovesnake:如果主體是遞迴，就必須使用遞迴樹之類 140.121.216.68 04/26 16:57
24F：→ yauhh:唉唷,相對於invariant當然是variant和guard. 59.112.229.204 04/26 17:31
25F：→ Favonia:（推文跳過）嘗試寫下m和k的精準關係吧～ 140.112.30.39 04/26 20:15