作者akalashnikov (Your Majesty!)
看板Programming
標題Re: [問題] 正整數的分解
時間Mon Apr 16 09:04:14 2007
# is this what you want?
# function run
def run(i, s, t, l, d):
a = i;
l[s] = i
l[s+1:] = [0]
if t >= i:
print l[:len(l) - 1]
i = i - 1
while i <> 0:
l[s] = i
if t >= i:
run(a - i, s + 1, i, l, d + 1)
i = i - 1
# main program start here
n = input()
run(n, 0, n-1, [0], 0)
------------------------------------------------------------
7 <-------- input
[7]
[6, 1]
[5, 2]
[5, 1, 1]
[4, 3]
[4, 2, 1]
[4, 1, 1, 1]
[3, 3, 1]
[3, 2, 2]
[3, 2, 1, 1]
[3, 1, 1, 1, 1]
[2, 2, 2, 1]
[2, 2, 1, 1, 1]
[2, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 1, 1]
※ 引述《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
: 我想到的一個解
: 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 時，結果就不正確了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.104
1F：推 pinglunliao:Yes, thanks a lot. 140.130.34.88 04/16 10:20