C++中的结构应用:Josephus问题

简介: C++中的结构应用:Josephus问题

Josephus问题是一个经典的理论问题,n个人围成一圈,从第一个人开始报数,每数到第m个人就被排除出圈,然后从下一个人继续开始报数,如此循环,直到只剩下最后一个人。问题要求找出这个幸存者的编号。

解题思路

解决Josephus问题主要有递归方法、迭代方法和数学公式法等几种策略。

递归方法

递归方法的基本思路是将问题分解为规模较小的相同问题。每次执行一轮淘汰后,问题规模减小,直至只剩一人。

迭代方法

迭代方法通过循环模拟整个过程,每次移除指定位置的人,更新剩余人数和起始报数的位置。

数学公式法

对于较大的n和m,直接使用递归或迭代可能效率较低,可以利用已知的数学公式直接计算幸存者的序号。公式较为复杂,但基于约瑟夫环的周期性特性得出。

运行代码

迭代法
#include <iostream>
using namespace std;
 
int josephus(int n, int m) {
    if(n == 1) return 1; // 只剩一个人时,直接返回他的编号
    return (josephus(n - 1, m) + m - 1) % n + 1; // 递推公式
}
 
int main() {
    int n = 7, m = 3;
    cout << "The survivor is at position: " << josephus(n, m) << endl;
    return 0;
}
循环迭代法
#include <iostream>
using namespace std;
 
int josephusIterative(int n, int m) {
    int last = 0;
    for(int i = 2; i <= n; ++i) {
        last = (last + m) % i;
    }
    return last + 1; // 由于循环是从1开始计数,所以最后加1
}
 
int main() {
    int n = 7, m = 3;
    cout << "The survivor is at position: " << josephusIterative(n, m) << endl;
    return 0;
}
数学公式法(Floyd's Cycle-Finding Algorithm变形)

Floyd's Cycle-Finding Algorithm,也常被称为“快慢指针法”或“龟兔赛跑算法”,是一种用于检测循环(环)的存在并在循环中找到重复节点的算法。其核心思想简述如下:

  1. 双指针策略:算法使用两个指针,通常称为“快指针”(fast)和“慢指针”(slow)。开始时,两者都指向链表(或其他数据结构如循环数组)的头部。快指针每次移动两步,慢指针每次移动一步。如果链表中存在循环,快指针最终会追上慢指针;如果链表无环,则快指针会到达链表尾部。
  2. 相遇点:当快慢指针在循环内的某一点相遇时,说明循环存在。这一点不一定是循环的入口点,但它是快慢指针在循环条件下必然会相遇的一个节点。
  3. 寻找循环入口:一旦相遇后,可以采取多种策略来确定循环的入口点。一种常见做法是,让一个指针(例如慢指针)保持在相遇点不动,另一个指针(可以是快指针重新回到起点,也可以直接使用慢指针)以每步一单位的速度前进,当这两个指针再次相遇时的位置就是循环的入口点。这是因为从循环入口到相遇点的距离等于从头节点到相遇点的距离,因此以相同速度前进的两个指针将再次在入口处相遇。
  4. 应用广泛:此算法不仅限于链表检测,还可以应用于其他数据结构中寻找循环的问题,以及某些情况下计算循环长度等。

核心在于利用两个速度不同的指针在循环结构中的相对运动特性,通过它们的相遇来判断循环的存在,并进一步找到循环的具体特征(如入口点)。这种方法效率高,时间复杂度为O(n),空间复杂度为O(1),是解决此类问题的经典算法之一。

目录
相关文章
|
9天前
|
存储 并行计算 安全
C++多线程应用
【10月更文挑战第29天】C++ 中的多线程应用广泛,常见场景包括并行计算、网络编程中的并发服务器和图形用户界面(GUI)应用。通过多线程可以显著提升计算速度和响应能力。示例代码展示了如何使用 `pthread` 库创建和管理线程。注意事项包括数据同步与互斥、线程间通信和线程安全的类设计,以确保程序的正确性和稳定性。
|
5月前
|
存储 安全 C++
C++中的引用和指针:区别与应用
引用和指针在C++中都有其独特的优势和应用场景。引用更适合简洁、安全的代码,而指针提供了更大的灵活性和动态内存管理的能力。在实际编程中,根据需求选择适当的类型,能够编写出高效、可维护的代码。理解并正确使用这两种类型,是掌握C++编程的关键一步。
70 1
|
1月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
47 2
|
2月前
|
编译器 C++
【C++核心】函数的应用和提高详解
这篇文章详细讲解了C++函数的定义、调用、值传递、常见样式、声明、分文件编写以及函数提高的内容,包括函数默认参数、占位参数、重载等高级用法。
22 3
|
2月前
|
C++
【C++基础】程序流程结构详解
这篇文章详细介绍了C++中程序流程的三种基本结构:顺序结构、选择结构和循环结构,包括if语句、三目运算符、switch语句、while循环、do…while循环、for循环以及跳转语句break、continue和goto的使用和示例。
39 2
|
3月前
|
存储 算法 C++
C++ STL应用宝典:高效处理数据的艺术与实战技巧大揭秘!
【8月更文挑战第22天】C++ STL(标准模板库)是一组高效的数据结构与算法集合,极大提升编程效率与代码可读性。它包括容器、迭代器、算法等组件。例如,统计文本中单词频率可用`std::map`和`std::ifstream`实现;对数据排序及找极值则可通过`std::vector`结合`std::sort`、`std::min/max_element`完成;而快速查找字符串则适合使用`std::set`配合其内置的`find`方法。这些示例展示了STL的强大功能,有助于编写简洁高效的代码。
43 2
|
3月前
|
C++ 容器
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
【C++航海王:追寻罗杰的编程之路】关联式容器的底层结构——AVL树
32 5
|
3月前
|
存储 搜索推荐 Serverless
【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
35 1
|
3月前
|
存储 编译器 C++
C++多态实现的原理:深入探索与实战应用
【8月更文挑战第21天】在C++的浩瀚宇宙中,多态性(Polymorphism)无疑是一颗璀璨的星辰,它赋予了程序高度的灵活性和可扩展性。多态允许我们通过基类指针或引用来调用派生类的成员函数,而具体调用哪个函数则取决于指针或引用所指向的对象的实际类型。本文将深入探讨C++多态实现的原理,并结合工作学习中的实际案例,分享其技术干货。
70 0
|
3月前
|
C++
c++学习笔记03 程序流程结构
C++学习笔记,主要介绍了程序流程结构,包括顺序结构、选择结构和循环结构。选择结构中详细解释了if语句、三目运算符和switch语句的用法和注意事项。循环结构部分则涵盖了while循环、do-while循环和for循环的语法和使用技巧。此外,还介绍了跳转语句,包括break、continue和goto语句的用途和用法。
34 0