【原理分析】

【原理分析】

1.本题首先需要生成圆环上的n个点，然后对n个点进行编号，这一步并不困难.

2.接着需要按次序依次删掉对应编号的点（因为网络网板不能实现删除对象，所以用标记“×”表示该点删掉了），这一步是非常难的.要实现这个效果肯定需要用迭代来实现，本题迭代的难点就是如何利用上一个被删除点的编号计算出下一个要删除点的编号.但是如果要通过数数来确定下一个被删除点的编号，那么在迭代过程中，不仅要能够对每个点的不同状态进行标记，在迭代过程中能够读出这些点的状态，而且还需要在每次迭代中能够实时更新每个点的状态.我感觉这是网络画板做不到的，所以这个思路不可行.

那么，这题到底该如何做呢？

3.这题的关键就是要找到约瑟夫环的递推关系.约瑟夫环问题：N个人编号为1，2，…，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号.

递推公式：f（N，M）=（f（N-1，M）+M）%N

f（N，M）表示：N个人报数，每报到M时杀掉那个人，最终胜利者的编号.

f（N-1，M）表示：N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号.

下面我们不用字母表示每一个人，而用数字.例如：

1、2、3、4、5、6、7、8、9、10、11

表示11个人，他们先围成一个圈，假设每报到3的人被杀掉.

刚开始时，头一个人编号是1，从他开始报数，第一轮被杀掉的是编号为3的人.编号为4的人从1开始重新报数，这时候我们可以认为编号为4的这个人是队伍的头，第二轮被杀掉的是编号为6的人.编号为7的人开始重新报数，这时候我们可以认为编号为7这个人是队伍的头，第三轮被杀掉的是编号为9的人.

……

第九轮时，编号为2的人开始重新报数，这时候我们可以认为编号为2的这个人是队伍的头，这轮被杀掉的是编号为8的人.下一个人还是编号为2的人，他从1开始报数，不幸的是他在这轮被杀掉了，最后的胜利者是编号为7的人.

下面我们利用公式对上面的过程分析一下：

这个公式描述的是：幸存者在这一轮的下标位置.(https://www.daowen.com)

f（1，3）：只有1个人了，那个人就是获胜者，他的下标位置是0.

f（2，3）=（f（1，3）+3）%2=3%2=1：在有2个人的时候，胜利者的下标位置为1.

f（3，3）=（f（2，3）+3）%3=4%3=1：在有3个人的时候，胜利者的下标位置为1.

f（4，3）=（f（3，3）+3）%4=4%4=0：在有4个人的时候，胜利者的下标位置为0.

……

f（11，3）=6

说明：这里的下标是从0开始，因为取余的最小值是0，为了简便起见，所以规定下标从0开始.从这个过程中可以看出，要想知道后面一轮的结果，可以利用上一轮的结果计算出来.

4.为了更好的理解这一递推关系，我们再来看下面3个问题：

问题1：假设我们已经知道11个人时，胜利者的下标位置为6.那下一轮10个人时，胜利者的下标位置为多少？

答：其实第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利者也往前移动了3位，所以他的下标位置由6变成3.

问题2：假设我们已经知道10个人时，胜利者的下标位置为3.那下一轮11个人时，胜利者的下标位置为多少？

答：这可以看成是上一个问题的逆过程，大家都往后移动3位，所以f（11，3）=f（10，3）+3.不过有可能结果会越界，所以最后模上当前人数的个数，即f（11，3）=（f（10，3）+3）%11.

问题3：现在人数改为N，报到M时，把那个人杀掉，那么结果是怎么移动的？

答：每杀掉一个人，下一个人成为头，相当于把每个人的下标位置向前移动M位.若已知N-1个人时，胜利者的下标位置为f（N-1，M），则N个人的时候，就是往后移动M位（因为有可能结果越界，超过的部分会被接到头上，所以还要模N），即f（N，M）=（f（N-1，M）+M）%N.

注：理解这个递推式的核心在于关注胜利者的下标位置是怎么变的.每杀掉一个人，其实就是把每个人的下标位置向前移动了M位，然后逆过来，就可以得到这个递推式.