约瑟夫问题-变式（一种个人的解法）

题目：有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。

解题思路（或者说过程）：不妨找到特殊的n值，使得1号选手留到最后，显而易见的是，当n为1时，1号选手必然留到最后，做出假设，存在正整数k，当n=k时，1号选手存活到最后（存在性可证），然后，于所有的非负整数s，n=k+s时，（1+3*s）或者（1+3*s-n）号选手可以活到最后，后者是为了保证结果不超出n。我们可以从排人的角度理解这个假设，首先，一开始我们指向的会是一号选手，此时报数必为1，然后接着，排出一个人之后，我们指向了4号选手，这是4号选手报数也为1，接着，我们指到的号数依次会为7，11，14.....不难看出，每次排除一个人，我们指到的号数便会增加3，所以，首先我们能知道的则是，排出了s号人之后，我们指到的位置号数是（1+3*s）或者（1+3*s-n），其次，我们控制n=k时，1号选手都会留到最后，那么我们可以将排除了s号人之后的指到的那个人，视作n=k时的1号选手，则这个人便能活到最后（等效替代），因此，我们可以通过推理得知这个假设是正确的，合理的，从另一个角度来看，这个假设亦可以用归纳假设的方式去做证明，这里本文便不对此处的归纳做过多展开，请读者自己证明。

在知道上面的规律之后，我们便要将其变换成程序可以做的形态。假设我们只知道n=1时1号选手留到最后(知道1个特殊解就足够），将n从一开始递增，每次增加的时候，对应的结果a【n】都要加3，顺便检测是否超出n的范围，超出范围的时候要及时对结果进行处理（-n）。这样的话，我们便可以通过这个循环，得出一个数组，该数组上面对应的则是对应项数的留到最后的选手号数。

代码展示：

#include

int main()

{

 int n;scanf("%d",&n);//输入

int a[n];a[0]=1;//需要补充的是，这里0对应的是总人数为1的情况，k对应的是总人数为k+1的情况。

int i;for(i=0;i<n-1;i++){

a[i+1]=a[i]=3;if(a[i+1]>i+1)a[i+1]-=(i+1);//写出循环，一定要补充if的条件。

                                   }

printf("%d",a[n-1]);return(0);//得出结果，返回0。

}

题外话：该题属于约瑟夫问题的延展，约瑟夫的问题就相当于报数报道2就要排人的情况，这种情况下，2的方幂次数的总人数总会是第一个人就留到最后，因此，我们可以率先得出无数个特殊解，便能避免了上面要减去总人数的那种情况，假设x为存活选手号数，y为总人数，a<2^n，a和n都是非负整数，在n最大化的情况下，y=a+2^n，则x=2*a+1，不难证出，这种情况下的x<=2^(n+1)-1=y，因此算出来的结果都是控制在范围之内的，就不需要对其作减法（减去总人数）处理。如果，增添了数到m才停止且m也要手动输入的要求，则把上面代码中的3改为m且增加m的输入语句即可。

最后，希望大家多多指教，本人为第一次撰写文章，很多地方用词可能不太舒服，还望各位多多谅解。谢谢阅读！