问题描述
设有n个人围坐在圆桌周围,现从某个位置m(1≤m≤n)上的人开始报数,报数到k的人就站出来。下一个人,即原来的第k+1个位置上的人,又从1开始报数,再报数到k的人站出来。依次重复下去,直到全部的人都站出来为止。试设计一个程序求出这n个人的出列顺序。
问题要求
- 构造一个具有n个结点的循环单链表,用于存储圆桌周围的人的编号,链表结点的data域存放桌子周围的人的编号。
- 为保持程序的通用性,问题中的n、m、k可由用户从键盘输入.
- 要求编写函数模拟约瑟夫问题的实现过程,并输出n个人的出列顺序。
问题分析
这个问题和综合实验一的思路一样,都是利用循环单链表(所以理论上之前的狐狸逮兔子应该用顺序表,而我用了链表)。
代码
写代码过程中,题目没看清楚,一开始以为是被选中的人还呆在环里面,就导致我的指针指了一下午的寂寞……,不说了,交实验报告去了……
#include<bits/stdc++.h>
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<<p->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);
}
评论区