實驗五指定子集個數(shù)的集合劃分

1、指定子集個數(shù)的集合劃分 課程名稱：算法分析與設計 指定子集個數(shù)的集合劃分 曾會蜜 1409J 葉苗 實驗名稱 實驗地點 指導教師 學號 日期 同組成員 3090717116 2011年10月 獨立完成 系別 班級 實驗時數(shù) 成績 信科院 計本09-1 1 實驗目的及要求 ?明確遞歸和遞推的基本概念 ?用遞歸和遞推解決指定子集個數(shù)的集合劃分問題 ?通過本例掌握遞歸和遞推的程序設計方法 實驗環(huán)境及相關情況（包括使用的軟件、實驗設備） ? 工具軟件：Microsoft visual C+ 6.0 ? 硬件：主板，鼠標，鍵盤，顯示器，U盤 ? 操作系統(tǒng)：Win dows 7 實驗內(nèi)容及步驟（包括簡要的

2、實驗步驟流程） 1. 2. n-1 根據(jù)題目確定思路，劃分集合，可以找出其中的邏輯關系 根據(jù)邏輯關系，運用遞歸的算法來求，劃分為兩種情況對于一種情況，等價于把前 素分成m份，然后把n號元素放入這m個集合中的一個（也就是說有 那麼總數(shù)就是 F（n ,m） = F（ n-1,m-1） + m * F（ n-1,m） 3.根據(jù)分析建立遞推方程 個元素分成m-1份，然后n號元素單獨放。對于第二種情況，等價于把前n-1個元 m種放法） 實驗結(jié)果（拷貝屏幕，加上必要的文字說明） 1 1 0 31 63 127 25S 511 25 99 301 弘E 3025 9330 0 0 3 1 10 int i,

3、j; printf(輸入集合的個數(shù)); scan f(%d, printf(”輸入子集的個數(shù)); scan f(%d, for(i=1;i=10;i+) for(j=1;j=10;j+) sij=0; for(i=1;i=10;i+) sii=1； for(i=1;i=10;i+) si1=1; for(i=2;i=10;i+) for(j=2;j=10;j+) sij=j*si-1j+si-1j-1; for(i=1;i=10;i+) for(j=1;j=10;j+) prin tf(%6d,sij); prin tf(n); prin tf( n=%d,k=%d,總共個數(shù)為：%d n, n,k,s nk); 2. #include int recurs ion (i nt a, int b); void mai n() int a,b,c; printf(輸入集合個數(shù)”)； scan f(%d, printf(輸入子集個數(shù)); scan f(%d, c=recurs ion( a,b); printf(劃分的總個數(shù)為%dn ,c); int recurs ion (i nt a, int b) int c=0; if(a=b) return 1; if(a=O|b=O|ab) return 0; if(b=1) return 1; c=b*recurs ion( a-1,b