1234: 华科版C语言程序设计教程（第二版）习题6.11（约瑟夫问题）

题目：
Description
n个人围成一圈，依次从1至n编号。从编号为1的人开始1至k报数，凡报数为k的人退出圈子，输出最后留下的一个人原来的编号。
Input
 首先输入一个t，表示有t组数据（1<= t <= 10010）
然后有t行，每行有2个正整数n和k。（1<= n，k<= 20）
Output
 对于每组测试数据，输出一个数，表示最后留下来的人的编号。

样例：
Sample Input
3
10 3
7 1
5 4
Sample Output
4
7
1

提示： 例如第三组样例：5个人围成一圈，编号1-5。第一轮报数4号出列，第二轮从5开始报数1，3报4，3出列，第三轮从5开始报1，5报4，5出列，第四轮1开始报1，2报4，2出列，最后剩下的为1号。

思路：这题是一个约瑟夫问题，处理方式就是用一个数组，其下标表示序号，其存的指用0，1分别表示其是否出去了，然后用循环，依次进行，若没出去则看这个是第几个没出去的，若是要出去的报数的那个数的倍数，则让其出去，即将存的指由1变为0；然后再找一个计数器表示剩余人数，当剩余只有1个的时候则跳出循环，输出最后的；

新技巧：在于用数组的下标表示序号，用内部存的值表示其状态，还有一个重要的点就是人数计数器，因为这里是要记录出去的人数，所以一开始计数器为总数，之后每次出去就减一，这样从逻辑上好记录与理解；

代码：

#include<stdio.h>
#include<string.h>

int main()
{
    int i,t,x,y,a[10015];
    scanf("%d",&t);
    for(i=0;i<t;i++)
    {
        memset(a,0,sizeof(a));
        scanf("%d%d",&x,&y);
        int num=x,j,k;
        for(j=1;j<=x;j++)
            a[j]=1;
        k=0;
        for(j=0;;j++)
        {

            if(a[j%x+1])
            {
                k++;
                if(k%y==0)
                {
                    if(num==1)
                        break;
                    a[j%x+1]=0;
                    num--;
                }
            }
        }
        printf("%d\n",j%x+1);
    }
    return 0;
}