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 Qiu 原创并发布在 被遗忘的曙光 技术博客

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