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 }
还有很多解法,个人觉得这是最易懂的一种……
黑夜给了我黑色的眼睛,我却用它寻找光明