约瑟夫问题

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld

Description

约瑟夫问题：n个人围成一圈，从第一个人开始报数，数到m的人出圈。再由下一个人开始报数，数到m的人出圈。......

请编写程序输出倒数第k个出圈人的编号。

例如：n=5，m=3，k=1，则应该输出4。

注意：main函数已经给定（如下所示）。

           请将程序补充完整。

           提交时只需要提交自己补充的代码部分，不需要提交给定的main函数的代码部分。

#include<stdio.h>
int main()
{
    int n,m,k,t;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {  //n个人排成一圈数数，数到m的人出圈，返回倒数第k个陈泉人的编号
        t=f(n,m,k);
        printf("%d\n",t);
    }
    return 0;
}

 

Input

包含多组测试数据，每组测试数据占一行，每行3个正整数，分别代表n，m和k。k小于等于n，n不超过100。

 

Output

每组测试数据输出占一行，每行输出倒数第k个出圈人的编号。

 

Sample Input 

5 3 1

 

Sample Output

4

题目分析：

跟士兵报数类似，要记个数，记循环，总体不算难。

抄代码是会被查重的哦！！！

#include<stdio.h>
int f(int n,int m,int k)
{
//抄代码是有害无益的~
	int a[1001],x,p;
	int i;
	x=n;//剩余人数
	for(i=1;i<=n;i++)
		a[i]=0;
	p=1;
	i=1;
	while(x>0)
	{
		if(p==n+1)
			p=1;
		if(a[p]==0)
		{
			if(i==m)
			{
				a[p]=x;
				x--;
				i=0;
			}
			i++;
			p++;
		}
		else
			p++;
	}
	for(i=1;i<=n;i++)
		if(a[i]==k)
			return i;
}
int main()
{
    int n,m,k,t;
    while(scanf("%d%d%d",&n,&m,&k)!=EOF)
    {  //n个人排成一圈数数，数到m的人出圈，返回倒数第k个出圈人的编号
        t=f(n,m,k);
        printf("%d\n",t);
    }
    return 0;
}