P1996 约瑟夫问题
题目描述
n 个人围成一圈，从第一个人开始报数,数到 m的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。
注意：本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n-1 名小朋友，而该题是全部出圈。
输入格式
输入两个整数 n,m。
输出格式
输出一行 n个整数，按顺序输出每个出圈人的编号。
#include <iostream> #include <vector> using namespace std; vector<int> Fn(int n, int m) { vector<int> pe(n); vector<int> r; for (int i = 0; i < n; ++i) { pe[i] = i + 1; } int h = 0; while (!pe.empty()) { h = (h + m - 1) % pe.size(); r.push_back(pe[h]); pe.erase(pe.begin() + h); } return r; } int main() { int n, m; cin >> n >> m; vector<int> out = Fn(n, m); for (int num : out) { cout << num << " "; } cout << endl; return 0; }
线性表
C++中的线性表是一种数据结构，它指的是元素之间存在一对一的线性关系的数据集合。在线性表中，元素按照一定的顺序排列，每个元素都有一个前驱（除了第一个元素）和一个后继（除了最后一个元素），这样的结构允许元素按照线性顺序进行访问。
线性表可以分为两大类：
1. 顺序表Sequential List：元素在内存中是连续存储的。最典型的例子就是数组（Array），数组的所有元素在内存中占据一段连续的地址空间。顺序表的优点是访问速度快，通过索引可以直接定位到元素；缺点是在插入和删除操作时，尤其是当操作发生在表中间时，可能需要移动大量元素。
2.链表（Linked List）：与顺序表不同，链表中的元素在内存中不必连续存放，每个元素（节点）包含两个部分：存储数据的部分和指向下一个元素（节点）的指针（对于双向链表还包括指向前一个元素的指针）。链表的优点是可以高效地进行插入和删除操作，因为只需要修改相邻节点之间的指针即可，但访问速度相对较慢，因为需要从头节点开始逐个遍历查找。
在C++中，标准模板库(STL)提供了多种线性表的实现，包括：
- `std::vector`：这是一个动态数组，属于顺序表，提供了数组的直接访问性能，同时又有自动扩容的能力。
- `std::list`：这是一个双向链表，属于链表类型，支持快速的插入和删除操作。
- `std::forward_list`：这是一个单向链表，比`std::list`节省空间，但只支持单向遍历。
- `std::deque`（双端队列）：主要用途不是作为线性表，也支持随机访问，并且两端都可以高效地进行插入和删除，因此有时也被视为一种特殊的线性表结构。
容器的选择取决于具体的应用场景和对性能的需求，如是否频繁插入删除、是否需要随机访问等。
