一个组合数的求解谈开去

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

初看这个问题，确实不太好下手，虽然我们理解这个问题很容易，但要让计算机“理解”可得花点功夫了。
先分析：首先想到，如果由10个元素中的7个组成一个序列，并且这7个元素互不相等，这就比较接近于正解了；然后考虑，组合中7元素是不分先后的，我们如何剔除多余的数据呢（如四选二中(1,3)与(3,1)是相同解）？
　　 我们可以在编程时作一种限定，７个元素的排列顺序满足我们的一个规定，这样，就可以依据相同位置的值不能相同来排除不正确的解。
　　 这样我们的第一个解呼之欲出了：可以利用数组来进行选取，不同的数组下标顺序就代表了不同的解，而且我们约定这个下标序列必须是升序，这就利于我们排除冗余值。
在本文中，约定这10个数是如下形式的数组，并且已经赋值。计算的结果在一个TMemo控件中显示。
var
Value:array[1..10] of integer;

解法一、
按钮１的点击事件处理。
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个，所有选七的组合完成，也就是所有选三的组合完成，反之亦然。
按钮２的点击事件处理：
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;

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有