※ 引述《billy20510 ( ＊～鸭子～＊)》之铭言： : char buf[3]={'a','b','c'}, ans[4]; : int total_len=3; : void Powerset(int i, int j) : { : if (j==total_len) { : ans[i]=0; : cout<<'{'<<ans<<'}'<<endl; : } : else { : Powerset(i,j+1); : ans[i]=buf[j]; : Powerset(i+1,j+1); : } : } 我想要这样解释。一个规划得很好的递回，可分为 basic case 和 recursive case 。 在 base case 中，程式经过 recursive case 之後，最後累积一些东西，可以印出。 所以想想以下这个，写了一半的 Powerset ： void Powerset(int i, int j) { if (j == total_len) { ans[i] = 0; cout << '{' << ans << '}' << endl; } else { ans[i] = buf[j]; Powerset(i+1, j+1); } } 丢一个 Powerset(0, 0) 下去，会印出 abc\0 。 同理，丢一个 Powerset(1, 1) 下去，会印出 bc\0 。 丢一个 Powerset(2, 2) 下去，会印出 c\0 。 接着再想想下面这个写了另一半的 Powerset ： void Powerset(int i, int j) { if (j == total_len) { ans[i] = 0; count << '{' << ans << '}' << endl; } else { Powerset(i, j+1); ans[i] = buf[j]; } } 丢个 Powerset(0, 0) 会一路拉到 Powerset(0, 3) ，结果印出 \0 ， empty set 。 丢个 Powerset(1, 1) 会一路拉到 Powerset(1, 3) ，结果印出 ans[0]\0 ， 看之前 ans[0] 放了什麽。 丢个 Powerset(2, 2) 会拉到 Powerset(2, 3) ，结果印出 ans[0] ans[1]\0 ， 看之前 ans[0] 和 ans[1] 遗留了什麽。 ---- 比较罗唆的实例解释： 前後两半 Powerset 合在一起，效果是，当 Powerset(0, 0) 在走向 Powerset(3,3) 时，会带出 Powerset(0, 1) ，而 Powerset(0, 1) 中间会有 ans[0] = buf[1] ， 得到 b 开头的状态，之後又产生 Powerset(1, 2) 。 所以看起来， Powerset(m, n) 是什麽东西呢？我觉得，可以说是 m 是空间索引， n 是字集索引，而 Powerset(m, n) 则称为「把第 n 个字复制到 第 m 个位置上做为开头的 power set 」，这样，把 Powerset(m, n) 当作是醒目 的物件，来阅读原程式，可能会比较读得懂意思。 把 Powerset(0,0) 的生成层次写出来，就很清楚，而且前面所讲的两半合在一起 的时候，有点像「乘法」的效果。 [ ] Powerset(0, 0) Powerset(0, 1) Powerset(0, 2) Powerset(0, 3) => \0 [c ] Powerset(1, 3) => c\0 [b ] Powerset(1, 2) Powerset(1, 3) => b\0 [bc ] Powerset(2, 3) => bc\0 [a ] Powerset(1, 1) Powerset(1, 2) Powerset(1, 3) => a\0 [ac ] Powerset(2, 3) => ac\0 [ab ] Powerset(2, 2) Powerset(2, 3) => ab\0 [abc ] Powerset(3, 3) => abc\0 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.42.69.214 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Programming/M.1413392877.A.345.html ※ 编辑: yauhh (114.42.69.214), 10/16/2014 01:09:50