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; }
运行时的预览图:
Ꮩery nice article, exactly what I wanted to find.