第6章 组合数学中的程序设计.ppt

《第6章 组合数学中的程序设计.ppt》由会员分享，可在线阅读，更多相关《第6章 组合数学中的程序设计.ppt（101页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章组合数学中的程序设计组合数学中的程序设计沈云付沈云付上海大学计算机工程与科学学院上海大学计算机工程与科学学院本章主要内容本章主要内容6.1组合数学中有关概念与公式组合数学中有关概念与公式6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法6.1.2母函数母函数6.1.3容斥原理与错排容斥原理与错排6.1.4Polya定理定理6.2实例研究实例研究6.1组合数学中有关概念与公式组合数学中有关概念与公式6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法1 1排列与组合的基本概念和公式排列与组合的基本概念和公式排列、相异元素可重复的排列排列、相异元素可重复的排列组合

2、、相异元素可重复的组合组合、相异元素可重复的组合6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法在多项式在多项式 的展开式中的项的展开式中的项 的系数的系数不定方程不定方程 的有非负整数解的个数为的有非负整数解的个数为设设n n是一个正整数，令是一个正整数，令Q Qn n表示在表示在11，2 2，nn中不允许中不允许出现两个连续数字的排列方法出现两个连续数字的排列方法数，则有数，则有Q Qn n =6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法2全排列的生成算法全排列的生成算法全排列的生成算法有：字典序法、递增进位制数法、全排列的生成算法有：字典序法、递增进位制数

3、法、递减进位制数法和邻位对换法等递减进位制数法和邻位对换法等全排列的字典序算法全排列的字典序算法问题：对于给定的一个全排列问题：对于给定的一个全排列P P，要生成要生成P P的下一个的下一个排列排列Q Q6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法字典序全排列：字典序全排列：给定给定n个元素的集合个元素的集合x1，x2，x3，xn，对，对X中的中的元素规定了一个先后关系。在两个排列中，按字典序元素规定了一个先后关系。在两个排列中，按字典序方式对它们的位从左到右每位比较，较小的字符对应方式对它们的位从左到右每位比较，较小的字符对应的排列较先，按这样的序生成的全排列称为字典序全的

4、排列较先，按这样的序生成的全排列称为字典序全排列。排列。给定排列给定排列P，求下一个排列求下一个排列Q例：求例：求X=1，2，3，4，5，6，7上排列上排列P=2637541的的下一个排列下一个排列Q1)从右到左找出比右边数字小的第一个数，即从右到左找出比右边数字小的第一个数，即3。2)再从右到左考察比再从右到左考察比3大的第一个数，是大的第一个数，是43)将将3与与4对换位置，得对换位置，得26475314)将得到的排列将得到的排列2647531从从4后面的后面的7531翻转得翻转得13575)把前缀把前缀264接在接在1357的前面得的前面得2641357，它就是所求的，它就是所求的排列排

5、列2647531的下一个排列。的下一个排列。给定排列给定排列P，求下一个排列求下一个排列Q算法算法设设X=1，2，n，求求P=a1a2an的下一个排列：的下一个排列：1)1)在在P中从右到左寻找右边比左边大的数的第一个位置中从右到左寻找右边比左边大的数的第一个位置j，即即j=maxi|aiaj。此时排列此时排列P形如形如a1a2aj-1ajaj+1ak-1akak+1an。3)3)对换对换aj，ak，并将并将aj+1ak-1ajak+1an翻转，得翻转，得Q=a1a2aj-1akanak-1ajak+1an即为即为P的下一个排列。的下一个排列。6.1.1排列与组合及有关的生成算法排列与组合及有

6、关的生成算法3.组合的生成算法组合的生成算法令令j=maxi|ain-m+i+1。那么那么a1a2am的下一个组合为的下一个组合为a1a2aj-1(aj+1)(aj+2)(aj+m-j)。例如，给定例如，给定n=13，m=6，组合组合45781213，于是可见，于是可见j=3。将。将81213依次修改为依次修改为91011。那么组合。那么组合45781213的下一个组合为的下一个组合为45791011。6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法4.字典序全排列与序号的转换字典序全排列与序号的转换字典序全排列的序号字典序全排列的序号记记P=a1a2an。记。记ki为元素为元素

7、ai的逆序数，则排列的逆序数，则排列P P的序号的序号为为问题：给定排列的序号，如何求全排列？问题：给定排列的序号，如何求全排列？排列排列123458697的的逆序数分别为逆序数分别为000002010，序序号为号为345给定排列的序号给定排列的序号/给定元素个数给定元素个数n，及全排列及全排列p/返回字典序全排列下排列序号返回字典序全排列下排列序号numintperm2num(intn,int*p)inti,j,num=0,k=1;for(i=n-2;i=0;k*=n-(i-)/因子为因子为(n-i-1)!，注意下标从注意下标从0开始开始for(j=i+1;jn;j+)if(pj=0;i-)

8、pi=num%(n-i),num/=n-i;for(i=n-1;i;i-)for(j=i-1;j=0;j-)if(pj=pi)pi+;/根据逆序数数组进行调整根据逆序数数组进行调整6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法5字典序组合与序号的转换字典序组合与序号的转换实例：设实例：设n=9，m=4。将从将从n n个元素取个元素取m m个的所有组合从个的所有组合从1开始从小到大编序，组合开始从小到大编序，组合3579的的序号是多少？序号是多少？一种计算方法：首位小于一种计算方法：首位小于3的组合的个数为的组合的个数为91；首位是；首位是3，第，第2位小于位小于5的组合的个数为

9、的组合的个数为10；前；前2位是位是35，第，第3位位小于小于7的组合的个数为的组合的个数为3；前；前3位是位是357，第，第4位小于位小于9的的组合的个数为组合的个数为1。所有这些数之和。所有这些数之和105，加上它本身的，加上它本身的1个号，得组合个号，得组合3579的序号是的序号是106。另一种思路由组合求序号另一种思路由组合求序号考虑从当前考察的组合的后面有多少个组合。考虑从当前考察的组合的后面有多少个组合。/传入传入n、m及组合及组合c，返回返回c的序号的序号num/下面的下面的comb(n,m)是是n个元素取个元素取m个的组合数个的组合数intcomb2num(intn,intm,

10、int*c)intnum=comb(n,m),i;for(i=0;im;i+)num=num-comb(n-ci,m-i);returnnum;由序号求组合由序号求组合由序号求组合算法是前面由组合求序号的逆过程由序号求组合算法是前面由组合求序号的逆过程 /输入输入n、m，序号序号num，传回所求的组合传回所求的组合cvoidnum2combA(intn,intm,int*c,intnum)inti,j=1,k;for(i=0;icomb(n-j,m-i-1)num-=comb(n-j,m-i-1),j+;ci=j;6.1.2母函数母函数母函数：给定序列母函数：给定序列a0、a1、a2、an、那

11、么函数那么函数G(x)=a0+a1x+a2x2+akxk+称为序列称为序列a0、a1、a2、an、的母函数（也叫生成函数）。的母函数（也叫生成函数）。给定一个序列，可确定对应的母函数；反过来，给定一给定一个序列，可确定对应的母函数；反过来，给定一个母函数，那么也能确定对应的序列。个母函数，那么也能确定对应的序列。例：斐波那契数列例：斐波那契数列an，n=0，1，2，a0=a1=1，an=an-1+an-2。对应的母函数可表示为对应的母函数可表示为可求得可求得举例举例问题描述问题描述 小明手中有小明手中有3张一元张一元,2张张2元和元和3张张5元的钱币元的钱币,问小明都能问小明都能买价值为多少的

12、物品？对每种价值的物品他有几种付款买价值为多少的物品？对每种价值的物品他有几种付款方法？如小明手中有方法？如小明手中有k张一元，张一元，m张张2元和元和n张张5元的钱币，元的钱币，结果又如何？结果又如何？输入输入输入的第一行是一个整数输入的第一行是一个整数T，（，（1T10）,表示测试数据表示测试数据的个数。接下来有的个数。接下来有T行，每行上有行，每行上有3个非负整数个非负整数k，m，n，（，（1k，m，n10），分别表示一元、二元和五元的钱），分别表示一元、二元和五元的钱币数。币数。k，m，n中至少有一个非中至少有一个非0。输出输出对输入中的三种钱币数，输出小明能买物品的价值总数对输入中的

13、三种钱币数，输出小明能买物品的价值总数以及所有的付款方法数。以及所有的付款方法数。输入输入与输出与输出样例样例输入样例输入样例13 2 3输出样例输出样例22 47对实例的说明对实例的说明k=3，m=2，n=3一元、二元、五元钱币对应的能买物品的生成函数一元、二元、五元钱币对应的能买物品的生成函数小明能买的物品对应的生成函数为小明能买的物品对应的生成函数为结论结论小明可以买价值分别为小明可以买价值分别为0，1，2，21，22元的物品，元的物品，即即22种非零的钱数，并且付款的方法数分别为种非零的钱数，并且付款的方法数分别为0，1，2，2，2，3，2，3，2，2，3，2，3，2，2，3，2，3，

14、2，2，2，1，1，总数为，总数为47。6.1.3容斥原理与错排容斥原理与错排1容斥原理容斥原理设设A为任一个有限集合。用为任一个有限集合。用|A|记集合记集合A中元素的个数。当中元素的个数。当A为空集时，为空集时，|A|=0。定理定理6.1设设A，B为两个有限集合，那么为两个有限集合，那么定理定理6.2设设A1，A2，An是是n个有限集合，则个有限集合，则2错排错排当当n 1时，若时，若n个元素个元素1，2，n的排列的排列P其每个元素都其每个元素都不在原来的位置上（即元素不在原来的位置上（即元素k不在位置不在位置k上），则该排列称上），则该排列称为错排。为错排。n个元素的集合个元素的集合1，

15、2，n的错排个数为的错排个数为Dn。有递推关系有递推关系很容易得到关于很容易得到关于Dn的关系式的关系式 Dn=3抽屉原理抽屉原理1.1.将将m m个物品放入个物品放入n n个抽屉，则其中至少有一个抽屉里含有个抽屉，则其中至少有一个抽屉里含有 个物品个物品2.设设m1 1、m2 2，m1 1，mn n都是正整数，且将都是正整数，且将n个物品放入个物品放入n个抽屉，则：第一个抽屉至少有个抽屉，则：第一个抽屉至少有m1 1个物品，第二个抽个物品，第二个抽屉至少有屉至少有m2 2个物品，个物品，第，第n个抽屉至少有个抽屉至少有mn n个物品，个物品，至少其中之一必定成立。至少其中之一必定成立。6.1

16、.4Plya定理定理群群:定义定义6.3 6.3 设设G G是一个集合，是一个集合，*是是G G上的二元运算，如果上的二元运算，如果(G G，*)满满足如下条件：足如下条件：封闭性：对于任何封闭性：对于任何a a，b b G G，有，有a*ba*b G G；结合律：对任何结合律：对任何a a，b b，c c G G，(a*b)*c=a*(b*c)(a*b)*c=a*(b*c)；单位元：存在单位元：存在e e G G，使得对使得对a a G G，有，有a*e=e*a=aa*e=e*a=a；逆元：对于每个元素逆元：对于每个元素a a G G，存在存在x x G G，使得使得a*x=x*a=a*x=

17、x*a=e e。那么称（那么称（G G，*）为一个群。为一个群。群的例子群的例子例例1：设设G=1,-1，*为普通乘法，那么（为普通乘法，那么（G，*）为一个群，为一个群，1是单位元。是单位元。例例2：设设G=0，1，2，3，m-1，*为普通的模为普通的模m加法，加法，那么（那么（G，*）为一个群，为一个群，0是单位元。是单位元。例例3：设设m=10，记，记G=1，3，7，9，那么那么G关于模关于模10的乘法的乘法构成一个群。构成一个群。子群、交换群子群、交换群子群：子群：设（设（G，*）是任何一个群，又设）是任何一个群，又设H是是G的子集，若的子集，若（H，*）是一个群，则称（）是一个群，则

18、称（H，*）是（）是（G，*）的一个群，）的一个群，简称简称H是是G的子群的子群。交换群：交换群：设（设（G，*）是一个群，如果对于）是一个群，如果对于G的任何元素的任何元素a，b，有，有ab=ba，那么称，那么称G为交换群为交换群。置换：置换：设设X是一个有限集，是一个有限集，是是X到到X的一个一一变换，那的一个一一变换，那么称么称 是是X上的一个置换。上的一个置换。有限群的阶：有限群的阶：G的元素个数称为的元素个数称为G的阶，记为的阶，记为|G|置换置换设设X是一个有限集，是一个有限集，是是X到到X的一个一一变换，那么称的一个一一变换，那么称 是是X上的一个置换上的一个置换：1a1，2a2

19、，nan，置换的一种记号置换的一种记号注意：上述记号下，同一置换用这样的表示有注意：上述记号下，同一置换用这样的表示有n!种，但关种，但关键的对应关系不变，只有一种。键的对应关系不变，只有一种。正三角形正三角形ABC的变换的变换正三角形正三角形ABC的旋转变换和轴对称变换的旋转变换和轴对称变换正三角形的所有变换正三角形的所有变换沿中心逆时针旋转，有沿中心逆时针旋转，有0，120，240三种三种旋转旋转0，0：AA，BB，CC旋转旋转120，1：AC，BA，CB旋转旋转240，2：AB，BC，CA沿对称轴翻转沿对称轴翻转180，也有三种：，也有三种：沿沿AO轴翻转，轴翻转，3：AA，BC，CB沿

20、沿BO轴翻转，轴翻转，4：AC，BB，CA沿沿CO轴翻转，轴翻转，5：AB，BA，CC正三角形的所有变换正三角形的所有变换沿中心逆时针旋转沿中心逆时针旋转旋转旋转0旋转旋转120旋转旋转240沿对称轴翻转沿对称轴翻转180沿沿AO轴翻转，沿轴翻转，沿BO轴翻转轴翻转沿沿CO轴翻转轴翻转置换的乘法运算置换的乘法运算置换的乘法运算是置换的连接置换的乘法运算是置换的连接X的所有的所有n!个置换关于置换的乘法构成一个群个置换关于置换的乘法构成一个群G，记为记为Sn，其单位元是，其单位元是举例：设举例：设 3=，2=3与与 2的积为置换的积为置换 5。循环循环循环循环 是这样一个置换，满足是这样一个置换

21、，满足：a1a2，a2a3，aka1，但对其它的元素保持不变，但对其它的元素保持不变，称为称为k阶循环。阶循环。k阶循环可阶循环可记为：记为：k称为循环节长度称为循环节长度2阶循环阶循环也称为对换，简记为（也称为对换，简记为（a1a2）置换置换与循环与循环定理定理6.3每个置换都可以写成若干互不相交的循每个置换都可以写成若干互不相交的循环的乘积，且表示是唯一的。环的乘积，且表示是唯一的。例：置换例：置换可表示为可表示为(124)(35)(6)，其循环节数是其循环节数是32Burnside引理引理定义定义6.7等价：设等价：设G是有限集是有限集X上的置换群，点上的置换群，点a，b X称为称为“等

22、价等价”的，当且仅当，存在置换的，当且仅当，存在置换 G使得使得(a)=b，记为记为a b。轨道：在这种等价关系下，轨道：在这种等价关系下，X的元素形成的等价类称为的元素形成的等价类称为G的的轨道。轨道。a X所在的等价类所在的等价类Ea，即为即为a所在的所在的轨道。轨道。G的任意两个不同的轨道之交是空集。的任意两个不同的轨道之交是空集。等价类：集合等价类：集合X上的所有等价类构成上的所有等价类构成X的一个划分，等价类的一个划分，等价类的个数记为的个数记为L。a不动置换类不动置换类Za：设：设G是是X=1，2，n上的置换群。若上的置换群。若a X，G中使中使a保持不变的置换的全体保持不变的置换

23、的全体|有有 G，使使(a)=a，记为记为Za，叫做叫做G中使中使a保持不动的置换类保持不动的置换类，简称，简称a不动置不动置换类。换类。性质：对所有性质：对所有a X，|Ea|Za|=|G|成立。成立。证明证明略略C()：对于一个置换对于一个置换 G，及，及a X，若若(a)=a，则称则称a为为 的不动点。的不动点。的不动点的全体记为的不动点的全体记为C()。Burnside引理引理证明：略证明：略L：等价类的个数：等价类的个数|C()|：的不动点的全体的个数的不动点的全体的个数|Za|：G中使中使a保持不动的置换类保持不动的置换类个数个数|G|：置换群置换群G的元素个数的元素个数3Plya

24、定理定理定理定理6.4设设G=1，2，t是是X=a1,a2,an上一上一个置换群，用个置换群，用m种颜色对种颜色对X中的元素进行涂色，那么不中的元素进行涂色，那么不同的涂色方案数为同的涂色方案数为其中其中Cyc(Cyc(k k)是置换是置换 k k的循环节的个数。的循环节的个数。证明：略证明：略循环节个数计算循环节个数计算/输入：一个置换输入：一个置换perm，即一个排列即一个排列/返回：置换的最小周期，传回待求置换的循环节个数返回：置换的最小周期，传回待求置换的循环节个数numintpolya(int*perm,intn,int&num)inti,j,p,vMAXN=0,cycle=1;fo

25、r(num=i=0;in;i+)if(!vi)/vi=0表示元素表示元素i尚未处理过尚未处理过num+;p=i;for(j=0;!vpermp;j+)/j记录当前循环节长度记录当前循环节长度p=permp;vp=1;cycle*=j/gcd(cycle,j);returncycle;6.2实例研究实例研究6.2.1蛋糕蛋糕6.2.2杨辉三角形中的奇偶问题杨辉三角形中的奇偶问题6.2.3足球赛票足球赛票6.2.4棋盘格数棋盘格数6.2.5保险柜上锁保险柜上锁6.2.6弹球游戏弹球游戏6.2.7最少砝码最少砝码6.2.8环环6.2.9珍珠项链珍珠项链6.2.10统计棋局数统计棋局数6.2.1蛋糕蛋

26、糕问题描述问题描述瓦尔特夫人本周六邀请她的朋友吃晚饭。到那个时候，瓦尔特夫人本周六邀请她的朋友吃晚饭。到那个时候，她想准备一个大的蛋糕。晚饭后，她要把蛋糕切成几她想准备一个大的蛋糕。晚饭后，她要把蛋糕切成几块给他们中的每一人。瓦尔特夫人认为如果蛋糕块大块给他们中的每一人。瓦尔特夫人认为如果蛋糕块大小不一样，那么得到小块的客人会不高兴。因此，她小不一样，那么得到小块的客人会不高兴。因此，她将把蛋糕分成如下图所示的形状，即把蛋糕在中间切将把蛋糕分成如下图所示的形状，即把蛋糕在中间切割。割。为使蛋糕更可口，她要用各种为使蛋糕更可口，她要用各种不同颜色的果酱涂在上面。要不同颜色的果酱涂在上面。要知道，

27、相邻两块是不能有相同知道，相邻两块是不能有相同颜色的。如果这样的话，她会颜色的。如果这样的话，她会认为这两块当作一块看待。认为这两块当作一块看待。她发现，将她发现，将2种果酱放在种果酱放在3块蛋糕上是不可能做到的。但如块蛋糕上是不可能做到的。但如果将果将3种果酱放在种果酱放在3块蛋糕上，她发现有块蛋糕上，她发现有6种方法。而如果种方法。而如果将将4种果酱放在种果酱放在3块蛋糕上，她发现有块蛋糕上，她发现有24种方法。现在，瓦种方法。现在，瓦尔特夫人对果酱涂在蛋糕上的方法数感兴趣。她需要你的尔特夫人对果酱涂在蛋糕上的方法数感兴趣。她需要你的帮助，请你为她编写一个程序进行计算。也许方法数太多，帮助

28、，请你为她编写一个程序进行计算。也许方法数太多，因此瓦尔特夫人只要你告诉她方法数的最后一位数。因此瓦尔特夫人只要你告诉她方法数的最后一位数。注意：因客人不同，下图所示的注意：因客人不同，下图所示的2种方法是不同的。因此种方法是不同的。因此你不应混为一谈。你不应混为一谈。输入输入输入有多组测试数据。每一组测试数据由两个整数输入有多组测试数据。每一组测试数据由两个整数m，n组成，其中整数组成，其中整数m是果酱颜色数，整数是果酱颜色数，整数n是客人数，也是是客人数，也是蛋糕块数，蛋糕块数，(0m100，1n10000)。当输入当输入m=n=0时表示输入结束，这种情况你不必处理。时表示输入结束，这种情

29、况你不必处理。输出输出对每种情况，如输入描述中所说，输出将果酱放在蛋糕上对每种情况，如输入描述中所说，输出将果酱放在蛋糕上的方法数的个位数。的方法数的个位数。输入与输出样例输入与输出样例输入样例输入样例输出样例输出样例3 34 34 42 30 06440分析与讨论分析与讨论令令an表示这表示这n块蛋糕用块蛋糕用m种果酱的的摆设方案数。大蛋糕切成种果酱的的摆设方案数。大蛋糕切成n块后的形状如图所示，各块分别标记为块后的形状如图所示，各块分别标记为C1，C2，Cn。分两种情况：分两种情况：（1）C1和和Cn-1有相同的颜色有相同的颜色（2）C1和和Cn-1有不同的颜色有不同的颜色分析分析第一种情

30、况：第一种情况：C1，Cn-1颜色相同，颜色相同，Cn，C1，C2，Cn-2有有m-1种颜色可种颜色可用，；而且用，；而且C1，C2，Cn-2的着色方案与大蛋糕切成的着色方案与大蛋糕切成n-2块小蛋糕的着色方案一一对应。此时小蛋糕块小蛋糕的着色方案一一对应。此时小蛋糕Cn可用可用m-1种种颜色。这种情况，颜色。这种情况，n块蛋糕的颜色涂法数为块蛋糕的颜色涂法数为(m-1)an-2。第二种情况：第二种情况：C1与与Cn-1颜色不同，颜色不同，Cn的颜色可用的颜色可用m-2种。此时种。此时C1，C2，Cn-1的着色方案与大蛋糕切成的着色方案与大蛋糕切成n-1块小蛋糕的着色方案块小蛋糕的着色方案一一

31、对应。这种情况，一一对应。这种情况，n块蛋糕的颜色涂法数为块蛋糕的颜色涂法数为(m-2)an-1。结论：结论：参考程序参考程序#includeusingnamespacestd;intcomput(intn,intm)inti,ret,k=m-1;for(ret=1,i=0;imn)&(!(n=0&m=0)coutcomput(n,m)endl;return(0);6.2.2杨辉三角形中的奇偶问题杨辉三角形中的奇偶问题问题描述问题描述在如下所示的杨辉三角形中，第在如下所示的杨辉三角形中，第1行有行有1个奇数，第个奇数，第2行有行有2个奇数，第个奇数，第3，4，5，6行分别有行分别有2，4，2，

32、4个奇数。个奇数。11 11 2 11 3 3 11 4 6 4 1 1 5 10 10 5 11 6 15 20 15 6 1你的任务：对一般的正整数你的任务：对一般的正整数n，计算杨辉三角形中第计算杨辉三角形中第n行上行上奇数的个数。奇数的个数。输入与输出输入与输出输入输入输入有若干行。每一行上有一个正整数输入有若干行。每一行上有一个正整数n，（1n232）。）。输入直到文件结束。输入直到文件结束。输出输出对输入文件每行上的正整数对输入文件每行上的正整数n，输出杨辉三角形中第，输出杨辉三角形中第n行上奇数的个数。行上奇数的个数。输入样例输入样例输出样例输出样例348102484分析分析在杨

33、辉三角形中，将每行上的奇数用在杨辉三角形中，将每行上的奇数用1表示、偶数表示、偶数用用0表示，可得如下的简化的杨辉三角形，其中空表示，可得如下的简化的杨辉三角形，其中空白位置对应的行上是数白位置对应的行上是数0。构造下页所示的简化杨辉三角形图构造下页所示的简化杨辉三角形图图例图例有趣的规律有趣的规律34行上的行上的2个三角形与个三角形与12行上的三角形完全一样；行上的三角形完全一样；58行上稍大的行上稍大的2个三角形（底边个三角形（底边4个个1）与）与14行上的三角形行上的三角形完全一样；完全一样；916行上再稍大的行上再稍大的2个三角形（底边个三角形（底边8个个1）与）与18行上的三行上的三

34、角形完全一样；角形完全一样；第第16行上行上1的个数是第的个数是第8行上行上1的个数的的个数的2倍；倍；第第15行上行上1的个数是第的个数是第7行上行上1的个数的的个数的2倍；倍；第第8行上行上1的个数是第的个数是第4行上行上1的个数的的个数的2倍；倍；第第7行上行上1的个数是第的个数是第3行上行上1的个数的的个数的2倍；倍；计算公式计算公式给定行数给定行数n，记，记m=n-1的二进制表示为，的二进制表示为，用用g(m)表示第表示第m+1行上奇数的个数，则行上奇数的个数，则g(m)=2g()另一种分析方法另一种分析方法杨辉三角第杨辉三角第n行中奇数的项数是二项式行中奇数的项数是二项式的展开式中

35、系的展开式中系数为奇数的项数。数为奇数的项数。（1）(x+1)n-1中系数为奇数的项数中系数为奇数的项数=(x+1)n-1(mod2)中系数中系数非非0的项数；的项数；（2）(x+1)2(mod2)=(x2+1)(mod2)（3）(x+1)4(mod2)=(x4+1)(mod2)（4）(x+1)8(mod2)=(x8+1)(mod2)，等等等等将将n-1写为二进制数写为二进制数akak-1a1a0，那么那么分析分析对等式两边作对等式两边作mod2运算，运算，丢掉那些使丢掉那些使ai=0的项的项(mod2)。于是，于是，(x+1)n-1中系数为奇数的项数就是所有使中系数为奇数的项数就是所有使ai

36、=1=1的项的项 (mod 2)(mod 2)的乘积展开式中系数为奇数的项数。的乘积展开式中系数为奇数的项数。结论：杨辉三角形中第结论：杨辉三角形中第n行上奇数的个数为行上奇数的个数为6.2.3足球赛票足球赛票问题描述问题描述 一场激烈的足球赛开始前，售票工作正在紧张地进行中。一场激烈的足球赛开始前，售票工作正在紧张地进行中。每张球票每张球票为为50元。现有元。现有2n个人排队等待购票，其中有个人排队等待购票，其中有n个个人手持人手持50元的钞票，另外元的钞票，另外n个人手持个人手持100元的钞票，假设开元的钞票，假设开始售票时售票处没有零钱。问这始售票时售票处没有零钱。问这2n个人有多少种排

37、队方式，个人有多少种排队方式，使售票处不至出现找不开钱的局面？使售票处不至出现找不开钱的局面？输入输入输入的每行上有一个非负整数输入的每行上有一个非负整数n，（，（1n1000）。）。输出输出对输入每行上的整数对输入每行上的整数n，输出这，输出这2n个人的排队方式数。个人的排队方式数。输入与输出样例输入与输出样例输入样例输入样例输出样例输出样例34511分析分析令令f(m,n)表示有表示有m个人手持个人手持50元的钞票，元的钞票，n个人手持个人手持100元的元的钞票时共有的方案总数。钞票时共有的方案总数。1.n=0，f(m,0)=12.mn，f(m,n)=03.其它，考虑（其它，考虑（m+n）

38、个人排队购票个人排队购票1)第（第（m+n）个人手持个人手持100元的钞票元的钞票：有：有f(m,n-1)种种2)第（第（m+n）个人手持个人手持50元的钞票元的钞票：有：有f(m-1,n)种种由加法原理得由加法原理得f(m,n)=f(m-1,n)+f(m,n-1)综合，得：综合，得：6.2.4棋盘格数棋盘格数问题描述问题描述设设有有一一个个方方格格棋棋盘盘，求求出出该该棋棋盘盘中中包包含含有有多多少少个个正正方方形、多少个长方形（不包括正方形）。形、多少个长方形（不包括正方形）。输入输入有有若若干干个个棋棋盘盘，每每个个棋棋盘盘对对应应一一行行上上两两个个整整数数n，m，（ln100，1m1

39、00），），表示有一个表示有一个n m方格的棋盘。方格的棋盘。输出输出对输入的对输入的n m方格棋盘，输出正方形的个数与长方形方格棋盘，输出正方形的个数与长方形的个数。的个数。输入与输出样例输入与输出样例输入样例输入样例输出样例输出样例2 36 38 1032 94分析分析1.1.先考虑正方形的个数先考虑正方形的个数 边长为边长为k的正方形个数为的正方形个数为(n-k+1)(m-k+1)。2.2.再考虑长方形（包括正方形）的个数再考虑长方形（包括正方形）的个数 根据乘法原理，长方形和正方形的个数总计根据乘法原理，长方形和正方形的个数总计Total=(1+2+n)(1+2+m)3.3.长宽不等的

40、长方形个数为长宽不等的长方形个数为Rec_total=Total-Sq_total4.因此，长宽不等的长方形个数为因此，长宽不等的长方形个数为Rec_total=TotalSq_total6.2.5保险柜上锁保险柜上锁问题描述问题描述有有n个人组成的委员会负责保管一个保险箱。该委员会个人组成的委员会负责保管一个保险箱。该委员会经过研究形成决议：委员会中任何经过研究形成决议：委员会中任何m个委员同时到场就个委员同时到场就能打开保险柜，而任何能打开保险柜，而任何m-1个委员则不能打开保险柜。个委员则不能打开保险柜。你的任务是计算至少要给这个保险柜加多少把锁才能你的任务是计算至少要给这个保险柜加多少

41、把锁才能满足上述要求。满足上述要求。输入输入输入文件中有若干行。每一行上有两个正整数输入文件中有若干行。每一行上有两个正整数n和和m是是一组测试数据，（一组测试数据，（1n50，0mn）。）。输入直到文件输入直到文件结束。结束。输出输出对输入文件中的每组测试数据对输入文件中的每组测试数据n，m，输出满足要求的输出满足要求的锁的最少数目。锁的最少数目。输入与输出样例输入与输出样例输入样例输入样例 输出样例输出样例 2 15 412 5 110495（2）如果取）如果取k=，即加即加把锁，那么可以按问题要把锁，那么可以按问题要求向委员们分配钥匙。求向委员们分配钥匙。现从这两方面考虑：现从这两方面考

42、虑：（1）首先确定）首先确定k：作一个表格可以说明之作一个表格可以说明之 分析分析设设k为符合要求的最少的锁的把数。记为符合要求的最少的锁的把数。记Ai是第是第i个委员可以个委员可以打开的锁的集合，打开的锁的集合，A=1，2，3，k是所有锁的集合。是所有锁的集合。问题的要求：问题的要求：A1，A2，An中任何中任何m个的并是集合个的并是集合A，而任何而任何m-1个集合的并不是集合个集合的并不是集合A。向委员们分配钥匙的一种方案向委员们分配钥匙的一种方案任意取出任意取出m-1列（即取列（即取m-1个委员），个委员），记为（记为（j1，j2，jm-1）。）。m-1列列（j1，j2，jm-1）对应于

43、一个行对应于一个行row，该行上与该行上与m-1个列个列j1，j2，jm-1交叉处的格子中都是交叉处的格子中都是0，而其，而其他格子都是他格子都是1。将编号为将编号为row的钥匙分配给编号不的钥匙分配给编号不是是j1，j2，jm-1的所有其他委员，的所有其他委员，即可满足要求。即可满足要求。计算的问题，这是容易的。计算的问题，这是容易的。A1A2An12k6.2.6弹球游戏弹球游戏问题描述问题描述有一个三角形容器，上部开一个小口，里面如图中所示按有一个三角形容器，上部开一个小口，里面如图中所示按层整齐地放了许多小圆棍作为阻挡物，第层整齐地放了许多小圆棍作为阻挡物，第n层有层有n根阻挡物。根阻挡

44、物。弹球游戏时，小球从容器上部的口子中间处跌落，碰到第弹球游戏时，小球从容器上部的口子中间处跌落，碰到第一层挡物后等概率地向两侧跌落，碰到与之相邻的第二层一层挡物后等概率地向两侧跌落，碰到与之相邻的第二层两个阻挡物中的一个，再向两侧跌落第三层阻挡物，如此两个阻挡物中的一个，再向两侧跌落第三层阻挡物，如此一直下跌最终小球落入底层。一直下跌最终小球落入底层。在容器底层放了若干奖品。如下页图所示的在容器底层放了若干奖品。如下页图所示的6层容器中，层容器中，A，G区奖品最好，区奖品最好，B，F区奖品次之，区奖品次之，C，E区奖品第三，区奖品第三，D区奖品最差。为方便起见，约定区奖品最差。为方便起见，约

45、定A，B，C，D，E，F，G区分别用区分别用0，1，2，3，4，5，6区表示。区表示。弹球游戏示意图弹球游戏示意图一般地，如容器有一般地，如容器有n层，相应地得到不同大小的容器，其层，相应地得到不同大小的容器，其底层根据位置不同也放了相应的奖品。该区域奖品的价值底层根据位置不同也放了相应的奖品。该区域奖品的价值与小球落入该区域的概率反向相关，即：区域的概率越大，与小球落入该区域的概率反向相关，即：区域的概率越大，该区域奖品的价值越小。该区域奖品的价值越小。你的任务：计算弹球落入某个区域的概率。你的任务：计算弹球落入某个区域的概率。输入输入输入文件中有若干行。每一行上有两个整数输入文件中有若干行

46、。每一行上有两个整数n，m，（1n65535，0mn）。）。输入直到文件结束。输入直到文件结束。输出输出对输入中每行上的正整数对输入中每行上的正整数n，m，输出弹球落入有输出弹球落入有n层的三层的三角形容器底层中第角形容器底层中第m个区的概率（四舍五入后保留个区的概率（四舍五入后保留6位小位小数）。数）。输入与输出样例输入与输出样例输入样例输入样例 输出样例输出样例 3 24 18 510 3 0.3750000.2500000.2187500.117188 分析分析如果如果m=0或或m=n，那么小球落入那么小球落入m区的概率等于它肩上一区的概率等于它肩上一个区域概率的个区域概率的1/2。如果

47、如果0m(3s-1)/2时，时，s-1个砝码不够。个砝码不够。其中，其中，i=0，1或或-1，（，（i=1，2，3，s）。系数）。系数 i=-1表表示砝码与物体放在同一托盘，系数示砝码与物体放在同一托盘，系数 i=1表示砝码与物体放表示砝码与物体放在不同托盘。在不同托盘。分析分析可证，当可证，当a2=3s-1时，时，(i=1，2，3，s)，满足，满足的任何整数的任何整数k都可表示为（都可表示为（*）的形式。）的形式。事实上，记事实上，记M=，那么显然，指数在显然，指数在-M与与M之间的项都出现了。之间的项都出现了。这表明，当这表明，当n 满足满足时，所需的砝码为时，所需的砝码为s个，可个，可以

48、称出重量以称出重量n，且表示方式唯一。且表示方式唯一。6.2.8环环他在一个环上写了他在一个环上写了n个字母个字母“X”和和“E”。他注意到一些他注意到一些不同的字母序列用循环移动可以变到另一个（这表示这实不同的字母序列用循环移动可以变到另一个（这表示这实际上是同一个环形串）。例如，串际上是同一个环形串）。例如，串“XXE”-“XEX”-“EXX”实际上都是相同的。他想知道对于实际上都是相同的。他想知道对于n个字母有多少个字母有多少种不同的环形串出现。请您帮助他找出答案。种不同的环形串出现。请您帮助他找出答案。输入输入每行有一个整数每行有一个整数n，（，（1n200000）。）。输出输出输出长

49、度为输出长度为n的环形串的个数的环形串的个数输入样例输入样例输出样例输出样例3446分析分析环只能顺时针或逆时针旋转环只能顺时针或逆时针旋转顺时针方向移动顺时针方向移动k k个位置等同于逆时针方向转动个位置等同于逆时针方向转动n-kn-k个位置个位置 一共有一共有n n个置换，记个置换，记G=G=0 0，1 1，2 2，n-1n-1 逆时针旋转逆时针旋转k k个位置，那么个位置，那么 k k=循环节个数求法循环节个数求法以以n=8，k=6时的置换时的置换 6=为例为例考查考查循环节个数。循环节个数。易见，易见，6=(0642)(1753)有有2个循环节。个循环节。一般情况下，可以证明一般情况下

50、，可以证明 k的循环节个数是的循环节个数是GCD(n,k)，因此，因此没有必要构建置换没有必要构建置换（或进行分解）（或进行分解）。长度为长度为n的环形串的个数的环形串的个数根据根据Plya定理，长度为定理，长度为n的环形串的个数的环形串的个数L=L的数目很大，实际编程时需要自己编写计算幂函数的数目很大，实际编程时需要自己编写计算幂函数pow(m,x)的程序，可能需要用到高精度计算的程序，可能需要用到高精度计算 6.2.9珍珠项链珍珠项链问题描述问题描述n颗红、蓝、绿三种颜色的珍珠串起来形成一个环形项链，颗红、蓝、绿三种颜色的珍珠串起来形成一个环形项链，（n24）。）。如果将沿着中心旋转或者沿