※ 引述《calqlus (東方一隻鹿)》之銘言：
: input:
: 4
: output:
: he partitions of 4 are listed below:
: 4
: 3 + 1
: 2 + 2
: 2 + 1 + 1
: 1 + 1 + 1 + 1
: 有快的方法也可以大概講
這個問題藏著一個子問題為: 給你 n 個 1, 你可不可以產生以下列表
1 1 1 1 1
2 1 1 1
2 2 1
3 1
大問題是給你一個 n = 5, 請你列你所說的展開式. 而解決辦法就是先產生一列
降階序列:
5
4
3
2
1
然後,分別將序列中的每個數字當做開頭,將其補數展開成連續一列 1:
5
4 1
3 1 1
2 1 1 1
1 1 1 1 1
然後,分別將每一列,除了開頭數字之外,其餘部份按照子問題模式列出列表:
5
4 1
3 1 1
2
2 1 1 1
2 1
1 1 1 1
然後把前置項補齊:
5
4 1
3 1 1
3 2
2 1 1 1
2 2 1
1 1 1 1
那我寫以下的程式,來顯示一下這問題的解決架構; 我只用 '\t' 做層次的表示,
主要是因為做字串銜接真是煩死了. 字串銜接就讓你自己想辦法了:
int tabs = 0;
void roll(int n, int lim) {
if (n == 0) return;
tabs++;
int i, j;
for (i=1; i<=(n > lim? lim : n); i++) {
for (j=0; j<tabs; j++) printf("\t");
printf(%d\n", i);
roll(n-i, i);
}
tabs--;
}
void expand(int n) {
int i;
for (i=n; i>0; i--) {
printf("%d\n", i);
roll(n-i, i);
}
}
呼叫 expand(6), 印出:
6
5
1
4
1
1
2
3
1
1
1
2
1
3
2
1
1
1
1
2
1
1
2
1
1
1
1
1
1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.211.169
※ 編輯: yauhh 來自: 218.160.211.169 (10/10 00:44)