超难的排列组合 ( 积分: 200 )

M

mawp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-07

• #1

从1，2，3，...9的数字中，如何得到下面的排列组合（列数不相等，但各列只和等于排列的数字的个数，即等于9）：
比如:三列，用；号隔开。
1;4;4
2;5;2
3;3;3
...
比如，四列，用；号隔开
1;6;1;1
3;3;2;1
2;2;3;2
...

 

M

mawp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-07

• #2

从1，2，3，...9的数字中，如何得到下面的排列组合（列数不相等，但各列只和等于排列的数字的个数，即等于9）：
比如:三列，用；号隔开。
1;4;4
2;5;2
3;3;3
...
比如，四列，用；号隔开
1;6;1;1
3;3;2;1
2;2;3;2
...

 

完

完美动物

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-07

• #3

应该还是用枚举吧，只是算法要好好的优化
循环套循环，尽量多的排除不必要的枚举。
呵呵 ，有意思。中午休息的时候再想想

 

大

大大懒虫

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-07

• #4

有意思.

 

H

hhmyz

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-08

• #5

去找算法吧。瞎想是沒用的。象這種數學上經典的題都有算法的。

 

C

cst_zf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-08

• #6

就是用回溯穷举（就是自己模拟栈来消除递归），也没什么好优化的
最后一个数直接用前面的数可以求出
每层填完数字后，如果已填数之和超过或等于总和就返回（回溯）

 

M

mawp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-09

• #7

cst_zf,能给出具体的算法吗？

 

C

chenybin

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-09

• #8

留名

 

L

liugaohui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-13

• #9

具体的算法?顶一下～～～～～～～～～～～

 

S

shine007

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-13

• #10

收藏了先。

 

C

cst_zf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-13

• #11

我给个递归的大概思路吧，用回溯法消递归可读行有点差了
var
S: array[1..100] of Integer;
procedure find(Num,Sum,N,P:Integer);
{ Num 递归层数
Sum 当前之和
　N　总列数
　P 总和 }
var
i: Integer;
begin
if Num>N then
//递归终点
begin
//自己根据需要处理S[1]-S[N]吧
exit;
end;
for i:=1 to Pdo
begin
if Sum+i+N-Num<=P then
begin
S[Num]:=i;
find(Num+1,Sum+i,N,P);
end;
end;
end;

 

C

cst_zf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-13

• #12

调用的起点是find(1,0,N,P)

 

C

cst_zf

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-13

• #13

有好多可以优化的地方
一是最后一个数可以不求，直接在Num=N的层上做递归终点处理
二是当sum+i+N-Num=P是最后所有数必定为一，自己处理掉就行了
三是用回溯消递归，需要的数组多了一些，像Sum[Num]也需要保存了

 

M

mawp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-14

• #14

cst_zf，多谢，问题已经解决，采用另外一种方法

 

M

mawp

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2005-09-14

• #15

接受答案了.