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

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

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

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

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

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

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

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

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

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