Josephus约瑟夫环问题的不同实现方法与概括

发布时间：2021-11-15 15:04:13 所属栏目：教程来源：互联网

导读：/************************************************************************/ /* Josephus问题数组实现 */ /************************************************************************/ #include stdio.h #include malloc.h int Josephus(int times, int

/************************************************************************/
/*                  Josephus问题——数组实现                          */
/************************************************************************/
#include <stdio.h>
#include <malloc.h>

int Josephus(int times, int number, int id){
    int *a;
    int i, count = 0, t = 0;
    a = (int *)malloc(sizeof(int) * number);

    for(i = 0; i < number; i++)
        a[i] = i + 1;            // 数组a用于储存每个元素的编号
    i = id - 1;

    while(count < number - 1){
        if(a[i] != 0)
            t++;
        if(t == times){
            t = 0;
            count++;
            printf("%4d", a[i]);
            a[i] = 0;                // 当该元素被剔除时，该数组元素置为0
        }
        i++;
        if(i == number)
            i = 0;
    }
    for(i=0;i<number;i++)
        if(a[i]!=0)
        {
            printf("n最后剩余的结点是:%4dn",a[i]);
            return;
        }

}

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

    return 0;
}

/************************************************************************/
/* 总结：
        优点为可以得出每次被剔除的元素编号
        缺点为内存空间占用较大，没有数学归纳法快速                        */
/************************************************************************/

/************************************************************************/
/*                  Josephus问题——循环链表实现                      */
/************************************************************************/
#include <stdio.h>
#include <malloc.h>

typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode,*Linkhead;
void Josephus(int m,int n,int k)
{
    Linkhead p,r,head = NULL;
    int i;
    for(i = 1;i <= n;i++)
    {
        p = (Linkhead)malloc(sizeof(LNode));//申请一个新的链结点
        p->data = i;//存放第i个结点的编号
        if(head == NULL)
            head = p;
        else
            r->next = p;      // 因为Insert和Del操作都需要之前一个节点的地址，故用r来存储。其作用类似栈的top
        r = p;
    }
    p->next = head;//至此，建立一个循环链表

    p = head;
    for(i = 1;i < k;i++)
    {
        r=p;
        /*请注意，此行不是多余的，因为当k!=1,但m=1时如果没有这条语句，此时删除动作无法完成*/
        p=p->next;
    }        //此时p指向第1个出发结点

    while(p->next != p)
    {
        for(i = 1;i < m;i++)
        {
            r = p;
            p = p->next;
        }                        //p指向第m个结点,r指向第m-1个结点
        r->next = p->next;        //删除第m个结点
        printf("%4d",p->data);    //依次输出删除结点的编号
        free(p);                //释放被删除结点的空间
        p = r->next;            //p指向新的出发结点
    }
    printf("n最后剩余的结点是:%4dn",p->data);//输出最后一个结点的编号
}

int main(){
    int times, number, id;
    printf("请输入总人数：");
    scanf("%d", &number);
    printf("请输入报数周期:");
    scanf("%d", ×);
    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, ×);
    printf("起始报号者的编号：");
    scanf("%d", &id);
    for(i = 1; i <= number; i++) {
        answer = (answer + times) % i;      // 核心算法，利用数学归纳法得出
    }
    if(answer + id == number)
        printf("Survial: %dn", number);    // 防止当幸存者为最后一个编号时输出0的情况
    else
        printf("Survival: %dn",(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计数从而删除成员的方法与此相比起来逊色不少，故之后我们将采用此方法来解决问题。

（编辑：东莞站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

电脑公司 xp 纯净版系	电脑按哪个键是转换拼
液晶电视为什么无法替	扩展器扩展后为什么不