Josephus环

今天来讲解一下比较常用的“Josephus环”算法，它又称“约瑟夫环”或者是“约瑟夫问题”。它是一个数学的应用问题，但在计算机程序中也常会用到。

“Josephus环”的意思就是有N个元素，它们是一个接着一个排列的，但最后一个元素N是连接着第一个元素的。然后选择一个元素开始，按一个指定的数来数，每次数到的元素就删除掉，一直循环数下去，直到所有的元素都被删除掉。

举一个例子（详细请见下图）：有8个元素，它们是以“Josephus环”的形式存放的。现在我要从第2个元素开始数，每次数3个元素。那么第一次数到的元素就是4，第二次数到的就是7。因为是以环的形式存放数据，所以第三次数到的就是元素2。然后循环数下去，直到删除掉所有的元素为止。

下面的是以链表形式实现“Josephus环”的代码：
Josephus.h 算法的头文件

class Josephus{
public:
    Josephus():head(nullptr){};
    ~Josephus(){};

    struct Node;

    void Create(int n);
    void Show();
    void Delete(int start, int n);

private:
    Node *head;
};

Josephus.cpp 算法的源文件

#include <iostream>
#include "Josephus.h"

struct Josephus::Node{
    int code;
    Node *next;
};

void Josephus::Create(int n){
    head = new Node;
    Node *p = head;

    for(int i = 1; i < n + 1; i++){
        p->code = i;

        if(i < n){ 
            p->next = new Node;
            p = p->next;
        }

    }
    p->next = head;
}

void Josephus::Show(){
    Node *p = head;

    do 
    {
        std::cout << p << "\t" << p->code << "\t" << p->next << std::endl;
        p = p->next;
    }while(p != head);

    std::cout << std::endl;
}

void Josephus::Delete(int start, int n){
    Node *p = head, *tmp = nullptr;

    while(p != p->next){
        for(int i = start + 1; i < start + n + 1; i++){
            if(i == start + n){
                std::cout << p->next << "\t" << p->next->code << "\t" << p->next->next << std::endl;

                tmp = p->next->next;
                delete p->next;
                p->next = tmp;
                break;

            }

            p = p->next;

        }
    }

    std::cout << p << "\t" << p->code << "\t" << p->next << std::endl;

    delete p;
    p = nullptr;

    std::cout << std::endl;
}

Main.cpp 程序的主文件

#include <iostream>
#include "Josephus.h"

using namespace std;

int main(){
    Josephus _josephus;
    _josephus.Create(8);
    _josephus.Show();

    _josephus.Delete(2, 3);

    system("pause");
    return 0;
}

运行时的预览图：

标签：计算机, 程序, 设计, 常用, 算法, josephus, 环

该文章由 Shiqi 原创并发布在 被遗忘的曙光 技术博客

转载请标明来源：https://fdawn.com/CPP/20.html