约瑟夫环C#解决方法

时间：2023-03-08 15:45:51

/*约瑟夫环
（问题描述）
约瑟夫问题的一种描述是：编号为1，2，......n，的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任意选
一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新
的m值，从他在顺时针方向下一个人开始从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
（基本要求）
利用单向循环链表存储结构模拟此过程，按照出列顺序印出个人的编号。
（测试数据）
m的初值为20；n=7，7个人的密码依次为：3，1，7，2，4，8，4，首先m为6（正确的出列顺序应为6，1，4，7，2，3，5）。

下面是我的解决方法：
根据问题所描述的，这是个环问题，我们可以先模拟一个环.
声明：我这里是用双向链表的，虽然对这个问题没太大意义，但我还是保留为双向的，因为我在考虑这个问题可以衍生出很多其它问题来，只为我自己所用而以。呵呵……为了性能，而且只是解决这一个问题，你可以改成单向链表。

public class Circle
    {
        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;
        }

//pre node;current node;next node
        //first node-pre->last node
    }

2。根据问题加载数据

 List<Circle.Node> outList = new List<Circle.Node>();
            int index = 0;
            int n = 7;
            uint m = 20;

List<Circle.Node> nodeList = new List<Circle.Node>();
            Circle.Node nd = new Circle.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 (Circle.Node node in nodeList)
            {
                c.Add(node.ID, node.Password);
            }

3.根据问题事件开始起动

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

4.显示结果

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

完整源代码：

  
using System;            using System.Collections.Generic;            using System.Text;namespace Arithmetic            {                class Program                {                    static void Main(string[] args)                    {            List<Circle.Node> outList = new List<Circle.Node>();                        int index = 0;                        int n = 7;                        uint m = 20;            List<Circle.Node> nodeList = new List<Circle.Node>();                        Circle.Node nd = new Circle.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 (Circle.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);                        }                        Console.Read();                    }                }    public class Circle                {                    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;                    }        //pre node;current node;next node                    //first node-pre->last node                }            }

总结：当碰到问题时，思路理清。程序只不过是解决问题的工具，当你分析到问题本质，还原问题真相，有时会给你海阔天空的感觉。不要一味的去为写代码而写代码，写代码是为了解决问题，呵呵……
      用“面向对象”来思考问题，解决问题，把问题分层，分块，这样你的思路就清晰得多。
      以上代码只是做为参考，如果你有兴趣，可以写得更完善一些。

相关文章