Question

约瑟夫问题

【问题描述】

n个人围成一圈，顺序编号。从第一个人开始从1到3报数，凡报到3的人退出圈子，编程求解最后留下的人的初始编号。

【输入】

输入由键盘输入，只有一行

这一行有一个正整数n，代表n个人围成一圈

【输出】

输出共一行，为最后留下来的那个人的编号

【样例输入】

5

【样例输出】

4

【数据范围】

保证100%数据 2<=n<=200

Answer 1

简单一点 直接数组模拟

如下

#include <stdio.h>
int main()
{
	int a[201] = {0};
	int n;
	int left;
	int i = 1, k=1;

	scanf("%d", &n);
	left = n;
	while(left != 1)
	{
		while(a[k])
		{
			k++;
			if(k > n) k = 1;
		}
		if(i == 3) 
		{
			i = 0;
			a[k] = 1;
			left --;
			printf("r %d\n", k);
		}
		i++;
		k++;
		if(k>n) k = 1;
	}
	for(i = 1; i <= n; i ++)
		if(!a[i]) break;
	printf("%d\n", i);
	return 0;
}