约瑟夫问题C语言编程问题：约瑟夫问题求解

约瑟夫问题链表方法

//原来的程序是用数组做的，这个题目用数组做其实比用链表要直观，简便 //给出一个链表的解法： #include <iostream> #include <malloc.h> struct man{ int num; //编号 bool out; //是否报过数 struct man *next; }; #define N 100 /*圈内人数*/ #define M 10 /*报数*/ using namespace std; void main(){ man *head,*p,*q; int i,j=0; head=(man*)malloc(sizeof(man)); p=head; head->num=1; for(i=2;i<=N;i++) /*编号*/{ q=(man*)malloc(sizeof(man)); q->num=i; p->next=q; p=q; } q->next=head; //采用的是循环链表 int count=N; while(count){ p->out=false; p=p->next; count--; } cout<<"The out sequence is:"<<endl; //打印出圈顺序 p=head; while(count<N){ while(j<M){ q=p; if(!(p->out)) j++; p=p->next; } q->out=true; cout<<q->num<<" "; count++; j=0; } cout<<endl; getchar(); }

C语言编程：约瑟夫问题

#include "stdio.h" main() { int i,k,quit_num,a[30],*p; p=a; for(i=0;i<30;i++) *(p+i)=i+1; printf("the position of feijiaotu are: "); quit_num=0; k=0; i=0; while(quit_num<15) {if(*(p+i)!=0)k++; if(k==9) {printf("%5d",*(p+i)); quit_num++; *(p+i)=0; k=0; } i++; if(i==30)i=0; } printf(" the position of jiaotu are: "); for(i=0;i<30;i++) if(*(p+i)!=0)printf("%5d",*(p+i)); }

求约瑟夫问题思路

m从k+1开始向后迭代 用数组a[2*k]存人，1为好人0为坏人，num存剩余人数，loc存当前位置 确定下一个人用a[(loc+m)%num](具体你再算算)，若要杀的人是1则看num，num==k说明此m成功

约瑟夫问题！！

只实现出列顺序 #define JN 7 #define JM 20 void jossen() { int a[JN+1]; int i=0; int j=0; int k=0; //intpwd[JN+1]; for(i=0;i<=JN;i++) {a[i]=i; /*cout<<"input the password for man “<<i<<":"; cin>>&pwd[i]*/} for(i=JN;i>=1;i--) { k=JM%i; if(0==k) k=i; /*cout<<"NO "<<JN+1-i<<": looking for "<<k<<" in: "; for(j=0;j<=JN;j++) {cout<<"a["<<j<<"]="<<a[j]<<",";} cout<<endl;*/ for(j=1;j<=JN;j++) { if(k == a[j]) { cout<<j<<", "; a[j]=0; int l=1; for(int p=j+1;l<i;p++) { if(p != JN+1 && a[p%(JN+1)]) { a[p%(JN+1)]=l++; } //cout<<"a["<<p%(JN+1)<<"]="<<a[p%(JN+1)]<<","; } break; } } cout<<endl; } }

什么是约瑟夫问题

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。

例如N=6，M=5，被杀掉的人的序号为5，4，6，2，3。

最后剩下1号。

假定在圈子里前K个为好人，后K个为坏人，你的任务是确定这样的最少M，使得所有的坏人在第一个好人之前被杀掉。

C语言编程问题：约瑟夫问题求解

用一个循环链表就可以完成了！ #include struct node{ int data; struct node *next; }node,*list,*p,*r; void JOSEPHU(int n,int k,int m) { int i,j; list=NULL; for(i=1;i<=n;i++) { p=(struct node*)malloc(sizeof(node)); p->data=i; if(list==NULL) list=p; else r->next=p; r=p; } p->next=list; /*建立一个循环链表*/ p=list; for(i=1;i<=n+1;i++) { printf("%d ",p->data); p=p->next; } printf(" "); /*打印链表,并检查循环链表是不输入正确*/ p=list; i=1; while(p&&inext; ++i; } for(i=1;inext; } printf("The out=%d ",p->data); r->next=p->next; } } void main() { int x, y, z; printf("input the lenth n ");/*n,k,m分别代表总的人数，第一个报数的人，间隔的人数*/ scanf("%d",&x); printf("input the start k "); scanf("%d",&y); printf("input the m "); scanf("%d",&z); JOSEPHU(x,y,z); }