猴王算法

Question

谁能用C#给我写一个猴王算法:
有n只猴子围成一圈,从第一个开始数,数到第m个将其踢出,接着后面继续从1数,如此循环,直到只剩最后一只z,那只就是猴王.输入n,m.输出z.

Answer 1

using System; 
using System.Collections.Generic; 
using System.Text; namespace Monkey 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            int num; 
            num=Monkey(3, 1, 2); 
            Console.WriteLine(num); 
            Console.ReadKey(); 
        }         static int Monkey(int sum, int diJiGe, int shuDaoJi) 
        { 
            int paiChu=0; 
            int i =diJiGe - 1; 
            int k = 0; 
            int [] myMonkey=new int [sum]; 
            while ((sum - paiChu) != 1) 
            { 
                if (myMonkey[i] == 0) 
                { 
                    k = k + 1; 
                    if (k == shuDaoJi) 
                    { 
                        myMonkey[i] = 1; 
                        k = 0; 
                        paiChu = paiChu + 1; 
                    } 
                } 
                i = i + 1; 
                if (i > (sum - 1)) 
                    i = 0; 
            } 
          int m=0; 
            for (int j = 0; j < myMonkey.Length; j++) 
            { 
                if (myMonkey[j] == 0) 
                    m = i; 
            } 
            return m+1; 
        } 
    } 
} 

Answer 2

       public int monkeyKing(int n, int m)  //n只猴 ，m个排除。
        {
            int z=0; //z是王
            for (int j = 2; j <= n; j++) z = (z + m) % j;
            return ++z;
        }

Answer 3

最后一道题是1000个猴子从0到999编号手拉手，从头开始数把单数都扔出去，然后剩下的再手拉手单数扔出去……依此类推，剩下的最后一只猴子应该是多少号的。     这传说中的猴子选大王的题目董延明是第一次碰到，他一边看题的时候一边跑神，想的是把单数猴子都扔出去，扔出去干什么呢？做猴脑？后来又想到马三立买猴，总之是没有想到一个好算法。孔工笑眯眯的说，“写不出来能说个思路就好。”     “哦，哦，就是……弄个数组，从0到999，然后设个while遍历数组，把单数的置零，然后再从头遍历，再把单数置零，然后再循环，一直到剩最后一个了，它的下标就是那只猴子的编号。”董延明一边说一边在纸上给孔工画着圆圈，最后花成了五环才解释完。     孔工倒没问怎么确定循环到最后一个猴子会自动停止等细节，他不置可否把卷子拿到一边批阅了一下，然后把分数填到几页纸上，他坐着离董延明稍远问了董延明的年龄什么的填到那几页纸上。董延明藏不住事情，忍不住问他，“孔工，我刚才答了多少分？”     孔工一愣，显然之前不是有很多人问过，“还不错，七八十分吧。”     董延明有些心安了，又问：“那么，最后一道题我答的对么？”     孔工先点头又摇头然后想继续问董延明的个人情况，董延明不甘心抢着问：“那应该怎么做啊，怎么设计才对，我也觉得我设计的有点笨。”     孔工看来也是怕滚刀肉这类人，满脸我怕了你的笑容说：“其实不一定要用数组，你每次都遍历整个数组需要多少时间啊，有没有另外一种结构可以把用过资源抛出去？对，链表嘛！单向循环都可以，这样每次都遍历上次的二分之一……” 

Answer 4

正解啊，简短精悍，我为了验证其正确性，想了不少时间，如果lzsh0622可以说明原理的话，就可以省去其他人去理解的时间了。我来说说我的理解:由于猴子是围成一圈的，所以实际序号是可以无限大的，我们不妨假设当前序号z是前面一次序号减去了m后剩下的序号，如果前面一次序号小于m，只要反复+j（当前面一次有j个猴子时），让序号大于m即可，而最后剩下一个猴子的时候序号肯定为0，返回值是++z正好为1，代表第一个猴子。由此可见，只要每次将当期序号z反过来加上m后，就是前面一次的序号了，除j取余只不过是为了让序号正好在0~(j-1)的范围内而已。

Answer 5

单向循环链表 用这个最easy了

Answer 6

用标准的循环链表解决(约瑟夫环算法) 比较一下，过程差不太多using System;
using System.Collections.Generic;
using System.Text;namespace ExJose{
    class ClassJose    {
        //从第start人开始计数，以alter为单位循环记数出列，总人数为total 
        public int[] Jose(int total, int start,int alter)
        {
            int j, k = 0;
            //count数组存储按出列顺序的数据，以当结果返回 
            int[] count = new int[total + 1];
            //s数组存储初始数据 
            int[] s = new int[total + 1];
            //对数组s赋初值,第一个人序号为0,第二人为1，依此下去
            for (int i = 0; i < total; i++)
            {
                s[i] = i;
            }
            //按出列次序依次存于数组count中 
            for (int i = total; i >= 2; i--)
            {
                start = (start + alter - 1) % i;
                if (start == 0)
                    start = i;
                count[k] = s[start];
                k++;
                for (j = start + 1; j <= i; j++)
                    s[j - 1] = s[j];
            }
            count[k] = s[1];
            //结果返回 
            return count;
        }        static void Main(string[] args)
        {
            ClassJose    e=new ClassJose     ();
            int[] a = e.Jose(10,3,4);
            for (int i = 0; i < a.Length; i++)
            {
                Console.WriteLine(a[i].ToString ());
            }
        }
    }
}