8：圆桌问题 c++

问题描述 :

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

输入说明 :

输入：好人和坏人的人数n（<=32767）、步长m（<=50）；

输出说明 :

输出2n个大写字母，‘G’表示好人，‘B’表示坏人，50个字母为一行。

输入范例： 52 6

输出范例： BGGBGBGGBBBBGGGGBBBGBGGBGBBGGBBGBGBBGGGBBBGBGGBBGG BBGBBGGGGBBBBGGBGGBBGBBGGBGBBGGBBBGGBGGBBGGGBBGBGG GBGB

#include<iostream> using namespace std; struct ListNode { int data; struct ListNode *next; }; ListNode *create(int num) { //创建循环链表 ListNode *head=new ListNode; head->next=NULL; ListNode *r=head; for(int i=0;i<num;i++){ ListNode *p=new ListNode; p->data=1; r->next=p; r=p; } r->next=head; return head; } int main() { int n,num,count,m,i,sum; cin>>n; cin>>m; num=2*n; ListNode *head=create(num); ListNode *p=head; i=1; while(n){ if(i==m){ if(p->data==1){ p->data=0; n--; i=1; p=p->next; } else{ p=p->next; } } else if(i<m){ if(p->data==1){ p=p->next; i++; } else p=p->next; } if(p==head){ p=p->next; } } p=head->next; sum=0; for(int j=0;j<num;j++){ sum++; if(p->data==1) cout<<"G"; else cout<<"B"; if(sum==50){ cout<<"\n"; sum=0; } p=p->next; } return 0; }

注意： 1、这题即约瑟夫环问题，但是因为要整体输出2n个人的座位，所以并不能删除结点 2、利用count来计数时，当count=m的结点已经为0时（即此座位已坐坏人），要指向下一个结点来判断是否为坏人 3、当count<m时，也要判断该结点的data域是否为0（即相当于判断该结点是否删除），若为0时，即看成已经删除，此时是不能计数+1的