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

ericasadun 2019-06-26

题目:
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;
}

相关推荐