关于约瑟夫问题代码的分享

ByTime

用VScode写的

1. [code]//用循环链表模拟约瑟夫问题
   
2. 
   
3. #include<stdio.h>
   
4. #include<stdlib.h>
   
5. 
   
6. typedef struct people
   
7. {
   
8.     int number;
   
9.     struct people *next;
   
10. }people;
    
11. 
    
12. int globoal;
    
13. //循环链表的创立    创建number个节点  返回头部链表指针
    
14. people *creat_struct(int number)
    
15. {
    
16.    
    
17.     int creat_people;
    
18.     int struct_size;
    
19.         people *head,*p1,*p2;
    
20.         globoal = number;
    
21.     struct_size = sizeof(people);
    
22.     head = p1 = (people*)malloc(struct_size);
    
23.     //printf("请输入:");
    
24.     //scanf("%d",&head->number);
    
25.     head->number = 1;
    
26.     for(creat_people=1;creat_people<number;creat_people++)
    
27.     {
    
28.         p2 = (people*)malloc(struct_size);
    
29.         p1->next = p2;
    
30.         p1 = p2;
    
31.         //fflush(stdin);
    
32.         //printf("请输入:");
    
33.         //scanf("%d",&head->number);
    
34.         p1->number = creat_people+1;
    
35.         p1->next = head;
    
36.     }
    
37.     //printf("head=%p,p1=%p,p2=%p\n",head,p1,p2->next);
    
38.     return head;
    
39. }
    
40. 
    
41. 
    
42. 
    
43. //约瑟夫环问题
    
44. //head为传入循环链表的头结点，
    
45. //number为约瑟夫问题中的数到多少要杀掉的人数；
    
46. void joseph_problem(people *head,int number)
    
47. {
    
48.     people *del;
    
49.     int first_move = number-2;
    
50.     int after_move = number-1;
    
51.     int read;
    
52.         int move = 1;
    
53.     for(;move<=first_move;move++)
    
54.     {
    
55.         head = head->next;
    
56.     }
    
57.     del = head->next;
    
58.     head->next = head->next->next;
    
59.     printf("->%d",del->number);
    
60.     free(del);
    
61.     globoal--;
    
62.     while (globoal > after_move)
    
63.     {
    
64.         head = head->next->next;
    
65.         del = head->next;
    
66.         head->next = head->next->next;
    
67.         printf("->%d",del->number);
    
68.         free(del);
    
69.         globoal--;
    
70.     }
    
71.     read = globoal;
    
72.     while(read!=0)
    
73.     {
    
74.         printf("\n剩下:%d号\n",head->number);
    
75.         head=head->next;
    
76.         read--;
    
77.     }
    
78. }
    
79. 
    
80. int main()
    
81. {
    
82.     int pwd;
    
83.     people *headl;
    
84.    //41为约瑟夫问题中代表的人的数量
    
85.     head = creat_struct(41);
    
86.    //3代表每次数到多少杀掉的人
    
87.     joseph_problem(head,3);
    
88. 
    
89.     return 0;
    
90. }

复制代码

[/code]

ByTime

运行结果：
->3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->35
剩下:31号
剩下:16号

zhaopengfei

虽然实现了，但是过于复杂。