题目描述

n个人想玩残酷的死亡游戏，游戏规则如下：

n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，活到最后的一个人是胜利者。

请输出最后一个人的编号。

输入

输入n和m值。

输出

输出胜利者的编号。

示例输入

5 3

示例输出

4

提示

第一轮：3被杀第二轮：1被杀第三轮：5被杀第四轮：2被杀

数组解

1 #include
       
         2 int main() 3 { 4     int a[100],i,m,n,next,num,rest; 5     scanf("%d%d",&n,&m); 6     for(i=1;i<=n;i++) 7         a[i]=1; 8     rest=n; 9     num=1;10     next=1;11     while(rest>1)12     {13         if(a[num]==1)14             if(next==m)15             {16                 a[num]=0;17                 rest--;18                 next=1;19             }20             else21                 next++;22             if(num==n)23                 num=1;24             else25                 num++;26     }27     i=1;28     while((i<=n)&&(a[i]!=1))29         i++;30     printf("%d\n",i);31     return 0 ;32 }
       

链表解

 

1 #include
       
         2 #include
        
          3 struct node 4 { 5     int num ; 6     struct node *next ; 7 } ; 8 struct node *creat(int n) 9 {10     int i ;11     struct node *head, *p, *tail ;12     p = (struct node*)malloc(sizeof(struct node)) ;13     p -> num = 1 ;14     p -> next = NULL ;15     head = p ;16     tail = p ;17     for(i=2; i<=n; i++)18     {19         p = (struct node*)malloc(sizeof(struct node)) ;20         p -> num = i ;21         tail->next = p ;22         tail = p ;23         tail->next = NULL ;24 25     }26     tail->next = head ;27     return head ;28 }29 int del(struct node *head, int m, int n)30 {31     int count = 0, i = 0 ;32     struct node *p, *q ;33     q = head ;34     while(q->next!=head)35     {36         q = q -> next ;37     }38     while(count
         
          next ;41         i++ ;42         if(i%m==0)43         {44             q->next = p->next ;45             free(p) ;46             count++ ;47         }48         else49         q = p ;50     }51     return q->num ;52 }53 int main()54 {55     int n, m, c ;56     struct node *head ;57     scanf("%d %d", &n, &m) ;58     head = creat(n) ;59     c = del(head, m, n) ;60     printf("%d\n", c) ;61     return 0 ;62 63 }