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

在这里插入图片描述

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

专栏导读

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

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

一、题目描述

输入一个由随机数组成的数组（数组中每个数均是大于 0 的整数，长度已知），和初始计数值m。

从数组首位置开始计数，计数到 m 后，将数组该位置数值替换为计数值m，并将数组该位置数值出列，然后从下一个位置重新开始计数，直到数组所有数值出列为止。

如果计数到达数组尾部，则回到数组首位置继续计数。

请编程实现上述计数过程，同时输出数组出列的顺序。

例如：输入的随机数列为 3,1,2,4，初始计数值 m=7，从数组首位置开始计数（数值 3 所在位置）。

第一轮计数出列数字为 3，计数值更新为 m=2，出列后数组为 3,1,4，从数组 4 所在位置重新计数。

第一轮计数出列数字为 3，计数值更新为 m=3，出列后数组为 3,1,4，从数组 4 所在位置重新计数。

第一轮计数出列数字为 1，计数值更新为 m=1，出列后数组为 4，从数组 1 所在位置重新计数。

最终输出：2,3,1,4。

要求实现函数：

void array_iterate(int len, int input_array[], int m, int output_array[])

二、输入描述

int len：输入数组的长度；
int input_array[]：输入的初始数组；
int m：初始计数值。

三、输出描述

output_array[]：输出的数组出列顺序。

四、测试用例

1、输入

3,1,2,4
4
7

2、输出

2,3,1,4

3、说明

第一行是初始数组input_array。
第二行是初始数组的长度len。
第三行是初始计数值m。

五、解题思路

使用ArrayList来存储输入数组，因为ArrayList支持动态删除元素和随机访问，便于模拟循环数组的行为。
初始化一个ArrayList，将输入数组的元素添加进去。
使用一个索引变量currentIndex表示当前计数的位置，初始值为0。
在每次循环中，根据当前的计数值m计算出要移除的元素的位置，计算公式为(currentIndex + m - 1) % list.size()，这样可以实现循环计数。
移除该位置的元素，将其值赋给m，并将该元素添加到输出数组中。
更新currentIndex为被移除位置的下一个位置，继续下一轮计数。
重复上述过程，直到所有元素都被移除。

六、Python算法源码

python"># Python版本
# 导入所需的模块
import sysdef array_iterate(len, input_array, m, output_array):# 将输入数组转换为列表，便于动态删除元素lst = input_array.copy()currentIndex = 0  # 当前计数的位置outputIndex = 0    # 输出数组的索引while lst:# 计算移除元素的位置currentIndex = (currentIndex + m - 1) % len(lst)# 获取要移除的元素removed = lst[currentIndex]# 将移除的元素放入输出数组output_array[outputIndex] = removedoutputIndex += 1# 更新计数值m为移除的元素值m = removed# 移除元素lst.pop(currentIndex)def main():# 读取输入数组，支持逗号和空格分隔input_line = sys.stdin.readline().strip()input_strings = input_line.replace(',', ' ').split()input_array = list(map(int, input_strings))# 读取数组长度len_line = sys.stdin.readline().strip()length = int(len_line)# 读取初始计数值mm_line = sys.stdin.readline().strip()m = int(m_line)# 准备输出数组output_array = [0] * length# 调用函数进行处理array_iterate(length, input_array, m, output_array)# 输出结果，以逗号分隔print(','.join(map(str, output_array)))if __name__ == "__main__":main()

七、JavaScript算法源码

javascript">// JavaScript版本
// 使用Node.js的readline模块来读取输入
const readline = require('readline');// 创建接口用于读取标准输入
const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let inputLines = [];
rl.on('line', (line) => {inputLines.push(line.trim());// 当输入行数达到3行时，开始处理if (inputLines.length === 3) {rl.close();}
}).on('close', () => {// 读取输入数组，支持逗号和空格分隔let inputArray = inputLines[0].split(/[, ]+/).map(Number);// 读取数组长度let len = parseInt(inputLines[1]);// 读取初始计数值mlet m = parseInt(inputLines[2]);// 准备输出数组let outputArray = new Array(len);// 调用数组迭代函数array_iterate(len, inputArray, m, outputArray);// 输出结果，以逗号分隔console.log(outputArray.join(','));
});// 定义数组迭代函数
function array_iterate(len, input_array, m, output_array) {// 将输入数组复制到列表中，便于动态删除元素let lst = input_array.slice();let currentIndex = 0; // 当前计数的位置let outputIndex = 0;   // 输出数组的索引// 当列表不为空时，继续迭代while (lst.length > 0) {// 计算移除元素的位置currentIndex = (currentIndex + m - 1) % lst.length;// 获取要移除的元素let removed = lst[currentIndex];// 将移除的元素放入输出数组output_array[outputIndex++] = removed;// 更新计数值m为移除的元素值m = removed;// 移除元素lst.splice(currentIndex, 1);}
}

八、C算法源码

/* C语言版本 */
#include <stdio.h>
#include <stdlib.h>// 定义最大数组长度
#define MAX_SIZE 1000// 数组迭代函数
void array_iterate(int len, int input_array[], int m, int output_array[]) {// 创建一个标记数组，标记元素是否被移除int *removed = (int *)malloc(len * sizeof(int));for(int i = 0; i < len; i++) {removed[i] = 0; // 初始化为未移除}int count = 0;       // 已移除的元素数量int currentIndex = 0; // 当前计数的位置int outputIndex = 0;  // 输出数组的索引while(count < len) {// 计算移除元素的位置int steps = 0;while(steps < m) {if(!removed[currentIndex]) {steps++;if(steps == m) {break;}}currentIndex = (currentIndex + 1) % len;}// 移除当前元素removed[currentIndex] = 1;output_array[outputIndex++] = input_array[currentIndex];m = input_array[currentIndex];count++;// 移动到下一个未移除的位置currentIndex = (currentIndex + 1) % len;}free(removed); // 释放内存
}int main(){int input_array[MAX_SIZE];int len;int m;// 读取输入数组，支持逗号和空格分隔char input_line[500];fgets(input_line, sizeof(input_line), stdin);int index = 0;char *token = strtok(input_line, ", \n");while(token != NULL){input_array[index++] = atoi(token);token = strtok(input_line, ", \n");}len = index;// 读取数组长度scanf("%d", &len);// 读取初始计数值mscanf("%d", &m);// 准备输出数组int output_array[MAX_SIZE];// 调用数组迭代函数array_iterate(len, input_array, m, output_array);// 输出结果，以逗号分隔for(int i = 0; i < len; i++) {if(i != 0) printf(",");printf("%d", output_array[i]);}printf("\n");return 0;
}

九、C++算法源码

// C++版本
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;// 定义数组迭代函数
void array_iterate(int len, vector<int> input_array, int m, vector<int> &output_array) {// 将输入数组复制到列表中，便于动态删除元素vector<int> lst = input_array;int currentIndex = 0; // 当前计数的位置int outputIndex = 0;   // 输出数组的索引// 当列表不为空时，继续迭代while(!lst.empty()) {// 计算移除元素的位置currentIndex = (currentIndex + m - 1) % lst.size();// 获取要移除的元素int removed = lst[currentIndex];// 将移除的元素放入输出数组output_array[outputIndex++] = removed;// 更新计数值m为移除的元素值m = removed;// 移除元素lst.erase(lst.begin() + currentIndex);}
}int main(){// 读取输入数组，支持逗号和空格分隔string input_line;getline(cin, input_line);vector<int> input_array;stringstream ss(input_line);string token;while(getline(ss, token, ',')) {// 去除可能的空格size_t start = token.find_first_not_of(" ");if(start != string::npos){token = token.substr(start);}input_array.push_back(stoi(token));}// 读取数组长度int len;cin >> len;// 读取初始计数值mint m;cin >> m;// 准备输出数组vector<int> output_array(len, 0);// 调用数组迭代函数array_iterate(len, input_array, m, output_array);// 输出结果，以逗号分隔for(int i = 0; i < len; i++) {if(i != 0) cout << ",";cout << output_array[i];}cout << endl;return 0;
}