一个组合数的求解谈开去

来源:计算机等级考试    发布时间:2012-08-28    计算机等级考试视频    评论

  考试大计算机等级站整理:

  有从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这十个数中任一个数都不被其它三个数的乘积整除的特性。

上一页12下一页

视频学习

我考网版权与免责声明

① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;

② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。

最近更新

社区交流

考试问答