Re: [問題] 正整數的分解

看板Programming作者akalashnikov (Your Majesty!)時間18年前 (2007/04/16 09:04)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/4 (看更多)

# 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