Question

求约瑟夫环问题的解法

Answer 1

自己写的 C++程序
希望对你有帮助
/*约瑟夫环 Joseph
是一个数学的应用问题：
已知n个人（以编号1，2，3...n分别表示）
围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；
依此规律重复下去，直到圆桌周围的人全部出列。
例如：n = 9, m = 5
【解答】 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。*/

#include<iostream>
using namespace std;
struct list
{
struct list *last;
int data;
int xh;
struct list *next;
};
int main()
{
int n, m;
cin>>n>>m;
int i;
list *h=NULL,*q=NULL,*d=NULL;
for(i=1;i<=n;i++)
{
list *p=new list;
p->last=NULL;
p->data=0;
p->xh=i;
p->next=NULL;
if(h==NULL)
{
h=p;
q=h;
}
else
{
q->next=p;
p->last=q;
q=p;
}
}
q->next=h;
h->last=q;
q=h;
i=1;
while(q->last!=q)
{
if(i>m)
i=i%m;
q->data=i;
if(q->data==m)
{
cout<<q->xh<<' ';
q->last->next=q->next;
q->next->last=q->last;
d=q;
q=q->next;
delete d;
}
else
q=q->next;
i++;
}
cout<<q->xh<<' ';
system("pause");
return 0;
}

Answer 2

#include <iostream>
using namespace std;
struct Josephus{
int a;
int num;
struct Josephus *next;
};

struct Josephus *head;
void InitList( int n ){
struct Josephus *p;
int i;
p = (struct Josephus *)malloc( sizeof(struct Josephus) );
head = p;

for( i = 0; i < n; i++ ){
struct Josephus *p2;
scanf( "%d", & p->a );
p->num = i + 1;
if( i != 6){
p2 = (struct Josephus *)malloc( sizeof(struct Josephus) );
p->next = p2;
p = p->next;
}
}
p->next = head;
}

void Exclude(){
struct Josephus *p,*prev;
int m = 20, i = 1;
p = head;
while (1){
prev = p;
p = p->next;
i++;
if( i == m ){
cout << p->num << ' ';
m = p->a;
prev->next = p->next;
i = 0;
if( p->next == p ){
free( p );
return;
}
free( p );
p = prev;
}
}
}
int main(){
int n = 7;
InitList(n);
Exclude();
}

Answer 3

是约瑟夫森环吗？