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.
Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword....
Me and this article, sitting in a tree.
不错的文章，内容十全十美.
好文章，内容文风幽默.
好文章，内容出口成章.
I watned to spend a minute to thank you for this.