尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:
目录
  1. 问题描述
  2. 问题要求
  3. 问题分析
  4. 代码

尼采般地抒情

尼采般地抒情

公告栏

此网站主题为本人手写主题,主题还在开发中……


作者:尼采般地抒情
本站主页面和blog页面暂时一样,目的是为了百度收录,百度收录之后,会将主页换回引导页~

站点信息

文章数目:195
已运行时间:

问题描述

设有 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,不说了,交实验报告去了……

#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);
}

image.png

博客内容遵循: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0)

本文永久链接: https://www.wztlink1013.com/blog/itu2g5/

编辑: 部署: 订阅:

评论区

Twikoo 转换 utterances

最新评论

Loading...