大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C#技巧 > 约瑟夫环的数组

约瑟夫环的数组

关键词:约瑟夫数组  阅读(688) 赞(19)

[摘要]本文是对约瑟夫环的数组的讲解,对学习C#编程技术有所帮助,与大家分享。

最近忙着提升自身的访谈能力,美其曰:“提高自身的业务能力”,两字呵呵。感觉在公司前途一片黑暗,连丝曙光都不见,好在我有一颗强大的❤,感谢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

代码如下

  /// <summary>
         /// 约瑟夫环的数组实现
         /// </summary>
         /// <param name="n">总人数</param>
         /// <param name="m">从编号为几开始数数</param>
         /// <param name="k">数到几的人出局</param>
         public  static void Josehp(int n, int m, int k)
         {   
 
             //创建一个和总人数相同长度的数组
             int[] array = new int[n];
             for (int i = 0; i < n; i++)
             {
                 array[i] = i + 1; //循环给每一个数组元素赋值,编号为 1, 2, 3, 4 ,...., n 
             }
 
 
             int count = 0; //记录数数的标号
 
             int number = n; //记录剩余的总人数
 
             while (number > 1)
             {
                 for (int i = 0; i < n; i++) //循环遍历数据里面的每一个元素
                 {
                     if (m != 1) //如果不是从编号1开始
                     {
                         i = m - 1;  //从 m 为的成员开始, m 为的这个人 为第1个人
                         m = 1;
                     }
                     if (array[i] == 0) //判断array[i] 这个人是否已经出局,如果出局,继续循环,判断下一位
                         continue;
                     count++;
                     if (count == k) //如果要数的数字与出局数字相同
                     {
                         Console.Write(array[i] + " "); //输出出局的编号
                         array[i] = 0; //将该位置标记为0
                         count = 0; //数数标号从0开始
                         number--; //总人数 -1 
                     }
                 }
             }
 
 
             //循环判断不为0的元素,即为最终留下的人
             for (int i = 0; i < n; i++)
             {
                 if (array[i] != 0)
                 {
                     Console.Write(array[i]);
                     break;
                 }
             }
 
             Console.WriteLine();
         }
约瑟夫环的数组实现
   static void Main(string[] args)
         {
             Console.WriteLine("请输入总人数:");
             int m = int.Parse(Console.ReadLine());
             
             Console.WriteLine("请输入报数:");
             int n = int.Parse(Console.ReadLine());
 
             Console.Write("总人数是{0}, 从第{1}个人开始数数, 数到{2}时出局,出局人的顺序是:",m,1,n);
             Josehp(m,1,n);
 
             Console.ReadLine();
         }


相关评论