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

小小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();
        }

 

附录: 

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

无论是用链表实现还是用数组实现都有一个共同点:要模拟整个游戏过程,不仅程序写起来比较烦,而且时间复杂度高达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人参与评论

请发表评论

全部评论

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

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

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

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