《step-组合数学.doc》由会员分享，可在线阅读，更多相关《step-组合数学.doc（11页珍藏版）》请在金锄头文库上搜索。
1、目 录组A01 字串数（简单排列组合）1组B01 放苹果（多重集合的组合）2组B02 有趣的排列（排列组合）3组B03 旅游路线（不相邻的排列）4组B04 序列（Catalan数）5组B05 洗牌问题（置换群）6算A01 植树活动（蛮力法）7算A02 密码（蛮力法）8算A03 数制转换（栈）9算A04 愚人节的礼物（栈）10注：组表示本题属于组合数学，算表示本题属于算法设计技术，A表示简单，B表示稍难。1组A01 字串数（简单排列组合）【问题描述】一个A和两个B一共可以组成三种字符串:ABB,BAB,BBA.给定若干字母和它们相应的个数,计算一共可以组成多少个不同的字符串. 【数据输入】每组测
2、试数据分两行,第一行为n(1=n=26),表示不同字母的个数,第二行为n个数A1,A2,.,An(1=Ai=12),表示每种字母的个数.测试数据以n=0为结束. 【数据输出】对于每一组测试数据,输出一个m,表示一共有多少种字符串. 【样例输入】21 232 2 20【样例输出】390组B01 放苹果（多重集合的组合）【问题描述】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。 【要求】【数据输入】第一行是测试数据的数目t（0 = t = 20）。以下每行均包含二个整数M和N，以空格分开。1=M，N=10。 【
3、数据输出】对输入的每组数据M和N，用一行输出相应的K。 【样例输入】17 3【样例输出】8组B02 有趣的排列（排列组合）【问题描述】大家知道，给出正整数n，则1到n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出1 2 3，1 3 2，2 1 3，2 3 1，3 1 2，3 2 1六个排列。 任务描述： 给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列1 2 3n。 比如：n = 3，k=2 给出排列2 3 1，则它的下1个排列为3 1 2，下2个排列为3 2 1，因此答案为3 2 1。 【数据输入】第一行
4、是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n( 1 = n 1024 )和k(1=k=64)，第二行有n个正整数，是1，2 n的一个排列。【数据输出】对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。【样例输入】33 12 3 13 13 2 110 21 2 3 4 5 6 7 8 9 10【样例输出】3 1 21 2 31 2 3 4 5 6 7 9 8 10组B03 旅游路线（不相邻的排列）【问题描述】假如长江沿岸有n个城市，每个城市依次标号（上游到下游次序编）为1，2，3, n-3, n-2, n-1, n。alg
5、想从长江上游出发，游玩这些城市。其中alg的旅游路线选取原则为： 1.至少要游玩一个城市。 2.不会游玩相邻的两个城市。即相邻的两个城市不会出现在algoo的旅游路线中。例如：当游玩过城市n-k后，就不会考虑在城市n-k+1停下。 现在你的任务是：如果有n个城市，帮助algoo计算有多少种路线可以选择。 【数据输入】多组测试数据。每组测试数据一行，为一个数n（1=n 3 1- 4 2- 4 （1，3城市都不玩，游玩过城市2后再到城市4） 共7种路线。 组B04 序列（Catalan数）【问题描述】一个序列Ai, i=0,1,2,3N由3N+1 项组成，每一项要么为1，要么为-2。定义部分和S(
6、K)=A0+A1+AK，求所有满足性质P的序列的数目，性质P为：S(3N)=1 且对于所有的K=0,1,2,3N-1,3N，有S(K)0（即所有项的和为，且所有部分和为正）。例如N=2 的时候，共有3 组这样的序列： 1, 1, 1, -2, 1, 1, -2 1, 1, 1, 1, -2, 1, -2 1, 1, 1, 1, 1, -2, -2【数据输入】第一行输入N(N1000)。【数据输出】满足P 性质的序列数目【样例输入】2【样例输出】3组B05 洗牌问题（置换群）【问题描述】设2n张牌分别标记为1, 2, ., n, n+1, ., 2n，初始时这2n张牌按其标号从小到大排列。经一次
7、洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ., 2n, n。即前n张牌被放到偶数位置2, 4, ., 2n，而后n张牌被放到奇数位置1, 3, ., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n105)，最少需要经过多少次洗牌可恢复到初始状态。 【数据输入】输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。【数据输出】对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。 【样例输入】10【样例输出】6 算A01 植树活动（蛮力法）【问题描述】春暖花开，万物复苏，这正是植物生长的好季节。珠海校区举行了一
8、次题为“迎百年校庆，添三分绿色”的植树活动。这次植树活动的目的除了美化我们的校园，进一步增强同学们的环保意识以外，还在于迎接即将到来的百年校庆，张江河副院长认为这次活动意义重大，并不亚于其他大型的植树活动。他希望同学们要坚持照顾好自己所种的树，为它们浇水捉虫，让它们茁壮成长。 师生共同植树，打成一片。在这里我们看到的是热情，是团队合作精神，还有同学们为庆祝百年校庆的真诚的心！经过将近一个小时的努力，各单位基本上都把树种好。看到自己亲手种的树，同学们都非常兴奋，纷纷拍照留念，记下这个难忘的时刻！同学们感叹说：“这次活动很有意义啊！”，有的同学则希望能留下一个见证，让他们以后回来母校，可以看到自己
9、的班集体种的树，会觉得很有意义。 这次植树活动有n个部门参加，树种有米兰、玉兰，有桂花、榕树，还有大皇椰等。每个部门分别种了m个树种，每个树种分别种了k1,k2,k3,km-1,km棵，现在有一个简单的任务，就请你帮忙计算一下每个部门分别种了多少棵树，全院一共种了多少棵树。【数据输入】所有的数据都是从键盘输入，其数据格式是：第一行是参与植树的部门数n，后面跟着的每二行是一个部门的数据，在每一个部门的数据中，第一行是该部门植树的树种数m，第二行是m个树种所种的棵数k1,k2,k3,km-1,km。【数据输出】输出结果为按顺序输出每个部门所种的树棵数，及全院共种树的棵数。【样例输入】234 5 2
10、46 7 3 1【样例输出】111728算A02 密码（蛮力法）【问题描述】网上流传一句话:常在网上飘啊，哪能不挨刀啊。其实要想能安安心心地上网其实也不难，学点安全知识就可以。 首先，我们就要设置一个安全的密码。那什么样的密码才叫安全的呢？一般来说一个比较安全的密码至少应该满足下面两个条件： (1).密码长度大于等于8，且不要超过16。 (2).密码中的字符应该来自下面“字符类别”中四组中的至少三组。 这四个字符类别分别为： 1.大写字母：A,B,C.Z; 2.小写字母：a,b,c.z; 3.数字：0,1,2.9; 4.特殊符号：,!,#,$,%,; 给你一个密码，你的任务就是判断它是不是一个
11、安全的密码。【数据输入】输入数据有多组，对于每一组输入第一行包含一个数M，接下有M行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符输入0退出。【数据输出】对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。【样例输入】3a1b2c3d4LinleACM!%0【数据输出】NOYESNO算A03 数制转换（栈）【问题描述】有一种数制的基数是3，分别用数码0,1,2表示，如这种数制的101表示十进制数的10，即1*(32)+0*(31)+1*(30)=10，又如这种数制的-10 表示十进制数的-3，即-1*(31)+0*(30)=-3。编程要求把给定的
12、有符号整数转换为新数制的数，该数的前面不能有多余的0，如10的新数制表示是101，则不要输出成0101。【数据输入】文件有一行或多行，每行有一个整数N (-2,147,483,647N2,147,483,647)，整数内不会有其他分隔符。【数据输出】对输入文件的每一行输出一行，该行是输入行的整数的新数制表示，不能有多余空行，每行之前不能有前导空格。【样例输入】10-3【样例输出】101-10 算A04 愚人节的礼物（栈）【问题描述】四月一日快到了，Vayko想了个愚人的好办法送礼物。嘿嘿，不要想的太好，这礼物可没那么简单，Vayko为愚人准备了一堆盒子，其中有一个盒子里面装了礼物。盒子里面可以再放零个或者多个盒子。假设放礼物的盒子里不再放其他盒子。用()表示一个盒子，B表示礼物，Vayko想让你帮她算出愚人指数，即最少需要拆多少个盒子才能拿到礼物。 【要求】【数据输入】本题目包含多组测试，请处理到文件结束。每组测试包含一个长度不大于1000,只包含(,)和B三种字符的字符串，代表Vayko设计的礼物透视图。你可以假设，每个透视图画的都是合法的。 【数据输出】对于每组测试，请在一行里面输出愚人指数。 【样例输入】(B)()()(B)【样例输出】41
