我想知道约瑟夫算法的内容和含义 知道的请告诉一下 ( 积分: 0 )

约瑟夫算法的内容和含义 知道的请告诉一下
知道一点就告诉一点 谢谢了

约瑟夫算法的内容和含义 知道的请告诉一下
知道一点就告诉一点 谢谢了

设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。
就是这个意思。

这是C++的源码：
#include<iostream>
#include<limits>
using namespace std;
class NodeList
{
public:
struct Node
{ int value;

Node * prev;

Node * next;
};
NodeList(int nk);
~NodeList();
bool Run(int m);
private:
void Add(int val);
void Erase(void);
void Advance(int step);
Node head;
Node *cur;
int k;
};
NodeList::NodeList(int nk = 4)
{
head.prev = &amp;head;
head.next = &amp;head;
k = nk;
for (int i = 1;
i <= 2*k;
++i)
{ Add(i);
}
}
NodeList::~NodeList()
{
head.prev->next = &amp;head;
while (head.next != &amp;head)
{
Node *tmp = head.next;

head.next = tmp->next;

delete tmp;
}
}
void NodeList::Add(int val)
{
Node *tmp = new Node;
tmp->value = val;
if (head.next == &amp;head) {
// have no data
head.next = tmp;

head.prev = tmp;
}
tmp->next = head.next;
tmp->prev = head.prev;
head.prev->next = tmp;
head.next->prev = tmp;
head.prev = tmp;
}
void NodeList::Erase()
{
Node *tmp = cur->next;
cur->prev->next = tmp;
tmp->prev = cur->prev;
// cout << &quot;-R&quot;
<< cur->value;
if (head.next == cur)
{
head.next = cur->next;
}
if (head.prev == cur)
{ head.prev = cur->prev;
}
delete cur;
cur = tmp;
}
void NodeList::Advance(int step)
{
for (int i = 1;
i < step;
++i)
{ cur = cur->next;
}
}
bool NodeList::Run(int m)
{
int i;
cur = head.next;
Advance(m);
i = 1;
while (cur->value > k)
{
Erase();

if (i == k) { return true;
}
Advance(m);
++i;
}
return false;
}
int main(int argc, char* argv[])
{
int k[4], m,count=0;
NodeList *list;
while(1)
{
cin >>k[count];
if(k[count]==0) break;
else
count++;
}
for(int i=0;i<count;i++)
{
#define MAX_M numeric_limits<int>::max()
for (m=k+1;
m<MAX_M;++m)
{
list = new NodeList(k);
if (list->Run(m) == true)
{
cout<<m<<endl;
delete list;

break;
}
delete list;
}
}
return 0;
}

找本数据结构的书来看,一定有的,我记得类P的代码,很短的,而且很容易理解
//下面是抄来的
program JOSR;
const mmax=100;
var m,n,j:integer;
rou:array[1..mmax] of boolean;
procedure init;
var i:integer;
begin
write('Please input M:');readln(m);
write('Please input N:');readln;
for i:=1 to mdo
rou:=true;
j:=0;
end;

procedure check;
var i,k:integer;
begin
i:=0;k:=0;
repeat
inc(k);
if k>m then
k:=1;
if rou[k]=true then
begin
inc(i);
if i mod n=0 then
begin
rou[k]:=false;inc(j);
end;
end;
until j=m-1;
end;

procedure print;
var i:integer;
begin
for i:=1 to mdo
if rou=true then
writeln(i);
end;

begin
init;
check;
print;
readln;
end.

不就是猴子选大王的问题么?

呵呵，介个问题嘛主要是考环型链表的，zqw的算法用的就这招（还是双向的，赞一个），要是换成delphi的就更好了。
至于BlueVoice的方法就免了，虽然结果是对的，但不是这问题提出的初衷，而且数字大了以后白做很多工作的。