2011-06-10 20:55:31Morris
a144. 整數分拆
http://zerojudge.tw/ShowProblem?problemid=a144
內容 ：
一個正整數可以寫成一些正整數的和。在數論上，跟這些和式有關的問題稱為整數分拆、整數剖分或整數分割。其中最常見的問題就是給定正整數n，求不同數組(a1,a2,...,ak)的數目，符合下面的條件：
- a1 + a2 + ... + ak = n （k的大小不定）
- 其他附加條件（例如限定「k是偶數」，或「ai不是1就是2」等）
分割函數p(n)是求符合以上第一、二個條件的數組數目。
輸入說明
：
輸入一個正整數n , n < 100
EOF結束輸入
輸出說明
：
輸出符合分割函數p(n)的全部數組
以字典順序由大到小輸出
範例輸入 ：
4
範例輸出 ：
4 3 1 2 2 2 1 1 1 1 1 1
提示
：
出處
：
Netsphere | Wiki
(管理：netsphere)
作法 : 遞迴模擬
/**********************************************************************************/
/* Problem: a144 "整數分拆" from Netsphere | Wiki */
/* Language: C */
/* Result: AC (4ms, 272KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-07 17:14:06 */
/**********************************************************************************/
#include<stdio.h>
#define Max 101
int ans[100] = {Max}, n;
void div(int n, int index) {
int a, next = index+1;
if(n == 0) {
for(a = 1; a < index; a++) printf("%d ", ans[a]);
puts("");
return ;
}
for(a = (n > ans[index-1]) ? ans[index-1] : n; a >= 1; a--)
ans[index] = a, div(n-a, next);
}
main() {
while(scanf("%d", &n) == 1)
div(n, 1);
return 0;
}
上一篇：d652. 貪婪之糊
下一篇：a054. 電話客服中心