categories: DataStructure

问题描述

设有n个人围坐在圆桌周围，现从某个位置m(1≤m≤n)上的人开始报数，报数到k的人就站出来。下一个人，即原来的第k+1个位置上的人，又从1开始报数，再报数到k的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这n个人的出列顺序。

问题要求

  1. 构造一个具有n个结点的循环单链表，用于存储圆桌周围的人的编号，链表结点的data域存放桌子周围的人的编号。
  2. 为保持程序的通用性,问题中的n、m、k可由用户从键盘输入.
  3. 要求编写函数模拟约瑟夫问题的实现过程,并输出n个人的出列顺序。

    问题分析

    这个问题和综合实验一的思路一样，都是利用循环单链表（所以理论上之前的狐狸逮兔子应该用顺序表，而我用了链表huajif07e7f9f783b2e6.jpeg）。

    代码

    写代码过程中，题目没看清楚，一开始以为是被选中的人还呆在环里面，就导致我的指针指了一下午的寂寞……huaji-336495ce81a39782.jpeg，不说了，交实验报告去了…… ```cpp

    include

    using namespace std;

/**

  • 定义一个单链表 / typedef struct LNode { int data; struct LNode next; }Lnode, *LinkList;

/**

  • 初始化单链表 */ void InitList(LinkList &L) { L = new LNode; L->next = NULL; L->data = 1; }

/ 初始化循环链表的初始值 / void init_add(LinkList &L, int n) { InitList(L); LinkList p = L; for (int i = 2; i <= n;i++) { LinkList p_temp = new Lnode; p_temp->data = i; if (i == n) { p_temp->next = L; p->next = p_temp; } else { p_temp->next = p->next; p->next = p_temp; p = p->next; } } }

void joseph_ring(LinkList &L, int n, int m, int k) { init_add(L, n); LinkList p = L; for (int i = 0; i< m; i++) { p = p->next; } while(p->next != p) { for (int j = 1; j< k; j++) { if (j == k-1) { cout<next->data<<”号出来”<<”\n”; p->next = p->next->next; p = p->next; } else { p = p->next; } } } cout<< p->data<<”号出来”<<”\n”;

}

int main() { cout << “请依次输入人数n、报数位置m、报到指定值就站起来的k值” << “\n”; int n, m, k; cin >> n >> m >> k; LinkList p; joseph_ring(p, n, m, k); } ``` image.png