浅议约瑟夫问题

简介:

什么是约瑟夫问题,约瑟夫问题是据说著名犹太历史学家 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的项目时候,也是完全依据这个算法解决的问题,在做一个操作系统调度的时候,也是这个思想.所以,他的实用价值蛮大,所以像腾讯,华为,度娘面试的时候也经常考这个试题或者基于这个试题的变种。



目录
相关文章
|
2月前
|
机器学习/深度学习 Java Python
代码解密 | 2024春晚刘谦魔术与约瑟夫环问题
2024春节联欢晚会中,刘谦老师的魔术节目可以说是我心目中的全场最佳~春晚刚结束网上就有大佬给出了第二个魔术(拼扑克牌)的数学模拟,也有大佬发布了代码程序。博主在模拟了魔术过程之后,也在此分享一下程序代码和思路。同时,也借此回顾一下经典的数学问题:约瑟夫环问题。
60 8
|
2月前
DongDong认亲戚 - 并查集
DongDong认亲戚 - 并查集
10 0
|
12月前
|
算法
回溯算法——我欲修仙(功法篇)
回溯算法——我欲修仙(功法篇)
84 0
[软考]之树和二叉树
[软考]之树和二叉树
63 0
|
IDE Java 开发工具
[软考]之树与二叉树的遍历
[软考]之树与二叉树的遍历
61 0
|
存储 算法 C++
【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!
【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!
|
算法
算法竞赛题解:校门外的树
NOIP2005 普及组:校门外的树
213 0
|
前端开发 程序员 C语言
LeetCode | 循环队列的爱情【恋爱法则——环游世界】
环形队列包含真挚的我们 ❤ 兜兜转换最后还是你
96 0
LeetCode | 循环队列的爱情【恋爱法则——环游世界】
7-11 玩转二叉树 —— 程序设计天梯赛
给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。
87 0
7-11 玩转二叉树 —— 程序设计天梯赛