约瑟夫环的数组

最近忙着提升自身的访谈能力，美其曰：“提高自身的业务能力”，两字呵呵。感觉在公司前途一片黑暗，连丝曙光都不见，好在我有一颗强大的❤，感谢mother 。因为模拟对象中有一位学习中等，在班中扬言..... 此处略去一百字，所以我就想到自己教过的学生中就有这么一位。 然后就和他QQ聊了两句，我怎么能这么敬业呢O__O"…。 没想到该学生现在准备学IOS，IOS可是我一直想去学没学的技术啊，简直帅爆了。 今天早上他给我发了一道题：约瑟夫环的数组实现。为了打发我郁闷苦逼的心情和大把的时间，做了一下。 最后发现网上有写好的demo比我的要好，于是乎我就重新整理，添加了注释。题和正解如下：

约瑟夫环的数组实现

约瑟夫(Josephus)问题是由古罗马的史学家约瑟夫提出的,他参加并记录了公元 66-70 年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达 伯特城达 47 天之久,在城市沦陷之后,他和 40 名将士在附近的一个洞穴中避难。在哪里,将士们群情激奋并表示:要投降毋宁死。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签并且做为洞穴中两个幸存者之一生存下来。

约瑟夫环问题的具体描述是:设有编号为 1,2,......,n 的 n(n>0)个人围成一 个圈,从第一个人开始报数,报到 m 时停止报数,报 m 的人出圈,再从他的 下一个人起重新报数,

报到 m 时停止报数,报 m 的出圈,......,如此下去,知道只剩下一人为止。当任意给定 n 和 m 后,设计算法求 n 个人出圈的次序。

假设有n=5 ,5个人： 1 ，2 ， 3， 4， 5 ，

从第1个人开始报数字， 如果报的数字m为 2， 这个人被同伴杀死，出局被杀死人的顺序是： 2, 4, 3, 1, 5

代码如下

 1  /// <summary> 2         /// 约瑟夫环的数组实现 3         /// </summary> 4         /// <param name="n">总人数</param> 5         /// <param name="m">从编号为几开始数数</param> 6         /// <param name="k">数到几的人出局</param> 7         public  static void Josehp(int n, int m, int k) 8         {    9 10             //创建一个和总人数相同长度的数组11             int[] array = new int[n];12             for (int i = 0; i < n; i++)13             {14                 array[i] = i + 1; //循环给每一个数组元素赋值，编号为 1, 2, 3, 4 ,...., n 15             }16 17 18             int count = 0; //记录数数的标号19 20             int number = n; //记录剩余的总人数21 22             while (number > 1)23             {24                 for (int i = 0; i < n; i++) //循环遍历数据里面的每一个元素25                 {26                     if (m != 1) //如果不是从编号1开始27                     {28                         i = m - 1;  //从 m 为的成员开始， m 为的这个人 为第1个人29                         m = 1;30                     }31                     if (array[i] == 0) //判断array[i] 这个人是否已经出局，如果出局，继续循环，判断下一位32                         continue;33                     count++;34                     if (count == k) //如果要数的数字与出局数字相同35                     {36                         Console.Write(array[i] + " "); //输出出局的编号37                         array[i] = 0; //将该位置标记为038                         count = 0; //数数标号从0开始39                         number--; //总人数 -1 40                     }41                 }42             }43 44 45             //循环判断不为0的元素，即为最终留下的人46             for (int i = 0; i < n; i++)47             {48                 if (array[i] != 0)49                 {50                     Console.Write(array[i]);51                     break;52                 }53             }54 55             Console.WriteLine();56         }

 1   static void Main(string[] args) 2         { 3             Console.WriteLine("请输入总人数："); 4             int m = int.Parse(Console.ReadLine()); 5              6             Console.WriteLine("请输入报数："); 7             int n = int.Parse(Console.ReadLine()); 8  9             Console.Write("总人数是{0}, 从第{1}个人开始数数, 数到{2}时出局，出局人的顺序是：",m,1,n);10             Josehp(m,1,n);11 12             Console.ReadLine();13         }