约瑟夫问题
介绍
约瑟夫问题，又称约瑟夫置换、丢手绢问题。
一般形式
（本部分内容来自百度百科）
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
代码
问题描述
本文以以下问题为例
编号为1-10的10 个人围成一圈，从第一个开始报数，第9个被淘汰出圈，剩下的组成新的圈。依次这样下去，求最后一个人的编号
解决
注意：该段代码与上篇文章——《 循环链表定义及操作 》相接
//解答约瑟夫问题
bool Joseph(LinkList* &L, int interval)
{
LinkList *p = L, *q;
int i = 0, j = 0;
int times = 0; //当前轮数
int num = 0;
if(!L || p->next == L)
{
cout << "链表为空\n";
return false;
}
if(interval < 1)
{
cout << "报数淘汰口令不能小于1\n";
return false;
}
do{
i += interval;
//找查第i个结点，p指向该结点的上一个结点
while(p->next){
if(p->next != L)
{
//如果不是头结点的话
j++;
}
if(j >= i) break;
p = p->next;
}
times++;
q = p->next; //临时保存被删结点以备释放空间
num = q->data;
cout << "当前结点:" << q->data
<< " 上一个结点:" << p->data
<<" 下一个结点:" << q->next->data
<< endl;
p->next = q->next;
delete q; //释放被删除结点内存
LinkListPrint(L);
}while(L->next != L); //链表不为空，继续报数
cout << "最后一个出圈者的编号" << num << endl;
return true;
}
完整代码
代码
#include <iostream>
#include <string>
using namespace std;
typedef struct _LinkNode
{
int data;
struct _LinkNode *next;
}LinkList;
bool InitList(LinkList* &L)
{
L = new LinkList;
if(!L) return false;
L->next = L;
L->data = 0;
return true;
}
bool ListInsert_back(LinkList* &L, LinkList *node)
{
LinkList *last = NULL;
if(!L || !node) return false;
if(L == L->next)
{
//头结点指针指向了自己（链表只有头结点）
node->next = L;
L->next = node;
}else{
//非空的循环链表
last = L->next;
//寻找尾结点（指向头结点的结点）
while(last->next != L)
{
last = last->next;
}
node->next = L;
last->next = node;
}
return true;
}
void LinkListPrint(LinkList *L)
{
LinkList *p;
if(!L || L == L->next)
{
cout << "链表为空\n";
return;
}
p = L->next;
while(p != L)
{
cout << p->data << "\t";
p = p->next;
}
cout << endl;
}
//解答约瑟夫问题
bool Joseph(LinkList* &L, int interval)
{
LinkList *p = L, *q;
int i = 0, j = 0;
int times = 0; //当前轮数
int num = 0;
if(!L || p->next == L)
{
cout << "链表为空\n";
return false;
}
if(interval < 1)
{
cout << "报数淘汰口令不能小于1\n";
return false;
}
do{
i += interval;
//找查第i个结点，p指向该结点的上一个结点
while(p->next){
if(p->next != L)
{
//如果不是头结点的话
j++;
}
if(j >= i) break;
p = p->next;
}
times++;
q = p->next; //临时保存被删结点以备释放空间
num = q->data;
cout << "当前结点:" << q->data
<< " 上一个结点:" << p->data
<<" 下一个结点:" << q->next->data
<< endl;
p->next = q->next;
delete q; //释放被删除结点内存
LinkListPrint(L);
}while(L->next != L); //链表不为空，继续报数
cout << "最后一个出圈者的编号" << num << endl;
return true;
}
int main()
{
LinkList *L, *s;
int i = 0;
if(InitList(L))
{
cout << "创建一个空的循环链表\n";
}else{
exit(-1);
}
cout << "尾插10个元素...\n";
while((++i)<=10)
{
s = new LinkList;
s->data = i;
s->next = NULL;
if(ListInsert_back(L, s))
{
cout << "success\n";
}else{cout << "default\n";}
}
LinkListPrint(L);
Joseph(L,9);
return 0;
}
输出结果
注：0为头结点的数据，该结点并不计入约瑟夫环中（但最后也将其删除销毁链表释放内存）
创建一个空的循环链表
尾插10个元素...
success
success
success
success
success
success
success
success
success
success
1 2 3 4 5 6 7 8 9 10
当前结点:9 上一个结点:8 下一个结点:10
1 2 3 4 5 6 7 8 10
当前结点:8 上一个结点:7 下一个结点:10
1 2 3 4 5 6 7 10
当前结点:10 上一个结点:7 下一个结点:0
1 2 3 4 5 6 7
当前结点:2 上一个结点:1 下一个结点:3
1 3 4 5 6 7
当前结点:5 上一个结点:4 下一个结点:6
1 3 4 6 7
当前结点:3 上一个结点:1 下一个结点:4
1 4 6 7
当前结点:4 上一个结点:1 下一个结点:6
1 6 7
当前结点:1 上一个结点:0 下一个结点:6
6 7
当前结点:6 上一个结点:0 下一个结点:7
7
当前结点:7 上一个结点:0 下一个结点:0
链表为空
最后一个出圈者的编号7