一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入格式：

输入在一行中给一个正整数N（≤1000）。

输出格式：

在一行中输出当选猴王的编号。

输入样例：

11

输出样例：

7

约瑟夫环问题，本程序使用链表方法。

#include <stdio.h>
#include <stdlib.h> 

int out = 0;

typedef struct link_list
{
	int data;
	struct link_list *next;
}link_list_t;

link_list_t *list_init(int n)
{
	//创建一个循环链表 ,赋予的值分别为1，2，3，4....n 
	link_list_t *head = (link_list_t*)malloc(sizeof(link_list_t));
	link_list_t *end = head;
	head->next = NULL;
	head->data = 1;
	//创建其余节点
	for(int i = 2; i < n + 1; i++)
	{
		link_list_t *node = (link_list_t*)malloc(sizeof(link_list_t));
		node->data = i;
		node->next = NULL;
		//尾巴指向当前
		end->next = node;
		end = end->next;
	}
	//出循环，尾部指向头
	end->next = head; 
	return head;
}
void josepho(int n,int m,int k)
{
	//n代表输入的人数，m代表数到m删除,k代表从序号k开始数 
	link_list_t *peopleList = list_init(n);
	link_list_t *curr = peopleList, *q = NULL, *front = NULL;
	int i = 0;

	for(i = 0; i < k - 1; i++)
	 	curr = curr->next;//更新当前位置为下一位

	//每次淘汰1个，最多淘汰n个
	for(i = 0; i < n; i++)
	{
		/* m<=0:无效数
			==1:直接删除当前位置
			==2:直接删除下一位置
			>=3:数到m后删除m的位置      */
		if(m >= 3)
		{
			for(int j = 2; j <= m; j++)//2数到m
			{
				curr = curr->next;
				if(j == m - 1)
					front = curr;//记录当前位置为删除位置的前一位地址
			}	
		}
		else
		{
			if(m <= 0)
				return;
			else if(m == 1)
				front = curr;
			else
			{
				front = curr;
				curr = curr->next;	
			}
		}
		//循环结束 
		out = curr->data;	//记录被淘汰的人 
		q = curr;			//记录要释放的位置 
		front->next = curr->next; 
		curr = curr->next;	//从当前淘汰位置下一位置开始数
		free(q);			//淘汰当前数到m的位置 
	}
	return;
}

int main()
{
    int num;
    scanf("%d", &num);
	josepho(num, 3, 1);
    printf("%d", out);
	return 0;
}