有从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这十个数中任一个数都不被其它三个数的乘积整除的特性。
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。