本文共 854 字，大约阅读时间需要 2 分钟。

题目大意：

N个人坐成一个圆环（编号为1 - N），从第1个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2。2号先出列，然后是1号，最后剩下的是3号。 （其实这是一段非常悲惨的历史故事的改编，愿世界永无战争，虽然这是个幻想）

具体思路：

暴力的方法就不讨论了，我想从递推这个角度考虑 （万物皆可递推）

假设我们知道x个人，每次报数k个人，最终出列的人的编号是Y，那么是否可以推出x+1个人的时候呢？ 仔细想一想，x+1个人的时候，出列一个人之后，就变成了x个人，而且知道第一个出列的人的编号是k，那么k之后的所有人的位置就都向前k位（因为k+1成了第一个人），那么结果显然就是在新的序列里面的第Y个人。为了防止越界，只需取模就好了。

代码

#include
   
    #include
    
     int n,k;int main(){
       scanf("%d%d",&n,&k);    int p=0;//为了方便取模，从0开始，最后再加1    for(int i=2;i<=n;++i){
           p=(p+k)%i;    }    printf("%d\n",p+1);    return 0;}
    
   

一些思考：

在比赛的时候，我想到了用递推这个解法，但是始终觉得思路少了点什么。后来发现这种不想自信感来源于对这个递推式的理解不够透彻，其实这个递推式的来源，是分为两步的：

**1.**我们已经知道了x个人，最终剩下的人的位置是多少（从第一个往后数） **2.**我们知道了x+1个人第一次出列后，剩下的人的排列顺序。 所以我们的任务就变成了，在新的序列里面，找到最终剩下的位置上那个人的编号，就是那个递推式的意义。 个人感觉，弄清楚了这个关系，可能会更好理解这个递推式。 以后 递推也可以仿照这个思路，一步步来。

把你mikumiku掉！

今天是双十一，希望大家不会被消费主义蒙蔽了双眼。

转载地址：http://ouuci.baihongyu.com/