约瑟夫问题

这篇具有很好参考价值的文章主要介绍了约瑟夫问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

约瑟夫问题是一个经典的数学问题,也是计算机科学中常见的数据结构和算法题目之一。它的形式是:有n个人站成一排,从第一个人开始报数,每次报到m的人出列,直到所有人都出列为止。请问,最后留下的人原来在什么位置上?

这个问题可以用多种方法解决,其中包括使用数组、单链表、双向循环链表以及数学公式法等。下面我们将分别介绍这些解题方法的思路和实现。

1. 使用数组

如果我们使用数组来模拟约瑟夫问题,可以先创建一个长度为n的数组,表示n个人的编号。然后我们可以使用循环遍历该数组,并根据报数的规则删除数组中的元素,相当于把这个数组看作一个环形队列。

具体来说,从第一个人开始报数,每报到m的人就将其从数组中删除(将其值设为-1),并把后面的元素依次向前移动一位。然后从下一个人重新开始报数,直到所有人都出列。最后留下的那个人的编号就是数组中唯一一个没有被删除的数。

时间复杂度为O(nm),其中n表示人数,m表示报数到m的人出列。

#include <iostream>
#include <vector>
using namespace std;

vector<int> josephus(int n, int m) {
    vector<int> res;                    // 存储出列顺序
    vector<bool> used(n, false);        // 标记每个人是否已经出列
    int count = 0, index = -1;          // count表示当前报数的人数,index表示当前报数的人的下标
    while (res.size() < n) {            // 循环直到所有人都出列为止
        index++;                        // 按顺序遍历人数列表
        if (index >= n) index = 0;      // 处理超出范围的情况
        if (!used[index]) count++;      // 如果这个人还没有出列,则更新计数器
        if (count == m) {               // 如果这个人需要出列
            res.push_back(index + 1);   // 将他的编号存储在出列顺序列表中
            used[index] = true;         // 标记这个人已经出列
            count = 0;                  // 重置计数器
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    auto res = josephus(n, m);
    for (auto x : res) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

2. 使用单链表

如果我们使用单链表来模拟约瑟夫问题,我们可以创建一个带有n个节点的单链表,并将它闭合成环形链表。然后,从头结点开始依次遍历链表,每次找到要出列的节点的前一个节点,输出并删除该节点。因为单链表只能从前往后遍历,所以每次找到要出列的节点的前一个节点需要顺时针遍历m-1个节点。

时间复杂度为O(nm),与数组解法相同。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int d): data(d), next(nullptr) {}
};

void josephus(int n, int m) {
    Node* head = new Node(1);
    Node* prev = head;
    for (int i = 2; i <= n; i++) {
        Node* curr = new Node(i);
        prev->next = curr;
        prev = curr;
    }
    prev->next = head;  // 将链表闭合成环
    
    Node* curr = head;
    while (n > 0) {
        // 找到要出列的节点的前一个节点
        for (int i = 0; i < m-1; i++) {
            curr = curr->next;
        }
        // 输出并删除节点
        cout << curr->next->data << " ";
        Node* temp = curr->next;
        curr->next = curr->next->next;
        delete temp;
        n--;
    }

    // 释放内存
    Node* temp = head;
    while (temp != nullptr) {
        Node* next = temp->next;
        delete temp;
        temp = next;
    }
}

int main() {
    josephus(5, 3);  // 输出: 3 1 5 2 4
    return 0;
}

3. 使用双向循环链表

如果我们使用双向循环链表来模拟约瑟夫问题,我们可以创建一个带有n个节点的双向循环链表,并将它闭合成环形链表。然后,从头结点开始依次遍历链表,每次找到要出列的节点的前一个节点,输出并删除该节点。因为双向循环链表可以从前往后遍历,也可以从后往前遍历,所以每次找到要出列的节点的前一个节点需要顺时针或逆时针遍历m-1个节点。

时间复杂度为O(nm),与单链表解法相同。

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* prev;
    Node* next;
    Node(int d): data(d), prev(nullptr), next(nullptr) {}
};

void josephus(int n, int m) {
    Node* head = new Node(1);
    Node* prev = head;
    for (int i = 2; i <= n; i++) {
        Node* curr = new Node(i);
        prev->next = curr;
        curr->prev = prev;
        prev = curr;
    }
    prev->next = head;  // 将链表闭合成环
    head->prev = prev;
    
    Node* curr = head;
    while (n > 0) {
        // 找到要出列的节点的前一个节点
        for (int i = 0; i < m-1; i++) {
            curr = curr->next;
        }
        // 输出并删除节点
        cout << curr->next->data << " ";
        Node* temp = curr->next;
        curr->next = temp->next;
        temp->next->prev = curr;
        delete temp;
        n--;
    }

    // 释放内存
    Node* temp = head;
    do {
        Node* next = temp->next;
        delete temp;
        temp = next;
    } while (temp != head);
}

int main() {
    josephus(5, 3);  // 输出: 3 1 5 2 4
    return 0;
}

4. 数学公式法

除了用数据结构来模拟约瑟夫问题,还有一种数学公式法可以解决这个问题。根据数学公式,最后留下来的那个人的编号是一个关于n和m的递推公式,我们可以直接用递推公式来计算出最后留下来的人的编号。

具体来说,最后留下来的那个人的编号可以表示成:

f(n, m) = (f(n-1, m) + m) % n

其中,f(n, m)表示n个人中最后留下来的人的编号,%表示取余操作。

我们可以使用递归或循环来计算递推公式。时间复杂度为O(n),与其他算法相比更加高效。

总结

约瑟夫问题是一个经典的数学问题,也是计算机科学中常见的数据结构和算法题目之一。

我们可以使用数组、单链表、双向循环链表以及数学公式法等多种方法文章来源地址https://www.toymoban.com/news/detail-407976.html

到了这里,关于约瑟夫问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】约瑟夫环问题解析与实现

    约瑟夫环(Josephus Problem)是一个经典的数学问题,涉及一个编号为 1 到 n 的人围成一圈,从第一个人开始报数,报到某个数字 m 的人出列,然后再从下一个人开始报数,如此循环,直到所有人都出列。本篇博客将详细解析约瑟夫环问题,并使用 Python 实现算法。 在约瑟夫环问

    2024年02月06日
    浏览(42)
  • 4种方法解决约瑟夫环问题

            约瑟夫环问题是大多数编程初学者必须要跨越的一道坎。在第一次见到它的时候,我还是个刚刚学会循环语句的小蒟蒻,而现在的我已经是深陷图论以及各种其他算法的大蒟蒻了(bushi)。可以说,约瑟夫环问题是我从编程基础向编程思维踏出的重要一步。        

    2024年02月12日
    浏览(32)
  • C语言:约瑟夫环问题详解

    前言 哈喽,宝子们!本期为大家带来一道C语言循环链表的经典算法题(约瑟夫环)。 据说著名历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人

    2024年04月13日
    浏览(33)
  • C语言 | 约瑟夫问题(猴王争夺战)

             约瑟夫问题有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。下面我们将用猴子争大王这一故事以及采用单向循环链表这一方法来进行讲解这一问题。         设编号为1,2,……n得n个猴子围

    2024年02月01日
    浏览(33)
  • 重温数据结构与算法之约瑟夫问题

    约瑟夫问题 ,是一个计算机科学和数学中的问题,在计算机编程的算法中,类似问题又称为 约瑟夫环 ,又称“丢手绢问题”。 据说著名犹太历史学家 Josephus 有过以下的故事: 在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也

    2024年02月08日
    浏览(46)
  • 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)

    n n n 个人围成一圈,从第一个人开始报数,数到 m m m 的人出列,再由下一个人重新从 1 1 1 开始报数,数到 m m m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n − 1

    2024年02月07日
    浏览(36)
  • 约瑟夫环问题_数组解决_C语言

    有n个人围成一个圈,开始报数,报到m的人出局,并且不再参加报数,依次类推,直到n个人全部出局为止。 1.将抽象的问题实例化 假设有一个裁判: mouth:取值范围 1~m (报到m的人出局) finger: 取值范围1~n   (总共有n个人) 2.对n,m赋值,个人模拟报数 假设 n==8    , 

    2024年02月03日
    浏览(34)
  • 数据结构—约瑟夫环问题(C语言版)

    目录 首先什么是约瑟夫环 约瑟夫环实现方式 一、创建结构体变量 二、初始化链表 三、构建循环链表 四、删除链表  五、完整代码及注释讲解 约瑟夫环 是 循环链表 中的一个经典问题;题目描述:n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新

    2024年02月11日
    浏览(44)
  • 【c语言习题】使用链表解决约瑟夫问题

    创作不易,本篇文章如果帮助到了你,还请点赞 关注支持一下♡𖥦)!! 主页专栏有更多知识,如有疑问欢迎大家指正讨论,共同进步! 🔥c语言系列专栏:c语言之路重点知识整合 🔥 给大家跳段街舞感谢支持!ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ ዽ ጿ ኈ ቼ 链表有

    2024年02月08日
    浏览(38)
  • 数据结构学习-循环链表:处理约瑟夫环问题

    目录 问题描述 一、基本概念  1.普通链表 2.单向循环链表  二、问题处理 1.创建链表 2.查找 3.删除  4.其他  三.实验环节 四.总结 约瑟夫环问题的一种描述是:编号为1,2,...,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包