信息学竞赛习题解答5(模拟)

《信息学竞赛习题解答5(模拟)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与程序实践》习题解答5——模拟现实中的有些问题，难以找到公式或规律来解决，只能按照一定步骤，不停地做下去，最后才能得到答案。这样的问题，用计算机来解决十分合适，只要能让计算机模拟人在解决此问题的行为即可。这一类的问题可以称之为“模拟题”。比如下面经典的约瑟夫问题：CS51：约瑟夫问题（来源：poj.grids.cn2746，程序设计导引及在线实践（李文新）例6.1P141）问题描述：约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下

2、的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。输入：每行是用空格分开的两个整数，第一个是n，第二个是m(0

3、就不存在。用人工解决的办法就是将n个数写在纸上排成一圈，然后从1开始数，每数到第m个就划掉一个数，一遍遍做下去，直到剩下最后一个。有了计算机，这项工作做起来就会快多了，我们只要编写一个程序，模拟人工操作的过程就可以了。用数组anLoop来存放n个数，相当于n个数排成的圈；用整型变量nPtr指向当前数到的数组元素，相当于人的手指；划掉一个数的操作，就用将一个数组元素置0的方法来实现。人工数的时候，要跳过已经被划掉的数，那么程序执行的时候，就要跳过为0的数组元素。需要注意的是，当nPtr指向anLoop中最后一个元

4、素（下标n-1）时，再数下一个，则nPtr要指回到数组的头一个元素（下标0），这样anLoop才象一个圈。参考程序：#include10#include#defineMAX_NUM300intaLoop[MAX_NUM+1];intmain(){intn,m,i;while(1){scanf("%d%d",&n,&m);if(n==0)break;for(i=0;i

5、/每次循环将1只猴子赶出圈子{intnCount=0;//记录本轮数到的猴子数目while(nCount

6、[nPtr]=0;}}return0;}注意事项：上面的程序完全模拟了人工操作的过程，但因为要反复跳过为0的数组元素，因此算法的效率不是很高。后文的“链表”一章，采用单链表进行模拟来解决本题，就能省去跳过已出圈的猴子这个操作，大大提高了效率。n个元素的数组，从下标0的元素开始存放猴子编号，则循环报数的时候，下一个猴子的下标就是“(当前猴子下标+1)%n”。这种写法比用分支语句来决定下个猴子的下标是多少，更快捷而且写起来更方便。10对于本题，虽然很难直接找出结果函数f(n,m)，但是如果仔细研究，找出局部的一些规

7、律，比如，每次找下一个要出圈的猴子时，直接根据本次的起点位置就用公式算出下一个要出圈的猴子的位置，那么写出的程序就可以省去数m只猴子这个操作，大大提高效率，甚至不需要用数组来存放n个数。请写出这个高效而节省空间的程序。问题一：在数组里循环计数的时候，一定要小心计算其开始的下标和终止的下标。比如，语句15，循环是从0到n-1，而不是从0到n。问题二：nPtr--到nPtr=n-1回退一个位置，易被忽略或写错。比如只写了语句nPtr--，忘了处理nPtr变成小于0的情况。CS52：醉酒的狱卒（TheDrunkJai

8、ler）（来源：POJ1218ZOJ1350，程序设计方法及在线实践指导（王衍等）P169）问题描述：某个监狱有一排、共n间牢房，一间挨一间。每间牢房关着一名囚犯，每间牢房的门刚开始时都是关着的。有一天晚上，狱卒厌烦了看守工作，决定玩一个游戏。游戏的第1轮，他喝了一杯酒，然后沿着监狱，把所有的牢房的门挨个挨个打开；第2轮，他又喝了一杯酒，然后沿着监狱，把编号为偶数的牢房的门关上；第3轮