约瑟夫环问题

/*约瑟夫环问题*/
//一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？
#include <stdio.h>
#include <malloc.h>
typedef struct Node
{
   int data;
   struct Node *next;
}Node;

Node *Great(int n)
{
   Node *rear = NULL,*s;
   int i;
   rear = (Node*)malloc(sizeof(Node));
   rear->data = 1;
   rear->next = rear;
   for(i = 2;i<n;i++)
   {
       s = (Node*)malloc(sizeof(Node));
       s->data = i;
       s->next = rear->next;
       rear = s;
   }
   return rear;
}

void Joseph(Node *rear,int m)
{
   Node *pre = rear, *p = rear->next,*q;
   int count = 1;
   printf("出环的顺序：");
   while(p->next != p)
   {
       if(count < m)
       {
           pre = p;
           p = p->next;
           count++;
       }else{
           printf("%-3d",p->data);
           q = p;
           pre->next = p->next;
           p = pre->next;
           free(q);
           count = 1;
       }
   }
   printf("%-3d\n",p->data);
   free(p);
   return;
}

int main()
{
   int n,m;
   Node *rear = NULL;
   printf("请输入约瑟夫环的长度：");
   scanf("%d",&n);
   printf("请输入密码：");
   scanf("%d",&m);
   rear = Great(n);
   Joseph(rear,m);
   return 0;

}

约瑟夫环问题

相关推荐