约瑟夫环算法

显示全部楼层 · 2018-1-30 17:14:53

   前段时间在逛百度的时候，发现了约瑟夫环这个算法；当时刚好忙完了，左右没事就花了点时间去研究了下这个算法，研究了才知道这算法还真点研究价值。
   话说，在犹大人和罗马的战争期间，约瑟夫和其他40个犹大人反判者被罗马军队困在一个山洞中；这些犹大人反判者宁愿自己自杀也不想成为罗马的俘虏，于是他们站成了一个圆，从其中的某个人开始数每数到三就要被杀掉，直到所有人死光。但约瑟夫和他的一个朋友觉得自杀没意义，并不想死，于是他们很快就算出他和他朋友应该站在什么位置，使他们成为最后两个人，并最终活下来。
   从上面的事件中我们可以知道两点信息：
   1、人员的总数：40；
   2、每次数到三的人都要被杀掉（数到数值）：3；    好，现在我们就来解决这一题，然后写出成一个算法：
   首先，我们先把每个人分配个编号，第一个数数的为1号，第二个为2号，以些类推一直到40号；然后我们可以慢慢排除要死掉的人，剩下的最后两位数就是我们最终的解（13，28）。
方法操作思路出来了，我们就可以对算法进行实现了，代码如下：

[C#] 纯文本查看 复制代码

 /// <param name="strArr">源数组（1-40）</param>
        /// <param name="Num">数到几移除（3）</param> 
        /// <param name="StartNum">开始数（1）</param>
        /// <returns></returns>
        public ArrayList GetArrList(ArrayList strArr, int Num, int StartNum)
        {

            ArrayList ArrSource = new ArrayList();
            int nCount = 1; 
            int index = StartNum - 1;
            while (strArr.Count > 0)
            {
                //数到移除数（3）
                if (nCount == Num)
                {
                    ArrSource.Add(strArr[index]);
                    strArr.Remove(strArr[index]);
                    nCount = 1;
                }
                else
                { 
                    nCount++;
                    index++;
                }
                //数到最后一个后回到每一个。
                if (index == strArr.Count)
                {
                    index = 0;
                }
            }
            return ArrSource;
        }