首页 > > 程序设计 > C/C++ >

猴子选大王问题

2018-12-04 07:14:59来源：博客园阅读 ()

问题分析：

方法一：

创立一个记录编号的数组，用指针在这个数组循环移动计数，当计数为m时将这个元素做移除标记，直到剩下最后一个元素。

 1 int main()
 2 {
 3     int n,m;
 4     scanf("%d %d",&n,&m);
 5     int v[n];
 6     int i;
 7     for(i=0; i<n; i++)
 8     {
 9         v[i]=i+1;
10     }
11     int *p=&v[0];
12     int z=0,x=1,co=1;//z为剔除元素个数，x为元素在数组中位置，co为计数
13     for(;;)
14     {
15         while(*p==0)//当在循环中遇到已经剔除的元素，略过
16         {
17             if(x==n)
18             {
19                 x=1;
20                 p=&v[0];
21                 continue;
22             }
23             p++;
24             x++;
25         }
26         if(co==m)//当计数等于m，剔除该元素
27         {
28             co=0;
29             *p=0;
30             z++;
31         }
32         if(co!=m)//若计数不等于m，继续计数
33         {
34             if(x==n)//当这个猴子时最后一个，转向让第一个猴子报数
35             {
36                 x=1;
37                 p=&v[0];
38                 co++;
39                 continue;
40             }
41             p++;
42             x++;
43             co++;
44 
45         }
46         if(z==n-1)
47             break;//当剩下一个猴子时
48     }
49     for(i=0;; i++)
50     {
51         if(v[i]!=0)
52         {
53             printf("%d",v[i]);
54             break;
55         }
56     }
57     return 0;
58 }

View Code

方法二：

创立一个大小为n*n的数组，记录n次编号，用指针单向移动来假循环，当计数为m时把n个元素做移除标记，直到剩下最后一个元素。

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int n,m;
 5     scanf("%d %d",&n,&m);
 6     int v[n*n];
 7     int i,c;
 8     for(c=0; c<n; c++)//将数组循环赋编号，共赋n个
 9     {
10         for(i=0; i<n; i++)
11         {
12             v[i+c*n]=i+1;
13         }
14     }
15     int *p=&v[0];
16     int z=0,co=1;//co为计数
17     for(;;)
18     {
19         if(co==m)//当计数等于m，在v[n*n]里剔除该元素
20         {
21             for(i=0; i<n; i++)
22             {
23                 if(v[i]==*p)
24                 {
25                     for(c=0; c<n; c++)
26                     {
27                         v[i+c*n]=0;
28                     }
29                     break;
30                 }
31             }
32             co=0;
33             z++;
34         }
35         if(co!=m)
36         {
37             p++;
38             co++;
39         }
40         while(*p==0)//当遇到已经剔除的元素时
41         {
42             p++;
43         }
44         if(z==n-1)
45             break;//当剩下一个猴子时
46     }
47     for(i=0; i<n; i++)
48     {
49         if(v[i]!=0)
50         {
51             printf("%d",v[i]);
52             break;
53         }
54     }
55     return 0;
56 }