一個組合數的求解方法

一個組合數的求解方法
  有從10個不同的數中取出7個,如何求出所有組合?
  初看這個問題,確實不太好下手,雖然我們理解這個問題很容易,但要讓計算機“理解”可得花點功夫了。
  先分析:首先想到,如果由10個元素中的7個組成一個序列,並且這7個元素互不相等,這就比較接近於正解了;然後考慮,組合中7元素是不分先後的,我們如何剔除多餘的數據呢(如四選二中(1,3)與(3,1)是相同解)?
  我們可以在編程時作一種限定,7個元素的排列順序滿足我們的一個規定,這樣,就可以依據相同位置的值不能相同來排除不正確的解。
  這樣我們的第一個解呼之欲出了:可以利用數組來進行選取,不同的數組下標順序就代表了不同的解,而且我們約定這個下標序列必須是升序,這就利於我們排除冗餘值。
  在本文中,約定這10個數是如下形式的數組,並且已經賦值。計算的結果在一個TMemo控件中顯示。
  var
  Value:array[1..10]ofinteger;
  解法一、
  按鈕1的`點擊事件處理。
  on1Click(Sender:TObject);
  var
  idx1,idx2,idx3,idx4,idx5,idx6,idx7:integer;
  tmpStr:string;
  begin
  r;
  foridx1:=1to4do
  foridx2:=idx1+1to5do
  foridx3:=idx2+1to6do
  foridx4:=idx3+1to7do
  foridx5:=idx4+1to8do
  foridx6:=idx5+1to9do
  foridx7:=idx6+1to10do
  begin
  tmpStr:=IntToStr(idx1)+''+IntToStr(idx2)+''+IntToStr(idx3)
  +''+IntToStr(idx4)+''+IntToStr(idx5)+''+IntToStr(idx6)
  +''+IntToStr(idx7);
  (tmpStr);
  end;
  end;
  解中只顯示了下標的組合,實際應用把下標改爲Value數組即可:tmpStr:=IntToStr(Value[idx1])+''+IntToStr(Value[idx2])+...;。
  這個解的一個亮點就是每一個循環變量的初值都是它前一個變量加1;這就保證後一個下標一定不等於前一個下標,請體會一下爲什麼循環控制變量的終值爲4~10。
  解法二、
  中學的數學教材中就講到C(10,7)=C(10,3),這個很好理解,從10中選7,剩下3個,所有選七的組合完成,也就是所有選三的組合完成,反之亦然。
  按鈕2的點擊事件處理:
  on2Click(Sender:TObject);
  var
  idx1,idx2,idx3,idx4:integer;
  tmpStr:string;
  begin
  r;
  foridx1:=1to8do
  foridx2:=idx1+1to9do
  foridx3:=idx2+1to10do
  begin
  tmpStr:='';
  foridx4:=1to10do
  if(idx4<>idx1)and(idx4<>idx2)and(idx4<>idx3)//加入一個元素
  thentmpStr:=tmpStr+IntToStr(Value[idx4])+'';
  (tmpStr);
  end;
  end;
  這個解是十選三,然後顯示剩下的七個,是不是有點意思呢?
  以上加入元素的判斷可以改寫爲:
  if((idx1+100)*(idx2+100)*(idx3+100)mod(idx4+100)>0)
  請體會一下同餘理論的運用,這裏利用了101到110這十個數中任一個數都不被其它三個數的乘積整除的特性
  解法三、
  以上兩解也可用集合來實現。
  再想想,以上兩解都是用了多重循環,必須定義多個循環變量,通用性似乎差了點。
  觀察這些循環(尤其是解一),形式是何等的一致!
  也許諸位已經想到我要用遞歸調用來解決這個問題了。
  要設計遞歸,首先要確定哪些變量是必須向這個函數傳遞的,容易知道,調用時要知道當前元素的起始下標與終止下標,當然還有兩個必不可少的參數就是我這個函數計算的是從多少選多少的,這樣就確定了四個參數。
  還有一個要注意的地方,是遞歸何時顯示數據?顯然應當在求最後一個元素時。
  (關於遞歸調用的一些詳細的論述,可以參看喬林的《參透Delphi/Kylix》一書或其它教材)
  請看實現:
  全局變量
  var
  GIDX:array[1..20]ofinteger;//記錄下標的數組。
  procedureMyRecur(Total,SelCnt,BLoc,ELoc:integer);
  var
  idx,jjj:integer;
  tmpStr:string;
  begin
  if(ELoc=Total)//終止狀態
  thenbegin
  foridx:=BLoctoELocdo
  begin
  GIDX[SelCnt+ELoc-Total]:=idx;//注意此處應與下面8888處一致
  tmpStr:='';
  forjjj:=1toSelCntdotmpStr:=tmpStr+IntToStr(Value[GIDX[jjj]])+'';
  (tmpStr);
  end;
  end
  elsebegin
  foridx:=BLoctoELocdo
  begin
  GIDX[SelCnt+ELoc-Total]:=idx;//8888
  MyRecur(Total,SelCnt,idx+1,ELoc+1);
  end;
  end;
  end;
  procedureSelNumber(Total,SelCnt:integer);