奥赛经典——程序设计试题汇编

《奥赛经典——程序设计试题汇编》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、越秀区少年宫信息学奥林匹克竞赛辅导——排列与组合基础知识第4页排列与组合基础知识有关排列与组合的基本理论和公式：加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类中办法中有m2种不同的方法，……，在第n类办法中有mn种不同方法。那么完成这件事共有N＝m1＋m2＋…＋mn种不同的方法，这一原理叫做加法原理。乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×…×mn

2、种不同的方法，这一原理叫做乘法原理。公式：阶乘公式，规定0！＝1；全排列公式选排列公式、圆排列：n个不同元素不分首位围成一个圆圈达到圆排列，则排列数为：组合数公式、规定、、）提示：（1）全排列问题和选排列问题，都可根据乘法原理推导出来。（2）书写方式：记为P（n,r）；记为C（n,r）。加法原理例题：图1中从A点走到B点共有多少种方法？（答案：4＋2＋3＝9）乘法原理例题：图2中从A点走到B点共有多少种方法？（答案：4×6＝24）加法原理与乘法原理综合：图3、图4中从A走到B共有多少种方法？（答案：28、42）

3、4越秀区少年宫信息学奥林匹克竞赛辅导——排列与组合基础知识第4页而排列组合都是研究事物在某种给定的模式下所有可能的配置的数目问题，他们之间主要的区别在于是否要考虑选出元素的先后顺序，不需要考虑顺序的是组合问题，需要考虑顺序的是排序问题。注意：在信息学奥赛中，有许多只需计数而不需具体方案的问题，都可以通过思维转换或方法转换，最后变为两类问题：一类是转变为排列组合问题，另一类是转变为递推公式问题。因此对于加法原理、乘法原理、排列、组合等知识，需要非常熟练，以达到简化问题的目的。加法原理、乘法原理、排列、组合例题：1

4、.（1）用数字0、1、2、3能组成多少个三位数？（2）要求数字不能重复，又能组成多少个三位数？2.国际会议洽谈贸易，有5家英国公司，6家日本公司，8家中国公司，彼此都希望与异国的每个公司单独洽谈一次，问需要安排多少个会谈场次？3.有编号为1、2、3、4、5的五本书需要摆放在书架上，问有多少种不同的摆放方案数。4.有编号为1、2、3、4、5的五本书需要任选3本书摆放在书架上，问有多少种不同方案。5.有编号为1、2、3、4、5的五本书需要任选3本书，问有多少种方法。6.五种不同颜色的珠子串成一圈项链，问有多少种不同

5、的方法。7.把两个红色球、两个蓝色球、三个黄色球摆放在球架上，问有多少种方案。8.有男女各5人，其中3对是夫妻，他们坐成一排，若每对夫妻必须相邻而坐，问有多少种方法？（提示：因为3对夫妻必须相邻而坐，因此可以将每对夫妻看为一个整体进行排列，这样排列总数为（7!）种方法，又因为每对夫妻可以可以左右调换位置，因此总的方案为（7！×2×2×2））9.（1）把3个相同的球放到4个不同颜色的盒子中去，问有多少种方法？（2）把4个相同的球放到3个不同颜色的盒子中去，问有多少种方法？（3）推广开来，把R个相同的球放到N个不同

6、颜色的盒子中去，问有多少种方法？排列组合练习习题：1.有5本日文书、7本英文书、10本中文书。问（1）从中任取2本书有多少种方案？（2）从中取2本相同文字的书有多少种方案？（3）从中取2本不同文字的书有多少种方案？2.把八个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃（即在任何一行、任何一列都只有一个“车”），那么称八个“车”处于一个安全状态。问共有多少种不同的安全状态？3.从1～300之间任取3个不同的数，使得这3个数的和正好被3除尽，问有多少种方案？4.5对夫妇围绕圆桌坐下吃饭，共有多少种方案？

7、如果要求夫妇必须坐在一起，又有多少种方案？5.N个男同学和N个女同学围绕圆桌坐下，要求男女必须交替就座，问共有多少种就座方法？6.8人站成一排排队，如果其中的甲和乙两人要求一定站在一起，问有多少种排队方法？如果甲和乙两人要求一定不站在一起，又有多少种方法？7.有N个男同学和M个女同学站成一排，其中这M个女同学要求站在一起，问共有多少种排队方法？8.一个长度为N＋M个字符的01字符串，问其中有N个1的字符串有多少个？4越秀区少年宫信息学奥林匹克竞赛辅导——排列与组合基础知识第4页1.一个N*M（N表示行，M表示列

8、）的网格，从左上角（1，1）点开始走到右下角（N，M）点，每次只能向右或者向下走，问有多少种不同的路径。2.在上题中，若规定N