新星市网站建设_网站建设公司_动画效果_seo优化

(新卷,100分)- 约瑟夫问题（Java & JS & Python & C）

题目描述

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

从数列首位置开始计数，计数到 m 后，将数列该位置数值替换计数值 m，

并将数列该位置数值出列，然后从下一位置从新开始计数，直到数列所有数值出列为止。

如果计数到达数列尾段，则返回数列首位置继续计数。

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

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

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

第二轮计数出列数字为 3，计数值更新 m=3，出列后数列为 1,4，从数值 1 所在位置开始计数

第三轮计数出列数字为 1，计数值更新 m=1，出列后数列为 4，从数值 4 所在位置开始计数

最后一轮计数出列数字为 4，计数过程完成。输出数值出列顺序为：2,3,1,4。

要求实现函数：

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

输入描述

int len：输入数列的长度； int intput_array[]：输入的初始数列 int m：初始计数值

输出描述

int output_array[]：输出的数值出列顺序

用例

题目解析

本题就是约瑟夫环的变种题。

约瑟夫环的解题有多种方式，比较容易理解和实现的可以使用双端队列。

即intput_array当成双端队列，从队头取出元素，判断此时计数是否为m：

• 若是，则将取出的元素加入output_arr，并将取出的元素的值赋值给m，然后len--，计数重置为1
• 若不是，则将取出的元素塞回intput_array的队尾，仅计数++

但是本题JS是基于数组实现的双端队列，因此每次头部元素出队，都意味着一次O(n)复杂度的数组元素前移一位操作，这是非常影响性能的。

对于Java，Python都有内置的双端队列结构，因此可以直接复用，对于C，可以自己实现双端队列结构。

因此JS语言我们可以选择循环链表来模拟约瑟夫环。

循环链表本身就实现了环形结构，其head.prev = tail，tail.next = head。

且循环链表删除节点的复杂度是O(1)。

唯一的遗憾是，JS没有原生的循环链表结构，我们需要自己实现。但是我们只需要实现最简单的循环链表即可，即只实现循环链表的尾部新增节点操作即可。而删除操作可以在实际业务中完成。

JavaScript算法源码

双端队列

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 3) { const input_arr = lines[0].split(","); const len = lines[1]; const m = lines[2]; const output_arr = []; array_iterate(len, input_arr, m, output_arr); console.log(output_arr.join(",")); lines.length = 0; } }); function array_iterate(len, input_arr, m, output_arr) { let i = 1; while (len > 0) { const out = input_arr.shift(); if (i == m) { output_arr.push(out); m = out; i = 1; len--; } else { input_arr.push(out); i++; } } }

循环链表

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 3) { const input_arr = lines[0].split(","); const len = lines[1]; const m = lines[2]; const output_arr = []; array_iterate(len, input_arr, m, output_arr); console.log(output_arr.join(",")); lines.length = 0; } }); function array_iterate(len, input_arr, m, output_arr) { const cll = new CircularLinkedList(); cll.init(input_arr); let cur = cll.head; let i = 1; while (cll.size) { if (i == m) { const pre = cur.prev; const nxt = cur.next; pre.next = nxt; nxt.prev = pre; m = cur.val; output_arr.push(m); cur.next = cur.prev = null; cur = nxt; i = 1; cll.size--; } else { i++; cur = cur.next; } } } class Node { constructor(val) { this.val = val; this.next = null; this.prev = null; } } class CircularLinkedList { constructor() { this.head = null; this.tail = null; this.size = 0; } append(val) { const node = new Node(val); if (this.size) { this.tail.next = node; node.prev = this.tail; this.tail = node; } else { this.head = node; this.tail = node; } this.head.prev = this.tail; this.tail.next = this.head; this.size++; } init(arr) { arr.forEach((val) => { this.append(val); }); } }

Java算法源码

Java可以使用LinkedList模拟双端队列

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Integer[] input_arr = Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new); int len = Integer.parseInt(sc.nextLine()); int m = Integer.parseInt(sc.nextLine()); System.out.println(getResult(input_arr, len, m)); } public static String getResult(Integer[] input_arr, int len, int m) { LinkedList<Integer> dq = new LinkedList<>(Arrays.asList(input_arr)); ArrayList<Integer> output_arr = new ArrayList<>(); int i = 1; while (len > 0) { Integer out = dq.removeFirst(); if (i == m) { output_arr.add(out); m = out; i = 1; len--; } else { dq.add(out); i++; } } StringJoiner sj = new StringJoiner(","); for (Integer ele : output_arr) { sj.add(ele + ""); } return sj.toString(); } }

Python算法源码

from collections import deque # 输入获取 input_arr = deque(list(map(int, input().split(",")))) length = int(input()) m = int(input()) # 算法入口 def getResult(): global input_arr global length global m output_arr = [] i = 1 while length > 0: out = input_arr.popleft() if i == m: output_arr.append(out) m = out i = 1 length -= 1 else: input_arr.append(out) i += 1 return ",".join(map(str, output_arr)) # 算法调用 print(getResult())

C算法源码

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct ListNode { int ele; struct ListNode* next; } ListNode; typedef struct { int size; ListNode* head; ListNode* tail; } LinkedList; LinkedList* new_LinkedList(); void addLast_LinkedList(LinkedList* link, int ele); int removeFirst(LinkedList* link); int main() { LinkedList* dq = new_LinkedList(); int num; while(scanf("%d", &num)) { addLast_LinkedList(dq,num); if(getchar() != ',') break; } int len; scanf("%d", &len); int m; scanf("%d", &m); LinkedList* output_arr = new_LinkedList(); int i = 1; while(len > 0) { int out = removeFirst(dq); if(i == m) { addLast_LinkedList(output_arr,out); m = out; i = 1; len--; } else { addLast_LinkedList(dq,out); i++; } } char res[100000]; ListNode* cur = output_arr->head; while(cur != NULL) { char tmp[10]; sprintf(tmp, "%d", cur->ele); strcat(res, tmp); cur = cur->next; if(cur != NULL) { strcat(res, ","); } } puts(res); return 0; } LinkedList* new_LinkedList() { LinkedList* link = (LinkedList*) malloc(sizeof(LinkedList)); link->size = 0; link->head = NULL; link->tail = NULL; return link; } void addLast_LinkedList(LinkedList* link, int ele) { ListNode* node = (ListNode*) malloc(sizeof(ListNode)); node->ele = ele; node->next = NULL; if(link->size == 0) { link->head = node; link->tail = node; } else { link->tail->next = node; link->tail = node; } link->size++; } int removeFirst(LinkedList* link) { if(link->size == 0) exit(-1); ListNode* removed = link->head; if(link->size == 1) { link->head = NULL; link->tail = NULL; } else { link->head = link->head->next; } link->size--; int res = removed->ele; free(removed); return res; }