黑马程序员技术交流社区

标题: 约瑟夫环问题 [打印本页]

---

作者: wanghuailin1030    时间: 2013-6-30 14:47
标题: 约瑟夫环问题


设有编号为1,2,…,n的n（n＞0）个人围成一个圈。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序，求最后剩下的是n个人中的第几个人？
例子： 100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？

---

作者: 浪子小雨    时间: 2013-7-1 13:28
            Console.WriteLine("请输入一共有几个人");
            int total = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("请输入报道几停止");
            int alter = Convert.ToInt32(Console.ReadLine());
            start = 0;
            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];
            //结果返回  
            foreach (int i in count)
                Console.WriteLine(i + 1);
            Console.ReadLine();
        }

---

作者: 彭家贰小姐    时间: 2013-7-1 15:45
        public class CircularLinkedList
        {
                private class Node
                {
                        public Node(object value)
                        {
                                item = value;
                        }
                        public object item;
                        public CircularLinkedList.Node next;
                        public override string ToString()
                        {
                                return item.ToString();
                        }
                }
                private int count;  //记录元素个数；
                public int Count
                {
                        get { return count; }
                }
                private Node tail;  //尾指针；
                public object Current //指示当前节点中的值；
                {
                        get { return currentPre.next.item; }
                }
                private Node currentPre; //使用前驱结点来标示当前节点；
                //在链表尾部添加元素；
                public void Add(object values)
                {
                        Node newNode = new Node(values);
                        if (tail == null) //如果链表为空，则新节点既是头指针，又是尾指针；
                        {
                                tail = newNode;
                                tail.next = newNode;
                                currentPre = newNode;
                        }
                        else
                        {
                                newNode.next = tail.next;
                                tail.next = newNode;
                                if (currentPre == tail)
                                {
                                        currentPre = newNode;
                                }
                                tail = newNode; //把尾指针指向新节点；
                        }
                        count++;
                }
                //删除当前节点；
                public void RemoveCurrentNode()
                {
                        if (tail == null)
                        {
                                throw new NullReferenceException("集合中没有任何元素！");
                        }
                        else if (count == 1)
                        {
                                tail = null;
                                currentPre = null;
                        }
                        else
                        {
                                if (currentPre.next == tail)
                                {
                                        tail = currentPre;
                                }
                                currentPre.next = currentPre.next.next;
                        }
                        count--;
                }
                //让当前节点向前移动指定的步数；
                public void Move(int step)
                {
                        if (step < 0)
                        {
                                throw new ArgumentOutOfRangeException("移动步数不能小于0！");
                        }
                        if (tail == null)
                        {
                                throw new NullReferenceException("集合中没有任何元素！");
                        }
                        for (int i = 0; i < step -1; i++)
                        {
                                currentPre = currentPre.next;
                        }
                }
                //打印整个链表；（仅用于测试）
                public override string ToString()
                {
                        if (tail == null)
                        {
                                return string.Empty;
                        }
                        string s = "";
                        Node temp = tail.next;
                        for (int i = 0; i < count; i++)
                        {
                                s += temp.ToString() + " ";
                                temp = temp.next;
                        }
                        return s;
                }
        }
        class MyTest
        {
                static void Main()
                {
                        CircularLinkedList clist=new CircularLinkedList ();
                        string s=string.Empty;


                        Console.WriteLine("请输入总人数：");
                        int count = int.Parse(Console.ReadLine());


                        Console.WriteLine("请输入间隔数字M的值：");
                        int m = int.Parse(Console.ReadLine());
               
                        Console.WriteLine("开始：");
                        for(int i=1;i<count+1;i++)
                        {
                                clist .Add (i);
                        }
               
                        Console.WriteLine("所有人："+clist .ToString ()+"/n");
                        while (clist.Count>1)
                        {
                                clist.Move(m);
                                s+=clist.Current.ToString ()+" ";                       
                                Console .WriteLine ("出局的人："+clist.Current);
                                clist.RemoveCurrentNode ();                       
                                Console .WriteLine ("剩余的人："+clist .ToString ());
                                Console.WriteLine("开始数数的人："+clist .Current );
                        }
                        Console .WriteLine ("出队顺序："+s+clist.Current);
                        Console.ReadKey();
                }
        }

---

作者: wanghuailin1030    时间: 2013-7-4 16:57

浪子小雨 发表于 2013-7-1 13:28
Console.WriteLine("请输入一共有几个人");
            int total = Convert.ToInt32(Console ...

start是什么？不要百度上的！

---

作者: wanghuailin1030    时间: 2013-7-4 17:58

彭家贰小姐 发表于 2013-7-1 15:45
public class CircularLinkedList
        {
                private class Node

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

namespace test30
{
    //100个人围成一个圈，从1开始报数，报到14的这个人就要退出。然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中的第几个人？
    class Program
    {
        public static long Josephus(long n, long m, long start)
        { //参数分别为：人数，出圈步长，起使报数位置,
            long k = 1;
            for (long i = 2; i <= n; i++)
                k = (k + m - 1) % i + 1;
            return (k + start - 1) % n; //返回最后一人的位置
        }
        static void Main(string[] args)
        {
            long t=Josephus(3,3, 1);
            Console.WriteLine(t);
            Console.ReadKey();
        }
    }
}
这是一个高手做的，我是不懂，你参考一下

---

作者: 彭家贰小姐    时间: 2013-7-4 18:38

wanghuailin1030 发表于 2013-7-4 17:58
using System;
using System.Collections.Generic;
using System.Linq;

:handshake 谢谢

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2