约瑟夫问题

牡丹花下死做鬼

约瑟夫问题：简单来说就是 比如一共10个人 1 2 3 4 5 6 7 8 9 10
从第一个人开始 第三个人就死然后从下一个人继续从一开始数到三死
也就是说 3 6 9三个人先死了
然后10号人就是从一接着继续  1 2 4 5 7 8 10  10号一 一号2 二号3 然后二号死了 四号 1......
要求用代码写出人死亡的顺序



这个我想所有教程讲到链表都会讲到这个问题的把~~

代码其实也不难

1. #include<stdio.h>
   
2. #include<malloc.h>
   
3. 
   
4. #define MAX 41
   
5. 
   
6. int n = 0;
   
7. 
   
8. typedef struct People
   
9. {
   
10.         int data;
    
11.         struct People * next;
    
12. }p;
    
13. 
    
14. p * create();//创建链表
    
15. void print(p * head);//输出当前全部人死活状况
    
16. void calc(p * head);//约瑟夫问题计算
    
17. 
    
18. int main()
    
19. {
    
20.         p *head;
    
21.         head = create();
    
22.         calc(head);
    
23.         printf("\n");
    
24. 
    
25.         //print(head);
    
26.        
    
27. 
    
28.         return 0;
    
29. }
    
30. 
    
31. p * create()
    
32. {
    
33.         p * head;
    
34.         head = (p*)malloc(sizeof(p));
    
35.         p * p1;
    
36.         p1 = (p*)malloc(sizeof(p));
    
37.         head->data = 1;
    
38.         head->next = NULL;
    
39.         p1->data = 1;
    
40.         p1->next = NULL;
    
41.         int i;
    
42.         for ( i = 0; i < MAX; i++)
    
43.         {
    
44.                 if (n ==0)
    
45.                 {
    
46.                         head->next = (p*)malloc(sizeof(p));
    
47.                         head->next->data = 1;
    
48.                         p1->next = head->next;
    
49.                         n++;
    
50.                 }
    
51.                 else
    
52.                 {
    
53.                         p1->next->next = (p*)malloc(sizeof(p));
    
54.                         p1->next = p1->next->next;
    
55.                         p1->next->data = 1;
    
56.                         n++;
    
57.                 }
    
58.         }
    
59.         p1->next->next = head;
    
60.         return head;
    
61. }
    
62. 
    
63. void print(p * head)
    
64. {
    
65.         p * p1;
    
66.         p1 = head;
    
67.         n = 0;
    
68.         while (p1->next != head)
    
69.         {
    
70.                 if (p1->data)
    
71.                 {
    
72.                         printf("第%d个人:活\n",n+1);
    
73.                 }
    
74.                 else
    
75.                 {
    
76.                         printf("第%d个人:死\n",n+1);
    
77.                 }
    
78.                 p1 = p1->next;
    
79.                 n++;
    
80.         }
    
81. }
    
82. 
    
83. void calc(p * head)
    
84. {
    
85.         int i = 1, j = 1;
    
86.         p * p1;
    
87.         p1 = head;
    
88.         n = 41;
    
89.         while (n != 2)
    
90.         {
    
91.                 if (i != 3)
    
92.                 {
    
93.                         if (p1->data)
    
94.                         {
    
95.                                 i++;
    
96.                         }
    
97.                 }
    
98.                 else
    
99.                 {
    
100.                         if (p1->data)
     
101.                         {
     
102.                                 i = 1;
     
103.                                 p1->data = 0;
     
104.                                 n--;
     
105.                                 printf("%-5d", j);
     
106.                         }
     
107.                 }
     
108.                 p1 = p1->next;
     
109.                 if (j != MAX)
     
110.                 {
     
111.                         j++;
     
112.                 }
     
113.                 else
     
114.                 {
     
115.                         j = 1;
     
116.                 }
     
117.         }
     
118. }

复制代码

黑龍

前排支持
@小甲鱼  快出C教程啊 不是说要重录吗。。。