作者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