约瑟夫问题的代码(链表的运用).doc

有m个海盗得到了一笔宝藏，但海盗头想自己独吞。于是他发明了一种“公平”的方法来分财宝。他告诉大家，明天日出的时候我们围成一圈开始数数字，从我开始。我的编号是1。每次数到数字n，就把这个海盗扔进海里。最后一个留下来的海盗独得全部财宝。如果m10且n3，请求出最小的m和n。代码：#include#includestruct renint num;struct ren *next;struct ren *head;void main()void renshu();int flag,j;flag=1;while(flag=1)renshu();printf(是否还有继续：n 1.是n 2.否n);scanf(%d,&j);flag=j;if(j=1)system(pause);system(cls);void renshu()int flag,i,m,n,k,t,q;/m是人数，N是要丢掉的第几个人，I是编号，q=2证明循环没问题，q=1说明输入的数据出错struct ren *p,*d;t=1;/t用来计数的flag=1;/flag=1表示不符合要求，flag=2表示可以while(flag=1)printf(输入海盗人数：);/输入海盗人数scanf(%d,&m);printf(输入要丢掉的数字：);/输入第几个人要扔掉scanf(%d,&n);if(m10&n3)/判断输入的数据是否符合要求flag=2;/跳出while循环elseprintf(不符合要求，请重新输入!n);/ flag=2;/for(i=1;inum=i;p-next=NULL;head=p;d=p;elsep=(struct ren *)malloc(sizeof(struct ren);p-num=i;p-next=NULL;d-next=p;d=p;/开始循环d=head;printf(共有%d个人n,i-1);while(d)/只是显示人数printf(%dn,d-num);d=d-next;i=n;d=head;p=head;while(t!=m)/没进行一次就丢掉一个人while(i1)d=p;p=p-next;if(p=NULL)p=head;i=i-1;if(p=head)printf(释放了%d号n,p-num);printf(出错！n);q=0;k=t;/看看是哪里的T出错t=m;/结束程序elseif(p-next!=NULL)/链表未结束d-next=p-next;printf(释放了%d号n,p-num);t=t+1;free(p);p=NULL;p=d-next;i=n;else/链表结束d-next=NULL;printf(释放了%d号n,p-num);t=t+1;q=2;/释放成功free(p);p=NULL;p=head;i=n;if(q=2)printf(确定人数为%d个!n丢掉的数字是%dn,m,n);解析：此问题的解决需要运用链表的相关用法。所以我们要熟练掌握链表的运用。首先理清思路，这类问题需要一个链表，并且实现链表的循环，这样才能解决问题。接下来我就讲解链表的部分。现希望你能看清楚这代码，并且现运行这代码。接下来我只说链表部分。for(i=1;inum=i;p-next=NULL;head=p;d=p;elsep=(struct ren *)malloc(sizeof(struct ren);p-num=i;p-next=NULL;d-next=p;d=p;这段代码是建立链表，初学者应该也能明白。其中p-num=i;我用来标记海盗每个人的位置，应这道题的内容，第一个海盗不能被扔海里，这是此题的要求，不解释。d=head;printf(共有%d个人n,i-1);while(d)/只是显示人数printf(%dn,d-num);d=d-next;i=n;d=head;p=head;while(t!=m)/没进行一次就丢掉一个人while(i1)d=p;p=p-next;if(p=NULL)p=head;i=i-1;if(p=head)printf(释放了%d号n,p-num);printf(出错！n);q=0;k=t;/看看是哪里的T出错t=m;/结束程序elseif(p-next!=NULL)/链表未结束d-next=p-next;printf(释放了%d号n,p-num);t=t+1;free(p);p=NULL;p=d-next;i=n;else/链表结束d-next=NULL;printf(释放了%d号n,p-num);t=t+1;q=2;/释放成功free(p);p=NULL;p=head;i=n;if(q=2)printf(确定人数为%d个!n丢掉的数字是%dn,m,n);上面这部分才是这个代码的关键。首先，这要经过多次循环，因为只能留下一个人，就是第一个人。还有，当整个游戏未结束而链表结束时，则要连接尾部和头部，if(p=NULL)p=head;这个代码就是连接头部和尾部。如果运行了这段代码，if(p=head)printf(释放了%d号n,p-num);printf(出错！n);q=0;k=t;/看看是哪里的T出错t=m;/结束程序就意味着输入的数据出错了，因为扔掉了第一个。其中q=0;是说数据出错。而q=2;则表示此次运行成功，从头到尾都成功就行了。而t=m;意味着while(t!=m)循环要结束了。而这段代码:while(i1)d=p;p=p-next;if(p=NULL)p=head;i=i-1; 而这段代码，只能循环一次，这个if(p-next!=NULL)/链表未结束d-next=p-next;printf(释放了%d号n,p-num);t=t+1;free(p);p=NULL;p=d-next;i=n;else/链表结束d-next=NULL;printf(释放了%d号n,p-num);t=t+1;q=2;/释放成功free(p);p=NULL;p=head;i=n;这里的if和else是一对的，一次只能执行其中一段。if(p-next!=NULL)/链表未结束d-next=p-next;printf(释放了%d号n,p-num);t=t+1;free(p);p=NULL;p=d-next;i=n;上面这段是循环时未到尾节点，所以就继续。else/链表结束d-next=NULL;printf(释放了%d号n,p-num);t=t+1;q=2;/释放成功free(p);p=NULL;p=head;i=n;这段是循环到尾节点是，必须把尾部和头部连接。至于T的作用，当每一次数数都成功，就会自动加1，直到t=m。k什么作用。最后，关于此程序，用12和5就可以证明此程序时对的。当然把这段if(m10&n3)/判断输入的数