网站建设、成都做网站的开发，更需要了解用户，从用户角度来建设网站，获得较好的用户体验。创新互联多年互联网经验，见的多，沟通容易、能帮助客户提出的运营建议。作为成都一家网络公司，打造的就是网站建设产品直销的概念。选择创新互联，不只是建站，我们把建站作为产品，不断的更新、完善，让每位来访用户感受到浩方产品的价值服务。
1 /************************************************************************/ 2 /* Josephus问题——数组实现 */ 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;i 62 #include 63 64 typedef struct LNode 65 { 66 int data; 67 struct LNode *next; 68 }LNode,*Linkhead; 69 void Josephus(int m,int n,int k) 70 { 71 Linkhead p,r,head = NULL; 72 int i; 73 for(i = 1;i <= n;i++) 74 { 75 p = (Linkhead)malloc(sizeof(LNode));//申请一个新的链结点 76 p->data = i;//存放第i个结点的编号 77 if(head == NULL) 78 head = p; 79 else 80 r->next = p; // 因为Insert和Del操作都需要之前一个节点的地址，故用r来存储。其作用类似栈的top 81 r = p; 82 } 83 p->next = head;//至此，建立一个循环链表 84 85 p = head; 86 for(i = 1;i < k;i++) 87 { 88 r=p; 89 /*请注意，此行不是多余的，因为当k!=1,但m=1时如果没有这条语句，此时删除动作无法完成*/ 90 p=p->next; 91 } //此时p指向第1个出发结点 92 93 while(p->next != p) 94 { 95 for(i = 1;i < m;i++) 96 { 97 r = p; 98 p = p->next; 99 } //p指向第m个结点,r指向第m-1个结点100 r->next = p->next; //删除第m个结点101 printf("%4d",p->data); //依次输出删除结点的编号102 free(p); //释放被删除结点的空间103 p = r->next; //p指向新的出发结点104 }105 printf("\n最后剩余的结点是:%4d\n",p->data);//输出最后一个结点的编号106 }107 108 int main(){109 int times, number, id;110 printf("请输入总人数：");111 scanf("%d", &number);112 printf("请输入报数周期:");113 scanf("%d", ×);114 printf("请输入开始报数的编号：");115 scanf("%d", &id);116 Josephus(times, number, id);117 118 return 0;119 }120 121 /************************************************************************/122 /* 总结：123 优点为可以得出每次被剔除的元素编号124 缺点为相较数组方法需要更多的计算量125 总体而言与数组方法相差无几 */126 /************************************************************************/127 128 /************************************************************************/129 /* Josephus问题——数学归纳法直接计算 */130 /************************************************************************/131 #include 132 int main() {
133 int answer = 0;
134 int times, number, i, id; // number为环内总元素个数，times为报数周期， id为从第几个元素开始报数135 printf("请分别输入总人数和循环次数：");136 scanf("%d %d", &number, ×);137 printf("起始报号者的编号：");138 scanf("%d", &id);139 for(i = 1; i <= number; i++) {
140 answer = (answer + times) % i; // 核心算法，利用数学归纳法得出141 }142 if(answer + id == number)143 printf("Survial: %d\n", number); // 防止当幸存者为最后一个编号时输出0的情况144 else145 printf("Survival: %d\n",(answer + id) % number);
146 // 这边利用number对answer进行取余操作以防止编号数值超过最大编号（溢出）147 148 return 0;149 }
对于Josephus问题有两个地方是可以进行优化的。 (总人数为N，编号为从0~N-1；经过M次报数去除一个成员，剩余成员个数为numleft， 记M%numleft为mPrime)
1、被移除的成员离上一个成员之间的距离是M%numleft-1（报数次为M%numleft）.当M大于N时，该计算方式将节省大量时间
2、当mPrime大于numleft的时候可以反向遍历该表来查找要去除的成员。这样可以节省时间。同样这也就要求了该表必须是一个双向表才行。（即含有Previous方法）
该算法实现原理即为：
第一轮，必定为编号M%N-1的成员被去除，第二轮为在第一轮的基础上即从编号为M%N的成员开始正移mPrime-1个单位（或者反移numleft-mPrime-1个单位）。若将M%N即为编号0，开始重新编号，那么第二轮被删除的成员编号便是M%（numleft）-1，由此可得该轮要被删除的成员与上一轮去除成员之间的距离为M%numleft，这里可利用迭代器来实现。
这里我们便可以得到成员编号与该轮成员数目的关系是：（n表示该轮所剩余的成员数目，Index（n）表示该轮成员的编号（从0开始））
Index(n) = (Index(n - 1) + m) % n。
那么按照这个过程，我们这样一直移除元素下去，肯定能够找到最后一个被移除的元素。
这个元素则对应只有一个元素的环，很显然，它的值为0。也就是Index(1) = 0。
对于这个元素的索引，它对应两个元素的索引是多少呢？
按照前面的过程，我们倒推回去就是了。Index(2) = (Index(1) + m) % 2。
那么对应3个，4个元素的呢？我们这样一路继续下去就可以找到对应到n个元素的索引了。
所以，我们发现了一个有意思的数学归纳关系：
f(1) = 0, f(n) = (f(n - 1) + m) % n。
按照这个关系，我们可以得到最后一个被取出来的元素对应到n个元素的环里的索引值。
至此，我们可以发现，利用count计数从而删除成员的方法与此相比起来逊色不少，故之后我们将采用此方法来解决问题。
文章标题：Josephus问题的不同实现方法与总结
网页网址：
http://cdxtjz.cn/article/jcoidc.html
