约瑟夫环问题
已知 n 个人(n>=1)围坐一圆桌周围，从 1 开始顺序编号，从序号为 1 的人开始报数，顺时针数到 m 的那个人出列。下一个人又从 1 开始报数，数到m 的那个人又出列。依此规则重复下去，直到所有人全部出列。请问最后一个出列的人的初始编号。
要求
输入人数 n，所报数 m，输出最后一个人的初始编号。
解决思路
- 首先因为是圆桌问题，使用链表解决的话需要构建循环链表。
- 接着是出列问题，这里我的设计思路是将指向链表的指针移动到需要出列的人的位置，然后根据正常的链表删除进行操作即可。
- 最后是类的设计，可以将 head 、 m、 n、链表构建、链表删除等整合到一起进行封装。
代码
1 // 6.cpp -- using gcc compiler 2 #include3 using namespace std; 4 5 typedef struct List 6 { 7 int num; 8 struct List *next; 9 }*pList; 10 11 class Josephus 12 { 13 public: 14 Josephus() {} 15 Josephus(int number, int mes): 16 n(number), 17 m(mes){} 18 void set(); 19 void creat(); 20 void del(); 21 private: 22 pList head; 23 int n, m, tmp_n; 24 }; 25 26 void Josephus::set() 27 { 28 cout << "please input the number of the people: "; 29 cin >> n; 30 tmp_n = n; 31 cout << "please input the m: "; 32 cin >> m; 33 } 34 35 void Josephus::creat() 36 { 37 pList p1, p2; 38 pList p = new List; 39 n += 1; 40 p -> num = 1; 41 p2 = head = p; 42 for(int i = 2; i < n; i++) 43 { 44 p = new List; 45 p -> num = i; 46 47 p1 = p2; 48 p2 = p; 49 p1 -> next = p2; 50 } 51 52 p2 -> next = head; 53 // output each number of the circle list's members. 54 // and it should be: 1, 2, ..., n 55 p = head; 56 cout << "Now, the \"num\" member of the list is: " << endl; 57 while(n--) 58 { 59 if(n == 0) 60 cout << p-> num << "."; 61 else 62 { 63 cout << p->num << ", "; 64 p = p -> next; 65 } 66 } 67 } 68 69 void Josephus::del() 70 { 71 pList p1 = NULL; 72 pList p2 = head; 73 74 n = tmp_n + 1; 75 while(n--) 76 { 77 int s = m - 1; 78 while(s--) 79 { 80 p1 = p2; 81 p2 = p2 -> next; 82 } 83 84 if(n == 0) 85 { 86 p2 = p2 -> next; 87 p1 -> next = NULL; 88 cout << "The result is: " << p2 -> num << endl; 89 } 90 else 91 { 92 p2 = p2 -> next; 93 p1 -> next = p2; 94 } 95 } 96 } 97 98 int main() 99 {100 Josephus t;101 t.set();102 t.creat();103 cout << endl;104 t.del();105 return 0;106 }
代码解析
5-9行定义了链表的结构，其中 num就是初始编号
23行的 tmp_n 负责记录 n 的初始值
75行开始进行循环，共循环 n+1 次，每次都将 p2 移动到需要被排除的人的位置。
n=0时为最后一次循环，此时p1、p2都指向最后一个人，输出 num。
n!=0则去掉p2指向的节点，开始下一次循环。
解决约瑟夫环问题的关键在于去掉计数为 m 的那个人，并从他之后开始重新计数。
而以上的解决方案巧妙的利用了循环链表来解决问题。因为对链表的了解不算深入，所以暂时还想不出更好的解决方案。
总结
解决链表问题的关键在于对链表的构建以及其他操作，而链表的问题只靠想象是不可能的解决的，最好还是自己动手画图，这样一切都会变得清晰明了，问题也会迎刃而解。