【好记性不如烂笔头】约瑟夫环问题之形象解法(其实就是实实在在的模拟一下游戏过程)

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace 约瑟夫环游戏
  8 {
  9     class Program
 10     {
 11         /*
 12          * 约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。
 13          * 从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重
 14          * 复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后结果+1即为原问题的解。
 15          * 约瑟夫环运作如下:
 16               1、一群人围在一起坐成[2]  环状(如:N)
 17               2、从某个编号开始报数(如:K)
 18               3、数到某个数(如:M)的时候,此人出列,下一个人重新报数
 19               4、一直循环,直到所有人出列[3]  ,约瑟夫环结束
 20          * 
 21          * 实现思路:
 22          *      1,创建节点类,创建环(JosephCir)类,在JosephCir环内实现环的连接,提供游戏开始方法
 23          *      2,游戏开始,丢……
 24          *      3,当环当前长度LengthNow为1时,游戏结束,返回最后胜出同学的节点。
 25          */
 26         static void Main(string[] args)
 27         {
 28             JosephCir j = new JosephCir(3,1,4);
 29 
 30             Console.WriteLine("游戏开始!");
 31             Node n = j.GameStart();
 32 
 33             if (n != null)
 34                 Console.WriteLine("游戏胜出同学的编号为:"+n.Data);
 35             else
 36                 Console.WriteLine("游戏失败");
 37 
 38             Console.ReadKey();
 39         }
 40 
 41     }
 42     /*约瑟夫环*/
 43     class JosephCir
 44     {
 45         public int LengthNow { get; set; }/*环当前长度,如果环长为1则表示游戏结束*/
 46         public Node head;/*1号同学节点*/
 47         public Node now;/*即手绢所在同学节点*/
 48         public int Total { get; set; }/*总共玩游戏的人数*/
 49         public int Start { get; set; }/*从该编号开始游戏*/
 50         public int PlayNum { get; set; }/*每次游戏丢PlayNum次手绢*/
 51 
 52         /*创建约瑟夫环*/
 53         public JosephCir(int total,int start,int playNum)
 54         {
 55             this.Total = total;
 56             this.Start = start;
 57             this.PlayNum = playNum;
 58             this.LengthNow = total;
 59             head = new Node(1);
 60             now = head;
 61             for (int i = 1; i < total; i++) 
 62             {
 63                 Node temp = new Node(i+1);
 64                 now.next = temp;
 65                 now = temp;
 66             }
 67             now.next = head;
 68             /*now 和head指向1号编号同学*/
 69             now = head;
 70         }
 71 
 72         /*游戏开始,结束时返回游戏胜出的Node*/
 73         public Node GameStart()
 74         {
 75             if (head == null) return null;
 76 
 77             /*将手绢发给开始的那个人*/
 78             for (int i = 0; i < Start-1; i++)
 79             {
 80                 now = now.next;
 81             }
 82 
 83             /*开始游戏*/
 84             while (LengthNow > 1)
 85             {
 86                 for (int i = 0; i < PlayNum - 1; i++)
 87                     now = now.next;
 88 
 89                 now.next = now.next.next;
 90                 now = now.next;
 91                 LengthNow -= 1;
 92             }
 93             if(LengthNow==1&&now!=null)
 94                 return now;
 95             return null;
 96         }
 97     }
 98     /*节点类*/
 99     class Node
100     {
101         public Node next;
102         public int Data { get; set; }
103         public Node(int data)
104         {
105             this.Data = data;
106         }
107     }
108 }

还有很多解法,个人觉得这是最易懂的一种……

黑夜给了我黑色的眼睛,我却用它寻找光明
上一篇:【好记性不如烂笔头】分冶算法之归并排序


下一篇:【开发者笔记】归并排序过程呈现之java内置GUI表示