奧賽經(jīng)典——程序設(shè)計(jì)試題匯編

1、越秀區(qū)少年宮信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)——排列與組合基礎(chǔ)知識(shí)第1頁(yè)1排列與組合基礎(chǔ)知識(shí)有關(guān)排列與組合的基本理論和公式：加法原理：做一件事，完成它可以有n類(lèi)辦法，在第一類(lèi)辦法中有m1種不同的方法，在第二類(lèi)中辦法中有m2種不同的方法，……，在第n類(lèi)辦法中有mn種不同方法。那么完成這件事共有N＝m1＋m2＋…＋mn種不同的方法，這一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n個(gè)步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法

2、，……，做第n步有mn種不同的方法，那么完成這件事共有N＝m1m2…mn種不同的方法，這一原理叫做乘法原理。公式：階乘公式，規(guī)定0?。?；!(1)(2)321nnnn????????全排列公式!nnPn?選排列公式、!(1)(2)(1)()!mnnPnnnnmnm????????mmmnnmPCP?A圓排列：n個(gè)不同元素不分首位圍成一個(gè)圓圈達(dá)到圓排列，則排列數(shù)為：!(1)!nnn??組合數(shù)公式、規(guī)定(1)(2)(1)!!!()!mmnn

3、mmPnnnnmnCPmmnm?????????01nC?、、）mnmnnCC??11mmmnnnCCC????0122nnnnnnCCCC??????提示：（1）全排列問(wèn)題和選排列問(wèn)題，都可根據(jù)乘法原理推導(dǎo)出來(lái)。（2）書(shū)寫(xiě)方式：記為P（nr）；記為C（nr）。rnPrnC加法原理例題：圖1中從A點(diǎn)走到B點(diǎn)共有多少種方法？（答案：4＋2＋3＝9）乘法原理例題：圖2中從A點(diǎn)走到B點(diǎn)共有多少種方法？（答案：46＝24）加法原理與乘法原理綜合

4、：圖3、圖4中從A走到B共有多少種方法？（答案：28、42）AB圖1AB圖2越秀區(qū)少年宮信息學(xué)奧林匹克競(jìng)賽輔導(dǎo)——排列與組合基礎(chǔ)知識(shí)第3頁(yè)37.有N個(gè)男同學(xué)和M個(gè)女同學(xué)站成一排，其中這M個(gè)女同學(xué)要求站在一起，問(wèn)共有多少種排隊(duì)方法？8.一個(gè)長(zhǎng)度為N＋M個(gè)字符的01字符串，問(wèn)其中有N個(gè)1的字符串有多少個(gè)？9.一個(gè)NM（N表示行，M表示列）的網(wǎng)格，從左上角（1，1）點(diǎn)開(kāi)始走到右下角（N，M）點(diǎn)，每次只能向右或者向下走，問(wèn)有多少種不同的路徑。1

5、0.在上題中，若規(guī)定NM，行走方向仍然只能是向右或者向下行走，并且要求所經(jīng)過(guò)的每一個(gè)點(diǎn)的坐標(biāo)(ab)恒滿(mǎn)足ab的關(guān)系（a為行坐標(biāo)，b為列坐標(biāo)），問(wèn)有多少條路徑？11.在上上題中，如果其中有X個(gè)點(diǎn)設(shè)置有障礙而無(wú)法通過(guò)，問(wèn)有多少條路徑？其中X的值以及這X個(gè)點(diǎn)的坐標(biāo)由鍵盤(pán)輸入。12.一個(gè)由N個(gè)0和N個(gè)1組成的01字符串，要求從左往右，1的個(gè)數(shù)始終不少于0的個(gè)數(shù)的字符串共有多少個(gè)？如N＝1時(shí)，只有字符串10；如N＝2時(shí)，有1100、1010兩個(gè)

6、字符串；如N＝3時(shí)，有111000、110100、110010、101100、101010五個(gè)字符串。（提示：該字符串的長(zhǎng)度為2N，其中規(guī)定有N個(gè)1，即相當(dāng)于從2N個(gè)字符中取出N個(gè)字符，方案數(shù)為C（2N，N）。該題還規(guī)定從左往右，1的個(gè)數(shù)始終不少于0的個(gè)數(shù)，那么在C（2N，N）個(gè)方案中，必定有一些排列方案不符合要求，那么是哪些不符合要求呢？我們看N＝2的例子，此時(shí)所有的排列方案有0011、0101、0110、1001、1010、1100

7、六種，其中只有1010和1100兩種方案符合要求，為什么呢？實(shí)際上，在N＝2時(shí)，即有N個(gè)1，這樣，我們將任意一個(gè)0填充到這N個(gè)1中的方案數(shù)有N＋1種，如下圖有①、②、③三個(gè)格子可以填充0，但是要保證所有的0總在1之后，因此也就只有③的位置符合要求（如1100和1010我們都認(rèn)為是所有的0在1的右邊，而1001則有一個(gè)0不在1的右邊），即只有C（2N，N）的1／（N＋1）種方案符合要求。所以答案為：C（2N，N）／（）／（N＋1））。該數(shù)

8、列稱(chēng)為。該數(shù)列稱(chēng)為Catalan數(shù)列，其數(shù)列為列，其數(shù)列為1、2、5、14、42…………。對(duì)于此問(wèn)題，有許多變形應(yīng)用，請(qǐng)熟記該公式。。對(duì)于此問(wèn)題，有許多變形應(yīng)用，請(qǐng)熟記該公式。）①1②1③（舉一反三：一個(gè)由N個(gè)0和N個(gè)1組成的01字符串，要求從左往右，1的個(gè)數(shù)始終不多于0的個(gè)數(shù)的字符串共有多少個(gè)？同理：相當(dāng)于1的位置只能排在所有0的位置之后，因此個(gè)數(shù)同樣為：C（2N，N）／（N＋1）。）13.用N個(gè)A和N個(gè)B排列成一個(gè)字符串，要求從左往

9、右的任意一位，A的個(gè)數(shù)不能少于B的個(gè)數(shù)，問(wèn)有多少種排列方案。14.有2N個(gè)顧客排隊(duì)購(gòu)買(mǎi)一種產(chǎn)品，該產(chǎn)品的售價(jià)為5元，其中N個(gè)顧客手持5元的貨幣，其余N個(gè)顧客手持10元貨幣。由于售貨員手中沒(méi)有零錢(qián)找零，因此售貨員必須將這2N個(gè)顧客按照一定的次序排好隊(duì)，問(wèn)有多少種排隊(duì)方式可以依次順利發(fā)售貨品，而不出現(xiàn)無(wú)法找零的情況。15.學(xué)校某年級(jí)參加數(shù)學(xué)、物理、化學(xué)的培訓(xùn)，人數(shù)分別是150、120、100人。同時(shí)培訓(xùn)數(shù)學(xué)、物理兩門(mén)課的學(xué)生有21人；同時(shí)培