作者pinglunliao (王者：一条孤独的不归路)
看板Programming
标题[问题] 正整数的分解
时间Sun Apr 15 16:00:49 2007
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
我想到的一个解
Part( n, d )：印出 d 位数，总和为 n 的解
例如：
Part( 5, 3 )会输出 3 1 1、2 2 1
Part( 5, 2 )会输出 4 1、3 2
Part( 6, 2 )会输出 5 1、4 2、3 3
Algorithm：Part( n, d )
if( d = 1 )
输出 n，离开
else
{
Part( n - i, d - 1); // 1 <= i <= floor(n/d)
Part( i, 1 );
}
C++ Code:
void partNum(int n, int d)
{
if( d == 1 )
{
cout << n << " ";
return;
}
for( int i = 1; i <= (int) ( floor( n * 1.0 / d)); i++ )
{
partNum(n - i, d - 1);
partNum(i, 1);
}
}
int main(int argc, char* argv[])
{
int input;
cin >> input;
for(int i = 1; i <= input; i++)
{
cout << "digit: " << i << '\t';
partNum(input, i);
cout << endl;
}
return 0;
}
我的问题在於，我想出来的演算法似乎有错，因为 n >= 5 时，结果就不正确了
--
蛰伏秋山待枫红，青临洛水无云彩
麒麟降世多磨难，江郎愿使尽长才。 <卧江子>
我的个人网志：
http://blog.pixnet.net/pinglunliao Something About Game Programming
http://www.wretch.cc/blog/pinglunliao 白烂文
http://pinglunliao.blogspot.com/ 心情文
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.130.34.88