DHU-链表-圆桌问题

8 圆桌问题

问题描述： 圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。

输入范例 :

52 6 输出范例 : BGGBGBGGBBBBGGGGBBBGBGGBGBBGGBBGBGBBGGGBBBGBGGBBGG BBGBBGGGGBBBBGGBGGBBGBBGGBGBBGGBBBGGBGGBBGGGBBGBGG GBGB

---

注意：存在一种情况指针，指到的时候正好m为6，但该位置的标记为‘B’，所以用一个while循环找到第一个不是‘B’的地方。

---

#include <iostream> using namespace std; struct ListNode { char flag; ListNode *next; }; ListNode* createlist(int n){ ListNode *head = new ListNode; ListNode *cur = new ListNode; cur = head; for(int i = 0 ; i < 2*n ; i++){ ListNode *temp = new ListNode; temp->flag = 'A'; cur->next = temp; cur = temp; } cur->next = head; return head; } int main(){ int n,m; cin>>n>>m; ListNode *head = createlist(n);//创建一个单链表，个数为2n ListNode *cur = new ListNode; cur = head->next; int num = 0; int temp = 1; while(num != n){ while(temp != m){ if(cur->flag != 'A'){ if(cur->next == head){ cur = cur->next; } cur = cur->next; } else{ if(cur->next == head){ cur = cur->next; } cur = cur->next; temp++; } } while(cur->flag != 'A'){ cur = cur->next; } cur->flag = 'B';//杀死的位置必须是标记为‘A’ if(cur->next == head){ cur = cur->next->next; } else{ cur = cur->next; } num++; temp = 1; } ListNode *aa = new ListNode; aa = head->next; int total = 0; while(aa != head){ if(aa->flag == 'A'){ cout<<'G'; total++; if(total == 50){ cout<<endl; total = 0; } } if(aa->flag == 'B'){ cout<<'B'; total++; if(total == 50){ cout<<endl; total = 0; } } aa = aa->next; } }