• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号
登陆 注册

小小c#算法题-12-JosephCircle（约瑟夫环）

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数（从1开始报数)，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 

首先从编程的角度声明一下上面描述中的一点，就n,k,m这些都是下标从1开始的。而在实际编程中，我们一般将下标从0开始。所以这一点要注意一下。 

第一种方法：使用队列。 

这种解法直观，简单。首先你要明白队列这种数据结构，是一种先进先出的线性结构，如同生活中的排队，先到先处理。 

明白了队列的结构。下面讨论一下如何应用队列解决约瑟夫环的问题。为了方便，我们假设从第1个人开始报数。从其定义中可知，每数到m的那个人退出，那么对于队列，我们首先从队头开始报数， 

（1）如果不是m，把这个数从队头拿掉放到队尾； 

（2）如果是m，那么让这个元素出队列； 

如此循环下去，直接队列中的所有元素都出队列。  

例子： 

队列a，b，c 其中a为队头，c为队尾，报数为2时出队列 

处理队头元素a，报数为1，不为2，这时取出队头元素a放到队尾，队列变为b,c,a 其中b为队头，a为队尾 

处理队头元素b，报数为2，这时让b出队列，队列变为c,a 其中c为队头，a为队尾，报数从新开始，即下次c报数1，a报数2 

...如此循环下去，直到所有元素出列，队列长度为0 

 

下面再考虑如何从第k个元素开始，其实就是把第k个当作队头来使用就可以了。下面的c#代码先把数组元素放到一个队列中，然后在放的时候，先放第k个，依次放下去即可。这样第k个元素即队列的队头，也即从第k个元素开始报数。 

c#代码： 

        private static void JosephCircle(int[] numbers, int k, int m)
        {
            Queue<int> numbersQueue = new Queue<int>();
            k = k - 1;

            for (int i = k; i < numbers.Length; i++)
            {
                numbersQueue.Enqueue(numbers[i]);
            }

            for (int i = 0; i < k; i++)
            {
                numbersQueue.Enqueue(numbers[i]);
            }

            int flag = 0;
            while (numbersQueue.Count > 0)
            {
                flag++;

                if (flag != m)
                {
                    numbersQueue.Enqueue(numbersQueue.Dequeue());
                }
                else
                {
                    Console.WriteLine(numbersQueue.Dequeue()); //输出出列项的编号，下标从1开始
                    flag = 0;
                }
            }
        }

 

上面的代码中，直接使用了.net 类库中的Queue类，当然了你也可以自己实现一个队列的数据结构，比如用链表，此处不作示例了。 

 

第二种方法：递归 

也可以采用递归的算法，这里我们只关注最后退出的那个人。 

仍然假设从第一个人开始报数，每当数到m时退出：（下标从0开始） 

如果只有一个人，那么最后退出的肯定就是这个人，下标为0。 

… 

如果有x个人，每当数到m时退出，且已知最后退出的人的下标为i。 

那么当有x+1个人的时候，最后退出的人的下标应该是多少呢？下面我们来分析一下： 

有x+1个人的时候，数到第m个(下标为m-1的人），这个人退出，注意此时只剩x个人了，然后从下一个人开始报数，这个人的下标为m%(x+1)，这个人即为当有x个人的情况下，第一个开始报数的人。所以有： 

x+1个人的时候的下标为m%(x+1)的人 

 

就是

x个人的时候第一个报数的人 

 

也就是说 

x个人时候，下标为0的人，其实就是x+1个人的时候，下标为m%(x+1)的那个人  

那么如果x个人的时候最后退出的人的下标为i，如果把这个人放回到x+1个的情况的时候，这个人的下标就应该是 (m % (x + 1) + i) % (x + 1) = (m + i) % (x + 1)  

所以可以推导出一个公式，假设有x个元素时，最后退出的元素为f(x),那么有 

f(x+1) = (m+f(x))%(x+1) 

如果这里的推导没有看明白，可以参考一下文章最后的附录部分的推导，是从其他地方摘过来的。

所以有如下c#代码： 

        private static int GetIndex(int itemCount, int m)
        {
            if (itemCount == 0)
            {
                return 0;
            }
            else
            {
                return (GetIndex(itemCount - 1, m) + m) % itemCount;
            }
        }

现在再考虑从第k个人开始报数的情况，我们只需要在得到最后退出人的下标后稍微处理一下即可，然后根据下标输出相应的元素： 

        private static void JosephCircleRecurcively(int[] numbers, int k, int m)
        {
            int winnerIndex = GetIndex(numbers.Length, m);

            //输出最后一个出列项的编号，下标从1开始
            Console.WriteLine(numbers[(winnerIndex + k - 1) % numbers.Length]); 
        }


注意，递归是比较占用内存的，所以如果数据量特虽巨大，这肯定是不合适的。下面一种直接求解的算法比较高效。 

 

第三种方法：根据递归公式直接求解。 

依然是只关注最后退出的那个人。 

有了公式，那么可以一个for循环直接求解，代码如下： 

        private static void JosephCircleMath(int[] numbers, int k, int m)
        {
            int winnerIndex = 0;

            for (int i = 2; i <= numbers.Length; i++)
            {
                winnerIndex = (winnerIndex + m) % i;
            }

            //输出最后一个出列项的编号，下标从1开始
            Console.WriteLine(numbers[(winnerIndex + k - 1) % numbers.Length]); 
        }

当然了，这是最高效的算法。 

 

最后是Main方法中的测试调用代码： 

        static void Main(string[] args)
        {
            int[] numbers = { 10, 20, 30, 40, 50, 60 };
            int m = 3;
            int k = 2;
            JosephCircle(numbers, k, m);
            JosephCircleMath(numbers, k, m);
            JosephCircleRecurcively(numbers, k, m);
            Console.ReadLine();
        }

 

附录： 

下面是百度百科上递归公式的推导过程，供参考： 

http://baike.baidu.com/link?url=A5P0NnCQT2rzXMmmGKyLfdV_fti-1hL151QEFTAh3bnwY-Xe4FxmKxDTS36mJtsc 

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm），当n，m非常大（例如上百万，上千万）的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。 

为了讨论方便，先把问题稍微改变一下，并不影响原意： 

问题描述：n个人（编号0~(n-1）），从0开始报数，报到m-1的退出，剩下的人继续从0开始报数。求胜利者的编号。 

我们知道第一个人（编号一定是（m-1）%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）： 

k k+1 k+2 ... n-2,n-1,0,1,2,... k-2 

并且从k开始报0。 

我们把他们的编号做一下转换： 

k --> 0 

k+1 --> 1 

k+2 --> 2 

... 

... 

k-3 --> n-3 

k-2 --> n-2 

序列1：0,1,2,3 … n-2,n-1 

序列2：0,1,2,3 … k-2,k，…，n-2,n-1 

序列3：k,k+1,k+2,k+3，…，n-2,n-1,0，1,2,3，…，k-2, 

序列4：0,1,2,3 …，5,6,7,8，…，n-3,n-2 

变换后就完完全全成为了（n-1）个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来： 

∵ k=m%n; 

∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n 

∴x'= (x+ m%n)%n = (x+m)%n 


鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
C++获取基类指针所指子类对象的类名发布时间：2022-07-14
下一篇：
Emscripten编译环境搭建--将C和C++编译成JS发布时间：2022-07-14
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap