黑马程序员技术交流社区

标题: 约瑟夫环 [打印本页]
作者: 彭家贰小姐    时间: 2013-8-12 23:43
标题: 约瑟夫环
约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

  1. using System;

  3. namespace test26
  4. {
  5. public class CircularLinkedList
  6. {
  7. private class Node
  8. {
  9. public Node(object value)
  10. {
  11. Item = value;
  12. }

  14. public readonly object Item;
  15. public Node Next;

  17. public override string ToString()
  18. {
  19. return Item.ToString();
  20. }
  21. }

  23. private int _count; //记录元素个数；

  25. public int Count
  26. {
  27. get { return _count; }
  28. }

  30. private Node _tail; //尾指针；

  32. public object Current //指示当前节点中的值；
  33. {
  34. get { return _currentPre.Next.Item; }
  35. }

  37. private Node _currentPre; //使用前驱结点来标示当前节点；

  39. //在链表尾部添加元素；
  40. public void Add(object values)
  41. {
  42. var newNode = new Node(values);
  43. if (_tail == null) //如果链表为空，则新节点既是头指针，又是尾指针；
  44. {
  45. _tail = newNode;
  46. _tail.Next = newNode;
  47. _currentPre = newNode;
  48. }
  49. else
  50. {
  51. newNode.Next = _tail.Next;
  52. _tail.Next = newNode;
  53. if (_currentPre == _tail)
  54. {
  55. _currentPre = newNode;
  56. }
  57. _tail = newNode; //把尾指针指向新节点；
  58. }
  59. _count++;
  60. }

  62. //删除当前节点；
  63. public void RemoveCurrentNode()
  64. {
  65. if (_tail == null)
  66. {
  67. throw new NullReferenceException("集合中没有任何元素！");
  68. }
  69. if (_count == 1)
  70. {
  71. _tail = null;
  72. _currentPre = null;
  73. }
  74. else
  75. {
  76. if (_currentPre.Next == _tail)
  77. {
  78. _tail = _currentPre;
  79. }
  80. _currentPre.Next = _currentPre.Next.Next;
  81. }
  82. _count--;
  83. }

  85. //让当前节点向前移动指定的步数；
  86. public void Move(int step)
  87. {
  88. if (step < 0)
  89. {
  90. throw new ArgumentOutOfRangeException("移动步数不能小于0" + "！");
  91. }
  92. if (_tail == null)
  93. {
  94. throw new NullReferenceException("集合中没有任何元素！");
  95. }
  96. for (int i = 0; i < step - 1; i++)
  97. {
  98. _currentPre = _currentPre.Next;
  99. }
  100. }

  102. //打印整个链表；（仅用于测试）
  103. public override string ToString()
  104. {
  105. if (_tail == null)
  106. {
  107. return string.Empty;
  108. }
  109. string s = "";
  110. Node temp = _tail.Next;
  111. for (int i = 0; i < _count; i++)
  112. {
  113. s += temp + " ";
  114. temp = temp.Next;
  115. }
  116. return s;
  117. }
  118. }

  120. /// <summary>
  121. /// Program类
  122. /// </summary>
  123. internal class Program
  124. {
  125. /// <summary>
  126. /// Main
  127. /// </summary>
  128. /// <param name="args"></param>
  129. private static void Main(string[] args)
  130. {
  131. //题目: 约瑟夫环

  133. var clist = new CircularLinkedList();
  134. var s = string.Empty;

  136. Console.WriteLine("请输入总人数：");
  137. var count = Convert.ToInt32(Console.ReadLine());

  139. Console.WriteLine("请输入间隔数字M的值：");
  140. var m = Convert.ToInt32(Console.ReadLine());

  142. Console.WriteLine("开始：");
  143. for (int i = 1; i < count + 1; i++)
  144. {
  145. clist.Add(i);
  146. }

  148. Console.WriteLine("所有人：" + clist + "/n");
  149. while (clist.Count > 1)
  150. {
  151. clist.Move(m);
  152. s += clist.Current + " ";
  153. Console.WriteLine("出局的人：" + clist.Current);
  154. clist.RemoveCurrentNode();
  155. Console.WriteLine("剩余的人：" + clist);
  156. Console.WriteLine("开始数数的人：" + clist.Current);
  157. }
  158. Console.WriteLine("出队顺序：" + s + clist.Current);
  159. Console.ReadKey();
  160. }
  161. }
  162. }
复制代码
作者: 咖喱猫    时间: 2013-8-12 23:49
看起来蛮高级的{:soso_e129:}
作者: 熊丽    时间: 2013-8-25 09:51
牛X丫{:soso_e179:}



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