Re: [問題]用遞迴寫一個PowerSet,求解釋
※ 引述《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://www.ptt.cc/bbs/Programming/M.1413392877.A.345.html
※ 編輯: yauhh (114.42.69.214), 10/16/2014 01:09:50
推
10/16 16:17, , 1F
10/16 16:17, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):