《第6章-组合数学中的程序设计优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第6章-组合数学中的程序设计优秀PPT.ppt（102页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章主要内容本章主要内容6.1组合数学中有关概念与公式组合数学中有关概念与公式6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法6.1.2母函数母函数6.1.3容斥原理与错排容斥原理与错排6.1.4Polya定理定理6.2实例探讨实例探讨6.1组合数学中有关概念与公式组合数学中有关概念与公式6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法1 1排列与组合的基本概念和公式排列与组合的基本概念和公式排列、相异元素可重复的排列排列、相异元素可重复的排列组合、相异元素可重复的组合组合、相异元素可重复的组合6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法在多项式在
2、多项式 的绽开式中的项的绽开式中的项 的系数的系数 不定方程不定方程 的有非负整数解的个数为的有非负整数解的个数为设设n n是一个正整数，令是一个正整数，令QnQn表示在表示在11，2 2，nn中不允许中不允许出现两个连续数字的排列方法数，则有出现两个连续数字的排列方法数，则有Qn=Qn=6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法2全排列的生成算法全排列的生成算法全排列的生成算法有：字典序法、递增进位制数法、全排列的生成算法有：字典序法、递增进位制数法、递减进位制数法和邻位对换法等递减进位制数法和邻位对换法等全排列的字典序算法全排列的字典序算法问题：对于给定的一个全排列问题
3、：对于给定的一个全排列P P，要生成，要生成P P的下一个的下一个排列排列Q Q6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法字典序全排列：字典序全排列：给定给定n个元素的集合个元素的集合x1，x2，x3，xn，对，对X中的中的元素规定了一个先后关系。在两个排列中，按字典序元素规定了一个先后关系。在两个排列中，按字典序方式对它们的位从左到右每位比较，较小的字符对应方式对它们的位从左到右每位比较，较小的字符对应的排列较先，按这样的序生成的全排列称为字典序全的排列较先，按这样的序生成的全排列称为字典序全排列。排列。给定排列给定排列P，求下一个排列，求下一个排列Q例：求例：求X=1，
4、2，3，4，5，6，7上排列上排列P=2637541的的下一个排列下一个排列Q1)从右到左找出比右边数字小的第一个数，即从右到左找出比右边数字小的第一个数，即3。2)再从右到左考察比再从右到左考察比3大的第一个数，是大的第一个数，是43)将将3与与4对换位置，得对换位置，得26475314)将得到的排列将得到的排列2647531从从4后面的后面的7531翻转得翻转得13575)把前缀把前缀264接在接在1357的前面得的前面得2641357，它就是所求的，它就是所求的排列排列2647531的下一个排列。的下一个排列。给定排列给定排列P，求下一个排列，求下一个排列Q算法算法设设X=1X=1，2
5、2，nn，求，求P=a1a2anP=a1a2an的下一个排列：的下一个排列：在在P P中从右到左找寻右边比左边大的数的第一个位置中从右到左找寻右边比左边大的数的第一个位置j j，即，即j=maxi|aiai+1 j=maxi|aiajk=maxi|aiaj。此时排列。此时排列P P形如形如a1a2aj-1aj a1a2aj-1aj aj+1ak-1 akak+1anaj+1ak-1 akak+1an。对换对换ajaj，akak，并将，并将aj+1ak-1ajak+1anaj+1ak-1ajak+1an翻转，得翻转，得Q=Q=a1a2aj-1akanak-1ajak+1ana1a2aj-1aka
6、nak-1ajak+1an即为即为P P的下一个排列。的下一个排列。6.1.1排列与组合及有关的生成算法排列与组合及有关的生成算法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.字典序
7、全排列与序号的转换字典序全排列与序号的转换字典序全排列的序号字典序全排列的序号记记P=a1a2an。记。记ki为元素为元素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-
8、(i-)/因因子子为为(n-i-1)!，留留意意下下标标从从0起先起先for(j=i+1;jn;j+)if(pj=0;i-)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个元素取个元素取m个的全部组合从个的全部组合从1起先从小到大编序，组合起先从小到大编序，组合3579的序号是多少？的序号是多少？一种计算方法：首
9、位小于一种计算方法：首位小于3的组合的个数为的组合的个数为91；首位是；首位是3，第，第2位小于位小于5的组合的个数为的组合的个数为10；前；前2位是位是35，第，第3位位小于小于7的组合的个数为的组合的个数为3；前；前3位是位是357，第，第4位小于位小于9的的组合的个数为组合的个数为1。全部这些数之和。全部这些数之和105，加上它本身的，加上它本身的1个号，得组合个号，得组合3579的序号是的序号是106。另一种思路由组合求序号另一种思路由组合求序号考虑从当前考察的组合的后面有多少个组合。考虑从当前考察的组合的后面有多少个组合。/传入传入n、m及组合及组合c，返回，返回c的序号的序号num
10、/下面的下面的comb(n,m)是是n个元素取个元素取m个的组合数个的组合数intcomb2num(intn,intm,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-=co
11、mb(n-j,m-i-1),j+;ci=j;6.1.2母函数母函数母函数：给定序列母函数：给定序列a0、a1、a2、an、那么函数那么函数G(x)=a0+a1x+a2x2+akxk+称为序列称为序列a0、a1、a2、an、的母函数（也叫生成函数）。的母函数（也叫生成函数）。给定一个序列，可确定对应的母函数；反过来，给定一给定一个序列，可确定对应的母函数；反过来，给定一个母函数，那么也能确定对应的序列。个母函数，那么也能确定对应的序列。例：斐波那契数列例：斐波那契数列an，n=0，1，2，a0=a1=1，an=an-1+an-2。对应的母函数可表示为。对应的母函数可表示为可求得可求得举例举例问题
12、描述问题描述 小明手中有小明手中有3 3张一元张一元,2,2张张2 2元和元和3 3张张5 5元的钱币元的钱币,问小明都能问小明都能买价值为多少的物品？对每种价值的物品他有几种付款买价值为多少的物品？对每种价值的物品他有几种付款方法？如小明手中有方法？如小明手中有k k张一元，张一元，m m张张2 2元和元和n n张张5 5元的钱币，元的钱币，结果又如何？结果又如何？输入输入 输入的第一行是一个整数输入的第一行是一个整数T T，（，（1T101T10）,表示测表示测试数据的个数。接下来有试数据的个数。接下来有T T行，每行上有行，每行上有3 3个非负整数个非负整数k k，m m，n n，（，（
13、1k1k，m m，n10n10），分别表示一元、二元和五），分别表示一元、二元和五元的钱币数。元的钱币数。k k，m m，n n中至少有一个非中至少有一个非0 0。输出输出 对输入中的三种钱币数，输出小明能买物品的价值对输入中的三种钱币数，输出小明能买物品的价值总数以及全部的付款方法数。总数以及全部的付款方法数。输入输入与输出与输出样例样例输入样例输入样例13 2 3输出样例输出样例22 47对实例的说明对实例的说明k=3，m=2，n=3一元、二元、五元钱币对应的能买物品的生成函数一元、二元、五元钱币对应的能买物品的生成函数小明能买的物品对应的生成函数为小明能买的物品对应的生成函数为结论结论小
14、明可以买价值分别为小明可以买价值分别为0，1，2，21，22元的物品，元的物品，即即22种非零的钱数，并且付款的方法数分别为种非零的钱数，并且付款的方法数分别为0，1，2，2，2，3，2，3，2，2，3，2，3，2，2，3，2，3，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错排错
15、排当当n 1时，若时，若n个元素个元素1，2，n的排列的排列P其每个元素都其每个元素都不在原来的位置上（即元素不在原来的位置上（即元素k不在位置不在位置k上），则该排列称上），则该排列称为错排。为错排。n个元素的集合个元素的集合1，2，n的错排个数为的错排个数为Dn。有递推关系有递推关系很简洁得到关于很简洁得到关于Dn的关系式的关系式Dn=3抽屉原理抽屉原理1.1.将将m m个物品放入个物品放入n n个抽屉，则其中至少有一个抽屉里含有个抽屉，则其中至少有一个抽屉里含有 个物品个物品2.2.设设m1m1、m2m2，m1m1，mn mn都是正整数，且将都是正整数，且将n n个物品放入个物品放入n
16、n个抽屉，则：第一个抽屉至少有个抽屉，则：第一个抽屉至少有m1m1个物品，其次个抽个物品，其次个抽屉至少有屉至少有m2m2个物品，个物品，第，第n n个抽屉至少有个抽屉至少有mnmn个物品，个物品，至少其中之一必定成立。至少其中之一必定成立。6.1.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)
17、(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=ea*x=x*a=e。那么称（那么称（G G，*）为一个群。）为一个群。群的例子群的例子例例1 1：设：设G=1,-1G=1,-1，*为一般乘法，那么（为一般乘法，那么（G G，*）为一个群，）为一个群，1 1是单位元。是单位元。例例2 2：设：设G=0G=0，1 1，2 2，3 3，m-1m-1，*为一般的模为一般的模m m加法，那加法，那么（么
18、（G G，*）为一个群，）为一个群，0 0是单位元。是单位元。例例3 3：设：设m=10m=10，记，记G=1G=1，3 3，7 7，99，那么，那么G G关于模关于模1010的乘法构的乘法构成一个群。成一个群。子群、交换群子群、交换群子群：设（子群：设（G，*）是任何一个群，又设）是任何一个群，又设H是是G的子集，若的子集，若（H，*）是一个群，则称（）是一个群，则称（H，*）是（）是（G，*）的一个群，）的一个群，简称简称H是是G的子群。的子群。交换群：设（交换群：设（G，*）是一个群，假如对于）是一个群，假如对于G的任何元素的任何元素a，b，有，有ab=ba，那么称，那么称G为交换群。为
19、交换群。置换：设置换：设X是一个有限集，是一个有限集，是是X到到X的一个一一变换，那的一个一一变换，那么称么称是是X上的一个置换。上的一个置换。有限群的阶：有限群的阶：G的元素个数称为的元素个数称为G的阶，记为的阶，记为|G|置换置换设设X是一个有限集，是一个有限集，是是X到到X的一个一一变换，那么称的一个一一变换，那么称 是是X上的一个置换上的一个置换：1a1，2a2，nan，置换的一种记号置换的一种记号留意：上述记号下，同一置换用这样的表示有留意：上述记号下，同一置换用这样的表示有n!种，但关键种，但关键的对应关系不变，只有一种。的对应关系不变，只有一种。正三角形正三角形ABC的变换的变换
20、正三角形正三角形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沿沿BO轴翻转，轴翻转，4：AC，BB，CA沿沿CO轴翻转，轴翻转，5：AB，BA，CC正三角形的全部变换正三角形的全部变换沿中心逆时针旋转沿中心逆时针旋转旋转旋转0旋转旋转120旋转旋转240沿对称轴翻转沿对称轴翻转180沿沿A
21、O轴翻转，沿轴翻转，沿BO轴翻转轴翻转沿沿CO轴翻转轴翻转置换的乘法运算置换的乘法运算置换的乘法运算是置换的连接置换的乘法运算是置换的连接 X X的全部的全部n!n!个置换关于置换的乘法构成一个群个置换关于置换的乘法构成一个群G G，记为，记为SnSn，其单位元是其单位元是举例：设举例：设 3=，2=3与与 2的积为置换的积为置换 5。循环循环循环循环是这样一个置换，满足是这样一个置换，满足：a1a1 a2a2，a2a2 a3a3，akak a1a1，但对其它的元素保持不变，称为，但对其它的元素保持不变，称为k k阶循环。阶循环。k k阶循环可记为：阶循环可记为：k称为循环节长度称为循环节长度
22、2阶循环阶循环也称为对换，简记为（也称为对换，简记为（a1a2）置换置换与循环与循环定理定理6.3每个置换都可以写成若干互不相交的循每个置换都可以写成若干互不相交的循环的乘积，且表示是唯一的。环的乘积，且表示是唯一的。例：置换例：置换可表示为可表示为(124)(35)(6)，其循环节数是其循环节数是32Burnside引理引理定义定义6.7等价：设等价：设G是有限集是有限集X上的置换群，点上的置换群，点a，b X称为称为“等价等价”的，当且仅当，存在置换的，当且仅当，存在置换 G使得使得(a)=b，记为，记为a b。轨道：在这种等价关系下，轨道：在这种等价关系下，X的元素形成的等价类称为的元素
23、形成的等价类称为G的的轨道。轨道。a X所在的等价类所在的等价类Ea，即为，即为a所在的轨道。所在的轨道。G的随意两个不同的轨道之交是空集。的随意两个不同的轨道之交是空集。等价类：集合等价类：集合X上的全部等价类构成上的全部等价类构成X的一个划分，等价类的一个划分，等价类的个数记为的个数记为L。a不动置换类不动置换类Za：设：设G是是X=1，2，n上的置换群。若上的置换群。若a X，G中使中使a保持不变的置换的全体保持不变的置换的全体|有有 G，使，使(a)=a，记为，记为Za，叫做，叫做G中使中使a保持不动的置换类，保持不动的置换类，简称简称a不动置换类。不动置换类。性质：对全部性质：对全部
24、a X，|Ea|Za|=|G|成立。成立。证明证明 略略C()：对于一个置换：对于一个置换 G，及，及a X，若，若(a)=a，则，则称称a为为的不动点。的不动点。的不动点的全体记为的不动点的全体记为C()。Burnside引理引理证明：略证明：略L：等价类的个数：等价类的个数|C()|：的不动点的全体的个数的不动点的全体的个数|Za|：G中使中使a保持不动的置换类保持不动的置换类个数个数|G|：置换群置换群G的元素个数的元素个数3Plya定理定理定理定理6.4设设G=1，2，t是是X=a1,a2,an上一上一个置换群，用个置换群，用m种颜色对种颜色对X中的元素进行涂色，那么不中的元素进行涂色
25、，那么不同的涂色方案数为同的涂色方案数为其中其中Cyc(Cyc(k k)是置换是置换 k k的循环节的个数。的循环节的个数。证明：略证明：略循环节个数计算循环节个数计算/输入：一个置换输入：一个置换perm，即一个排列，即一个排列/返回：置换的最小周期，传回待求置换的循环节个数返回：置换的最小周期，传回待求置换的循环节个数numintpolya(int*perm,intn,int&num)inti,j,p,vMAXN=0,cycle=1;for(num=i=0;in;i+)if(!vi)/vi=0表示元素表示元素i尚未处理过尚未处理过num+;p=i;for(j=0;!vpermp;j+)/j
26、记录当前循环节长度记录当前循环节长度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蛋糕蛋糕问题描述问题描述瓦尔特夫人本周六邀请她的挚友吃晚饭。到那个时候，瓦尔特夫人本周六邀请她的挚友吃晚饭。到那个时候，她想准备一个大的蛋糕。晚饭后，她要把蛋糕
27、切成几她想准备一个大的蛋糕。晚饭后，她要把蛋糕切成几块给他们中的每一人。瓦尔特夫人认为假如蛋糕块大块给他们中的每一人。瓦尔特夫人认为假如蛋糕块大小不一样，那么得到小块的客人会不兴奋。因此，她小不一样，那么得到小块的客人会不兴奋。因此，她将把蛋糕分成如下图所示的形态，即把蛋糕在中间切将把蛋糕分成如下图所示的形态，即把蛋糕在中间切割。割。为使蛋糕更可口，她要用各种为使蛋糕更可口，她要用各种不同颜色的果酱涂在上面。要不同颜色的果酱涂在上面。要知道，相邻两块是不能有相同知道，相邻两块是不能有相同颜色的。假如这样的话，她会颜色的。假如这样的话，她会认为这两块当作一块看待。认为这两块当作一块看待。她发觉，
28、将她发觉，将2种果酱放在种果酱放在3块蛋糕上是不行能做到的。但假块蛋糕上是不行能做到的。但假如将如将3种果酱放在种果酱放在3块蛋糕上，她发觉有块蛋糕上，她发觉有6种方法。而假如种方法。而假如将将4种果酱放在种果酱放在3块蛋糕上，她发觉有块蛋糕上，她发觉有24种方法。现在，瓦种方法。现在，瓦尔特夫人对果酱涂在蛋糕上的方法数感爱好。她须要你的尔特夫人对果酱涂在蛋糕上的方法数感爱好。她须要你的帮助，请你为她编写一个程序进行计算。或许方法数太多，帮助，请你为她编写一个程序进行计算。或许方法数太多，因此瓦尔特夫人只要你告知她方法数的最终一位数。因此瓦尔特夫人只要你告知她方法数的最终一位数。留意：因客人不
29、同，下图所示的留意：因客人不同，下图所示的2种方法是不同的。因此种方法是不同的。因此你不应混为一谈。你不应混为一谈。输入输入输入有多组测试数据。每一组测试数据由两个整数输入有多组测试数据。每一组测试数据由两个整数m，n组成，其中整数组成，其中整数m是果酱颜色数，整数是果酱颜色数，整数n是客人数，也是是客人数，也是蛋糕块数，蛋糕块数，(0m100，1n10000)。当输入当输入m=n=0时表示输入结束，这种状况你不必处理。时表示输入结束，这种状况你不必处理。输出输出对每种状况，如输入描述中所说，输出将果酱放在蛋糕上对每种状况，如输入描述中所说，输出将果酱放在蛋糕上的方法数的个位数。的方法数的个位
30、数。输入与输出样例输入与输出样例分析与探讨分析与探讨令令an表示这表示这n块蛋糕用块蛋糕用m种果酱的的摆设方案数。大蛋糕切种果酱的的摆设方案数。大蛋糕切成成n块后的形态如图所示，各块分别标记为块后的形态如图所示，各块分别标记为C1，C2，Cn。分两种状况：分两种状况：（1）C1和和Cn-1有相同的颜色有相同的颜色（2）C1和和Cn-1有不同的颜色有不同的颜色分析分析第一种状况：第一种状况：C1，Cn-1颜色相同，颜色相同，Cn，C1，C2，Cn-2有有m-1种种颜色可用，；而且颜色可用，；而且C1，C2，Cn-2的着色方案与大蛋的着色方案与大蛋糕切成糕切成n-2块小蛋糕的着色方案一一对应。此时
31、小蛋糕块小蛋糕的着色方案一一对应。此时小蛋糕Cn可用可用m-1种颜色。这种状况，种颜色。这种状况，n块蛋糕的颜色涂法数为块蛋糕的颜色涂法数为(m-1)an-2。其次种状况：其次种状况：C1与与Cn-1颜色不同，颜色不同，Cn的颜色可用的颜色可用m-2种。此时种。此时C1，C2，Cn-1的着色方案与大蛋糕切成的着色方案与大蛋糕切成n-1块小蛋糕的着块小蛋糕的着色方案一一对应。这种状况，色方案一一对应。这种状况，n块蛋糕的颜色涂法数为块蛋糕的颜色涂法数为(m-2)an-1。结论：结论：参考程序参考程序#includeusingnamespacestd;intcomput(intn,intm)int
32、i,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，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行上
33、行上奇数的个数。奇数的个数。输入与输出输入与输出输入输入输入有若干行。每一行上有一个正整数输入有若干行。每一行上有一个正整数n，（1n232）。）。输入直到文件结束。输入直到文件结束。输出输出对输入文件每行上的正整数对输入文件每行上的正整数n，输出杨辉三角形中第，输出杨辉三角形中第n行上奇数的个数。行上奇数的个数。分析分析在杨辉三角形中，将每行上的奇数用在杨辉三角形中，将每行上的奇数用1表示、偶数表示、偶数用用0表示，可得如下的简化的杨辉三角形，其中空表示，可得如下的简化的杨辉三角形，其中空白位置对应的行上是数白位置对应的行上是数0。构造下页所示的简化杨辉三角形图构造下页所示的简化杨辉三角形图
34、图例图例好玩的规律好玩的规律34行上的行上的2个三角形与个三角形与12行上的三角形完全一样；行上的三角形完全一样；58行上稍大的行上稍大的2个三角形（底边个三角形（底边4个个1）与）与14行上的三角形行上的三角形完全一样；完全一样；916行上再稍大的行上再稍大的2个三角形（底边个三角形（底边8个个1）与）与18行上的三行上的三角形完全一样；角形完全一样；第第16行上行上1的个数是第的个数是第8行上行上1的个数的的个数的2倍；倍；第第15行上行上1的个数是第的个数是第7行上行上1的个数的的个数的2倍；倍；第第8行上行上1的个数是第的个数是第4行上行上1的个数的的个数的2倍；倍；第第7行上行上1的
35、个数是第的个数是第3行上行上1的个数的的个数的2倍；倍；计算公式计算公式给定行数给定行数n，记，记m=n-1的二进制表示为，的二进制表示为，用用g(m)表示第表示第m+1行上奇数的个数，则行上奇数的个数，则g(m)=2g()另一种分析方法另一种分析方法杨辉三角第杨辉三角第n行中奇数的项数是二项式行中奇数的项数是二项式的绽开式中系的绽开式中系数为奇数的项数。数为奇数的项数。（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)(m
36、od2)（4）(x+1)8(mod2)=(x8+1)(mod2)，等等，等等将将n-1写为二进制数写为二进制数akak-1a1a0，那么，那么分析分析对等式两边作对等式两边作mod2运算，丢掉那些使运算，丢掉那些使ai=0的项的项(mod2)。于是，于是，(x+1)n-1中系数为奇数的项数就是全部使中系数为奇数的项数就是全部使ai=1的项的项(mod2)的乘积绽开式中系数为奇数的项数。的乘积绽开式中系数为奇数的项数。结论：杨辉三角形中第结论：杨辉三角形中第n行上奇数的个数为行上奇数的个数为6.2.3足球赛票足球赛票问题描述问题描述 一场激烈的足球赛起先前，售票工作正在惊惶地进行中。一场激烈的足
37、球赛起先前，售票工作正在惊惶地进行中。每张球票为每张球票为5050元。现有元。现有2n2n个人排队等待购票，其中有个人排队等待购票，其中有n n 个个人手持人手持5050元的钞票，另外元的钞票，另外n n个人手持个人手持100100元的钞票，假设起元的钞票，假设起先售票时售票处没有零钱。问这先售票时售票处没有零钱。问这2n2n个人有多少种排队方式，个人有多少种排队方式，使售票处不至出现找不开钱的局面？使售票处不至出现找不开钱的局面？输入输入 输入的每行上有一个非负整数输入的每行上有一个非负整数n n，（，（1n10001n1000）。）。输出输出 对输入每行上的整数对输入每行上的整数n n，输
38、出这，输出这2n2n个人的排队方式数。个人的排队方式数。输入与输出样例输入与输出样例分析分析令令f(m,n)表示有表示有m个人手持个人手持50元的钞票，元的钞票，n个人手持个人手持100元的元的钞票时共有的方案总数。钞票时共有的方案总数。1.n=0，f(m,0)=12.mn，f(m,n)=03.其它，考虑（其它，考虑（m+n）个人排队购票个人排队购票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)综合，
39、得：综合，得：6.2.4棋盘格数棋盘格数问题描述问题描述设设有有一一个个方方格格棋棋盘盘，求求出出该该棋棋盘盘中中包包含含有有多多少少个个正正方方形、多少个长方形（不包括正方形）。形、多少个长方形（不包括正方形）。输入输入有有若若干干个个棋棋盘盘，每每个个棋棋盘盘对对应应一一行行上上两两个个整整数数n，m，（ln100，1m100），表示有一个），表示有一个n m方格的棋盘。方格的棋盘。输出输出对输入的对输入的n m方格棋盘，输出正方形的个数与长方形方格棋盘，输出正方形的个数与长方形的个数。的个数。输入与输出样例输入与输出样例分析分析1.1.先考虑正方形的个数先考虑正方形的个数2.2.边长为边
40、长为k k的正方形个数为的正方形个数为(n-k+1)(n-k+1)(m-(m-k+1)k+1)。3.3.再考虑长方形（包括正方形）的个数再考虑长方形（包括正方形）的个数4.4.依据乘法原理，长方形和正方形的个数总依据乘法原理，长方形和正方形的个数总计计 Total=(1+2+n)Total=(1+2+n)(1+2+m)(1+2+m)5.5.长宽不等的长方形个数为长宽不等的长方形个数为Rec_total=Total-Rec_total=Total-Sq_total Sq_total 6.6.因此，长宽不等的长方形个数为因此，长宽不等的长方形个数为7.7.Rec_total=Total Sq_to
41、tal Rec_total=Total Sq_total6.2.5保险柜上锁保险柜上锁问题描述问题描述有有n个人组成的委员会负责保管一个保险箱。该委员会个人组成的委员会负责保管一个保险箱。该委员会经过探讨形成决议：委员会中任何经过探讨形成决议：委员会中任何m个委员同时到场个委员同时到场就能打开保险柜，而任何就能打开保险柜，而任何m-1个委员则不能打开保险柜。个委员则不能打开保险柜。你的任务是计算至少要给这个保险柜加多少把锁才能你的任务是计算至少要给这个保险柜加多少把锁才能满足上述要求。满足上述要求。输入输入输入文件中有若干行。每一行上有两个正整数输入文件中有若干行。每一行上有两个正整数n和和m
42、是是一组测试数据，（一组测试数据，（1n50，0mn）。输入直到文件）。输入直到文件结束。结束。输出输出对输入文件中的每组测试数据对输入文件中的每组测试数据n，m，输出满足要求的，输出满足要求的锁的最少数目。锁的最少数目。输入与输出样例输入与输出样例（2）假如取）假如取k=，即加，即加把锁，那么可以按问题要把锁，那么可以按问题要求向委员们安排钥匙。求向委员们安排钥匙。现从这两方面考虑：现从这两方面考虑：（1）首先确定）首先确定k：作一个表格可以说明之：作一个表格可以说明之 分析分析设设k为符合要求的最少的锁的把数。记为符合要求的最少的锁的把数。记Ai是第是第i个委员可以个委员可以打开的锁的集合
43、，打开的锁的集合，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）对应于一）对应于一个行个行row，该行上与，该行上与m-1个列个列j1，j2，jm-1交叉处的格子中都是交叉处的格子中都是0，而其他格子都是，而其他格子都是1。将编号为将编号为row的钥匙安排给编号
44、不的钥匙安排给编号不是是j1，j2，jm-1的全部其他委的全部其他委员，即可满足要求。员，即可满足要求。计算的问题，这是简洁的。计算的问题，这是简洁的。6.2.6弹球游戏弹球游戏问题描述问题描述有一个三角形容器，上部开一个小口，里面如图中所示按有一个三角形容器，上部开一个小口，里面如图中所示按层整齐地放了很多小圆棍作为阻挡物，第层整齐地放了很多小圆棍作为阻挡物，第n层有层有n根阻挡物。根阻挡物。弹球游戏时，小球从容器上部的口子中间处跌落，遇到第弹球游戏时，小球从容器上部的口子中间处跌落，遇到第一层挡物后等概率地向两侧跌落，遇到与之相邻的其次层一层挡物后等概率地向两侧跌落，遇到与之相邻的其次层两
45、个阻挡物中的一个，再向两侧跌落第三层阻挡物，如此两个阻挡物中的一个，再向两侧跌落第三层阻挡物，如此始终下跌最终小球落入底层。始终下跌最终小球落入底层。在容器底层放了若干奖品。如下页图所示的在容器底层放了若干奖品。如下页图所示的6层容器中，层容器中，A，G区奖品最好，区奖品最好，B，F区奖品次之，区奖品次之，C，E区奖品第三，区奖品第三，D区奖品最差。为便利起见，约定区奖品最差。为便利起见，约定A，B，C，D，E，F，G区分别用区分别用0，1，2，3，4，5，6区表示。区表示。弹球游戏示意图弹球游戏示意图一般地，如容器有一般地，如容器有n层，相应地得到不同大小的容器，其层，相应地得到不同大小的容
46、器，其底层依据位置不同也放了相应的奖品。该区域奖品的价值底层依据位置不同也放了相应的奖品。该区域奖品的价值与小球落入该区域的概率反向相关，即：区域的概率越大，与小球落入该区域的概率反向相关，即：区域的概率越大，该区域奖品的价值越小。该区域奖品的价值越小。你的任务：计算弹球落入某个区域的概率。你的任务：计算弹球落入某个区域的概率。输入输入输入文件中有若干行。每一行上有两个整数输入文件中有若干行。每一行上有两个整数n，m，（1n65535，0mn）。）。输入直到文件结束。输入直到文件结束。输出输出对输入中每行上的正整数对输入中每行上的正整数n，m，输出弹球落入有，输出弹球落入有n层的三层的三角形容
47、器底层中第角形容器底层中第m个区的概率（四舍五入后保留个区的概率（四舍五入后保留6位小位小数）。数）。输入与输出样例输入与输出样例分析分析假如假如m=0或或m=n，那么小球落入，那么小球落入m区的概率等于它肩上一区的概率等于它肩上一个区域概率的个区域概率的1/2。假如假如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，
48、3，s)，满足，满足的任何整数的任何整数k都可表示为（都可表示为（*）的形式。）的形式。事实上，记事实上，记M=，那么，那么明显，指数在明显，指数在-M与与M之间的项都出现了。之间的项都出现了。这表明，当这表明，当n满足满足时，所需的砝码为时，所需的砝码为s个，可个，可以称出重量以称出重量n，且表示方式唯一。，且表示方式唯一。6.2.8环环他在一个环上写了他在一个环上写了n n个字母个字母“X”“X”和和“E”“E”。他留意到一些。他留意到一些不同的字母序列用循环移动可以变到另一个（这表示这事不同的字母序列用循环移动可以变到另一个（这表示这事实上是同一个环形串）。例如，串实上是同一个环形串）。
49、例如，串“XXE”-“XEX”-“XXE”-“XEX”-“EXX”“EXX”事实上都是相同的。他想知道对于事实上都是相同的。他想知道对于n n个字母有多少个字母有多少种不同的环形串出现。请您帮助他找出答案。种不同的环形串出现。请您帮助他找出答案。输入输入每行有一个整数每行有一个整数n，（，（1n200000）。）。输出输出输出长度为输出长度为n的环形串的个数的环形串的个数分析分析环只能顺时针或逆时针旋转环只能顺时针或逆时针旋转顺时针方向移动顺时针方向移动k k个位置等同于逆时针方向转动个位置等同于逆时针方向转动n-kn-k个位置个位置 一共有一共有n n个置换，记个置换，记G=G=0 0，1
50、1，2 2，n-1n-1 逆时针旋转逆时针旋转k k个位置，那么个位置，那么 k k=循环节个数求法循环节个数求法以以n=8，k=6时的置换时的置换 6=为例为例考查考查循环节个数。循环节个数。易见，易见，6=(0642)(1753)有有2个循环节。个循环节。一般状况下，可以证明一般状况下，可以证明k的循环节个数是的循环节个数是GCD(n,k)，因，因此没有必要构建置换（或进行分解）。此没有必要构建置换（或进行分解）。长度为长度为n的环形串的个数的环形串的个数依据依据Plya定理，长度为定理，长度为n的环形串的个数的环形串的个数L=L的数目很大，实际编程时须要自己编写计算幂函数的数目很大，实际