约瑟夫问题介绍约瑟夫问题，又称约瑟夫置换、丢手绢问题。一般形式（本部分内容来自百度百科）约瑟夫问题是个有名的问题：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