找出n个自然数(1,2,3,…,n)中r个数的组合的 经典算法(50分)

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #1

以下程序是从网上搜到的，说是找出n个自然数(1,2,3,…,n)中r个数的组合的经典算法，但运行后，得出的结果怪异，不知错在何处。
var
k,n,r:integer;
procedure comb(n,r:integer);
var
i,temp:integer;
begin
for i:=ndo
wnto rdo
begin
write(i:3);
if i>1 then
comb(i-1,r-1) {递推到下一情形}
else

writeln;
end;
end;

begin
{main}
write('n,r=');readln(n,r);
if r>n then
begin
writeln('Input n,r error!');
halt;
end;
comb(n,r);
{调用递归过程}
readln;
//暂停
end.

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #2

没人看过来？[]

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #3

真可怜

 

A

ASCII

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #4

有两个毛病：
1.递归结束条件不完整，似乎没有考虑到只需要取r个数就行了
if i>1 then
这句应该改为 if (i>1)and(r>1) then
2.前面的搜索结果没有保存和显示
以5取3为例子，如 5 4 3 接下来的一组组合结果应该是 5 4 2 ，但是这个算法好象没
有考虑完整的显示,在第一个的问题解决后只显示了最后的 2,同样接下来应该是
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
.....
但是这个算法只显示了(*代表实际应该显示数字的位置):
* * 1
* 3 2
* * 1
* 2 1
4 3 2
.....

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #5

to ASCii:
完全正确，请问大师，该如何修改呢？？

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #6

现我把结果保存在AB数组中，但发现AB的值并不正确，如下。
for i:=ACountdo
wnto ANumdo
begin
AB[ANum]:=i;
//应该是这里的问题。
if (i>1) and (ANum>1) then
begin
ZuHe(ACount-1,ANum-1);
end
else
begin
//现我把结果保存在AB数组中，但发现AB的值并不正确。如有时会有以下值
// 5 3 2 2 0，正确应是 5 3 2 1 0
//k:=High(AB);
//exit;
end;
end;

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #7

你應該做個棧來放。
就是說數組的下標也是要跟隨變的。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #8

楼上兄弟，是不是我用数组的方法不行？原因就是下标跟着变了？
1、 delphi中如何用棧呢？
2、 我好象记得栈的储存有两种方法，其中的一个就是用数组啊。
谢谢。

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #9

它的遞歸深度實際就是你的數組下標。而遞歸深度就是你的函數comb(i-1,r-1);
前一個參數與原始的n值的差。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #10

兄弟：
按你的意思，》》》它的遞歸深度實際就是你的數組下標。而遞歸深度就是你的函數comb(i-1,r-1);
前一個參數與原始的n值的差。
我把以下语句
AB[ANum]:=i;
//应该是这里的问题。
改为：
AB[OLD-ACount]:=i;
//OLD是ACount 最原始的的值。
发现也不行啊，AB数组的值也会有重复。
大师，麻烦帮我写出来啦，谢谢。
可以另开贴给分你。

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-09

• #11

啊呀，搞錯了，只有第一次是怎麼回事。
再搞個參數來表示當前在第幾層了就可以的。
{$apptype console}
program combo;
var
n,r:integer;
AB:array of integer;
procedure comb(n,r,m:integer);
var
i,j:integer;
begin
for i:=ndo
wnto rdo
begin
AB[m] := i;
if r>1 then
comb(i-1,r-1,m+1) {?推到下一情形}
else
begin
for j := low(ab) to high(ab)do
write(ab[j]:5);
writeln;
end;
end;
end;

begin
{main}
write('n,r=');readln(n,r);
setlength(AB,r);
if r>n then
begin
writeln('Input n,r error!');
halt;
end;
comb(n,r,0);
{?用???程}
readln;
//?停
end.

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-10

• #12

Lichdr兄弟，非常感谢，请到
http://www.delphibbs.com/delphibbs/dispq.asp?lid=2472989
看看，再给分你。
我的QQ：11602585，高攀你了。

 

E

e518

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-10

• #13

我的错误是因为我引用错变量了，如下，哈哈。。。。
if (i>1) and (ANum>1) then
begin
ZuHe(ACount-1,ANum-1);
//这一句应为 ZuHe(i-1,ANum-1,);
end

 

L

lichdr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-11

• #14

這幾天比較忙，有點迷了。
暈掉，不用改它的拉口的。
是原來的那個遞歸函數的第二個參數與原始值之差為遞歸深度。
{$apptype console}
program combo;
var
n,r,oldr:integer;
AB:array of integer;
procedure comb(n,r:integer);
var
i,j:integer;
begin
for i:=ndo
wnto rdo
begin
AB[oldr - r] := i;
if r>1 then
comb(i-1,r-1) {?推到下一情形}
else
begin
for j := low(ab) to high(ab)do
write(ab[j]:5);
writeln;
end;
end;
end;

begin
{main}
write('n,r=');readln(n,r);
setlength(AB,r);
oldr := r;
if r>n then
begin
writeln('Input n,r error!');
halt;
end;
comb(n,r);
{?用???程}
readln;
//?停
end.

 

L

liugaohui

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2004-03-31

• #15

以上几位大哥，正确的代码是什么？