蓝桥杯-作业2-版本1.doc

1、串。密码脱落X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。 ABA ABBA A由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。输入一行，表示现在看到的密码串（长度不大于1000）要求输出一个正整数，表示至少脱落了多少个种子。例如，输入：ABCBA则程序应该输出：0再例如，输入：ABDCDCBABC则程序应该输出：3-思路A.C*AC*代码实现：#include using namespace std;#include#includeint sinx=1000;void f(string a,int x,int y,int num)/num缺少的个数， if(x=y) if(sinxnum) sinx=num;/结束比较大小 return; if(ax!=ay)/不对称 f(a,x+1,y,num+1);/后面缺少 f(a,x,y-1,num+1);/前面缺少 else f(a,x+1,y-1,num);/对称继续比较int main() string a; cina; int along=a.size(); f(a,0,along-1,0); coutsinx; return 0;运行结果：2、递归1、39级台阶，1. 每步1或2阶2. 必须是偶数步 求上台阶的方案数。-没有偶数限制：f(n) = f(n-1) + f(n-2) -经典的间接递归的例子：f(n) 必须偶数步g(n) 必须奇数步f(n) = g(n-1) + g(n-2)g(n) = f(n-1) + f(n-2)出口：f(n) n=0: 1 n=1: 0 n=2: 1g(n) n=0: 0 n=1: 1 n=2: 1代码实现：#include using namespace std;#include#includeint f(int n);int g(int n) if(n=0) return 0; else if(n=1) return 1; else if(n=2) return 1; else return f(n-1)+f(n-2);int f(int n) if(n=0) return 1; else if(n=1) return 0; else if(n=2) return 1; else return g(n-1)+g(n-2);int main() coutf(39); return 0;运行结果：3、搭积木小明最近喜欢搭数字积木，一共有10块积木，每个积木上有一个数字，09。搭积木规则：每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。最后搭成4层的金字塔形，必须用完所有的积木。下面是两种合格的搭法： 0 1 2 3 4 56 7 8 9 0 3 1 7 5 29 8 6 4 请你计算这样的搭法一共有多少种？请填表示总数目的数字。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。代码实现：#include using namespace std;#include#includeint sum;bool p(int a10) if(a0a1|a0a2|a1a3|a1a4|a2a4|a2a5) return false; if(a3a6|a3a7|a4a7|a4a8|a5a8|a5a9) return false; return true;void f(int a10,int k,int n) if(n=k) if(p(a) sum+; else for(int i=k;in;i+) swap(ai,ak); f(a,k+1,n); swap(ai,ak); int main() int a10=0,1,2,3,4,5,6,7,8,9; f(a,0,10);/全排列 coutsum; return 0;运行结果：4、取球博弈两个人玩取球的游戏。一共有N个球，每人轮流取球，每次可取集合n1,n2,n3中的任何一个数目。如果无法继续取球，则游戏结束。此时，持有奇数个球的一方获胜。如果两人都是奇数，则为平局。假设双方都采用最聪明的取法，第一个取球的人一定能赢吗？试编程解决这个问题。输入格式：第一行3个正整数n1 n2 n3，空格分开，表示每次可取的数目 (0n1,n2,n3100)第二行5个正整数x1 x2 . x5，空格分开，表示5局的初始球数(0xi y if(f(y)=输) return 赢 if(f(y)=平局)逼平 = true; if(逼平) return 平局 return 输代码设计：#include using namespace std;#include int num3;int f(int n,int fnum,int gnum,int z) if(nnum0) if(fnum%2=0&gnum%2=1) return 1; else if(fnum%2=1&gnum%2=0) return -1; else return 0; bool bp = false; if(z%2=0) for(int i=0;i=numi) if(f(n-numi,fnum+numi,gnum,(z+1)%2)=-1) return 1; if(f(n-numi,fnum+numi,gnum,(z+1)%2)=0) bp = true; if(z%2=1) for(int i=0;i=numi) if(f(n-numi,fnum,gnum+numi,(z+1)%2)=-1) return 1; if(f(n-numi,fnum,gnum+numi,(z+1)%2)=0) bp = true; if(bp) return 0; return -1;int main() int a5; cinnum0num1num2; sort(num,num+3); for(int i=0;iai; for(int i=0;i5;i+) if(f(ai,0,0,0)=0) cout0 ; else if(f(ai,0,0,0)=1) cout+ ; else if(f(ai,0,0,0)=-1) cout- ; return 0;运行结果：5、题目描述 今盒子里有n个小球，A、B两人轮流从盒中取球，每个人都可以看到另一个人取了多少个，也可以看到盒中还剩下多少个，并且两人都很聪明，不会做出错误的判断。 我们约定： 每个人从盒子中取出的球的数目必须是：1，3，7或者8个。 轮到某一方取球时不能弃权！ A先取球，然后双方交替取球，直到取完。 被迫拿到最后一个球的一方为负方（输方） 请编程确定出在双方都不判断失误的情况下，对于特定的初始球数，A是否能赢？ 程序运行时，从标准输入获得数据，其格式如下： 先是一个整数n(n100)，表示接下来有n个整数。然后是n个整数，每个占一行（整数10000），表示初始球数。 程序则输出n行，表示A的输赢情况（输为0，赢为1）。 例如，用户输入：4121018 则程序应该输出：0110 注意： 请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！ 在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。代码实现：#include using namespace std;#include#includeint b4=1,3,7,8;int f(int n) for(int i=0;ibi) if(f(n-bi)=0) return 1;/对方输自己赢 return 0;/当N=1时没有选择int main() int n; cinn; int a100; for(int i=0;iai; for(int i=0;in;i+) coutf(ai)endl; return 0;运行结果：6、编程题 这是一个纵横火柴棒游戏。如图1.jpg，在一个3x4的方格中，游戏的双方轮流放置火柴棒。其规则是： 1. 不能放置在已经放置火柴棒的地方（即只能在空格中放置）。 2. 火柴棒的方向只能是垂直或水平放置。 3. 火柴棒不能与其它格子中的火柴“连通”。所谓连通是指两根火柴棒可以连成一条直线，且中间没有其它不同方向的火柴“阻拦”。 例如：图1.jpg所示的局面下，可以在C2位置竖直放置，但不能水平放置，因为会与A2连通。同样道理，B2，B3，D2此时两种方向都不可以放置。但如果C2竖直放置后，D2就可以水平放置了，因为不再会与A2连通（受到了C2的阻挡）。 4. 游戏双方轮流放置火柴，不可以弃权，也不可以放多根。直到某一方无法继续放置，则该方为负（输的一方）。 游戏开始时可能已经放置了多根火柴。 你的任务是：编写程序，读入初始状态，计算出对自己最有利的放置方法并输出。 如图1.jpg的局面表示为：00-1-0000100 即用“0”表示空格位置，用“1”表示竖直放置，用“-”表示水平放置。【输入、输出格式要求】 用户先输入整数 n(n100), 表示接下来输入 n 种初始局面，每种局面占3行(多个局面间没有空行)。 程序则输出对应的每种初始局面，计算出的最佳走法（行号+列号+放置方式）。 例如：用户输入：201110010 则程序可以输出：00-211 输出结果的含义为： 对第一个局面，在第0行第0列水平放置 对第二个局面，在第2行第1列垂直放置 注意： 行号、列号都是从0开始计数的。 对每种局面可能有多个最佳放置方法（解不唯一），只输出一种即可。 例如，对第一个局面，001 也是正解；最第二个局面，201也是正解。代码实现：#include #include using namespace std;int types2,map34;/map数组值对应意义：0表示留空,1表示垂直,-1表示水平/合法性验证bool validate(int i,int j,int type) if(type=1) /测试垂直方向 /向上边验证 for(int k=i-1;k=0;k-) if(mapkj=-type) break; else if(mapkj=type)return false; /向下边验证 for(int k=i+1;k=0;k-) if(mapik=-type) break; else if(mapik=type) return false; /向右边验证 for(int k=j+1;k4;k+) if(mapik=-type) break; else if(mapik=type) return false; return true;/调用方在i，j位置填入type能否必赢bool isWin(int i,int j,int type)/验证是否合法 if(!validate(i,j,type)return false; for(int a=0;a3;a+) for(int b=0;b4;b+) if(mapab=0) /对方找可以填的位置，如果没有可以填的位置，表示自己失败了，即调用方胜利了 for(int t=0;t2;t+) mapab=typest; if(isWin(a,b,typest)/如果对方胜利了，则表示调用方失败了 mapab=0;/要还原 return false; mapab=0;/要还原 /当没有位置可以填的时候，表示调用方胜利了 return true;void process() for(int i=0;i3;i+) for(int j=0;j4;j+) if(mapij=0) /如果位置为空位 for(int t=0;t2;t+) /可以放置水平和垂直两种火柴 mapij=typest; if(isWin(i,j,typest) /判断是否必赢 /如果必赢，则输出结果 coutij; if(typest=1) cout1; else coutn; while(n-) types0=1; types1=-1; for(int i=0;i3;i+) for(int j=0;j4;j+) mapij=0; for(int i=0;i3;i+) for(int j=0;jnumsj; if(numsj=-) mapij=-1; else if(numsj=1) mapij=1; process(); coutendl; return 0;运行结果：7、高僧斗法 古时丧葬活动中经常请高僧做法事。仪式结束后，有时会有“高僧斗法”的趣味节目，以舒缓压抑的气氛。 节目大略步骤为：先用粮食（一般是稻米）在地上“画”出若干级台阶（表示N级浮屠）。又有若干小和尚随机地“站”在某个台阶上。最高一级台阶必须站人，其它任意。(如图1所示) 两位参加游戏的法师分别指挥某个小和尚向上走任意多级的台阶，但会被站在高级台阶上的小和尚阻挡，不能越过。两个小和尚也不能站在同一台阶，也不能向低级台阶移动。 两法师轮流发出指令，最后所有小和尚必然会都挤在高段台阶，再也不能向上移动。轮到哪个法师指挥时无法继续移动，则游戏结束，该法师认输。 对于已知的台阶数和小和尚的分布位置，请你计算先发指令的法师该如何决策才能保证胜出。 输入数据为一行用空格分开的N个整数，表示小和尚的位置。台阶序号从1算起，所以最后一个小和尚的位置即是台阶的总数。（N100, 台阶总数1000） 输出为一行用空格分开的两个整数: A B, 表示把A位置的小和尚移动到B位置。若有多个解，输出A值较小的解，若无解则输出-1。例如：用户输入：1 5 9则程序输出：1 4再如：用户输入：1 5 8 10则程序输出：1 3资源约定：峰值内存消耗 64MCPU消耗 1000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入.” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI