Different implementation methods and Summary of Josephus problem

1 / * / 2 / * Josephus problem-- Array implementation * / 3 / * * * / 4 # include 5 # include 6 7 int Josephus (int times Int number, int id) {8 int * a 9 int I, count = 0, t = 0; 10 a = (int *) malloc (sizeof (int) * number); 11 12 for (I = 0; I

< number; i++) 13 a[i] = i + 1; // 数组a用于储存每个元素的编号 14 i = id - 1; 15 16 while(count < number - 1){ 17 if(a[i] != 0) 18 t++; 19 if(t == times){ 20 t = 0; 21 count++; 22 printf("%4d", a[i]); 23 a[i] = 0; // 当该元素被剔除时，该数组元素置为0 24 } 25 i++; 26 if(i == number) 27 i = 0; 28 } 29 for(i=0;inext = p; // 因为Insert和Del操作都需要之前一个节点的地址，故用r来存储。其作用类似栈的top 81 r = p; 82 } 83 p->

Next = head;// so far, set up a circular linked list 84 85 p = head; 86 for (I = 1 teri

< k;i++) 87 { 88 r=p; 89 /*请注意，此行不是多余的，因为当k!=1,但m=1时如果没有这条语句，此时删除动作无法完成*/ 90 p=p->

Next; 91} / / at this time p points to the first departure node 92 93 while (p-> next! = p) 94 {95 for (I = 1 * I).

< m;i++) 96 { 97 r = p; 98 p = p->

Next; 99} / / p points to m-th node, r points to m-1 node 100 r-> next = p-> next; / / deletes m-th node 101 printf ("% 4d", p-> data); / / outputs the serial number 102 free (p) of deleted node. / / release the space of the deleted node 103p = r-> next; / / p to the new departure node 104d / 105printf ("\ nThe last remaining node is:% 4d\ n", p-> data); / / output the number of the last node 106107108 int main () {109 int times, number, id;110 printf ("Please enter the total number:") 11111scanf ("% d", & number); 112printf ("Please enter the reporting period:"); 113scanf ("% d", & times); 114printf ("Please enter the starting number:"); 115scanf ("% d", & id); 116Josephus (times, number, id); 117118 return 0 119} 120 121 / * / 122 / * Summary: the advantage of 123 is that the element number 124 that is deleted each time can be obtained. The disadvantage is that compared to the array side. The method requires more computation 125. Overall, it is not much different from the array method * / 126 / * * * / 127128 / * / 129 / * Josephus problem-- Direct calculation by mathematical induction * / 130 / * * * / 131 # include 132 int main () {133 int answer = 0 134134int times, number, I, id; / / number is the total number of elements in the ring, times is the reporting cycle, id is 135printf from which element ("Please enter the total number and number of cycles respectively:"); 136scanf ("% d% d", & number, & times); 137printf ("initial number:"); 138scanf ("% d", & id); 139for (I = 1) I