當前位置:成語大全網 - 新華字典 - s是壹個有限集合 n,k是正整數,子集組

s是壹個有限集合 n,k是正整數,子集組

代碼就不貼了,給妳思路吧

這個題其實就是求集合數的具體集合.

如果不是輸出具體集合,而是輸出具體有多少個集合,那麽這題很簡單.

以N=5,K=3為例.C(5,3),5個裏面選3個不重復,計算結果是(5*4*3)/(1*2*3)=10,有10個.

那麽具體列舉出來看看:

(1,2,3)、(1,2,4)、(1,2,5)、(1,3,4)、(1,3,5)、(1,4,5)

(2,3,4)、(2,3,5)、(2,4,5)

(3,4,5)

沒錯,是10個.

這裏註意看,這裏按照第壹個數分隔每壹行,那麽可以看得出來:

如果第壹個是1,那麽就有6個集合

如果第壹個是2(是第壹個數是2,不是含有2),那麽就有3個集合,

第壹個是3,有1個集合.

6、3、1有沒有什麽規律?具體看看6

6個集合,第壹個是1,那麽就是說,第壹個數已經固定選1了,1已經不用選了,換個說法,就是1已經沒得選了,那麽剩下的情況,就變成是2,3,4,5這4個數裏選2個.

4個數裏選2個,這個好熟悉,不就和當初5個數裏選3個差不多嗎?

那麽計算壹下C(4,2),(4*3)/(1*2)=6,的確是6;和5個選3個結果是壹樣的.

去看看6、3、1的另外兩個,也是壹樣,3個數裏選2個是3個集合,2個數裏選2個是1個集合.

說到這個,可能已經知道了,C(5,3)=C(4,2)+C(3,2)+C(2,2)

這樣的公式,看起來不就是遞歸嗎?

到這裏,我們可以嘗試換初始值,比如換成是N=7,K=4,那麽結果就是C(7,4)=C(6,3)+C(5,3)+C(4,3)+C(3,3)

看到這個結果,我們可以假設C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1),而條件是K-1>=1

那麽當K==1呢?想想都知道了,N個數裏選1個,結果不就是有N個集合嘛

所以可以得出求集合數的公式

C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1) (K>=2)

C(N,K) = N (K=1)

既然有了公式,遞歸就很好實現了

INT C(N,K){

if(K==1) return N;

else

renturn C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1) //用個for或者while就可以了

}

求集合數的思路就是那樣,可問題是要求具體的集合,怎麽辦?

在這裏先設壹個全局數組S[K+1](設K+1可以避免用S[0],便於看代碼思路),用來存具體要輸出的集合.

其實很簡單嘛,既然妳知道了C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...+ C(K-1,K-1) (K>=2),那麽C(N-1,K-1) 具體集合的特點是什麽?答案是第壹個數,是1.

既然第壹個數是1,那麽就是S[1] = 1;

然後再來看看,遞歸首先會執行C(N,K) = C(N-1,K-1) + C(N-2,K-1) + ...,而進入了C(N-1,K-1),就會執行C(N-1,K-1) = C(N-2,K-2) + C(N-3,K-2) + ...;那麽就是進入C(N-2,K-2)了,其特點是第二個數,是2,就是S[2] = 2;

壹直這麽下去,知道第壹組出來了,S[K] = K;此時正在C(N-K+1,1)裏面,也就是說,到了最後第K個數要選擇了,之前的K-1個數已經選好了,是1,2,3,4...,K-1,X,X就是第K個要選的數,選了X就可以輸出第壹組集合了.

X有哪些選擇?可看到C(N-K+1,1)其實就是從K,K+1,...,N-1,N這N-K個數裏選壹個作為X.很簡單,用壹個for就可以了,把這N-K個數都選壹遍,輸出集合,那麽久完成了C(N-K+1,1)的任務了.

完成了C(N-K+1,1),接下來是遞歸哪個呢?

倒過來想,C(N-K+1,1)是怎麽出現的呢?

C(N-K+2,2) = C(N-K+1,1)+C(N-K,1)+...+C(1,1).

原來C(N-K+1,1)是這麽來的,所以說,接下來要進入的,是C(N-K,1).

C(N-K,與C(N-K+1,1)有什麽區別?

C(N-K+1,1)是設第K-1個數為K-1,然後去選擇第K個數,

所以C(N-K,1),就是第K-1個數不用K-1了,改為用它的下個數,用K,第K-1個數設為K,

然後繼續for把剩下的K+1到N這N-K-1個數都選壹遍,輸出集合,這樣就完成了C(N-K,1).

做到這裏,具體思路已經90%都出來了,剩下最後的畫龍點睛.

C(N-K-1,1),第K-1個數為K+1,然後從K+2到N裏面選1個.

那麽這裏具體的K-1、K+1、K、K+2、1都是怎麽算出來的呢?

如果已經看懂了思路,那麽其實在妳拿到C(N-K-1,1)時,妳就已經知道“C(N-K-1,1),第K-1個數為K+1,然後從K+2到N裏面選1個.”這句話裏的那些數是怎麽算出來的了.

如果還沒看懂,沒關系,可以先做壹些標記.

把壹開始的遞歸函數,C(N,K)改為C(N,K,A,B,C,D,E)

以N=5,K=3為例,把C(5,3)就是把第0個數設為0,然後從1到5裏選3個數

所以初始的C(5,3)就改寫為C(5,3,0,0,1,5,3).

C(5,3)=C(4,2)+C(3,2)+C(2,2)

那麽C(4,2)就是把第1個數設為1,然後從2到5裏面選2個數,所以C(4,2)改寫為C(4,2,1,1,2,5,2)

C(3,2)就是把第1個數設為2,然後從3到5裏面選2個數,所以C(3,2)改寫為C(4,2,1,2,3,5,2)

C(2,2)就是把第1個數設為3,然後從4到5裏面選2個數,所以C(2,2)改寫為C(4,2,1,3,4,5,2)

看這三個例子,可以發現,A=K全局-K遞歸,B=N全局-N遞歸,C=B+1,D=N全局,E=K遞歸

好咯,剩下的10%也解決了.這題也就完成咯