《第6章 组合数学中的程序设计精选文档.ppt》由会员分享，可在线阅读，更多相关《第6章 组合数学中的程序设计精选文档.ppt（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 组合数学中的程序设计本讲稿第一页，共一百零一页本章主要内容本章主要内容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 Q本讲稿第五页，共一百零一页6.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接在接在13
5、57的前面得的前面得2641357，它就是所求的排列，它就是所求的排列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-1a
6、jak+1an即为即为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排列与组合及有关的生成算法排
7、列与组合及有关的生成算法4.字典序全排列与序号的转换字典序全排列与序号的转换字典序全排列的序号字典序全排列的序号记记P=a1a2an。记。记ki为元素为元素ai的逆序数，则排列的逆序数，则排列P P的序号为的序号为问题：给定排列的序号，如何求全排列？问题：给定排列的序号，如何求全排列？排列排列123458697的的逆序数分别为逆序数分别为000002010，序号为序号为345本讲稿第十页，共一百零一页给定排列的序号给定排列的序号/给定元素个数给定元素个数n，及全排列，及全排列p/返回字典序全排列下排列序号返回字典序全排列下排列序号numintperm2num(intn,int*p)inti,j
8、,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-)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个的所有组合从个的所有组合从
9、1开始开始从小到大编序，组合从小到大编序，组合3579的的序号是多少？序号是多少？一种计算方法：首位小于一种计算方法：首位小于3的组合的个数为的组合的个数为91；首位是；首位是3，第，第2位小于位小于5的组合的个数为的组合的个数为10；前；前2位是位是35，第，第3位小于位小于7的组的组合的个数为合的个数为3；前；前3位是位是357，第，第4位小于位小于9的组合的个数为的组合的个数为1。所有这些数之和所有这些数之和105，加上它本身的，加上它本身的1个号，得组合个号，得组合3579的的序号是序号是106。本讲稿第十三页，共一百零一页另一种思路由组合求序号另一种思路由组合求序号考虑从当前考察的组
10、合的后面有多少个组合。考虑从当前考察的组合的后面有多少个组合。/传入传入n、m及组合及组合c，返回，返回c的序号的序号num/下面的下面的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，传回所求的组合，传回所求的组合cvoi
11、dnum2combA(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、那么函数那么函数G(x)=a0+a1x+a2x2+akxk+称为序列称为序列a0、a1、a2、an、的的母函数（也叫生成函数）。母函数（也叫生成函数）。给定一个序列，可确定对应的母函数；反过来，给定一个母函给定一个序列，可确定对应的母函数；反过来，给定一个母函数，那么也能确定对应的序列。数，那么也
12、能确定对应的序列。例：斐波那契数列例：斐波那契数列an，n=0，1，2，a0=a1=1，an=an-1+an-2。对应的母函数可表示为。对应的母函数可表示为可求得可求得本讲稿第十六页，共一百零一页举例举例问题描述问题描述 小明手中有小明手中有3张一元张一元,2张张2元和元和3张张5元的钱币元的钱币,问小明都能买价问小明都能买价值为多少的物品？对每种价值的物品他有几种付款方法？值为多少的物品？对每种价值的物品他有几种付款方法？如小明手中有如小明手中有k张一元，张一元，m张张2元和元和n张张5元的钱币，结果又如元的钱币，结果又如何？何？输入输入输入的第一行是一个整数输入的第一行是一个整数T，（，（
13、1T10）,表示测试数据的个数。表示测试数据的个数。接下来有接下来有T行，每行上有行，每行上有3个非负整数个非负整数k，m，n，（，（1k，m，n10），分别表示一元、二元和五元的钱币数。），分别表示一元、二元和五元的钱币数。k，m，n中至中至少有一个非少有一个非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|记集合
15、记集合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，2，n的错排个数为的错排个数为Dn。有递推关系有递推关系很容易得到关于很容易得到关于Dn的关系式的关系式 Dn=本讲稿第二十
16、二页，共一百零一页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.4Plya定理定理群群:定义定义6.3 6.3 设设G G是一
17、个集合，是一个集合，*是是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=ea*x=x*a=e。那么称（那么称（G G，*）为一个群。）为一
18、个群。本讲稿第二十四页，共一百零一页群的例子群的例子例例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，*）是一个群，则称（）是一
19、个群，则称（H，*）是（）是（G，*）的一个群，简称）的一个群，简称H是是G的子群。的子群。交换群：设（交换群：设（G，*）是一个群，如果对于）是一个群，如果对于G的任何元素的任何元素a，b，有，有ab=ba，那么称，那么称G为交换群。为交换群。置换：置换：设设X是一个有限集，是一个有限集，是是X到到X的一个一一变换，那么称的一个一一变换，那么称 是是X上的一个置换。上的一个置换。有限群的阶：有限群的阶：G的元素个数称为的元素个数称为G的阶，记为的阶，记为|G|本讲稿第二十六页，共一百零一页置换置换设设X是一个有限集，是一个有限集，是是X到到X的一个一一变换，那么称的一个一一变换，那么称 是是
20、X上的上的一个置换一个置换：1a1，2a2，nan，置换的一种记号置换的一种记号注意：上述记号下，同一置换用这样的表示有注意：上述记号下，同一置换用这样的表示有n!种，但关键的对应关种，但关键的对应关系不变，只有一种。系不变，只有一种。本讲稿第二十七页，共一百零一页正三角形正三角形ABC的变换的变换正三角形正三角形ABC的旋转变换和轴对称变换的旋转变换和轴对称变换本讲稿第二十八页，共一百零一页正三角形的所有变换正三角形的所有变换沿中心逆时针旋转，有沿中心逆时针旋转，有0，120，240三种三种旋转旋转0，0：AA，BB，CC旋转旋转120，1：AC，BA，CB旋转旋转240，2：AB，BC，C
21、A沿对称轴翻转沿对称轴翻转180，也有三种：，也有三种：沿沿AO轴翻转，轴翻转，3：AA，BC，CB沿沿BO轴翻转，轴翻转，4：AC，BB，CA沿沿CO轴翻转，轴翻转，5：AB，BA，CC本讲稿第二十九页，共一百零一页正三角形的所有变换正三角形的所有变换沿中心逆时针旋转沿中心逆时针旋转旋转旋转0旋转旋转120旋转旋转240沿对称轴翻转沿对称轴翻转180沿沿AO轴翻转，沿轴翻转，沿BO轴翻转轴翻转沿沿CO轴翻转轴翻转本讲稿第三十页，共一百零一页置换的乘法运算置换的乘法运算置换的乘法运算是置换的连接置换的乘法运算是置换的连接X的所有的所有n!个置换关于置换的乘法构成一个群个置换关于置换的乘法构成一
22、个群G，记为记为Sn，其单位，其单位元是元是举例：设举例：设 3=，2=3与与 2的积为置换的积为置换 5。本讲稿第三十一页，共一百零一页循环循环循环循环 是这样一个置换，满足是这样一个置换，满足：a1a2，a2a3，aka1，但但对其它的元素保持不变，称为对其它的元素保持不变，称为k阶循环。阶循环。k阶循环可记为：阶循环可记为：k称为循环节长度称为循环节长度2阶循环阶循环也称为对换，简记为（也称为对换，简记为（a1a2）本讲稿第三十二页，共一百零一页置换与循环置换与循环定理定理6.3每个置换都可以写成若干互不相交的循环的每个置换都可以写成若干互不相交的循环的乘积，且表示是唯一的。乘积，且表示
23、是唯一的。例：置换例：置换可表示为可表示为(124)(35)(6)，其循环节数是其循环节数是3本讲稿第三十三页，共一百零一页2Burnside引理引理定义定义6.7等价：设等价：设G是有限集是有限集X上的置换群，点上的置换群，点a，b X称为称为“等价等价”的，当的，当且仅当，存在置换且仅当，存在置换 G使得使得(a)=b，记为，记为a b。轨道：在这种等价关系下，轨道：在这种等价关系下，X的元素形成的等价类称为的元素形成的等价类称为G的轨道。的轨道。a X所在的等价类所在的等价类Ea，即为，即为a所在的所在的轨道。轨道。G的任意两个不同的轨道之交是空集。的任意两个不同的轨道之交是空集。等价类
24、：集合等价类：集合X上的所有等价类构成上的所有等价类构成X的一个划分，等价类的个数的一个划分，等价类的个数记为记为L。本讲稿第三十四页，共一百零一页a不动置换类不动置换类Za：设：设G是是X=1，2，n上的置换群。若上的置换群。若a X，G中使中使a保持不变的置换的全体保持不变的置换的全体|有有 G，使，使(a)=a，记为，记为Za，叫做叫做G中使中使a保持不动的置换类保持不动的置换类，简称，简称a不动置换类。不动置换类。性质：对所有性质：对所有a X，|Ea|Za|=|G|成立。成立。证明证明略略C()：对于一个置换：对于一个置换 G，及，及a X，若，若(a)=a，则称，则称a为为 的的不
25、动点。不动点。的不动点的全体记为的不动点的全体记为C()。本讲稿第三十五页，共一百零一页Burnside引理引理证明：略证明：略L：等价类的个数：等价类的个数|C()|：的不动点的全体的个数的不动点的全体的个数|Za|：G中使中使a保持不动的置换类个数保持不动的置换类个数|G|：置换群置换群G的元素个数的元素个数本讲稿第三十六页，共一百零一页3Plya定理定理定理定理6.4设设G=1，2，t是是X=a1,a2,an上一个置换上一个置换群，用群，用m种颜色对种颜色对X中的元素进行涂色，那么不同的涂色方案中的元素进行涂色，那么不同的涂色方案数为数为其中其中Cyc(Cyc(k k)是置换是置换 k
26、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记录当前循环节长度记录当前循环节长度p=permp;vp=1
27、;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蛋糕蛋糕问题描述问题描述瓦尔特夫人本周六邀请她的朋友吃晚饭。到那个时候，瓦尔特夫人本周六邀请她的朋友吃晚饭。到那个时候，她想准备一个大的蛋糕。晚饭后，她要把蛋糕
28、切成几块她想准备一个大的蛋糕。晚饭后，她要把蛋糕切成几块给他们中的每一人。瓦尔特夫人认为如果蛋糕块大小不给他们中的每一人。瓦尔特夫人认为如果蛋糕块大小不一样，那么得到小块的客人会不高兴。因此，她将把蛋一样，那么得到小块的客人会不高兴。因此，她将把蛋糕分成如下图所示的形状，即把蛋糕在中间切割。糕分成如下图所示的形状，即把蛋糕在中间切割。为使蛋糕更可口，她要用各种为使蛋糕更可口，她要用各种不同颜色的果酱涂在上面。要不同颜色的果酱涂在上面。要知道，相邻两块是不能有相同知道，相邻两块是不能有相同颜色的。如果这样的话，她会颜色的。如果这样的话，她会认为这两块当作一块看待。认为这两块当作一块看待。本讲稿第
29、四十页，共一百零一页她发现，将她发现，将2种果酱放在种果酱放在3块蛋糕上是不可能做到的。但如果将块蛋糕上是不可能做到的。但如果将3种果种果酱放在酱放在3块蛋糕上，她发现有块蛋糕上，她发现有6种方法。而如果将种方法。而如果将4种果酱放在种果酱放在3块蛋块蛋糕上，她发现有糕上，她发现有24种方法。现在，瓦尔特夫人对果酱涂在蛋糕上的种方法。现在，瓦尔特夫人对果酱涂在蛋糕上的方法数感兴趣。她需要你的帮助，请你为她编写一个程序进行计算。方法数感兴趣。她需要你的帮助，请你为她编写一个程序进行计算。也许方法数太多，因此瓦尔特夫人只要你告诉她方法数的最后一位也许方法数太多，因此瓦尔特夫人只要你告诉她方法数的最
30、后一位数。数。注意：因客人不同，下图所示的注意：因客人不同，下图所示的2种方法是不同的。因此你不应混为种方法是不同的。因此你不应混为一谈。一谈。本讲稿第四十一页，共一百零一页输入输入输入有多组测试数据。每一组测试数据由两个整数输入有多组测试数据。每一组测试数据由两个整数m，n组成，其组成，其中整数中整数m是果酱颜色数，整数是果酱颜色数，整数n是客人数，也是蛋糕块数，是客人数，也是蛋糕块数，(0m100，1n10000)。当输入当输入m=n=0时表示输入结束，这种情况你不必处理。时表示输入结束，这种情况你不必处理。输出输出对每种情况，如输入描述中所说，输出将果酱放在蛋糕上的对每种情况，如输入描述
31、中所说，输出将果酱放在蛋糕上的方法数的个位数。方法数的个位数。本讲稿第四十二页，共一百零一页输入与输出样例输入与输出样例输入样例输出样例3 34 34 42 30 06440本讲稿第四十三页，共一百零一页分析与讨论分析与讨论令令an表示这表示这n块蛋糕用块蛋糕用m种果酱的的摆设方案数。大蛋糕切成种果酱的的摆设方案数。大蛋糕切成n块后的块后的形状如图所示，各块分别标记为形状如图所示，各块分别标记为C1，C2，Cn。分两种情况：分两种情况：（1）C1和和Cn-1有相同的颜色有相同的颜色（2）C1和和Cn-1有不同的颜色有不同的颜色本讲稿第四十四页，共一百零一页分析分析第一种情况：第一种情况：C1，
32、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块小蛋糕的着色方案一一对应。块小蛋糕的着色方案一一对应。这种情
33、况，这种情况，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，
34、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行上奇数的行上奇数的个数。个数。本讲稿第四十七页，共一百零一页输入与输出输入与输出输入输入输入有若干行。每一行上有一个正整数输入有若干行。每一行上有一个正整数n，（，（1n232）。）。输入直到文件结束。输入直到文件结束。输出输出对输入文件每行上的正整数对输入文件每行上的正整数n，输出杨辉三角形中第，输出杨辉三角形中第n行上奇行上奇数的个数
35、。数的个数。输入样例输出样例348102484本讲稿第四十八页，共一百零一页分析分析在杨辉三角形中，将每行上的奇数用在杨辉三角形中，将每行上的奇数用1表示、偶数用表示、偶数用0表示，表示，可得如下的简化的杨辉三角形，其中空白位置对应的行上可得如下的简化的杨辉三角形，其中空白位置对应的行上是数是数0。构造下页所示的简化杨辉三角形图构造下页所示的简化杨辉三角形图本讲稿第四十九页，共一百零一页图例图例本讲稿第五十页，共一百零一页有趣的规律有趣的规律34行上的行上的2个三角形与个三角形与12行上的三角形完全一样；行上的三角形完全一样；58行上稍大的行上稍大的2个三角形（底边个三角形（底边4个个1）与）
36、与14行上的三角形完全一行上的三角形完全一样；样；916行上再稍大的行上再稍大的2个三角形（底边个三角形（底边8个个1）与）与18行上的三角形完全一行上的三角形完全一样；样；第第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)
37、表示第表示第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)(mod2)（4）(x+1)8(mod2)=(x8+1)(mod2)，等等，等等将将n-1写为二进制数写为二进制数akak-1
38、a1a0，那么，那么本讲稿第五十三页，共一百零一页分析分析对等式两边作对等式两边作mod2运算，运算，丢掉那些使丢掉那些使ai=0的项的项(mod2)。于是，于是，(x+1)n-1中系数为奇数的项数就是所有使中系数为奇数的项数就是所有使ai=1=1的项的项 (mod 2)(mod 2)的乘积展开式中系数为奇数的项数。的乘积展开式中系数为奇数的项数。结论：杨辉三角形中第结论：杨辉三角形中第n行上奇数的个数为行上奇数的个数为本讲稿第五十四页，共一百零一页6.2.3足球赛票足球赛票问题描述问题描述 一场激烈的足球赛开始前，售票工作正在紧张地进行中。每张球票为一场激烈的足球赛开始前，售票工作正在紧张地
39、进行中。每张球票为50元。现有元。现有2n个人排队等待购票，其中有个人排队等待购票，其中有n个人手持个人手持50元的钞票，元的钞票，另外另外n个人手持个人手持100元的钞票，假设开始售票时售票处没有零钱。元的钞票，假设开始售票时售票处没有零钱。问这问这2n个人有多少种排队方式，使售票处不至出现找不开钱个人有多少种排队方式，使售票处不至出现找不开钱的局面？的局面？输入输入输入的每行上有一个非负整数输入的每行上有一个非负整数n，（，（1n1000）。）。输出输出对输入每行上的整数对输入每行上的整数n，输出这，输出这2n个人的排队方式数。个人的排队方式数。本讲稿第五十五页，共一百零一页输入与输出样例
40、输入与输出样例输入样例输出样例34511本讲稿第五十六页，共一百零一页分析分析令令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)综合，得：综合
41、，得：本讲稿第五十七页，共一百零一页6.2.4棋盘格数棋盘格数问题描述问题描述设设有有一一个个方方格格棋棋盘盘，求求出出该该棋棋盘盘中中包包含含有有多多少少个个正正方方形形、多少个长方形（不包括正方形）。多少个长方形（不包括正方形）。输入输入有有若若干干个个棋棋盘盘，每每个个棋棋盘盘对对应应一一行行上上两两个个整整数数n，m，（ln100，1m100），表示有一个），表示有一个n m方格的棋盘。方格的棋盘。输出输出对输入的对输入的n m方格棋盘，输出正方形的个数与长方形的个数。方格棋盘，输出正方形的个数与长方形的个数。本讲稿第五十八页，共一百零一页输入与输出样例输入与输出样例输入样例输出样例2
42、 36 38 1032 94本讲稿第五十九页，共一百零一页分析分析1.1.先考虑正方形的个数先考虑正方形的个数 边长为边长为k的正方形个数为的正方形个数为(n-k+1)(m-k+1)。2.2.再考虑长方形（包括正方形）的个数再考虑长方形（包括正方形）的个数 根据乘法原理，长方形和正方形的个数总计根据乘法原理，长方形和正方形的个数总计Total=(1+2+n)(1+2+m)3.3.长宽不等的长方形个数为长宽不等的长方形个数为Rec_total=Total-Sq_total4.因此，长宽不等的长方形个数为因此，长宽不等的长方形个数为Rec_total=TotalSq_total本讲稿第六十页，共一
43、百零一页6.2.5保险柜上锁保险柜上锁问题描述问题描述有有n个人组成的委员会负责保管一个保险箱。该委员会经过个人组成的委员会负责保管一个保险箱。该委员会经过研究形成决议：委员会中任何研究形成决议：委员会中任何m个委员同时到场就能打开个委员同时到场就能打开保险柜，而任何保险柜，而任何m-1个委员则不能打开保险柜。你的任务个委员则不能打开保险柜。你的任务是计算至少要给这个保险柜加多少把锁才能满足上述要求。是计算至少要给这个保险柜加多少把锁才能满足上述要求。输入输入输入文件中有若干行。每一行上有两个正整数输入文件中有若干行。每一行上有两个正整数n和和m是一组测试是一组测试数据，（数据，（1n50，0
44、mn）。输入直到文件结束。）。输入直到文件结束。输出输出对输入文件中的每组测试数据对输入文件中的每组测试数据n，m，输出满足要求的锁，输出满足要求的锁的最少数目。的最少数目。本讲稿第六十一页，共一百零一页输入与输出样例输入与输出样例输入样例 输出样例 2 15 412 5 110495 本讲稿第六十二页，共一百零一页（2）如果取）如果取k=，即加，即加把锁，那么可以按问题要求向把锁，那么可以按问题要求向委员们分配钥匙。委员们分配钥匙。现从这两方面考虑：现从这两方面考虑：（1）首先确定）首先确定k：作一个表格可以说明之：作一个表格可以说明之 分析分析设设k为符合要求的最少的锁的把数。记为符合要求
45、的最少的锁的把数。记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）对应于一个行）对应于一个行row，该，该行上与行上与m-1个列个列j1，j2，jm-1交叉处交叉处的
46、格子中都是的格子中都是0，而其他格子都是，而其他格子都是1。将编号为将编号为row的钥匙分配给编号不是的钥匙分配给编号不是j1，j2，jm-1的所有其他委员，即可的所有其他委员，即可满足要求。满足要求。计算的问题，这是容易的。计算的问题，这是容易的。A1A2An12k本讲稿第六十四页，共一百零一页6.2.6弹球游戏弹球游戏问题描述问题描述有一个三角形容器，上部开一个小口，里面如图中所示按层整齐有一个三角形容器，上部开一个小口，里面如图中所示按层整齐地放了许多小圆棍作为阻挡物，第地放了许多小圆棍作为阻挡物，第n层有层有n根阻挡物。根阻挡物。弹球游戏时，小球从容器上部的口子中间处跌落，碰到第一弹球
47、游戏时，小球从容器上部的口子中间处跌落，碰到第一层挡物后等概率地向两侧跌落，碰到与之相邻的第二层两个层挡物后等概率地向两侧跌落，碰到与之相邻的第二层两个阻挡物中的一个，再向两侧跌落第三层阻挡物，如此一直下阻挡物中的一个，再向两侧跌落第三层阻挡物，如此一直下跌最终小球落入底层。跌最终小球落入底层。在容器底层放了若干奖品。如下页图所示的在容器底层放了若干奖品。如下页图所示的6层容器中，层容器中，A，G区奖品最好，区奖品最好，B，F区奖品次之，区奖品次之，C，E区奖品第三，区奖品第三，D区奖区奖品最差。为方便起见，约定品最差。为方便起见，约定A，B，C，D，E，F，G区分别区分别用用0，1，2，3，
48、4，5，6区表示。区表示。本讲稿第六十五页，共一百零一页弹球游戏示意图弹球游戏示意图本讲稿第六十六页，共一百零一页一般地，如容器有一般地，如容器有n层，相应地得到不同大小的容器，其底层根层，相应地得到不同大小的容器，其底层根据位置不同也放了相应的奖品。该区域奖品的价值与小球落入据位置不同也放了相应的奖品。该区域奖品的价值与小球落入该区域的概率反向相关，即：区域的概率越大，该区域奖品的该区域的概率反向相关，即：区域的概率越大，该区域奖品的价值越小。价值越小。你的任务：计算弹球落入某个区域的概率。你的任务：计算弹球落入某个区域的概率。输入输入输入文件中有若干行。每一行上有两个整数输入文件中有若干行
49、。每一行上有两个整数n，m，（，（1n65535，0mn）。）。输入直到文件结束。输入直到文件结束。输出输出对输入中每行上的正整数对输入中每行上的正整数n，m，输出弹球落入有，输出弹球落入有n层的三角形层的三角形容器底层中第容器底层中第m个区的概率（四舍五入后保留个区的概率（四舍五入后保留6位小数）。位小数）。本讲稿第六十七页，共一百零一页输入与输出样例输入与输出样例输入样例 输出样例 3 24 18 510 3 0.3750000.2500000.2187500.117188 本讲稿第六十八页，共一百零一页分析分析如果如果m=0或或m=n，那么小球落入，那么小球落入m区的概率等于它肩上一个区
50、域概区的概率等于它肩上一个区域概率的率的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，3，s)，满足，满足的任的任何整数何整数k都可表示为（都可表示为（*）的形式。）的形式。事实上，记事实上，记M=，那么显然，指数在显然，指数在-M与与M之间的项都出现了。之间的项都出现了