当前位置:C++技术网 > 资讯 > 约瑟夫环算法(循环链表解决)

约瑟夫环算法(循环链表解决)

更新时间:2016-01-24 22:22:03浏览次数:1+次

再细化一下题目:


  已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后[1]  结果+1即为原问题的解。


#include <stdio.h>  
struct node  
{  
  int v;  
  struct node *next;  
}*p,*head,h; //head是头指针,h是头结点  
  
main()  
{  
  int n,m;  
  int i;  
  puts("请输入人数n和报数上限m :");  
  scanf("%d%d",&n,&m);  
  
  h.next=NULL; //头结点的next为空  
  head=&h;     //头指针指向头结点  
  p=head;      //p也指向头结点  
  
  /**//*下面的循环用来建立循环链表*/  
  for(i=1;i<=n;i++)  
  {  
    p->next=(struct node*)malloc(sizeof(struct node));  
    p=p->next;  
    p->v=i;  
    if(i!=n)  
    {  
      p->next=NULL;  
    }  
    else  
    {  
      p->next=head->next;  
    }  
  }  
  
  p=head;  
  p=p->next; //p指向第一个结点  
  m%=n;//当m>n时有用  
  while(p!=p->next)  
  {  
    for(i=1;i<=m-2;i++)  
    {  
      p=p->next;  
    }  
    printf("%d  ",p->next->v);  
    p->next=p->next->next;  
    p=p->next;  
  }  
  printf("%d",p->v);  
}