組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用

上傳人:仙*** 文檔編號(hào):248385929 上傳時(shí)間:2024-10-23 格式:PPT 頁數(shù):16 大?。?61.50KB
收藏 版權(quán)申訴 舉報(bào) 下載
組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用_第1頁
第1頁 / 共16頁
組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用_第2頁
第2頁 / 共16頁
組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用_第3頁
第3頁 / 共16頁

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用》由會(huì)員分享,可在線閱讀,更多相關(guān)《組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用(16頁珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,組合數(shù)學(xué)在程序設(shè)計(jì)中的應(yīng)用,長(zhǎng)沙市第一中學(xué),曹利國,程序設(shè)計(jì)一直與數(shù)學(xué)聯(lián)系得非常的緊密,特別是像組合數(shù)學(xué)這一分支,與程序設(shè)計(jì)有著千絲萬縷的聯(lián)系。對(duì)于某些題目,我們用正常的做法想法也許無從下手,但是如果我們把題目的全局或者局部與組合數(shù)學(xué)聯(lián)系起來,或許就會(huì)“柳暗花明又一村”,找到了一種特別獨(dú)特,特別有效率的數(shù)學(xué)方法,把無從下手的棘手題變得簡(jiǎn)單易行。這就是組合數(shù)學(xué)在程序中的運(yùn)用。,下面使用幾個(gè)實(shí)例說明組合數(shù)學(xué)在程序中的運(yùn)用。,引言,Catalan,數(shù),定義:一個(gè)凸,n,邊形通過不相交于,n,邊形內(nèi)部的對(duì)角線把,n

2、,邊形拆分成若干三角形的不同拆分?jǐn)?shù)。,分析,設(shè),Cn,表示凸,n,邊形的拆分方案總數(shù)。由題目中的要求可知一個(gè)凸,n,邊形的任意一條邊都必然是一個(gè)三角形的一條邊,邊,P1 Pn,也不例外,再根據(jù)“不在同一直線上的三點(diǎn)可以確定一個(gè)三角形”,只要在,P2,,,P3,,,,,Pn-1,點(diǎn)中找一個(gè)點(diǎn),Pk(1k=0,的數(shù)列個(gè)數(shù)。,序列,a1a2.ak,的元素順序保持不變,按不同結(jié)合方式插入合法圓括號(hào)對(duì)的方案數(shù)。,n=4(a(bc)d)(a(b(cd)(ab)(cd)(ab)c)d)(a(bc)d),一個(gè)操作數(shù)序列,從,1,,,2,,一直到,n,,棧,A,的深度大于,n,。,現(xiàn)在可以進(jìn)行兩種操作:,1,將

3、一個(gè)數(shù),從操作數(shù)列的頭端移至棧的頭端(對(duì)應(yīng)棧的,push,操作),2,將一個(gè)數(shù),從棧的頭端移至輸出序列的尾端(對(duì)應(yīng)棧的,pop,操作)。,使用這兩種操作,由一個(gè)操作數(shù)序列就可以得到一系列的輸出序列,下表為由,1 2 3,生成序列,2 3 1,的過程。,步驟,0,1,2,3,4,5,6,操作數(shù)序列,123,23,3,3,棧,1,21,1,31,1,輸出序列,2,2,23,231,你的程序?qū)?duì)給定的,n,,,計(jì)算并輸出由操作數(shù)序列,1,,,2,,,,,n,經(jīng)過操作可能得到的輸出序列總數(shù)。,一,棧,(,Noip2003,普及組第三題,),結(jié)合定義我們很容易能發(fā)現(xiàn):如果進(jìn)??闯?1,,出??闯?0,,

4、在任何一位上累計(jì)的“,0,”,的個(gè)數(shù)不大于累計(jì)的“,1,”,的個(gè)數(shù),因?yàn)楸仨氃跅@镉袛?shù)的情況下才能向外彈數(shù)。,原題轉(zhuǎn)化為,n,個(gè),1,和,n,個(gè),0,組成一個(gè),2,n,位的二進(jìn)制數(shù),要求從左到右掃描,“,0,”,的累計(jì)數(shù)不大于“,1,”,的累計(jì)數(shù),求滿足條件的數(shù)有多少。,二,Little rooks(SGU 222),將,k,個(gè)車擺在,n*n,的棋盤上,使得任何兩個(gè)車不能互相攻擊(車可以橫著或豎著走無限格,不能走斜線),算法描述,組合數(shù)學(xué):排列與組合,由于題目里的棋子是“車”而不是“后”,所以一個(gè)棋子不會(huì)影響到與其不同行或與其不同列的棋子。結(jié)合,n,皇后問題的方案表示法,我們很容易想到排列組合

5、。,排列的定義:設(shè),A=a1,a2,a3,an,是,n,個(gè)不同元素的集合,,r,滿足,0=,r=k,,,先從簡(jiǎn)單的情況下手:,n=k,。,此時(shí)的公式非常簡(jiǎn)單:,P(n,k),。,主要就是對(duì)于,nk,的情況時(shí)的處理。,因?yàn)槊恳涣凶疃嘀荒芊乓活w棋子,所以我們首先把沒有棋子的列去掉,再合并成一個(gè),n*k,的棋盤,結(jié)合剛才的數(shù)據(jù)結(jié)構(gòu)我們能很快知道在這個(gè)新棋盤上擺,k,個(gè)棋子還是,P(n,k),種方案,再把去掉的,(,n-k+1),列插入擺棋子的,k,行中,插入方案總數(shù)易得為,C(n,k),種。,根據(jù)乘法原理,總方案數(shù)為,C(n,k)*P(n,k),種。這樣一來程序?qū)崿F(xiàn)起來就方便多了。,錯(cuò)排問題:,n,

6、個(gè)數(shù),分別為,1,n,,,排成一個(gè)長(zhǎng)度為,n,的排列。若每一個(gè)數(shù)的位置都與數(shù)的本身不相等,則稱這個(gè)排列是一個(gè)錯(cuò)排。例如,,n=3,,,則錯(cuò)排有,2 3 1,、,3 1 2,。編寫程序,求,n,的錯(cuò)排個(gè)數(shù)。,三,錯(cuò)排問題(經(jīng)典問題),組合數(shù)學(xué):遞推,我們?cè)O(shè),k,個(gè)元素的錯(cuò)位全排列的個(gè)數(shù)記做:,W(k),。,四個(gè)元素的錯(cuò)位排列,W(4),我們用窮舉法可以找到如下,9,個(gè):,(4,,,3,,,2,,,1)(3,,,4,,,1,,,2)(2,,,1,,,4,,,3),(4,,,1,,,2,,,3)(3,,,4,,,2,,,1)(3,,,1,,,4,,,2),(4,,,3,,,1,,,2)(2,,,4,

7、,,1,,,3)(2,,,3,,,4,,,1),它們有什么規(guī)律呢?,通過反復(fù)的試驗(yàn),我們發(fā)現(xiàn)事實(shí)上有兩種方式產(chǎn)生,錯(cuò)位排列,:,A.,將,k,與,(1,,,2,,,,,k,1),的某一個(gè)數(shù)互換,其他,k,2,個(gè)數(shù)進(jìn)行錯(cuò)排,這樣可以得到,(,k,1),W(k-2),個(gè)錯(cuò)位排列,。,B.,另一部分是將前,k,1,個(gè)元素的每一個(gè)錯(cuò)位排列(有,W(k-1),個(gè))中的每一個(gè)數(shù)與,k,互換,這樣可以得到剩下的,(,k,1),W(k-1),個(gè)錯(cuò)位排列。,根據(jù)加法原理,我們得到求,錯(cuò)位排列的遞推公式,W(k):,W(k)=(k,1)*W(k,1)+W(k,2),結(jié)論,其實(shí)視野看得發(fā)散一些,擴(kuò)展一些,能融入程序設(shè)計(jì)的知識(shí)點(diǎn)不僅限于組合數(shù)學(xué),還有拓?fù)鋵W(xué),微積分,計(jì)算幾何,甚至是物理,化學(xué)。這樣跨學(xué)科的融合相信能給信息學(xué)計(jì)算機(jī)這門學(xué)科煥發(fā)新的光彩。,從上述題我們能發(fā)現(xiàn)一個(gè)共同特點(diǎn),也就是將組合數(shù)學(xué)融入題目中,簡(jiǎn)單而又快速的解決題目。它說明:程序設(shè)計(jì)不一定是拿著現(xiàn)成的思路或算法去生搬硬套,也許我們換個(gè)角度,換個(gè)思路,或者進(jìn)行數(shù)學(xué)建模與變換,將組合數(shù)學(xué)里的一些結(jié)論,定理,性質(zhì)與程序結(jié)合起來,達(dá)到事半功倍的效果。當(dāng)然,要熟練的掌握這方面的技能與技巧還是在乎于我們平常的多看多想多練。,

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!