C求约瑟夫环问题.doc

《C求约瑟夫环问题.doc》由会员分享，可在线阅读，更多相关《C求约瑟夫环问题.doc（4页珍藏版）》请在三一办公上搜索。

1、C+求约瑟夫环问题C+编程求Josephus(约瑟夫环)问题:m个小孩子围成一圈,从第一个小孩子开始顺时针方向数数字,到第n个小孩子离开,这样反反复复,最终只剩下一个小孩子,求第几个小孩子留下?/用C+链表，次链表是单向循环链表，方便操作#include #include #include #include using namespace std;/class ys/定义类int s;public:ys *next;friend ys *set(int n);void get(ys *s);void putout(ys *t,int m,int n);/ys *set(int n)/初始化链表

2、ys *q=new ys,*h=q;int i;for( i=1;is=i;q-next=new ys;q=q-next;q-next=h;q-s=i;return q;/void ys:get(ys *s)/输出所有的小孩int tem=s-s;while(s-next-s!=tem) coutnext-snext;/ coutsendl;/void ys:putout(ys *t,int m,int n)/输出剩下的一个小孩/cout指针：snext,*p=t;int i=0;for(;n1;)i+;if(i%m!=0)p=h;h=h-next;elsep-next=h-next;delete h;h=p-next;n-;coutendln:sendl;/int main()coutnm;ys yue;ys *head;head=set(n);yue.get(head);yue.putout(head,m,n);return 0;