- 题目描述：
-
每年六一儿童节,JOBDU都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为JOBDU的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为1的小朋友开始报数。每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续1...m报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到JOBDU名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？
- 输入：
-
输入有多组数据。
每组数据一行,包含2个整数n(0<=n<=1,000,000),m(1<=m<=1,000,000),n,m分别表示小朋友的人数(编号1....n-1,n)和HF指定的那个数m(如上文所述)。如果n=0,则结束输入。
- 输出：
-
对应每组数据,输出最后拿到大奖的小朋友编号。
样例输入：
1 10 8 5 6 6 0样例输出：
1 3 4【解题思路】本题是一个约瑟夫环问题，具体可以参考百度百科“约瑟夫问题”的思想。在本题中同样为了处理的方便，我们假设编号从0开始到n-1。在n个人时，我们知道编号k-1人在第一次肯定出局，那么剩下0.....k-2 k k+1......n-1组成新的相对于n个人的编号：k k+1......n-1 0.......k。剩下的n-1个人（0.......n-2）组成一个新的问题，问题规模变小，但其他都没变。那么我们可以假设n-1个人中间编号为ans的人为最后的胜利者，那么这个人对应于有n个人时的编号应该就是（ans+k）mod n。
那么我们可以很容易得到一个递推关系，（ans+k）mod i。其中i表示有i个人时，ans表示有i-1个人时的最终胜利者的编号。我们很容易知道当i=1时，ans=0，我们可以用ans=0 i=1为基础推出有n个人时的最后胜利的编号。但我们要注意，根据题目的要求，我们采用0.....n-1的编号，所以，最后的结果需要+1才是题目需要的编号。
AC code：
#include <stdio.h>
int main()
{
int n,m;
while (scanf("%d", &n)!=EOF && n>0) {
scanf("%d", &m);
int ans = 0;
for (int i=1; i<=n; i++)
ans = (ans+m) % i;
printf("%d
", ans+1);
}
return 0;
}
/**************************************************************
Problem: 1356
User: huo_yao
Language: C++
Result: Accepted
Time:300 ms
Memory:1020 kb
****************************************************************/
题目链接：http://ac.jobdu.com/problem.php?pid=1356九度-剑指Offer习题全套答案下载：http://download.csdn.net/detail/huoyaotl123/8276299