从一个组合数的求解谈开去

王朝delphi·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

在CSDN上有网友问:有从10个不同的数中取出7个,如何求出所有组合?

初看这个问题,确实不太好下手,虽然我们理解这个问题很容易,但要让计算机“理解”可得花点功夫了。

先分析:首先想到,如果由10个元素中的7个组成一个序列,并且这7个元素互不相等,这就比较接近于正解了;然后考虑,组合中7元素是不分先后的,我们如何剔除多余的数据呢(如四选二中(1,3)与(3,1)是相同解)?

我们可以在编程时作一种限定,7个元素的排列顺序满足我们的一个规定,这样,就可以依据相同位置的值不能相同来排除不正确的解。

这样我们的第一个解呼之欲出了:可以利用数组来进行选取,不同的数组下标顺序就代表了不同的解,而且我们约定这个下标序列必须是升序,这就利于我们排除冗余值。

在本文中,约定这10个数是如下形式的数组,并且已经赋值。计算的结果在一个TMemo控件中显示。

var

Value:array[1..10] of integer;

解法一、

按钮1的点击事件处理。

procedure TForm1.Button1Click(Sender: TObject);

var

idx1,idx2,idx3,idx4,idx5,idx6,idx7: integer;

tmpStr:string;

begin

Memo1.Lines.Clear;

for idx1:=1 to 4 do

for idx2:=idx1+1 to 5 do

for idx3:=idx2+1 to 6 do

for idx4:=idx3+1 to 7 do

for idx5:=idx4+1 to 8 do

for idx6:=idx5+1 to 9 do

for idx7:=idx6+1 to 10 do

begin

tmpStr:=IntToStr(idx1)+' '+IntToStr(idx2)+' '+IntToStr(idx3)

+' '+IntToStr(idx4)+' '+IntToStr(idx5)+' '+IntToStr(idx6)

+' '+IntToStr(idx7) ;

Memo1.Lines.Add(tmpStr);

end;

end;

解中只显示了下标的组合,实际应用把下标改为Value数组即可:tmpStr:=IntToStr(Value[idx1])+' '+IntToStr(Value[idx2])+...; 。

这个解的一个亮点就是每一个循环变量的初值都是它前一个变量加1;这就保证后一个下标一定不等于前一个下标,请体会一下为什么循环控制变量的终值为4~10。

解法二、

中学的数学教材中就讲到C(10,7)=C(10,3),这个很好理解,从10中选7,剩下3个,所有选七的组合完成,也就是所有选三的组合完成,反之亦然。

按钮2的点击事件处理:

procedure TForm1.Button2Click(Sender: TObject);

var

idx1,idx2,idx3,idx4: integer;

tmpStr:string;

begin

Memo1.Lines.Clear;

for idx1:=1 to 8 do

for idx2:=idx1+1 to 9 do

for idx3:=idx2+1 to 10 do

begin

tmpStr:='';

for idx4:=1 to 10 do

if (idx4<>idx1) and (idx4<>idx2) and (idx4<>idx3) // 加入一个元素

then tmpStr:=tmpStr+IntToStr(Value[idx4])+' ';

Memo1.Lines.Add(tmpStr);

end;

end;

这个解是十选三,然后显示剩下的七个,是不是有点意思呢?

以上加入元素的判断可以改写为:

if ((idx1+100)*(idx2+100)*(idx3+100) mod (idx4+100) >0 )

请体会一下同余理论的运用,这里利用了101到110这十个数中任一个数都不被其它三个数的乘积整除的特性。

解法三、

以上两解也可用集合来实现。

再想想,以上两解都是用了多重循环,必须定义多个循环变量,通用性似乎差了点。

观察这些循环(尤其是解一),形式是何等的一致!

也许诸位已经想到我要用递归调用来解决这个问题了。

要设计递归,首先要确定哪些变量是必须向这个函数传递的,容易知道,调用时要知道当前元素的起始下标与终止下标,当然还有两个必不可少的参数就是我这个函数计算的是从多少选多少的,这样就确定了四个参数。

还有一个要注意的地方,是递归何时显示数据?显然应当在求最后一个元素时。

(关于递归调用的一些详细的论述,可以参看乔林的《参透Delphi/Kylix》一书或其它教材)

请看实现:

全局变量

var

GIDX:array[1..20] of integer; // 记录下标的数组。

procedure MyRecur(Total,SelCnt,BLoc,ELoc:integer);

var

idx,jjj:integer;

tmpStr:string;

begin

if (ELoc=Total) // 终止状态

then begin

for idx:=BLoc to ELoc do

begin

GIDX[SelCnt+ELoc-Total]:=idx; // 注意此处应与下面 8888处一致

tmpStr:='';

for jjj:=1 to SelCnt do tmpStr:=tmpStr+IntToStr(Value[GIDX[jjj]])+' ';

Form1.Memo1.Lines.Add(tmpStr);

end;

end

else begin

for idx:=BLoc to ELoc do

begin

GIDX[SelCnt+ELoc-Total]:=idx; // 8888

MyRecur(Total,SelCnt,idx+1,ELoc+1);

end;

end;

end;

procedure SelNumber(Total,SelCnt:integer);

begin

if (Total<1) or (Total<SelCnt)

then begin

ShowMessage('数据不正确!');

Exit;

end;

MyRecur(Total,SelCnt,1,Total-SelCnt+1);// 最初第三个参数总为1

end;

使用:

procedure TForm1.Button3Click(Sender: TObject);

var

ttl,sel:integer;

begin

Memo1.Clear;

ttl:=StrToInt(Edit1.Text);// 请自己加上对TEdit的容错处理。

sel:=StrToInt(Edit2.Text);

SelNumber(ttl,sel);

end;

好了,在Edit1中输入‘100’,在Edit2中输入'3',执行试试,三十多万行的数据不断地滚出来了吧。

建议在计算前先估算一下共多少组合,最好不要超过10万。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航