题目先导：

　　有N个人围成一圈，按照1~n的顺序编好号。从第一个人开始报数，报到2的人退出圈子，下一个人从1开始重新报数，报到3的人退出圈子。如此下去，直到留下最后一个人，求留下来最后一个人的编号。

 

 

首先这题是我之前写过的一个题，当时第一反应是数组，确实数组使用标记可以完成任务。

代码如下:

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int a[1000]={0};//数组a大小为人数上限 
 5     int n,m=3,i,f=0,t=0,s=0;
 6     scanf("%d",&n); 
 7     do
 8     {
 9         t++;//逐个枚举圈中的所有位置
10         if(t>n)
11             t=1;//数组模拟环状，最后一个与第一个相连
12         if(!a[t])
13             s++;//第t个位置上有人则报数
14         if(s==m)//当前报的数是m
15         {
16             s=0;//计数器清零
17             
18             a[t]=1;//此处人已退圈，设置为空
19             f++;//退圈人数+1
20         }
21     }while(f!=n);//直到所有人都退圈为止
22     printf("%d",t);//输出最后一人编号
23     return 0;
24 }

但是N可以非常大，这种方法的时间复杂度是O（nm）,所以效率比较低。

当然，还有其他解决方法。其实这是一个典型的约瑟夫问题。

我们可以把问题重新分析：

　　为了方便程序设计我们将报号从1,2,3改为0,1,2（原因后面解释），为了使问题更具有普遍性将报数上限从3修改为m；

　　那么对于n个人有一下序列：

       0,1,2,3,4,······，m-1,m,m+1，······，n-1,n

　　那么有人（m-1）退出后序列应该为：

       m,m+1，······，n-1,n，0,1,2,3,4,······，m-2

　　对应新的编号为：

       0,1,2,3,4,······，m-1,m,m+1，······，n-1

　　如果我们一直列举到最后一个人的话

　　最后的序列应该是

       1

　　对应的编号为

       0

　　但是n可以趋近无穷大，所以一次次列举是不现实的，所以我们可以分析下上述列举过程。

　　我们先从有n个人开始，对这n个人中的第一个人开始编号为0，第二个为1...以此类推直到编号到m-1时，将m-1所代表的人剔除

则下一轮中有n-1个人，并以m开始编号，令其为0，以此类推。

　　我们可以发现每一次剔除一个人，总人数就减少一个，当总人数sum = n到sum = n-1这个过程中，并不影响最终的结果，所以我们可以把总人数sum = n-1状态看做一个新序列，那么这个新的n-1序列的解仍是sum = n时的解，那么序列n-2的解就是序列n-1的解，所以我们一层层递推就可以发现原序列n的解就是序列长度为1时的解，对应的编号是0。

我们从正向思考，设题目的解在X长度下的编号为f(X)，当长度为n时，编号为m的人，在新的序列n-1中的编号应该为f(n-1) = [ f(n) + m ] % n （因为出现了取模运算所以会出现0的结果，所以之前需要在编号时0开始）（不理解的话可以往下翻翻看看递推图）

　　那么不难得出 f(n) = [ f(n-1) + m ] % ( n - 1 ) ,由此我们得出了递推公式。便可以设计一下程序：

 1 #include <stdio.h> 
 2 int main() 
 3 { 
 4     int n, s = 0,m = 3; 
 5     scanf("%d", &n); 
 6     for (int i = 2; i <= n; ++i) 
 7         s = (s+m)%i; 
 8     printf("%d\n", s+1); //加1是因为从0开始编号
 9     return 0; 
10 }

当然还可以设计以下标准递推函数：

1 int function(int n,int m){
2     if(n==2)  return 1;
3     return (function(n-1,m)+m)%(n-1);
4 }

但是不建议这样做，因为这种方式使用到了栈，对空间的消耗比较大。

其实这题深入下去会涉及到链表，但是最近时间比较紧，有时间再写链表。

附图：

 

 如果你细心的话，或者手写过程的话你会发现N之后的数字就是N在每一轮的编号。