约瑟夫环问题 Time Limit:1000MS  Memory Limit:65536KTotal Submit:50 Accepted:8 Description 约瑟夫环问题；有N个人围成一个环，从第一个人开始报数，报到M的人退出环，并且由他的M值来代替原有的M值，要求输出离开环的顺序。 Input 第一行有2个数，M和N。(0<N<=1000) 第二行有N个数，表示每个人的M值。 Output 按照样例的格式，输出所有人退出环的顺序。 Sample Input 4 6 5 4 2 3 4 2 Sample Output 4,1,2,3,6,5   Source #include"iostream" #include"cstdio" #include"cstdlib" using namespace std; typedef struct cnode{ int label; int data; struct cnode *next; }cnode; int m,n,i,value,j; cnode *p,*q; int main() { cin>>m>>n; cnode *clist; q=(cnode *)malloc(sizeof(cnode)); clist=q; for(i=1;i<=n;i++) { //cin>>value; cin>>value; p=(cnode *)malloc(sizeof(cnode)); //p=new cnode; p->label=i; p->data=value; p->next=NULL; q->next=p; q=p; if(i==n)q->next=clist->next; } p=clist; //cout<<p->label<<endl; for(i=1;i<=n;i++) { for(j=1;j<m;j++) { p=p->next; } q=p->next; m=q->data; if(i==n){cout<<q->label<<endl;break;} cout<<q->label<<","; p->next=q->next; delete q; } //system("pause"); return 1; } 数组解法： #include<iostream>using namespace std; int main() { int *a,*b; int i,j,t,k,l,m,n;  cin>>m>>n;  a=new int[n];  b=new int[n];  for (i=0;i<n;i++)     {  cin>>a[i];  b[i]=i+1; }  b[n-1]=0; k=0; l=n-1; m=m%n; if (m==0) m=n;  for (i=0;i<n-1;i++)     {  for (j=1;j<m;j++)         {    l=k;    k=b[k];   }  cout <<k+1<<',';  t=n-i-1;  m=a[k]%t;  if (m==0) m=n-i-1;  b[l]=b[k];  k=b[k]; } cout << k+1<<endl;  free(a); free(b); system("pause"); return 0;}

评论