计算机科学论坛--约瑟夫问题集

贴子主题：约瑟夫问题集

本主题类别:

第一题：
猴子选大王。题目：有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的猴子出圈，最后剩下来的就是大王。要求：从键盘输入M，N，编程计算哪一个编号的猴子成为大王。

第二题：变形猴子选大王
题目：有M个人围成一圈，每人有一个编号，从编号为1的人开始，每隔N个出圈，按出圈次序排成一列，其编号刚好按顺序从1到M。
要求：从键盘输入M，N，编程计算并输出这M个人原来在圈中的位置。

第三题：设有N个人围成一圏，并且按照顺时针方向从1到N编号，由第S个人开始进行从1到M报数，报数到第M个人时，此人出圏，再从下一个人重新开始从1到M报数，如此进行下去，直到所有的人都出圏为止。现在要求编程按照出圏的顺序，打印这N个人的顺序表。

第四题：狸捉兔子
【问题】围绕着山顶有１０个洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你从１０号洞出发，先到１号洞找，第二次隔１个洞找，第三次隔２个洞找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了１０００次，仍没有找到兔子。问兔子究竟藏在哪个洞里？

第五题：慈善的约瑟夫
你一定听说过约瑟夫问题吧？即从N个人找出唯一的幸存者。现在老约瑟夫将组织一个皆大欢喜的新游戏，假设N个人站成一圈，从第1人开始交替的去掉游戏者，但只是暂时去掉，直到最后剩下唯一的幸存者为止。幸存者选出后，所有比幸存者号码高的人每人得到1个金币，永久性离开。其余剩下的将重复以上的游戏过程，比幸存者号码主的人每人得到1个金币后离开。经过这们的过程后，一旦人数不再减少，则最后剩下的那些人将得到2个金币。请你计算一下老约瑟夫一共要付出多少钱？
例如第一轮有5人，幸存者是3，所以4,5得到1个金币后离开，下一轮幸存者仍然是3，因此没有人离开，所以前面3人每人得2个金币。总共要付出2+2*3=8个金币。
输入：N
输出：金币数。

第六题：50枚棋子围成圆圈，编上号码1，2，3，…每隔一枚棋子取出一枚，要求最后留下的一枚棋子的号码是42，那该从几号棋子开始取呢？

第七题：41枚棋子围成圆圈，编上号码1，2，3，…沿圆圈自1开始，每数三枚棋子，就取出第3枚棋子，这样陆续取出1，4，7，…问最后留下的是第几枚？

第八题：用1到6摆成一个圆圈如图。先取1，然后每数k枚棋子就取出第k枚棋子。要是取出的顺序刚好是1，2，3，4，5，6。问k＝？

第九题：猴子选大王
题目：有n个猴子选大王，选举办法如下：从头到尾1，2，3报数，凡报到3的退出，余下的从尾到头1，2，3报数，凡报3的退出。。。。如此类推，当剩下两只猴子时，取这时报1的为王，若想当猴王，请问当初应站在什么位置？

题目的分析与伪码：


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	51.270ms