[抛砖引玉]一起来做道算法题吧。解决方案-C#教程-爱易网页

[抛砖引玉]一起来做道算法题吧。解决方案

日期：2014-05-20　浏览次数：21201 次

[抛砖引玉]一起来做道算法题吧。
有n个孩子（编号1,2...n）围成一圈，现在从编号为k的孩子开始报数，当报数到m时，报m的那个孩子出列，然后从报m的那个孩子的下一个孩子重新开始从1报数...
求：孩子们出列的序列。

以上是题目，我自己实现了一下，感觉不好，但测试了几个，序列还是正确的，现贴出来，希望和大家讨论以后能够得到更精妙的算法。本人算法实在是太差了。

C# code


static void Main(string[] args)
        {
            int[] a = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
            OutQueue(a, 2, 4);
        }

        static void OutQueue(int[] obj, int k, int m)
        {
            if (obj == null || obj.Length == 0)
                return;
            if (k < 1 || k > obj.Length)
            {
                Console.WriteLine("K value is invalid!");
                return;
            }
            if (m <= 0)
            {
                Console.WriteLine("m value is invalid!");
                return;
            }

            int count = 0;               //同m比较，数到m就输出当前位置
            int mod = m % obj.Length == 0 ? obj.Length : m % obj.Length;    //防止m超过数组长度，取模代替之
            int index = k-1;               //存放当前的index,为什么要-1？因为数组下标从0开始
            int got = 0;

            while (got < obj.Length - 1)
            {
                count = 1;
                for (int j = 0; j < mod; j++)
                {
                    if (count == mod)
                    {
                        while (obj[index % obj.Length] == 0)
                            index++;
                        Console.WriteLine("The {0} person is out of queue!", index % obj.Length + 1);
                        got++;
                        obj[index % obj.Length] = 0;
                    }
                    count++;
                    index++;
                }
            }


            for (int i = 0; i < obj.Length; i++)
            {
                if (obj[index % obj.Length] != 0)
                    Console.WriteLine("The {0} person is out of queue!", index % obj.Length + 1);
                index++;
            }
        }

输出结果：

XML code


The 5 person is out of queue!
The 9 person is out of queue!
The 2 person is out of queue!
The 6 person is out of queue!
The 10 person is out of queue!
The 3 person is out of queue!
The 7 person is out of queue!
The 11 person is out of queue!
The 4 person is out of queue!
The 8 person is out of queue!
The 1 person is out of queue!

------解决方案--------------------
约瑟夫环
------解决方案--------------------
网上找的：

C++版
int fun(int n, int m)
{

int i, r = 0;

for (i = 2; i <= n; i++)

r = (r + m) % i;

return r+1;

}

循环链表解决

优化
------解决方案--------------------
类似于猴子选大王问题: 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1到m的顺序围坐一圈，

从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王

C# code

using System;
using System.Collections.Generic;
using System.Text;

namespace ExMonkey
{
    class Monkey
    {
        public int King(int M, int N)
        {
            //总人数 M ，数到第 N 个排除。 
            int k=0;
            for (int i = 2; i <= M; i++)
                k = (k + N) % i;
            return ++k;
        }
        static void Main(string[] args)
        {
            Monkey M = new Monkey();
            Console.WriteLine ("第"+M.King(10,3)+"号猴子为大王。");
        }
    }
}

------解决方案--------------------
只要排成队的增插删改一律用链表，高效。

------解决方案--------------------
using System;

免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。

[抛砖引玉]一起来做道算法题吧。解决方案

相关资料更多>

推荐阅读更多>