一道习题,求解题的思路.

坦_然

题目如下: 一个旅行社 要从n个旅客中选出一位旅客,为他提供免费的环球旅行服务.旅行社安排这些旅客围成一个圆圈,从帽子中取出一张纸条,用上面的写正整数 m(m<n)作为报数值.游戏进行时,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人被淘汰出列,然后从他顺时针方向上的下一个人开始重新报数,如此下去,知道圆圈中只剩下一个人,这个最后的幸存者就是游戏的胜利者,将得到免费旅行的奖励.

流程图 也可 .非常感谢.

故乡的风

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define N 10        // 旅客数
   
5. #define M 4                // m
   
6. 
   
7. typedef struct _Node {
   
8.         int num;
   
9. 
   
10.         struct _Node *next;
    
11. } Node, *PNode, *Ring;
    
12. 
    
13. bool InitRing(Ring &r) {
    
14.         PNode pr = NULL;
    
15.         for (int i = 0; i < N; ++i) {
    
16.                 // 创建节点
    
17.                 PNode p = (PNode)malloc(sizeof(Node));
    
18.                 if (!p) return false;
    
19. 
    
20.                 if (0 == i) {        // 第一个节点为首节点
    
21.                         pr = r = p;
    
22.                 } else {                // 节点加入链表
    
23.                         pr->next = p;
    
24.                         pr = pr->next;
    
25.                 }
    
26. 
    
27.                 p->num = i + 1;        // 旅客编号
    
28.                 p->next = r;        // 形成循环链表
    
29.         }
    
30. 
    
31.         return true;
    
32. }
    
33. 
    
34. bool DestroyRing(Ring r) {
    
35.         if (!r) return false;
    
36. 
    
37.         PNode pdel = r;
    
38.         PNode pr = NULL;
    
39.         do {
    
40.                 pr = pdel->next;        // 需删除节点的下一个节点
    
41.                 free(pdel);                        // 删除节点
    
42.                 pdel = pr;
    
43.         } while (pr != r);        // 已删除节点的下一节点若为r，则节点删除完毕
    
44. 
    
45.         return true;
    
46. }
    
47. 
    
48. int GamePlaying(Ring &r) {
    
49.         PNode pr = r;
    
50.         PNode pdel = r;
    
51.         while (pr != pr->next) { // 只有一个节点时，退出循环
    
52.                 // 找到淘汰者
    
53.                 for (int i = 0; i < M - 1; ++i) {
    
54.                         pr = pdel;
    
55.                         pdel = pdel->next;
    
56.                         printf("%d\n", pr->num);
    
57.                 }
    
58.                 pr->next = pdel->next;
    
59.                 free(pdel);        // 删除淘汰者节点
    
60.                 pdel = pr->next;
    
61.         }
    
62. 
    
63.         r = pr;
    
64.         return r->num;
    
65. }
    
66. 
    
67. int main(int argc, char *argv[]) {
    
68.         Ring JosephRing = NULL;
    
69.         InitRing(JosephRing);
    
70. 
    
71.         int pnum = GamePlaying(JosephRing);
    
72.         printf("Game Winner:%4d\n", pnum);
    
73. 
    
74.         DestroyRing(JosephRing);
    
75. 
    
76.         return 0;
    
77. }

复制代码

只要使用循环的线性表，都可以按游戏描述简单的实现这个问题。这是我使用循环链表写的代码。

SXDA

用循环队列可以不？用一个循环判断队列是否只剩下一个元素。最后打印该元素~~

1187059391

甲鱼的数据结构视频中，讲了一道这样的题

1187059391

记得甲鱼的数据结构视频中，讲了一道这样的题

小亮1201

要求有点高，网上应该有源码吧。自己下去

wangyexin

一、数组模拟
二、数学公式

坦_然

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int paixu ( int *, int , int ,int ,int *, int * );
   
5. int blSZ ( int * ,int  );
   
6. 
   
7. 
   
8. int main(int argc, char *argv[])
   
9. {       
   
10.         int i,n,m;
    
11.         printf("输入人数和随机数\n");
    
12.         scanf ( "%d %d",&n,&m );
    
13.         if (m>n)
    
14.         {
    
15.                 printf("输入错误.\n");
    
16.                 system ("Pause");
    
17.                 return 0 ;
    
18.         }
    
19.         int a[n];
    
20.         for ( i=0 ;        i<n ;i++ )  //数组置1 ,淘汰则被置 0;
    
21.         {
    
22.                 a[i]= 1;
    
23.         }
    
24.         paixu ( a , n, m ,0,  a, a);
    
25.         for ( i=0 ;        i<n ;i++ )   
    
26.         {
    
27.                 printf("a[%d]=%d \n",i,a[i]);
    
28.         }
    
29.         system ( "Pause" );
    
30.         return 0;
    
31. }
    
32. 
    
33. 
    
34. 
    
35. 
    
36. 
    
37. int paixu ( int *P ,int N , int M ,int iJishu, int *iWeizhi,int *iChaxun )
    
38. {
    
39.         if (blSZ( P,N )==1)
    
40.         {
    
41.                 return ;
    
42.         }
    
43.         else
    
44.         {
    
45.                 // iChaxun指向最后一个数组元素时的处理.
    
46.                 if (iChaxun-P==N)
    
47.                         {
    
48.                         if (iJishu<M)
    
49.                                 {
    
50.                                         if (*iChaxun==0)
    
51.                                         {
    
52.                                                 iChaxun=P;
    
53.                                         }
    
54.                                         if (*iChaxun==1)
    
55.                                         {
    
56.                                                 iJishu++;
    
57.                                         }
    
58.                                 }
    
59.            if (iJishu==M)
    
60.                         {
    
61.                                 *iChaxun=0;
    
62.                                  iJishu=0;
    
63.                         }
    
64.                         //查询起始数组元素位于数组尾时
    
65.                         if (iWeizhi-P==N)
    
66.                         {
    
67.                                 iWeizhi=P;
    
68.                                 iChaxun=iWeizhi;
    
69.                         }
    
70.                         else
    
71.                         {
    
72.                                 iChaxun=P;
    
73.                         }
    
74.         }
    
75. /////////////////////////////////////////////
    
76.    // 计数 查询 置 0
    
77.         if (iChaxun-P<N)
    
78.                 {
    
79.                         if (*iChaxun==0)
    
80.                         {
    
81.                                 iChaxun++;
    
82.                         }
    
83.                         if (*iChaxun==1)
    
84.                         {
    
85.                                 iJishu++;
    
86.                                 if (iJishu==M)
    
87.                                 {
    
88.                                         iJishu=0;
    
89.                                         iWeizhi ++;
    
90.                                         *iChaxun=0;
    
91.                                         iChaxun=iWeizhi;
    
92.                                 }
    
93.                                 if (iJishu<M)
    
94.                                 {
    
95.                                         iChaxun ++;
    
96.                                 }
    
97.                
    
98.                         }
    
99.                 }
    
100.         }
     
101.         return paixu(P, N , M, iJishu ,iWeizhi , iChaxun );
     
102. }
     
103. 
     
104. 
     
105. int blSZ ( int *sz ,int n )
     
106. {
     
107.         int i;
     
108.         int temp=0 ;
     
109.         for ( i=0 ; i<n ; i++ ) //遍历数组,查看值是否为1,是否只剩下一个人 ;
     
110.         {
     
111.                 temp += *sz++ ;
     
112.                  
     
113.         }
     
114. 
     
115.         if (temp==1)
     
116.         {
     
117.                 return 1;
     
118.         }
     
119.         else
     
120.         {
     
121.                 return 0;
     
122.         }
     
123. }
     
124. 
     
125. 
     

复制代码

坦_然

wangyexin 发表于 2013-3-31 10:03

                               
登录/注册后可看大图

一、数组模拟
二、数学公式

用什么数学公式,能否介绍下.谢谢.

wangyexin

坦_然 发表于 2013-3-31 13:18

                               
登录/注册后可看大图

用什么数学公式,能否介绍下.谢谢.

百度约瑟夫环问题 百度百科里就有

坦_然

故乡的风 发表于 2013-3-30 17:58

                               
登录/注册后可看大图

只要使用循环的线性表，都可以按游戏描述简单的实现这个问题。这是我使用循环链表写的代码。

不太懂,复制保存,留作日后学习.谢谢你的解答.你的付出,我们为之努力.