【项目-Josephus(约瑟夫环)问题】
n个小孩子围成一圈,从第一个小孩子开始顺时针方向数数字,到第m个小孩子离开,这样反反复复,最终只剩下一个小孩子,求第几个小孩子留下?
提示:约瑟夫环即是一个首尾相连的链表,在建立好这个环以后,从头结点开始,每次间隔m孩子删除一个结点,直至只余下一个结点(删除了n-1个)。
参考下面的代码,也可以自行设计类。
//链表结点kid,其中number为这个人的编号 struct kid { int number; kid *next; }; //约瑟夫环类 class joseph_ring { private: int n;//用于存放人数 int m;//用于存放初始密码 kid *head;//链表的头结点,初始化时指向1号孩子 public: joseph_ring(int nn, int mm);//创建nn个孩子,间隔为mm的约瑟夫环 void show();//运算并输出的成员函数 }; //定义joseph_ring类中的成员函数 …… int main() { int n,m; cout<<"n="; cin>>n; cout<<"m="; cin>>m; joseph_ring j(n,m); j.show(); return 0; }
#include <iostream> using namespace std; //链表结点kid,其中number为这个人的编号 struct kid { int number; kid *next; }; //约瑟夫环类 class joseph_ring { private: int n;//用于存放人数 int m;//用于存放间隔 kid *head;//链表的头结点 public: joseph_ring(int nn, int mm);//创建nn个孩子,间隔为mm的约瑟夫环 ~joseph_ring(); void show();//运算并输出的成员函数 }; //创建nn个孩子,间隔为mm的约瑟夫环 joseph_ring::joseph_ring(int nn, int mm) { n=nn; //构造函数,把成员变量赋初值 m=mm; kid *p1,*p2; //定义2个临时指针 for(int i=1; i<=n; i++)//for循环用于初始化环 { p1=new kid; p1->number=i; //编号 if(i==1) //如果当前链表为空,头指针指向第一个人 { head=p1; p2=p1; } else //否则,p2永远指向尾结点,新建立的结点都插入到p2之后 { p2->next=p1; p2=p1; } } p2->next=head;//把链表连成一个循环链表 } joseph_ring::~joseph_ring() { delete head; head=NULL; } void joseph_ring::show() //执行出圈操作 { kid *p1,*p2,*p; int count; p1=head; for(int i=1; i<=n-1; i++)//有n个人,所以执行n-1次循环,删除n-1个人 { count=1; //用count定位到第m个人,循环后,p1指向这个人,p2指向这个人的上一个人 while(count<m) { p2=p1; //p2指向前一个 p1=p1->next; count++; } cout<<p1->number<<"\t";//这指向的是当前要删除人 p=p1;//p指向当前这个人 p2->next=p1->next;//将当前出圈人的直接前驱和直接后继连接起来 p1=p1->next;//下次从当前人的下一个人开始数 delete p;//释放内存 } cout<<endl; cout<<"The last one is No. "<<p1->number<<endl; head=p1; //环中只剩下了一个结点 } int main() { int n,m; cout<<"n="; cin>>n; cout<<"m="; cin>>m; joseph_ring j(n,m); j.show(); return 0; }