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