约瑟夫环

问题有很多种类型。。。比如每次报m个,或者第i次报第i个的干掉

最后一个被干的原编号?

考试看错题了推了两小时的假题(......)

所以有个递推公式。。。

找了篇不错的博客终于看懂;

将编号统一减一最后加回来。。。(为了方便啊)

假设现在有n个人那么被干的是当前编号为m-1的这很显然。((m-1)%n=m-1)  (应该还记得把编号减一了吧,所以不是m)

新的一轮从第m个人开始

m->0

m+1->1

m+2->2

m-3->n-3

m-2->n-2

注: 有n个人干掉一个编号从0->n-2所以没有m-1->n-1他已经出局了。

解(x+m)%n->x

所以求出新一轮编号x后(x+m)%n  (剩余人数这一轮是n而已) 即可求解

所以每次n个人最后一个可以由n-1个的问题递推过来

起始:只有1个人新编号当然是0

f[1]=0;

f[i]=(f[i-1]+m)%i;

答案为f[n];

考虑第二个问题:其实一样只不过每次报的号是与i有关的把+m和%i换成每次未干之前的应报编号和剩余人数即可。

复杂度O(n);

原文地址:https://www.cnblogs.com/three-D/p/11400049.html