本文目录
- 有一堆人排成一圈,喊到一个数就出局,最后剩下的人,用c语言用动态链表编程
- 约瑟夫环问题的C++算法,求用链表和递归两种方法,尽量详细!
- C++单链表做约瑟夫环
- 约瑟夫问题，怎么用C语言写
- 求个约瑟夫循环链表的C++程序
- 请教C++约瑟夫问题代码
- （C语言）用静态链表求解约瑟夫问题
有一堆人排成一圈,喊到一个数就出局,最后剩下的人,用c语言用动态链表编程
这个问题是有名的约瑟夫问题。
假设有n个人参加报数，依次编号1~n。从编号1开始依次报数，从1报到m，报到m的人出列，剩下来的人重新开始报数，报到m的人出列，如此重复直到所有人都出列为止。最后出列的人原来的编号是多少？
链表程序如下：
#include 《stdio.h》#include《stdlib.h》struct node{int num;struct node *next;};struct node *create(int n){int i;struct node *p,*head=NULL,*rear;for(i=0;i《n;i++){p=(struct node *)malloc(sizeof(struct node));p-》num=i+1;if(head==NULL){head=p;rear=p;}else{rear-》next=p;rear=p;}}rear-》next=head;return head;}void Del(struct node *head,int n,int m){int i,j; struct node *p,*q=head,*front=head;while(q-》next!=head)q=q-》next;for(j=0;j《n;j++){for(i=1;i《m;i++){q=front;front=front-》next;} printf("%d\t",front-》num);p=front;q-》next=front-》next;front=front-》next;free(p);}}void main(){int m,n; struct node *head;printf("输入报到人数n:"); scanf("%d",&n);printf("输入报数终值m:"); scanf("%d",&m);head=create(n); if(n》0 && m》0){Del(head,n,m);head=0;}}
运行结果：
假设10个人参加报数，报到3的人出列，则出列顺序为
最后出列的是原来编号为4的人。
约瑟夫环问题的C++算法,求用链表和递归两种方法,尽量详细!
#include 《iostream.h》typedef struct node { //结点类型定义，每个结点表示一个孩子 int data; //用于存放结点（孩子）编号 node *next; node(int _data = 0, node *_next = NULL) //带缺省参数的结点构造函数
: data(_data),next(_next)
{}}*PNode, Node, *JosephusCycle;
void InitJCycle(JosephusCycle &last, int n) {
//初始化一个含有n个孩子的约瑟夫环，用带尾指针last的单循环链表表示，建表时采用首插法。 last = new Node(n); //last指针始终指向表尾结点，先创建表尾结点 last-》next = last; //先初始化只含一个结点的环。 for(int i = n - 1; i 》 0; i--) last-》next = new Node(i, last-》next); //将新结点插入到表头(即循环链表表尾的下一个)之前}
int GetWinner(JosephusCycle &last, int k) { //第一种方法，返回剩下的最后这个孩子的编号 if(last == NULL) return -1; //如果为空环，则返回-1表示失败 int sum; //报数器 PNode prior = last, current = prior-》next;//current表示当前报数结点，prior为当前结点的前驱 while(prior != current) {//如果prior==current则意味着环中剩下一个孩子 sum = 1; //报数开始 while(sum 《 k) { //进行报数，报数时，current指针与prior指针需同时移动 prior = current; current = prior-》next; sum++; } cout 《《 current-》data 《《 "\t"; //将报到k的孩子的序号输出。接下来的两行是该孩子删除出环 prior-》next = current-》next; delete current; current = prior-》next; //重新定位当前孩子 } //end while，结束循环时，环中只剩最后一个孩子 last = current; //将环尾指针指向最后这个孩子 return last-》data;}
int GetWinner(JosephusCycle &last, int n, int k) {
//方法二，递归，参数last是环尾指针，n表示环中孩子个数，k为报数的目标数 if(n == 1) return last-》data; //如果环中只有一个孩子，则结束，并返回这个孩子的编号 int sum = 1; //否则，则开始报数 while(sum 《 k) { //进行报数 last = last-》next; sum++; } //结束while时，last-》next即为报到k的孩子结点 PNode p = last-》next;//本行及后续3行是输出该孩子并删除该孩子 cout 《《 p-》data 《《 "\t"; last-》next = p-》next; delete p; GetWinner(last, n - 1, k); //在剩下的n-1个孩子的环中继续找优胜者}
void main( ) { JosephusCycle cycle; int m, k, winner; cin 》》 m 》》 k;
cout 《《 "方法一的出圈序列为：\n"; InitJCycle(cycle, m); winner = GetWinner(cycle, k); cout 《《 "\n优胜者：" 《《 winner 《《 endl;
delete cycle;
cout 《《 "\n方法二的出圈序列为：\n"; InitJCycle(cycle, m); winner = GetWinner(cycle, m, k); cout 《《 "\n优胜者：" 《《 winner 《《 endl;}
C++单链表做约瑟夫环
#include《iostream》#include《cstdio》#include《cstring》using namespace std;int a;struct LNode{ int num; LNode *next;};LNode *p, *r, *list;/*利用单向循环链表实现*/void joseph(int n, int m){//n：总人数；m：报数上限 printf("\n%d个人报数，上限为%d \n", n, m); int i; //创建链表 for (i = 1; i 《= n; i++){ p = new LNode; p-》num = i; if (list == NULL) list = p; else r-》next = p; r = p; } p-》next = list;//使链表循环 p = list;//p指向头结点 r = p; //x循环删除队列中的结点，即出列 printf("出列者序列："); while (p-》next != p){ for (i = 1; i《m; i++){ r = p; p = p-》next; } r-》next = p-》next; printf("%d ", p-》num); free(p); p = r-》next; } printf("\n最后留下的人是：%d\n", p-》num);}int main(){ for (int m, n; cin 》》 m 》》 n;) joseph(m, n); return 0;}/** n的初值为10，m为2，则出列顺序为 2 4 6 8 10 3 7 1 9，最后留下者是 5.* n的初值为20，m为5，则出列顺序为 5 10 15 20 6 12 18 4 13 1 9 19 11 3 17 16 2 8 14，最后留下者是 7.*/
约瑟夫问题，怎么用C语言写
#include《stdio.h》#include《malloc.h》typedef struct LNode{ int number; int password; struct LNode *next;}LNode,*LinkList;void CreatLink(LinkList &tail,int n) //尾插法建立不带头结点单向循环链表，返回尾指针{ LNode *head,*p; for(int i=1;i《=n;i++) //依次输入n个人的密码，建立单向循环链表 { p=(LNode*)malloc(sizeof(LNode)); p-》number=i; printf("请输入第%d个人的密码：",i); scanf("%d",&(p-》password)); if(i==1) //建立第一个结点 { head=p; tail=p; tail-》next=head; } //第2-n个结点，插入表尾 tail-》next=p; tail=p; tail-》next=head; }/* p=head; //输出链表 while(p-》next!=head) { printf("%d ",p-》password); p=p-》next; } printf("%d ",p-》password);*/}void joseph(LinkList &tail){ int m; printf("\n请输入一个正整数作为初始报数上限值："); scanf("%d",&m); int i=1; LNode *p=tail-》next,*pre=tail; printf("\n出圈顺序依次为："); while(p-》next!=p) //圈中多于1个人时 { while(i《m) //报数 { pre=p; p=p-》next; i++; } printf(" %d ",p-》number); //报数为m的人数列 m=p-》password; pre-》next=p-》next; free(p); i=1; //从下一个人开始重新报数 p=pre-》next; } printf(" %d \n",p-》number); //最后一个人出列 free(p);}void main(){ int n; printf("\n请输入圈中人数："); scanf("%d",&n); LinkList tail; CreatLink(tail,n); joseph(tail);}额，不知道你看不看的懂
求个约瑟夫循环链表的C++程序
#include《iostream》using namespace std;//链表结点类number为这个人的编号,key为密码struct person{unsigned int number;unsigned int key;person *next;};//约瑟夫环类,此类包含多个person类,并控制输入输出.class joseph_ring{private:unsigned int n;//用于存放人数unsigned int m;//用于存放初始密码person *head;//链表的头结点public:joseph_ring(){m=0;n=0;head=NULL;}//构造函数,把成员变量赋初值void create();//建立环的成员函数void show();//运算并输出的成员函数};void joseph_ring::create(){cout《《"请输入人数:";cin》》n;cout《《"请输入m的初值:";cin》》m;//定义2个临时指针person *p1,*p2;//for循环中用于初始化环for(int i=1;i《=n;i++){p1=new person;//新实例化一个"人"的对象p1-》number=i;//给这个"人"编个号cout《《"请输入第 "《《i《《"个人对应密码:";cin》》p1-》key;//给这个"人"一密码//如果当前链表为空,头结点指向第一个"人"if(i==1){head=p1;p2=p1;}//否则,p2永远指向尾结点,新建的结点都接到p2之后else{p2-》next=p1;p2=p1;}}p2-》next=head;//把链表连成一个循环链表(就是一个环)}void joseph_ring::show(){person *p1,*p2,*p;p1=head;//有n个人,所以执行n次循环for(int i=1;i《=n;i++){int count=1;//用count定位到第m个出圈人,循环后,p1指向这个出圈人,p2指向这个出圈人的上一个人while(count++《m){p2=p1;p1=p1-》next;}cout《《p1-》number《《"\t";//输入当前出圈人的编号m=p1-》key;//把当前出圈人的密码作为指向下一个出圈人所要经过的人数p=p1;//p指向当前这个出圈人p2-》next=p1-》next;//把出圈人前的人和出圈人后的人连上.p1=p1-》next;//下次从当前出圈人的下一个人开始数delete p;//把出圈人毙掉(就是释放这块内存)}cout《《endl;cin》》m;}int main(){joseph_ring j;j.create();j.show();return 0;}
请教C++约瑟夫问题代码
#include《iostream.h》#include《malloc.h》#include《string.h》structperson//定义结构体变量person{intnum;//编号structperson*next;//指向自身类型的指针};intmain(){inti;intm,n;structperson*p1,*p2,*head;cout《《"请输入总人数n：";cin》》n;while(n《1){cout《《"Inputerror!Enteragain:"《《endl;cin》》n;}cout《《"请输入报数m值：";cin》》m;p1=(structperson*)malloc(sizeof(structperson));//申请首元结点空间head=p1;//用head保留链表首元结点地址p1-》num=1;p2=p1;for(i=2;i《=n;){p1=(structperson*)malloc(sizeof(structperson));//申请新结点空间p1-》num=i;p2-》next=p1;//新结点插入链表尾部p2=p1;i++;}p1-》next=head;//尾结点的next指向首元结点，形成单循环链表cout《《"\n\n*****************************\n";cout《《"出队顺序为：\n";p1=head;//从首元结点开始访问链表intwinner;while(n》=1)//链表不为空{for(i=1;i《m;i++){p2=p1;p1=p1-》next;}cout《《p1-》num《《"";//喊到m的人出列winner=p1-》num;p2-》next=p1-》next;//链表不断链free(p1);//释放已删除结点空间p1=p2-》next;n=n-1;}cout《《"\n\n*****************************\n";cout《《"得胜者是："《《winner《《endl《《endl;return0;}
（C语言）用静态链表求解约瑟夫问题
#include"stdio.h"//#include"conio.h"#include"stdlib.h"#defineMAX100typedefstructnodes{intdata;nodes*next;}Lnode;/*静态链表节点结构体定义*///typedefstructlist//{//Lnodenode;//inthead;//}List,*PList;voidInitList(Lnode*pHead,intn)/*n为节点数*/{pHead-》data=0;Lnode*pPre=pHead;for(inti=1;i《n;++i){Lnode*pTemp=(Lnode*)malloc(sizeof(Lnode));pTemp-》data=i;pPre-》next=pTemp;pPre=pTemp;if(i==n-1){pTemp-》next=pHead;}}}voidSearchnode(Lnode*pHead,intn)/*m为报数，n为节点数,start为初始报数序号*/{Lnode*pNext=pHead;Lnode*pPreNode=NULL;while(1){for(inti=0;i《n;++i){pPreNode=pNext;pNext=pNext-》next;}printf("delete:%d",pNext-》data);if(pPreNode-》next==pNext-》next){break;}pPreNode-》next=pNext-》next;free((void*)pNext);pNext=pPreNode-》next;}}voidmain(){inti;intn=10,start=1;Lnode*pHeadNode=(Lnode*)malloc(sizeof(Lnode));InitList(pHeadNode,n);Lnode*pNext=pHeadNode;for(i=0;i《10;++i){printf("%d",pNext-》data);pNext=pNext-》next;}printf("请输入一个数");scanf("%d",&n);n%=10;Searchnode(pHeadNode,n);getchar();//printf("Hello,world");}
