报数游戏（约瑟夫环问题）

题目描述：

有n个小朋友做游戏，他们的编号分别是1,2,3…n。他们按照编号从小到大依次顺时针围成一个圆圈，第一个小朋友从1开始报数，依次按照顺时针方向报数（报数的值加一），每个报m的人会离开队伍，然后下一个小朋友会继续从1开始报数，直到只剩下一个小朋友为止。

求最后一位小朋友的编号。

Input
输入两个数字n，m(1<=m<=n<100000)，用空格隔开。
Output
输出最后一个小朋友的编号，独占一行。

Sample Input 1

7 5
Sample Output 1

6

仔细分析，用数组，循环解决：

#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n,k,i;							//总人数n，跳出数字k 
	scanf("%d%d", &n, &k);
	int *arr=(int*)calloc(n,sizeof(int));//分配大小为n的空间，并赋初值0 
	
	for(i=0;i<n;i++){//给这组数赋值 
		arr[i]=i+1;
	}
	int t=0,num=n;//计数变量
	for(i=1; ;i++){
		if(i>n)//回溯，从头开始计数 
		i=1;
		
		if(arr[i-1]!=0)//计数直到跳出数字k 
		++t;
		
		if(t==k){
			arr[i-1]=0;
			--num;
			t=0;
		} 
		if(num==1)//只剩一人跳出循环 
		break;
	} 
	//找出最后剩余的一位输出来 
	for(i=0;i<n;i++){
		if(arr[i]!=0){
			printf("%d",arr[i]);
			break;
		}
	}
	return 0;
}

百度借鉴大佬的代码，不用数组，用链表：

#include<stdio.h>  
#include<stdlib.h>  
typedef struct List  
{  
    int  data;  
    struct List *next;  
}list;  
   
int main()  
{
	list *L = (list*)calloc(1, sizeof(list));	//头结点
	L->next = NULL;
	int n, k, i;
	scanf("%d%d", &n, &k);
 
	list *s, *q = L;
	for (i=0; i<n; ++i)							//赋初值
	{
		s = (list*)calloc(1, sizeof(list));
		s->data = i+1;
		s->next = NULL;
		q->next = s;
		q = s;
	}
 
	q->next = L->next;							//让尾结点指向头结点的下一个，即第一个人的位置，单向循环链表创建完成
	q = L->next;								//让q指向头结点的下一个
 
	while (q->next != q)						//只剩一个元素时，退出循环
	{
		for (i=1; i<k-1; ++i)
		{q = q->next;}							//q指向删除节点的前一个
		s = q->next;							//s指向删除节点
		q->next = s->next;						//将去除s后的链表重新连接起来
		q = q->next;							//让q指向下次循环的起始位置
		//printf("%d ", s->data);
		free(s);
		s = NULL;
	}
 
	printf ("%d\n", q->data);
	free(q);
	q = NULL;
	free(L);
	L = NULL;
	return 0;
}

后来还有大佬写出迄今为止看到的最短小版本 tql：

#include<stdio.h> 
int main(){ 
  int n, k, i, s = 0; 
  scanf("%d%d", &n, &k); 
  for (i = 2; i <= n; ++i){ 
    s = (s+k)%i; 
  } 
  printf("%d\n", s+1); 
  return 0; 
}