Question

c#中关于“猴子选大王”代码的困惑！

猴子选大王问题: 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1到m的顺序围坐一圈，

从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王

using System;
using System.Collections.Generic;
using System.Text;

namespace ExMonkey
{
class Monkey
{
public int King(int M, int N)
{
//总人数 M ，数到第 N 个排除。
int k=0;
for (int i = 2; i <= M; i++)
k = (k + N) % i;
return ++k;
}
static void Main(string[] args)
{
Monkey M = new Monkey();
Console.WriteLine ("第"+M.King(10,3)+"号猴子为大王。");
}
}
}

求下面此循环的意义？
for (int i = 2; i <= M; i++)
k = (k + N) % i;

Answer 1

总人数是M，所以需要数M-1次才能得到结论：
for (int i = 2; i <= M; i++)就是循环M-1次；

这个其实是个极简化的递归公式，详情你看百度百科好吧，Josephus(约瑟夫)问题的数学方法这一段

追问

谢谢，我昨天就看了，有点不太明白，这个
现在我们把他们的编号做一下转换： 　　k --> 0 　　k+1 --> 1 　　k+2 --> 2 　　... 　　... 　　k-3 --> n-3 　　k-2 --> n-2
对应关系中为什么最后是k-2 --> n-2 ；搞清楚这个我差不多就明白了，是不是我太笨了！

追答

现在我们把他们的编号做一下转换： 　　k --> 0 　　k+1 --> 1 　　k+2 --> 2 　　... 　　... 　　k-3 --> n-3 　　k-2 --> n-2
这一段是说第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人给他们分别标号为0,1,2,....,n-2

追问

我想说的是为什么n-2的标号是k-2啊？

追答

k=m%n，也就是说结束了第一轮之后还剩下n-1个人，然后假设k是第二轮报数开始的第一个人。
k-1不是第一圈被选中了么，所以k前面那一个就是k-2啊！然后把这个序号给变成从0开始的连续序号，第一圈之后不是剩下n-1个人么，排序的序号就是0~n-2啊。。我觉得解释的很清楚了。。楼主还不明白的话再留言。。。我再想想怎么解释。。。

追问

这个我明白了！谢谢！下面的序列是什么意思呢？
序列1： 1, 2, 3, 4, …, n-2, n-1, n 　　
序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n 　
序列3： k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1 　
序列4：1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1

追答

呃，大哥你这零分的问题啊。。
序列1->序列2就是k被选中以后剩下n-1个人的状况
序列2->序列3是把上面的那个环从k+1开始变成头
序列3->序列4就是把这个新的序列用1~n-1来编号
也就是说n个人的问题推导成n-1个人的问题

追问

你才是大哥，放心吧，搞明白这个好处大大的有，我先研究着，追加一条不是给10分么，面包会有的，牛奶也会有的！think you！

追答

额。。你继续研究吧。。

追问

求下面这个公式 x' = x+k的意义？我想了很久没想明白和上面这个表的联系！

追答

x'表示n个人的解，x表示n-1个人的解，然后n个人的问题根据上面那四个序列的变化就能转化成n-1个人的问题，倒着推回去的话也是成立的。。
x'=x+k就是中间的推导关系。。你再仔细想想