作者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