菜缤的世界 CairBin's Blog - Joseph
type: channel
link: https://blog.cairbin.top/index.php/tag/Joseph/
items: 循环链表应用——约瑟夫置换

循环链表应用——约瑟夫置换
type: item
date: 2021-09-18T15:22:00+00:00
description: 约瑟夫问题介绍约瑟夫问题，又称约瑟夫置换、丢手绢问题。一般形式（本部分内容来自百度百科）约瑟夫问题是个有名的问题：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…