1.问题描述
据说,鲁智深一天中午匆匆来到开封府大相国寺,想蹭顿饭吃,当时大相国寺有99个和尚,只做了99个馒头,智清长老不愿得罪鲁智深,便把他安排在一个特定位置,之后对所有人说,从我开始报数(围成一圈),第5个人可以吃到馒头(并退下),按照这个公平的方法,所有和尚都吃到了馒头,唯独鲁智深没有吃上。请问他在哪个位置?
2.问题分析
看似公平,其实仔细一想只是一个特定序列问题——100个人按照特定的序列依次去取99个馒头,将最后取不到的那个序号安排给鲁智深即可。所以问题的关键在于怎么安排这个序列,智清长老是将100个人围成一团,然后报数是5号(5的倍数)位置的人依次去领馒头来规定领取的序列,这个看似公平的解决方案其实背后的结局早已注定。第一次接触这个问题是学习筛选法求100以内所有的素数的时候,而后通过对筛选法的反思,归纳了三种思路四种解决方法:数组筛选、循环链表、递归还原、递归循环。这四种方法的实现过程也是对同一个问题解决方案不断优化及思考的过程,接下来就对每个方法的特点及不足逐个分析。
3.数组筛选法——大浪淘沙
原理:设定一个计数器,计数器到达5的倍数便让馒头数目减1(用数组值为0标记吃了馒头的和尚),99个馒头用完为止,最后大浪淘沙,吃饱的人都走了,留下的便是鲁智深:

void LuZhiShenArray(){ int i,count = 1; int a[101]; //总共100个人 int b = 99; //篮子里有99个馒头 //让每个人都保持饥饿状态 for(i=1; i <=100; i++) a[i] = i; while(b > 0){ for(i=1; i<=100; i++){ if(a[i] != 0){ if(count%5 == 0){ b--; //拿走一个馒头 a[i] = 0; //吃饱——退出 } count++; //未吃码头的人参与报数 } } } for(i=1; i<=100; i++){ if(a[i]!=0)printf("鲁智深的位置编号是:%d\n",a[i]); } }
讯享网
优劣:该方法能较为接近的模拟报数的过程,思路简单明了;但仍有不足,在用数组的时候必须首先明确数组的大小,虽然可以用宏常量提前规定大小但仍缺失动态性。另一个问题是该方法的时间复杂度为O(mn),人数和馒头较大时则略显尴尬。
4.循环链表法——阿弥陀佛
原理:所有的和尚手拉手围成一个圆圈,从智清长老开始报数,报数为5的倍数的和尚退下去,此时退下和尚左右两边的和尚进行牵手(脑补画面,友谊万岁),那最后终止的条件是鲁智深自己的左手牵右手,双手合于胸前,仰天长叹一声:“阿弥陀佛,玩不过这帮老和尚,看来这大相国寺是呆不下去了,明天就去梁山...”。智清长老逼鲁智深上梁山的细节如下:
讯享网 typedef struct Item *PtrPerson;

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/82360.html