浅议约瑟夫问题-阿里云开发者社区

开发者社区> 人工智能> 正文

浅议约瑟夫问题

简介:

什么是约瑟夫问题,约瑟夫问题是据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到留下一个人都自杀身亡为止。

解决这个问题,有多少种方法。

①最常用的方法是使用循环链表的解决。首先, 将这39 个犹太人构成一个循环链表,每个犹太人等同与一个结点,这个结点有后继结点相连,最后的结点与第一个结点相连。我实现的思路如下所示:

结点

翻译成源代码如下:


 public class Node
        {
            private Node preNode;
            private Node nextNode;

            private int id;
            private uint password;

            public Node PreNode
            {
                get {
                    return preNode;
                }
                set {
                    preNode = value;
                }
            }

            public Node NextNode {
                get {
                    return nextNode;
                }
                set {
                    nextNode = value;
                }
            }

            public int ID
            {
                get {
                    return id;
                }
                set {
                    id = value;
                }
            }

            public uint Password
            {
                get {
                    return password;
                }
                set {
                    password = value;
                }
            }
            
        }

 循环链表

翻译成源代码如下:


private Node firstNode = null;
        private Node lastNode=null;
        private Node nextNode = null;
        private int count = 0;
       

        public int Count
        {
            get {
                return count;
            }
            set {
                count = value;
            }
        }

        public Circle()
        {
         
        }

        public void Add(int id,uint password)
        {
            count++;
             Node node = new Node();
             node.ID = id;
             node.Password = password;

             this.Add(node);
        }

        public void Add(int id)
        {
            count++;
            Node node = new Node();
            node.ID = id;
            this.Add(node);
            
        }

        private void Add(Node node)
        {
            if (firstNode == null)
            {

                firstNode = node;
                lastNode = firstNode;

                lastNode.NextNode = firstNode;
                lastNode.PreNode = firstNode;

                firstNode.NextNode = lastNode;
                firstNode.PreNode = lastNode;
            }
            else
            {
                lastNode.NextNode = node;

                node.PreNode = lastNode;
                node.NextNode = firstNode;

                firstNode.PreNode = node;
                lastNode = node;
            }
        }

        public Node NextNode()
        {
            Node node=new Node();
            if (nextNode == null)
            {
                node = firstNode;
                nextNode = firstNode.NextNode;
               
            }
            else
            {
                node = nextNode;
                nextNode = node.NextNode;
            }
            return node;
        }

        public void RemoveNode(Node node)
        {
            count--;
            Node _preNode = node.PreNode;
            Node _nextNode = node.NextNode;
            _preNode.NextNode = _nextNode;
            _nextNode.PreNode = _preNode;
        }

把每个循环链表初始化,相应的源代码如下:


List<Node> outList = new List<Node>();
            int index = 0;
            int n = 7;
            uint m = 20;
            List<Node> nodeList = new List<Node>();
            Node nd = new Node();
            nd.ID = 1;
            nd.Password = 3;
            nodeList.Add(nd);

            nd = new Circle.Node();
            nd.ID = 2;
            nd.Password = 1;
            nodeList.Add(nd);

            nd = new Circle.Node();
            nd.ID = 3;
            nd.Password = 7;
            nodeList.Add(nd);

            nd = new Circle.Node();
            nd.ID = 4;
            nd.Password = 2;
            nodeList.Add(nd);

            nd = new Circle.Node();
            nd.ID = 5;
            nd.Password = 4;
            nodeList.Add(nd);

            nd = new Circle.Node();
            nd.ID = 6;
            nd.Password = 8;
            nodeList.Add(nd);

            nd = new Circle.Node();
            nd.ID = 7;
            nd.Password = 4;
            nodeList.Add(nd);

 

            Circle c = new Circle();
            foreach (Node node in nodeList)
            {
                c.Add(node.ID, node.Password);
            }

  这是把所有的数据添加到泛型数组中。

 在进行点名,出列。相应的源代码如下:


while (c.Count > 0)
            {
                index++;
                nd = c.NextNode();
                if (index == m)
                {
                    c.RemoveNode(nd);
                    outList.Add(nd);
                    index = 0;
                    m = nd.Password;
                }
            }

也是放入新的泛型数组中去。

把所显示的结果最终显示的源代码:


foreach (Circle.Node node in outList)
            {
                Console.WriteLine(node.ID);
            }


最终运行的结果如下:

②基于位图算法的思想,

这里做法是建立一个数组来存储相应的数据,建立一个布尔变量来编辑是不是是不是进行了出列的标志,没出列一次,把相应的布尔的变量就置为假,一次循环操作,直到满足题意。这就基本思路,相应的流程图如下:

那实现的源代码就非常简单了,①对数据进行赋值的数组,一个布尔变量标记的数组。②判断布尔变量只有一个为真的方法。③依次报数,当报到相应的数字就进行了出列。④相应的索引大于数列的总长度又归零,直到布尔数组中一个为真的方法。源代码如下:


   public static bool CheckArray(bool[] array)
        {
            int temp = 0;
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i])
                {
                    temp++;
                }
            }
            return temp == 1;
        }
            int[] array = new int[M];
            ;
            bool[] blarray = new bool[M];
            for (int i = 0; i < M; i++)
            {
                array[i] = (i + 1);
                blarray[i] = true;
            }
            int count = 0;
            int index = 0;

            while (!CheckArray(blarray))
            {


                if (blarray[index])
                {
                    count++;

                }
                if (count == N)
                {
                    Console.WriteLine("数字" + array[index] + "出列");
                    count = 0;
                    blarray[index] = false;
                }
                index++;
                if (index == M)
                {
                    index = 0;
                }

            }

运行结果如下:

两种方法互有千秋。比较如下:

2

这就是我对约瑟夫环问题的一点点心得,请大家多多指教。

协后感,不要看这个算法,我以前在做一个callcenter的项目时候,也是完全依据这个算法解决的问题,在做一个操作系统调度的时候,也是这个思想.所以,他的实用价值蛮大,所以像腾讯,华为,度娘面试的时候也经常考这个试题或者基于这个试题的变种。



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章