[問題] 正整數的分解
看板Programming作者pinglunliao (王者：一條孤獨的不歸路)時間18年前 (2007/04/15 16:00)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/4 (看更多)
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
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
