作者windf4 (windf4)
看板Programming
標題Re: [問題] 正整數的分解
時間Mon Apr 16 14:11:25 2007
※ 引述《pinglunliao (王者：一條孤獨的不歸路)》之銘言：
: For a positive integer N, you can partition it into several units.
: To write a program to separate input into smaller positive integers
: that sum up to N. For example, if N=5, then your output should be:
: 5
: 4 1
: 3 2
: 3 1 1
: 2 2 1
: 2 1 1 1
: 1 1 1 1 1
〔恕刪〕
我的想法是將輸出視為一個項數會遞增的數列，將數列分成
前兩項的頭部和剩下的尾部，則頭的變化共四種：
[ x, 0 ] [ x-1, 0+1 ] x >= 2 〔第一次分解〕
[ x, 1 ] [ x-1, 1+1 ] x >= 3
[ x, 2 ] [ x-1, 1, 1 ] x >= 2
[ 2, 1 ] [ 1, 1, 1 ] 為特例〔最後一次分解〕
而尾部則全部為１，每做一次 [ x, 2 ] => [ x-1, 1, 1 ]
時會增加一項。
所以不用遞迴的寫法：
int main()
{
// temp: 數列第二項; count: 增長的尾部項數.
int num, temp, count, i;
temp = count = 0;
printf("\n Input a positive integer: ");
scanf(" %d", &num);
printf("\n\n [ %d ]", num);
while( num > 1 ) {
if( temp <= 1 ) {
// 特例[2, 1, ...] => [ 1, 1, 1, ...]
if( (num==2) && (temp==1) ) {
printf(" [ 1, 1, 1");
num--;
}
// [2~n, 0] or [3~n, 1, ...]
else {
printf(" [ %d, %d", --num, ++temp);
}
}
else {
printf(" [ %d, %d", num, --temp);
count++;
}
// 補上尾部的項數
for( i=0; i<count; i++) {
printf(", 1");
}
printf(" ]\n");
}
system( "pause" );
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.231.65.159
※ 編輯: windf4 來自: 125.231.65.159 (04/16 14:12)
1F：推 pinglunliao:這解法似乎沒辦法求 n > 5 的解吧？ 140.130.34.88 04/16 15:44
2F：→ pinglunliao:因為 n = 6 時有個解為 [3, 3] 140.130.34.88 04/16 15:46