猴子选大王(约瑟夫环问题)c语言描述

猴子选大王(约瑟夫环问题),用链表实现的

#include 
#include 
#define n 20
#define m 5
typedef struct monkey
{
  int num;
  struct monkey *next;
} Monkey,*LINK;
int main()
{
   LINK p,head,p2;
   int i;
   head=p=p2=(LINK)malloc(sizeof(Monkey));
   for(i=1;i   {
     p=(LINK)malloc(sizeof(Monkey));
  p2->next=p;
  p2=p;
   }
   p2->next=head;
   p=head;
   printf("对猴子进行编号!\n");
      for(i=1;i<=n;i++)
   {
     p->num=i;
  printf("%d号猴子:%d\n",p->num,p->num);
  p=p->next;
   }
   i=0;
   p=head;
   while(1)
   {
   i++;
   printf("%d号猴子报:%d\n",p->num,i);if(p->next==p) break;

   if(i==m)
   {
   i=0;
   printf("%d号猴被淘汰\n",p->num);
   printf("\n");
   p2->next=p->next;
   p=p2->next;
   continue;
   }
   else
   {
 if(i==m-1) p2=p;
   p=p->next;
   }
   }

   printf("胜出:%d",p->num);

}

3 thoughts on “猴子选大王(约瑟夫环问题)c语言描述

  1. digiter

    那次做哈尔滨的网预,有这道题,用树状数组O(n * log n)过掉的,感觉灰常强大

    Reply
  2. digiter

    说错了,用二分 + 树状数组是O(n * log n * log n),用线段树才是O(n * log n)的

    Reply
  3. coder4

    @digiter
    其实这个程序我写的很幼稚的,因为当时还是大一呢。06年写的……呵呵,都被你找到这里来了。。

    Reply

Leave a Reply

Your email address will not be published.