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

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

ID:51795984

大小:86.00 KB

页数:10页

时间:2020-03-15

信息学竞赛习题解答5(模拟).doc_第1页
信息学竞赛习题解答5(模拟).doc_第2页
信息学竞赛习题解答5(模拟).doc_第3页
信息学竞赛习题解答5(模拟).doc_第4页
信息学竞赛习题解答5(模拟).doc_第5页
资源描述:

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

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

2、猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。输入:每行是用空格分开的两个整数,第一个是n,第二个是m(0

3、。有了计算机,这项工作做起来就会快多了,我们只要编写一个程序,模拟人工操作的过程就可以了。用数组anLoop来存放n个数,相当于n个数排成的圈;用整型变量nPtr指向当前数到的数组元素,相当于人的手指;划掉一个数的操作,就用将一个数组元素置0的方法来实现。人工数的时候,要跳过已经被划掉的数,那么程序执行的时候,就要跳过为0的数组元素。需要注意的是,当nPtr指向anLoop中最后一个元素(下标n-1)时,再数下一个,则nPtr要指回到数组的头一个元素(下标0),这样anLoop才象一个圈。参考程序:#include#include#de

4、fineMAX_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个nCount++;nPtr=(nPtr+1)%n;}nPtr--;//找到要出圈的猴子,位置要回退一个if(nPtr<0)nPtr=n-1;if(i==n-1)//最后一个出圈的猴子printf("%d",aLoop[nPtr]);aLoop[nPtr]=0;}}return0;}注意事项:上面的程序完全模拟了人工操作的过程,但因为要反复跳过为0的数组元素,因此算法的效率不是很高。后文的“链表”一章,采用单链表进行模拟来解决本题,就能省去跳过已出圈的猴子这个操作,大大提高了效率。n个元素的数组,从下标0的元素开始存放猴子编号,则循环报数的时候,下一个猴子的下标

6、就是“(当前猴子下标+1)%n”。这种写法比用分支语句来决定下个猴子的下标是多少,更快捷而且写起来更方便。对于本题,虽然很难直接找出结果函数f(n,m),但是如果仔细研究,找出局部的一些规律,比如,每次找下一个要出圈的猴子时,直接根据本次的起点位置就用公式算出下一个要出圈的猴子的位置,那么写出的程序就可以省去数m只猴子这个操作,大大提高效率,甚至不需要用数组来存放n个数。请写出这个高效而节省空间的程序。问题一:在数组里循环计数的时候,一定要小心计算其开始的下标和终止的下标。比如,语句15,循环是从0到n-1,而不是从0到n。问题二:nPtr--到nPtr=n-1回退一个位置

7、,易被忽略或写错。比如只写了语句nPtr--,忘了处理nPtr变成小于0的情况。CS52:醉酒的狱卒(TheDrunkJailer)(来源:POJ1218ZOJ1350,程序设计方法及在线实践指导(王衍等)P169)问题描述:某个监狱有一排、共n间牢房,一间挨一间。每间牢房关着一名囚犯,每间牢房的门刚开始时都是关着的。有一天晚上,狱卒厌烦了看守工作,决定玩一个游戏。游戏的第1轮,他喝了一杯酒,然后沿着监狱,把所有的牢房的门挨个挨个打开;第2轮,他又喝了一杯酒,然后沿着监狱,把编号为偶数的牢房的门关上;第3轮,他又喝

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。