算法与程序实践习题解答5(模拟)

目录CS51：约瑟夫问题1CS52：花生问题（同CS93）3CS53：显示器（见CS327）6CS54：排列10CS55：宇航员13CS56：数根24CS57：武林26CS58：循环数32CS59：醉酒的狱卒（TheDrunkJailer）35CS510：网络拥堵解决方案（EenyMeenyMoo）37CS511：约瑟夫环问题（Joseph）40CS512：另一个约瑟夫环问题（未做）（YetAnotherJosephusProblem）42CS513：三子棋游戏（TicTacToe）42CS514：扫雷游戏（MineSweeper）45CS515：弹球游戏（LinearPachinko）49CS516：分糖果的游戏（CandySharingGame）52CS517：爬动的蠕虫(ClimbingWorm)55CS518：遍历迷宫（MazeTraversal）57CS319：59CS320：63CS321：66CS322：69CS323：71CS324：73CS325：75CS326：77CS327：79CS328：82CS329：84《算法与程序实践》习题解答5——模拟现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决此问题的行为即可。这一类的问题可以称之为“模拟题”。比如下面经典的约瑟夫问题：讲课：CS51CS52CS53实验：CS56CS516CS517讲课：CS59CS513CS518CS51：约瑟夫问题（来源：2746，程序设计导引及在线实践（李文新）例6.1P141）问题描述：约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。输入：每行是用空格分开的两个整数，第一个是n，第二个是m(0<m,n<300)。最后一行是：00输出：对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号。样例输入：621248300样例输出：517解题思路：初一看，很可能想把这道题目当作数学题来做，即认为结果也许会是以n和m为自变量的某个函数f(n,m)，只要发现这个函数，问题就迎刃而解。实际上，这样的函数很难找，甚至也许根本就不存在。用人工解决的办法就是将n个数写在纸上排成一圈，然后从1开始数，每数到第m个就划掉一个数，一遍遍做下去，直到剩下最后一个。有了计算机，这项工作做起来就会快多了，我们只要编写一个程序，模拟人工操作的过程就可以了。用数组anLoop来存放n个数，相当于n个数排成的圈；用整型变量nPtr指向当前数到的数组元素，相当于人的手指；划掉一个数的操作，就用将一个数组元素置0的方法来实现。人工数的时候，要跳过已经被划掉的数，那么程序执行的时候，就要跳过为0的数组元素。需要注意的是，当nPtr指向anLoop中最后一个元素（下标n-1）时，再数下一个，则nPtr要指回到数组的头一个元素（下标0），这样anLoop才象一个圈。参考程序：#include<stdio.h>#include<stdlib.h>#defineMAX_NUM300intaLoop[MAX_NUM+1];intmain(){ intn,m,i; while(1) { scanf("%d%d",&n,&m); if(n==0)break;for(i=0;i<n;i++) aLoop[i]=i+1; intnPtr=0;//存储位置信息 for(i=0;i<n;i++)//每次循环将1只猴子赶出圈子 { intnCount=0;//记录本轮数到的猴子数目 while(nCount<m)//一直要数出m个猴子 { while(aLoop[nPtr]==0)//跳过已经出圈的猴子 nPtr=(nPtr+1)%n;//到下一个位置，如果到最后就跳到第1个 nCount++; nPtr=(nPtr+1)%n; } nPtr--;//找到要出圈的猴子，位置要回退一个 if(nPtr<0) nPtr=n-1; if(i==n-1)//最后一个出圈的猴子 printf("%d\n",aLoop[nPtr]); aLoop[nPtr]=0; } } return0;}注意事项：上面的程序完全模拟了人工操作的过程，但因为要反复跳过为0的数组元素，因此算法的效率不是很高。后文的“链表”一章，采用单链表进行模拟来解决本题，就能省去跳过已出圈的猴子这个操作，大大提高了效率。n个元素的数组，从下标0的元素开始存放猴子编号，则循环报数的时候，下一个猴子的下标就是“(当前猴子下标+1)%n”。这种写法比用分支语句来决定下个猴子的下标是多少，更快捷而且写起来更方便。对于本题，虽然很难直接找出结果函数f(n,m)，但是如果仔细研究，找出局部的一些规律，比如，每次找下一个要出圈的猴子时，直接根据本次的起点位置就用公式算出下一个要出圈的猴子的位置，那么写出的程序就可以省去数m只猴子这个操作，大大提高效率，甚至不需要用数组来存放n个数。请写出这个高效而节省空间的程序。问题一：在数组里循环计数的时候，一定要小心计算其开始的下标和终止的下标。比如，语句15，循环是从0到n-1，而不是从0到n。问题二：nPtr--到nPtr=n-1回退一个位置，易被忽略或写错。比如只写了语句nPtr--，忘了处理nPtr变成小于0的情况。CS52：花生问题（同CS93）（来源：2950，程序设计导引及在线实践（李文新）例4.3P107）问题描述：鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格（如图5-1）。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”我们假定多多在每个单位时间内，可以做下列四件事情中的一件：1)从路边跳到最靠近路边（即第一行）的某棵花生植株；2)从一棵植株跳到前后左右与之相邻的另一棵植株；3)采摘一棵植株下的花生；4)从最靠近路边（即第一行）的某棵花生植株跳回路边。图5-1花生地图5-2摘花生过程现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图5-2所示的花生田里，只有位于(2,5),(3,7),(4,2),(5,4)的植株下长有花生，个数分别为13、7、15、9。沿着图示的路线，多多在21个单位时间内，最多可以采到37个花生。输入：输入的第一行包括三个整数，M,N和K，用空格隔开；表示花生田的大小为M*N（1<=M,N<=20），多多采花生的限定时间为K（0<=K<=1000）个单位时间。接下来的M行，每行包括N个非负整数，也用空格隔开；第i+1行的第j个整数Pij（0<=Pij<=500）表示花生田里植株(i,j)下花生的数目，0表示该植株下没有花生。输出：输出包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。样例输入：672100000000000130000000070150000000090000000000样例输出：37解题思路：试图找规律，得到一个以花生矩阵作为自变量的公式来解决这个问题，是不现实的。结果只能是做了才知道。即走进花生地，每次要采下一株花生之前，先计算一下，剩下的时间，够不够走到那株花生，采摘，并从那株花生走回到路上。如果时间够，则走过去采摘；如果时间不够，则采摘活动到此结束。参考程序：#include<stdio.h>#include<stdlib.h>#include<memory.h>#include<math.h>intT,M,N,K;#defineMAX_NUM55intaField[MAX_NUM][MAX_NUM];intmain(){ inti,j,t,m,n; scanf("%d",&T); for(t=0;t<T;t++){ scanf("%d%d%d",&M,&N,&K); for(m=1;m<=M;m++) for(n=1;n<=N;n++) scanf("%d",&aField[m][n]); intnTotalPeanuts=0;//摘得的花生总数 intnTotalTime=0;//已经花去的总时间 intnCuri=0,nCurj;//当前位置坐标 while(nTotalTime<K) { intnMax=0,nMaxi,nMaxj;//最大的花生数目，及其所处的位置 //寻找下一个最大花生数目及其位置for(i=1;i<=M;i++) { for(j=1;j<=N;j++){ if(nMax<aField[i][j]){ nMax=aField[i][j]; nMaxi=i; nMaxj=j; } } } if(nMax==0)//地里没有花生了 break; if(nCuri==0) nCurj=nMaxj;//如果当前位置在路上，那么应走到横坐标nMaxj处，再进入花生地//下面检查剩余的时间够不够走到nMaxi,nMaxj处，摘取花生，并回到路上 if(nTotalTime+nMaxi+1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj)<=K) { nTotalTime+=1+abs(nMaxi-nCuri)+abs(nMaxj-nCurj); nCuri=nMaxi; nCurj=nMaxj; nTotalPeanuts+=aField[nMaxi][nMaxj]; aField[nMaxi][nMaxj]=0;//摘走花生赋值为0 } else break; } printf("%d\n",nTotalPeanuts); } return0;}实现技巧：用二维数组存放花生地的信息是很自然的想法。然而，用aField[0][0]还是aField[1][1]对应花生地的左上角，是值得思考一下的。因为从地里到路上还需要1个单位时间，题目中的坐标又都是从1开始，所以若aField[1][1]对应花生地的左上角，则从aField[i][j]点，回到路上所需时间就是i，这样更为方便和自然，不易出错。并不是C/C++的数组下标从0开始，我们使用数组的时候，就要从下标为0的元素开始用。常见问题：问题一：读题时应该仔细读。有的同学没有看到每次只能拿剩下花生株中最大的，而是希望找到一种在规定时间内能够拿最多花生的组合，把题目变成了另外一道题。问题二：有的同学没有读到“没有两株花生株的花生数目相同”的条件，因此把题目复杂化了。问题三：这个题目是假设猴子在取花生的过程中不会回到大路上的，有些同学在思考是否可能在中间回到大路上，因为题目没说在大路上移动要花时间，所以有可能中途出来再进去摘的花生更多。CS53：显示器（见CS327）（来源：2745，程序设计导引及在线实践（李文新）例6.3P147）问题描述： 你的一个朋友刚买了一台新电脑，之前，他用过的最好的电脑只能是便携式计数器。现在，你的朋友看着他的新电脑，他很失望，因为他喜欢他的计数器的LC显示器。因此你决定给你的朋友编写一个程序模拟LC显示器来显示数字。输入： 输入文件包含多行，每一行为需要显示的数。每一行中有两个整数s和n，1<=s<=10，0<=n<=99999999。n为要显示的数值，s是显示的大小。 输入文件的最后一行为两个0，这一行不需要处理。输出： 以LC显示器方式输出输入文件中的数，用符号“-”表示水平的线段，用符号“|”表示垂直的线段。数值中的每个数字占s+2列，2s+3行。在输出时，对每两个数字之间的空白区域，要确保用空格填满，对最后一位数字之后的空白区域，不能输出空格。每两个数字之间仅有一个空列。（样例输出中给出了0~9每个数字的输出格式） 每个数值之后输出一个空行。样例输入：21234536789000样例输出：------||||||||||||--------||||||||||------||||||||||||||||||||||||||||||||||||||||||||||||解题分析：一个计算器上的数字显示单元，可以看作由以下编号从1到7的7个笔画组成：图5-3显示单元的笔画那么，我们可以说，数字8覆盖了所有的笔画，数字7覆盖笔画1、3和6，而数字1覆盖笔画3、6。注意，每个笔画都是由s个’-‘或s个’|’组成。输出时，先输出第1行，即整数n中所有数字里的笔画1，然后输出第2行到第s+1行，即所有数字的笔画2和笔画3，接下来是第s+2行，即所有数字的笔画4，再接下来是第s+3行到2×s+2行，，就是所有数字的笔画5和笔画6，最后的第2×s+3行，是所有数字的笔画7。如果某个数字d没有覆盖某个笔画m(m=1…7)，那么，输出数字d的笔画m的时候，就应该都输出空格；如果覆盖了笔画m，则输出s个’-‘或s个’|’，这取决于笔画m是横的还是竖的。由上思路，解决这道题目的关键，就在于如何记录每个数字都覆盖了哪些笔画。实际上，如果我们记录的是每个笔画都被哪些数字覆盖，则程序实现起来更为容易。一个笔画被哪些数字所覆盖，可以用一个数组来记录，比如记录笔画1覆盖情况的数组如下：charn1[11]={"---"};其中，n1[i](i=0……9)代表笔画1是否被数字i覆盖。如果是，则n1[i]为'-'，如果否，则n1[i]为空格。上面的数组的值体现了笔画1被数字0,2,3,5,6,7,8,9覆盖。对于竖向的笔画2，由字符'|'组成，则记录其覆盖情况的数组如下：charn2[11]={"||||||"};该数组的值体现了笔画2被数字0,4,5,6,8,9覆盖。参考程序：//显示器（见CS327）2745#include<stdio.h>#include<string.h>charn1[11]={"---"};//笔画1被数字0,2,3,5,6,7,8,9覆盖charn2[11]={"||||||"};//笔画2被数字0,4,5,6,8,9覆盖charn3[11]={"||||||||"};//笔画3被数字0,1,2,3,4,7,8,9覆盖charn4[11]={"--"};//笔画4被数字2,3,4,5,6,8,9覆盖charn5[11]={"||||"};//笔画5被数字0,2,6,8覆盖charn6[11]={"|||||||||"};//笔画6被数字0,1,3,4,5,6,7,8,9覆盖charn7[11]={"-------"};//笔画7被数字0,2,3,5,6,8,9覆盖intmain(){ ints; charszNumber[20]; intnDigit,nLength,i,j,k; while(1) { scanf("%d%s",&s,szNumber); if(s==0) break; nLength=strlen(szNumber); //输出所有数字的笔画1 for(i=0;i<nLength;i++) {if(i!=0)printf(""); nDigit=szNumber[i]-'0'; printf(""); for(j=0;j<s;j++)//一个笔画由s个字符组成printf("%c",n1[nDigit]); printf(""); } printf("\n"); for(i=0;i<s;i++)//输出所有数字的笔画2和笔画3 { for(j=0;j<nLength;j++) {if(j!=0)printf(""); nDigit=szNumber[j]-'0'; printf("%c",n2[nDigit]); for(k=0;k<s;k++) printf("");//笔画2和笔画3之间的空格 printf("%c",n3[nDigit]); } printf("\n"); } for(i=0;i<nLength;i++)//输出所有数字笔画4 {if(i!=0)printf(""); printf(""); nDigit=szNumber[i]-'0'; for(j=0;j<s;j++) printf("%c",n4[nDigit]); printf(""); } printf("\n"); for(i=0;i<s;i++)//输出所有数字的笔画5和笔画6 { for(j=0;j<nLength;j++) {if(j!=0)printf(""); nDigit=szNumber[j]-'0'; printf("%c",n5[nDigit]); for(k=0;k<s;k++) printf(""); printf("%c",n6[nDigit]); } printf("\n"); } for(i=0;i<nLength;i++)//输出笔画7 {if(i!=0)printf(""); printf(""); nDigit=szNumber[i]-'0'; for(j=0;j<s;j++) printf("%c",n7[nDigit]); printf(""); } printf("\n");printf("\n"); } return0;}实现技巧：一个笔画被哪些数字所覆盖，最直接的想法是用整型数组来记录，比如：intn1[10]={1,0,1,1,0,1,1,1,1,1};表示笔画1的被覆盖情况。可是与其在数字i的笔画1所处的位置进行输出的时候，根据n1[i]的值决定输出空格还是'-’，还不如直接用下面的char类型数组来表示覆盖情况：charn1[11]={"---"};这样，在数字i的笔画1所处的位置进行输出的时候，只要输出s个n1[i]就行了。这是一个很好的思路，它提醒我们，以后在编程时设置一些标志的时候，要考虑一下是否可以直接用更有意义的东西将0，1这样的标志代替。常见问题：问题一：没有注意到输出是按行，即先输出所有数字的第一画，再输出第二画……。于是想一个数字一个数字地从左到右输出，编了一阵才发现不对。问题二：忘了输出空格。应把所有的空白用空格符填充。例如：若要输出4的话就是这样：（。表示空格）。。。。｜｜｜｜--。。。。｜。。。｜。。。。问题三：两组数据之间要加一个空行。解题分析： 用一个三维数组把0~9共10个数字的字符形式存放起来，这个数组可以定义为digit[10][5][4]，第1维10代表10个数字，第2维5代表5行，第3维4代表3列加上一个字符串结束标志。 注意：两个数字之间有空列，但最后一个数字后没有。另外最后一个数字后也没有任何空白区域。参考程序（zzg）：#include<stdio.h>#include<string.h>chardigit[10][5][4]={//存放0~9 {"-","||","","||","-"},//0 {"","|","","|",""},//1 {"-","|","-","|","-"},//2 {"-","|","-","|","-"},//3 {"","||","-","|",""},//4 {"-","|","-","|","-"},//5 {"-","|","-","||","-"},//6 {"-","|","","|",""},//7 {"-","||","-","||","-"},//8 {"-","||","-","|","-"}//9 };intmain(){ ints;//存储s charn[10];//用来存储n，要显示的数值 inti,j,k,m; intlen;//用来存储n的长度// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout); while(1) { scanf("%d%s",&s,n); if(s==0)break; len=strlen(n); for(i=0;i<5;i++)//输出5行，其中第2行和第4行需要输出s倍 { if(i==1||i==3)//第2行 { for(j=1;j<=s;j++) { for(k=0;k<len;k++)//第1列和第3列正常输出，第2列需要输出s倍最后一个不留空白区域 { printf("%c",digit[n[k]-'0'][i][0]); for(m=1;m<=s;m++) printf("%c",digit[n[k]-'0'][i][1]); printf("%c",digit[n[k]-'0'][i][2]); if(k<len-1)printf(""); } printf("\n"); } } else { for(k=0;k<len;k++)//第1列和第3列正常输出，第2列需要输出s倍最后一个不留空白区域 { printf("%c",digit[n[k]-'0'][i][0]); for(m=1;m<=s;m++) printf("%c",digit[n[k]-'0'][i][1]); printf("%c",digit[n[k]-'0'][i][2]); if(k<len-1)printf(""); } printf("\n"); } } printf("\n"); } return0;}CS54：排列（来源：1833，程序设计导引及在线实践（李文新）例题6.4P152）问题描述：给出正整数n，则1~n这n个数可以构成n！种排列，把这些排列按照从小到大的顺序（字典顺序）列出，如n=3时，列出123，132，213，231，312，321这6个排列。给出某个排列，求出这个排列的下k个排列，如果遇到最后一个排列，则下1排列为第1个排列，即排列123…n。比如：n=3，k=2给出排列231，则它的下1个排列为312，下2个排列为321，因此答案为321。输入：第一行是一个正整数m，表示测试数据的个数，下面是m组测试数据，每组测试数据第一行是2个正整数n(1<=n<1024)和k(1<=k<=64)，第二行有n个正整数，是1，2…n的一个排列。输出：对于每组输入数据，输出一行，n个数，中间用空格隔开，表示输入排列的下k个排列。样例输入：3312313132110212345678910样例输出：31212312345679810解题思路：这道题目，最直观的想法是求出1到n的所有排列，然后将全部排列排序……且慢，n最大可以是1024，1024!个排列，几乎永远也算不出来，算出来也没有地方存放。那么，有没有公式或规律，能够很快由一个排列推算出下k个排列呢？实际上寻找规律或公式都是徒劳的，只能老老实实由给定排列算出下一个排列，再算出下一个排列……一直算到第k的排列。鉴于k的值很小，最多只有64，因此这种算法应该是可行的。如何由给定排列求下一个排列？不妨自己动手做一下。比如：“2147635”的下一个排列是什么？容易，显然是“2147653”，那么，再下一个排列是什么？有点难了，是“215346以从“2147653”求出下一个排列“2153467假设给定排列中的n个数从左到右是a1,a2,a3……an。1)从an开始，往左边找，直到找到某个aj，满足aj-1<aj（对上例j,这个aj就是7，aj-1就是4）。2)在aj、aj+1……an中找到最小的比aj-1大的数，将这个数和aj-1互换位置（对上例,这个数就是5，和4换完位置后的排列是“2157643”3)将从位置j到位置n的所有数（共n-j+1个）从小到大重新排序，排好序后，新的排列就是所要求的排列。（对上例，就是将“7643”排序，排好后的新排列就是“2153467当然，按照题目要求，如果a1,a2,a3……an已经是降序，那么它的下一个排序就是an,an-1,an-2……a1。参考程序：#include<stdio.h>#include<stdlib.h>#defineMAX_NUM1024intan[MAX_NUM+10];//用以排序的比较函数intMyCompare(constvoid*e1,constvoid*e2){ return*((int*)e1)-*((int*)e2);}intmain(){ intM; intm,n,k,i,j;//freopen("in.txt","r",stdin); scanf("%d",&M); for(m=0;m<M;m++){ scanf("%d%d",&n,&k); //排列存放在an[1],an[2],...an[n]for(i=1;i<=n;i++) scanf("%d",&an[i]); an[0]=100000;//确保an[0]比排列中所有的数都大 for(i=0;i<k;i++)//每次循环都找出下一个排列 { for(j=n;j>=1&&an[j-1]>an[j];j--);if(j>=1) { intnMinLarger=an[j]; intnMinIdx=j; //下面找出从an[j]及其后最小的比an[j-1]大的元素，并记住其下标intkk; for(kk=j;kk<=n;kk++){ if(nMinLarger>an[kk]&&an[kk]>an[j-1]) { nMinLarger=an[kk]; nMinIdx=kk; } } //交换位置 an[nMinIdx]=an[j-1]; an[j-1]=nMinLarger; qsort(an+j,n-j+1,sizeof(int),MyCompare);//排序 } else//an里的排列已经是降序了，那么下一个排序就是123...n { for(j=1;j<=n;j++)an[j]=j; } } for(j=1;j<=n;j++)printf("%d",an[j]); printf("\n"); } return0;}实现技巧：1.把排列存放在an[1]an[n]，而在an[0]存放一个比排列中所有的数都大的数，这个an[0]所起的作用通常称之为“哨兵”。有了“哨兵”，就可以写语句：for(j=n;j>=1&&an[j-1]>an[j];j--);不必担心j-1小于0导致数组越界。如果没有“哨兵”，而且将排列存放在an[0]an[n-1]中，那么写到相当于这个for循环的时候，就要判断j-1小于0的情况，比较罗嗦，也容易出错。放置“哨兵”，是在数组或链表中进行各种操作时常用的做法。2.学过C++标准模板库的同学会注意到，用标准模板库中的next_permutation算法直接就能求给定排列的下一个排列，根本不需动脑筋。常见问题：这个题目的测试数据比较多，用scanf读入没有问题，有的同学学了点C++,用C++中的cin读入数据，就会造成超时。注意最后一个数据输出后有个空格。CS55：宇航员（来源：1835，程序设计导引及在线实践（李文新）练习1P155）问题描述：宇航员在太空中迷失了方向，在他的起始位置现在建立一个虚拟xyz坐标系，称为绝对坐标系，宇航员正面的方向为x轴正方向，头顶方向为z轴正方向，则宇航员的初始状态如图5-4所示：图5-4宇航员初始状态现对六个方向分别标号，x，y，z正方向分别为0，1，2，负方向分别为3，4，5；称它们为绝对方向。宇航员在宇宙中只沿着与绝对坐标系xyz轴平行的方向行走，但是他不知道自己当前绝对坐标和自己面向的绝对方向。任务描述：请根据宇航员对自己在相对方向上移动的描述确定宇航员最终的绝对坐标和面向的绝对方向。对在相对方向上移动的描述及意义如下：forwardx向前走x米。backx先转向后，再走x米。leftx先转向左，再走x米。rightx先转向右，再走x米。upx先面向上，再走x米。downx先面向下，再走x米。其中向上和向下如图5-5所示：图5-5宇航员向上、向下移动过程输入：第一行一个正整数m，表示测试数据的组数。每组测试数据第一行是一个正整数n(1<=n<=10000)表示宇航员行走的次数，下面n行每行输入一次相对行走，格式如上所述，其中(1<=x<=10000为正整数)。输出：对于每组输入数据输出一行，xyzp,中间用空格隔开，xyz是宇航员的位置的绝对坐标，p是宇航员面向的绝对方向编号（0<=p<=5）。样例输入：16left10right11up12down13forward14back15样例输出：23-10123解题思路：使用x,y,z来存储坐标，使用direction来存储当前方向（取值为0~5）参考程序1（zzg）：#include<stdio.h>#include<stdlib.h>voidchange(intdirection,intdistance);//根据走的方向和距离来求xyz的坐标值voidchangeDirection(intpredirection,charway,inthead);//根据前一个方位和走向，求新方位intx,y,z;intm,n,distance;//distance移动距离intdirection,predirection,head;//当前方位和前一个方位,头部的方位charway[10];intmain(){ inti;//freopen("in.txt","r",stdin); scanf("%d",&m); while(m--)//m组测试数据 { scanf("%d",&n); x=0; y=0; z=0; predirection=-1;//初始方位为0 head=2;//头向上 for(i=1;i<=n;i++)//n次行走{ scanf("%s%d",way,&distance); changeDirection(predirection,way[0],head); change(direction,distance);} printf("%d%d%d%d\n",x,y,z,direction);} return0;}voidchange(intdirection,intdistance){ switch(direction) { case0: x+=distance; break; case1: y+=distance; break; case2: z+=distance; break; case3: x-=distance; break; case4: y-=distance; break; case5: z-=distance; break; }}voidchangeDirection(intpredirection1,charway1,inthead1){ if(predirection1==-1) { head=2; switch(way1) { case'f'://forward向前走 direction=0; break; case'b'://back向后走 direction=3; break; case'l'://left向左走 direction=4; break; case'r'://right向右走 direction=1; break; case'u'://up向上走 direction=2; head=3; break; case'd'://down向下走 direction=5; head=0; break; } } else { switch(way1) { case'f'://forward向前走 direction=predirection1; head=head1; break; case'b'://back向后走 direction=(predirection1>2?predirection1-3:predirection1+3); head=head1; break; case'l'://left向左走 if(head1==2) { head=head1; if(predirection1==0) direction=4; if(predirection1==4) direction=3; if(predirection1==3) direction=1; if(predirection1==1) direction=0; } if(head1==5) { head=head1; if(predirection1==0) direction=1; if(predirection1==4) direction=0; if(predirection1==3) direction=4; if(predirection1==1) direction=3; } if(head1==0) { head=head1; if(predirection1==1) direction=5; if(predirection1==5) direction=4; if(predirection1==4) direction=2; if(predirection1==2) direction=1; } if(head1==3) { head=head1; if(predirection1==1) direction=2; if(predirection1==5) direction=1; if(predirection1==4) direction=5; if(predirection1==2) direction=4; } if(head1==1) { head=head1; if(predirection1==2) direction=3; if(predirection1==3) direction=5; if(predirection1==5) direction=0; if(predirection1==0) direction=2; } if(head1==4) { head=head1; if(predirection1==2) direction=0; if(predirection1==3) direction=2; if(predirection1==5) direction=3; if(predirection1==0) direction=5; } break; case'r'://right向右走 if(head1==5) { head=head1; if(predirection1==0) direction=4; if(predirection1==4) direction=3; if(predirection1==3) direction=1; if(predirection1==1) direction=0; } if(head1==2) { head=head1; if(predirection1==0) direction=1; if(predirection1==4) direction=0; if(predirection1==3) direction=4; if(predirection1==1) direction=3; } if(head1==3) { head=head1; if(predirection1==1) direction=5; if(predirection1==5) direction=4; if(predirection1==4) direction=2; if(predirection1==2) direction=1; } if(head1==0) { head=head1; if(predirection1==1) direction=2; if(predirection1==5) direction=1; if(predirection1==4) direction=5; if(predirection1==2) direction=4; } if(head1==4) { head=head1; if(predirection1==2) direction=3; if(predirection1==3) direction=5; if(predirection1==5) direction=0; if(predirection1==0) direction=2; } if(head1==1) { head=head1; if(predirection1==2) direction=0; if(predirection1==3) direction=2; if(predirection1==5) direction=3; if(predirection1==0) direction=5; } break; case'u'://up向上走 direction=head1; head=(predirection1>2?predirection1-3:predirection1+3); break; case'd'://down向下走 head=predirection1; direction=(head1>2?head1-3:head1+3); break; } } predirection=direction;}参考程序2（程颖宇）：#include<stdio.h>classV{ protected: intx,y,z; public: V(){x=y=z=0; }; V(intpx,intpy,intpz){ x=px; y=py; z=pz; }; Voperator=(Vv){ x=v.x;y=v.y; z=v.z; return*this; }; Voperator-(){//取负 returnV(-x,-y,-z); }; Voperator-(Vv){//减 returnV(x-v.x,y-v.y,z-v.z); }; Voperator+(Vv){//加 returnV(x+v.x,y+v.y,z+v.z); }; Voperator*(Vv){//点乘 returnV(x*v.x,y*v.y,z*v.z); }; Voperator*(ints){//数乘 returnV(x*s,y*s,z*s); }; Voperator%(Vv){//叉乘 returnV(y*v.z-z*v.y,z*v.x-x*v.z,x*v.y-y*v.x); }; voidrev(){//反向 x=-x;y=-y; z=-z; }; voidoperator()(intpx,intpy,intpz){ x=px; y=py; z=pz; }; voidset(intpx,intpy,intpz){ x=px; y=py;z=pz; }; voidget(int&px,int&py,int&pz){px=x; py=y; pz=z; }; voidprint(){ printf("%d%d%d",x,y,z);}; voidp(){ if(x>0&&y==0&&z==0){ printf("0"); }elseif(x==0&&y>0&&z==0){ printf("1"); }elseif(x==0&&y==0&&z>0){ printf("2"); }elseif(x<0&&y==0&&z==0){ printf("3"); }elseif(x==0&&y<0&&z==0){ printf("4"); }elseif(x==0&&y==0&&z<0){ printf("5"); } };};intmain(){ intm,n,s; chardir[10]; Vface,head,pos,tmp; scanf("%d",&m); while(m--){ scanf("%d",&n); face(1,0,0); head(0,0,1);pos(0,0,0); while(n--){ scanf("%s%d",dir,&s);switch(dir[0]){ case'f': break; case'b': face.rev(); break; case'l': face=face%head; break; case'r': face=head%face; break; case'u': tmp=face; face=head; head=-tmp; break; case'd': tmp=face; face=-head; head=tmp; break; } pos=pos+face*s; } pos.print(); printf(""); face.p(); printf("\n"); } return0;}CS56：数根（来源：2764，程序设计导引及在线实践（李文新）练习2P156）问题描述：数根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根。如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。比如，对于24来说，把2和4相加得到6，由于6是一位数，因此6是24的数根。再比如39，把3和9加起来得到12，由于12不是一位数，因此还得把1和2加起来，最后得到3，这是一个一位数，因此3是39的数根。输入：输入包括一些正整数(小于101000)，每个一行。输入的最后一行是0，表示输入的结束，这一行不用处理。输出：对每个正整数，输出它的数根。每个结果占据一行。样例输入：24390样例输出：63CS57：武林（来源：2785，程序设计导引及在线实践（李文新）练习3P157）问题描述：在一个有12行12列的方形的武林世界里，少林、武当和峨嵋三派的弟子们在为独霸武林而互相厮杀。武林世界的第一行的一列格子的坐标是(1,1)，第一行第二列坐标是(1,2)……右下角的坐标为(12,12)。如图5-6：图5-6武林世界的坐标图少林派弟子总是在同一列来回不停地行走。先往下走，走到头不能再走时就往上走，再到头则又往下走……比如，(1,1)->(2,1)->(3,1)。武当派弟子总是在同一行来回不停地行走。先往右走，走到头不能再走时就往左走，再到头则又往右走……比如，(2,1)->(2,2)->(2,3)。峨嵋派弟子总是在右下-左上方向来回不停走，先往右下方走，走到头不能再走时就往左上方走，再到头则又往右下方走……比如，(1,1)->(2,2)->(3,3)。峨嵋弟子如果位于(1,12)或(12,1)，那当然只能永远不动。每次走动，每个弟子必须而且只能移动一个格子。每名弟子有内力、武艺和生命力3种属性。这3种属性的取值范围都是大于等于0，小于等于100。当有两名不同门派的弟子进入同一个格子时，一定会发生一次战斗，而且也只有在这种情况下，才会发生战斗（同派弟子之间当然不会自相残杀；一个格子里三派弟子都有时，大家都会因为害怕别人渔翁得利而不敢出手；而多名同门派弟子也不会联手对付敌人，因为这有悖于武林中崇尚的单打独斗精神，会被人耻笑）。一次战斗的结果将可能导致参战双方生命力发生变化，计算方法为：战后生命力=战前生命力-对方攻击力而不同门派的弟子攻击力计算方法不同：少林派攻击力=(0.5*内力+0.5*武艺)*(战前生命力+10)/100武当派攻击力=(0.8*内力+0.2*武艺)*(战前生命力+10)/100峨嵋派攻击力=(0.2*内力+0.8*武艺)*(战前生命力+10)/100对攻击力的计算过程为浮点运算，最终结果去掉小数点后部分取整，使得攻击力总是整数。一次战斗结束后，生命力变为小于或等于0的弟子，被视为“战死”，会从武林中消失。两名不同门派的弟子相遇时，只发生一次战斗。初始状态下，不存在生命值小于或等于0的弟子，而且一个格子里有可能同时有多个弟子。一系列战斗从初始状态就可能爆发，全部战斗结束后，仍然活着的弟子才开始一齐走到下一个格子。总之，不停地战斗－行走－战斗－行走……所有弟子都需等战斗结束后，才一齐走到下一个格子。你需要做的是，从一个初始状态，算出经过N步（N<1000）后的状态。所有的弟子先进行完全部战斗（当然也可能没有任何战斗发生），然后再一齐走到下一个格子，这称为一步。所有弟子总数不会超过1000。输入：第一行是测试数据的组数，随后是各组测试数据。每组数据第一行是行走步数N。接下来的若干行，每行描述一名弟子的位置及其各项参数。描述弟子时，格式为“弟子代号行号列号内力武艺生命力”。弟子代号就是一个字母：‘S’代表少林派弟子‘W’代表武当派弟子‘E’代表峨嵋派弟子比如：W10210310表示第10行第2列有一名武当派弟子，他的内力是10，武艺是3，生命力是10。每组测试数据以一个结束标志行结尾。结束标志行只含有一个字符’0’输出：针对每组测试数据，您的输出应该是4行，前3行每行是用空格分隔的两个整数，前一个是某派弟子总数，后一个是本派所有弟子生命力之和。规定第1行代表少林派，第2行代表武当派，第3行代表峨嵋派。第4行是“***”表示结束。样例输入：21S12202020W2120202002S12202020W21202020E121220201000样例输出：12012000***1141141100***参考程序（董利鹏）：#include<stdio.h>#include<string.h>structkongfu{//定义弟子结构体charcc;//门派intr;//行号intc;//列号intnl;//内力intwy;//武艺intsml;//生命力intdir;//运动的方向};intmain(){kongfua[1001];//定义弟子的数组intexit[1001];//表示在走完n步之后该弟子是否存在intcount[13][13];//在n步之后count[i][j]表示第i行第j列的弟子的个数charpk[13][13];//pk[i][j]表示n步之后在第i行第j列会不会发生战斗inti,j,n,step,js;//step表示行走步数，js表示输入弟子的个数scanf("%d",&n);while(n--){js=0;scanf("%d\n",&step);while(scanf("%c",&a[js].cc)!=EOF&&a[js].cc!='0'){//输入弟子scanf("%d%d%d%d%d\n",&a[js].r,&a[js].c,&a[js].nl,&a[js].wy,&a[js].sml);a[js].dir=1;//并把弟子的初始方向设为1if(a[js].cc=='E'){//如果是峨眉的弟子并在左下角或右上角，则把方向改为0if((a[js].r==1&&a[js].c==12)||(a[js].r==12&&a[js].c==1))a[js].dir=0;}js++;}for(i=0;i<js;i++)exit[i]=1;//初始时每个弟子都是存在的赋值为1step-=1;//根据结果来看step减一是对的while(step--){memset(pk,'',sizeof(pk));memset(count,0,sizeof(count));for(i=0;i<js;i++){//遍历每个弟子if(a[i].cc=='S'){//如果是少林的弟子if(a[i].r+a[i].dir>=1&&a[i].r+a[i].dir<=12){//如果在走完这步时没有走出方阵a[i].r=a[i].r+a[i].dir;}else{//否则掉转方向a[i].dir*=-1;a[i].r=a[i].r+a[i].dir;}if(pk[a[i].r][a[i].c]=='')pk[a[i].r][a[i].c]=a[i].cc;//这两条语句表示至少有两个不同门派的elseif(pk[a[i].r][a[i].c]!=a[i].cc)pk[a[i].r][a[i].c]='p';//弟子时该位置的字符就是'p'count[a[i].r][a[i].c]++;//在该位置的弟子数加一}elseif(a[i].cc=='W'){//如果是武当的弟子，同理if(a[i].c+a[i].dir>=1&&a[i].c+a[i].dir<=12){a[i].c=a[i].c+a[i].dir;}else{a[i].dir*=-1;a[i].c=a[i].c+a[i].dir;}if(pk[a[i].r][a[i].c]=='')pk[a[i].r][a[i].c]=a[i].cc;elseif(pk[a[i].r][a[i].c]!=a[i].cc)pk[a[i].r][a[i].c]='p';count[a[i].r][a[i].c]++;}elseif(a[i].cc=='E'){//如果是峨眉的弟子if(a[i].r+a[i].dir>=1&&a[i].r+a[i].dir<=12&&a[i].c+a[i].dir>=1&&a[i].c+a[i].dir<=12){a[i].r=a[i].r+a[i].dir;a[i].c=a[i].c+a[i].dir;}else{a[i].dir*=-1;a[i].r=a[i].r+a[i].dir;a[i].c=a[i].c+a[i].dir;}if(pk[a[i].r][a[i].c]=='')pk[a[i].r][a[i].c]=a[i].cc;elseif(pk[a[i].r][a[i].c]!=a[i].cc)pk[a[i].r][a[i].c]='p';count[a[i].r][a[i].c]++;}}//走完一步之后for(i=1;i<13;i++){for(j=1;j<13;j++){//遍历方阵的每个位置if(count[i][j]==2&&pk[i][j]=='p'){//如果该位置有两个弟子，并且该位置有至少两个不同门派的弟子intk;intnum=0;intp1,p2;for(k=0;k<js;k++){if(exit[k]==1&&a[k].r==i&&a[k].c==j){if(num==0){p1=k;//找到第一个弟子编号p1num++;}else{p2=k;//找到第二个弟子编号p2break;}}}intg1,g2;//g1，g2分别表示p1和p2的攻击力，以下就是二人pkif(a[p1].cc=='S'){g1=(5*a[p1].nl+5*a[p1].wy)*(a[p1].sml+10)/1000;}elseif(a[p1].cc=='W'){g1=(8*a[p1].nl+2*a[p1].wy)*(a[p1].sml+10)/1000;}else{g1=(2*a[p1].nl+8*a[p1].wy)*(a[p1].sml+10)/1000;}if(a[p2].cc=='S'){g2=(5*a[p2].nl+5*a[p2].wy)*(a[p2].sml+10)/1000;}elseif(a[p2].cc=='W'){g2=(8*a[p2].nl+2*a[p2].wy)*(a[p2].sml+10)/1000;}else{g2=(2*a[p2].nl+8*a[p2].wy)*(a[p2].sml+10)/1000;}a[p1].sml=a[p1].sml-g2;if(a[p1].sml<=0)exit[p1]=0;//如果生命力不大于0，就视为不存在了a[p2].sml=a[p2].sml-g1;if(a[p2].sml<=0)exit[p2]=0;//如果生命力不大于0，就视为不存在了}}}}intsum1[3]={0},sum2[3]={0};//最后按照要求统计输出for(i=0;i<js;i++){if(a[i].cc=='S'&&exit[i]==1){sum1[0]++;sum2[0]+=a[i].sml;}if(a[i].cc=='W'&&exit[i]==1){sum1[1]++;