关于约瑟夫环递推式的一些思考

题目大意：

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<cstdio>
#include<iostream>

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个人第一次出列后，剩下的人的排列顺序。
所以我们的任务就变成了，在新的序列里面，找到最终剩下的位置上那个人的编号，就是那个递推式的意义。
个人感觉，弄清楚了这个关系，可能会更好理解这个递推式。
以后 递推也可以仿照这个思路，一步步来。

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/01/16/2021-01-16-YSF/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！