华为OD机试 - 报数问题 - 约瑟夫环（Python/JS/C/C++ 2024 E卷 100分）

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

有n个人围成一圈，顺序排号为1~n。

从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

二、输入描述

输入人数n（n < 1000）

三、输出描述

输出最后留下的是原来第几号

四、测试用例

测试用例1：

1、输入

2

2、输出

2

3、说明

报数序号为1的人最终报3，因此序号1的人退出圈子，最后剩下序号为2的那位

测试用例2：

1、输入

5

2、输出

4

3、说明

按照上述规则，最后剩下的人的编号为 4。

五、解题思路

1、约瑟夫环

这个问题是经典的“约瑟夫环”问题。在这个问题中，n 个人站成一圈，每个人按照顺序报数，报到 3 的人退出圈子，直到只剩下一个人为止。要解决这个问题，我们可以使用数组或链表模拟这个过程，也可以使用数学方法直接找到最后剩下的人的位置。

核心算法是从第一个人开始，顺序报数。每次移除报数到 3 的人，然后继续报数。通过一个索引变量和模运算来模拟环形的报数过程。

模运算处理循环：index = (index + 2) % size 的模运算用于处理圆圈结构，使得报数可以循环进行，即在列表末尾后又从头开始。

2、具体步骤

1. 初始化圈子：将 n 个人的编号加入到一个数据结构中，形成一个环形队列，方便按照顺序报数和移除元素。
2. 模拟报数过程：
   • 从第一个人开始报数，每数到 3 的人退出圈子。
   • 移除报数到 3 的人后，继续从下一个人开始报数，直到只剩下一个人。
   • 我们使用一个索引变量来记录当前报数的位置，利用模运算 (%) 来处理环形报数。
3. 输出结果：循环结束后，列表中只剩下一个人，输出该人的编号。

3、时间复杂度

每次移除一个人，最多需要花费 O(n) 的时间，因为在最坏情况下需要遍历整个列表（比如在使用数组或链表时需要寻找并移除第 k 个元素）。

总共需要进行 n-1 次移除操作，因此时间复杂度是 O(n * n) = O(n^2)。

4、空间复杂度

O(n)，因为需要存储 n 个人的编号。所有算法和数据结构（列表、链表）都需要占用线性空间来存储这些元素。

六、Python算法源码

def find_last_person(n):# 初始化圈子，将1到n编号加入列表circle = list(range(1, n + 1))index = 0  # 当前报数的位置# 模拟报数过程，直到只剩一个人while len(circle) > 1:# 找到要移除的人的位置，报数到3的人退出index = (index + 2) % len(circle)  # +2 是因为要报到3（报数从0开始计数）circle.pop(index)# 返回最后剩下的人的编号return circle[0]if __name__ == "__main__":n = int(input())  # 输入人数last_person = find_last_person(n)print(last_person)

七、JavaScript算法源码

function findLastPerson(n) {// 初始化圈子，将1到n编号加入数组let circle = [];for (let i = 1; i <= n; i++) {circle.push(i);}let index = 0;  // 当前报数的位置// 模拟报数过程，直到只剩一个人while (circle.length > 1) {// 找到要移除的人的位置，报数到3的人退出index = (index + 2) % circle.length;  // +2 是因为要报到3（报数从0开始计数）circle.splice(index, 1);}// 返回最后剩下的人的编号return circle[0];
}// 输入人数
let n = parseInt(prompt("请输入人数:"));
let lastPerson = findLastPerson(n);
console.log(lastPerson);

八、C算法源码

#include <stdio.h>int findLastPerson(int n) {int circle[1000];  // 初始化圈子数组int size = n;      // 当前圈子中人数// 初始化圈子，将1到n编号加入数组for (int i = 0; i < n; i++) {circle[i] = i + 1;}int index = 0;  // 当前报数的位置// 模拟报数过程，直到只剩一个人while (size > 1) {// 找到要移除的人的位置，报数到3的人退出index = (index + 2) % size;  // +2 是因为要报到3（报数从0开始计数）// 移除报数为3的人，将后面的元素前移for (int i = index; i < size - 1; i++) {circle[i] = circle[i + 1];}size--;  // 减少圈子中人数}// 返回最后剩下的人的编号return circle[0];
}int main() {int n;printf("请输入人数: ");scanf("%d", &n);  // 输入人数int lastPerson = findLastPerson(n);printf("%d\n", lastPerson);return 0;
}

九、C++算法源码

#include <iostream>
#include <list>using namespace std;int findLastPerson(int n) {list<int> circle;// 初始化圈子，将1到n编号加入列表for (int i = 1; i <= n; i++) {circle.push_back(i);}auto it = circle.begin();  // 当前报数的位置// 模拟报数过程，直到只剩一个人while (circle.size() > 1) {// 找到要移除的人的位置，报数到3的人退出for (int count = 0; count < 2; count++) {  // +2 是因为要报到3it++;if (it == circle.end()) {it = circle.begin();  // 循环到列表开头}}it = circle.erase(it);  // 移除当前报数为3的人if (it == circle.end()) {it = circle.begin();  // 如果到达列表末尾，循环到开头}}// 返回最后剩下的人的编号return circle.front();
}int main() {int n;cout << "请输入人数: ";cin >> n;  // 输入人数int lastPerson = findLastPerson(n);cout << lastPerson << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。