Josephus约瑟夫环问题的不同实现方法与总结(2)

int main(){
    int times, number, id;
    printf("请输入总人数:");
    scanf("%d", &number);
    printf("请输入报数周期:");
    scanf("%d", &times);
    printf("请输入开始报数的编号:");
    scanf("%d", &id);
    Josephus(times, number, id);

return 0;
}

/************************************************************************/
/* 总结:
        优点为可以得出每次被剔除的元素编号
        缺点为相较数组方法需要更多的计算量
        总体而言与数组方法相差无几                                        */
/************************************************************************/

/************************************************************************/
/*            Josephus问题——数学归纳法直接计算                      */
/************************************************************************/
#include <stdio.h>
int main() { 
    int answer = 0; 
    int times, number, i, id;    // number为环内总元素个数,times为报数周期, id为从第几个元素开始报数
    printf("请分别输入总人数和循环次数:");
    scanf("%d %d", &number, &times);
    printf("起始报号者的编号:");
    scanf("%d", &id);
    for(i = 1; i <= number; i++) { 
        answer = (answer + times) % i;      // 核心算法,利用数学归纳法得出
    }
    if(answer + id == number)
        printf("Survial: %d\n", number);    // 防止当幸存者为最后一个编号时输出0的情况
    else
        printf("Survival: %d\n",(answer + id) % number); 
        // 这边利用number对answer进行取余操作以防止编号数值超过最大编号(溢出)
   
    return 0;
}

对于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计数从而删除成员的方法与此相比起来逊色不少,故之后我们将采用此方法来解决问题。
该问题的最终解决程序可参见另一篇文章: Java实现 Josephus约瑟夫环问题 

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/bcb9debcbf7fa135108ca4ebee5fd921.html