asp.net微信网站闸北企业网站建设

asp.net微信网站,闸北企业网站建设,硅塑胶 东莞网站建设,开源网站建设(100分)- 报数游戏#xff08;Java JS Python#xff09;题目描述100个人围成一圈#xff0c;每个人有一个编码#xff0c;编号从1开始到100。他们从1开始依次报数#xff0c;报到为M的人自动退出圈圈#xff0c;然后下一个人接着从1开始报数#xff0c;直到…(100分)- 报数游戏Java JS Python题目描述100个人围成一圈每个人有一个编码编号从1开始到100。他们从1开始依次报数报到为M的人自动退出圈圈然后下一个人接着从1开始报数直到剩余的人数小于M。请问最后剩余的人在原先的编号为多少输入描述输入一个整数参数 M输出描述如果输入参数M小于等于1或者大于等于100输出“ERROR!”否则按照原先的编号从小到大的顺序以英文逗号分割输出编号字符串用例输入3输出58,91说明输入M为3最后剩下两个人。输入4输出34,45,97说明输入M为4最后剩下三个人。题目解析本题是经典的约瑟夫环问题可以利用循环链表解决。解法一循环链表定义一个循环链表头节点val1尾节点val100头.prev 尾尾.next 头这样的话就构造出了一个循环链表。我们还需要为循环链表设置尾部追加新节点删除任意节点的操作。另外我们还需要维护一个报数变量idx从1开始。这样的话我们从链表头head开始查询此时报数idx1如果idxm则删除当前节点cur下一个查询节点变为删除节点的下一个节点并且重置报数idx1如果idx!m则继续查询下一节点即cur cur.next并且报数idx按上面逻辑直到链表的size m时结束。然后for(i0; isize; i) 遍历出循环链表的每一个节点值就是题解。Java算法源码import java.util.Scanner; import java.util.StringJoiner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); System.out.println(getResult(m)); } public static String getResult(int m) { if (m 1 || m 100) return ERROR!; CycleLinkedList list new CycleLinkedList(); for (int i 1; i 100; i) list.append(i); int idx 1; Node cur list.head; while (list.size m) { if (idx m) { idx 1; cur list.remove(cur); } else { idx; cur cur.next; } } return list.toString(); } } class Node { int val; Node prev; Node next; public Node(int val, Node prev, Node next) { this.val val; this.prev prev; this.next next; } } class CycleLinkedList { Node head; Node tail; int size 0; public void append(int val) { Node node new Node(val, null, null); if (this.size 0) { 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; } public Node remove(Node cur) { Node pre cur.prev; Node nxt cur.next; pre.next nxt; nxt.prev pre; cur.next cur.prev null; if (this.head cur) { this.head nxt; } if (this.tail cur) { this.tail pre; } this.size--; return nxt; } Override public String toString() { StringJoiner sj new StringJoiner(,); Node cur this.head; for (int i 0; i this.size; i) { sj.add(cur.val ); cur cur.next; } return sj.toString(); } }JS算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on(line, (line) { const m line - 0; console.log(getResult(m)); }); function getResult(m) { if (m 1 || m 100) { return ERROR!; } const list new CycleLinkedList(); for (let i 1; i 100; i) list.append(i); let idx 1; let cur list.head; while (list.size m) { if (idx m) { idx 1; cur list.remove(cur); } else { idx; cur cur.next; } } return list.toString(); } // 节点定义双向 class Node { constructor(val) { this.val val; this.next null; this.prev null; } } // 循环链表定义 class CycleLinkedList { 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; } remove(cur) { const pre cur.prev; const nxt cur.next; pre.next nxt; nxt.prev pre; cur.next cur.prev null; if (this.head cur) { this.head nxt; } if (this.tail cur) { this.tail pre; } this.size--; return nxt; } toString() { const arr []; let cur this.head; for (let i 0; i this.size; i) { arr.push(cur.val); cur cur.next; } return arr.join(); } }Python算法源码# 双向节点 class Node: def __init__(self, val): self.val val self.next None self.prev None # 循环链表 class CycleLinkedList: def __init__(self): self.head None self.tail None self.size 0 def append(self, val): node Node(val) if self.size 0: self.tail.next node node.prev self.tail self.tail node else: self.head node self.tail node self.head.prev self.tail self.tail.next self.head self.size 1 def remove(self, cur): pre cur.prev nxt cur.next pre.next nxt nxt.prev pre cur.next cur.prev None if self.head cur: self.head nxt if self.tail cur: self.tail pre self.size - 1 return nxt def __str__(self): arr [] cur self.head for i in range(self.size): arr.append(str(cur.val)) cur cur.next return ,.join(arr) # 输入获取 m int(input()) # 算法入口 def getResult(): if m 1 or m 100: return ERROR! cycList CycleLinkedList() for i in range(1, 101): cycList.append(i) idx 1 cur cycList.head while cycList.size m: if idx m: idx 1 cur cycList.remove(cur) else: idx 1 cur cur.next return str(cycList) # 算法调用 print(getResult())解法二递归逻辑分析需要先考虑两点找到报数M的人维持连续报数我这边维护了一个外部变量count让他初始值为1因为报数从1开始。遍历数组每遍历完一次则count下次遍历时判断count是不是已经超过M了若超过则count重置为1以此模拟报数。当count%M0时表示当前遍历的数组元素就是报数M的人我们将他filter踢出去了。维持连续报数指的是当我遍历完数组后如果数组元素个数不少于M个则需要新的报数轮次此时新一轮的遍历时第一个元素的报数需要接着上一轮结束时的报数这个也可以通过外部变量count来维护。Java算法源码import java.util.ArrayList; import java.util.Scanner; import java.util.StringJoiner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); System.out.println(getResult(m)); } public static String getResult(int m) { if (m 1 || m 100) return ERROR!; ArrayListInteger arr new ArrayList(); for (int i 1; i 100; i) arr.add(i); return recursive(arr, m, 1); } public static String recursive(ArrayListInteger arr, int m, int count) { ArrayListInteger nxt new ArrayList(); for (Integer v : arr) { if (count m 1) { count 1; } if (count % m ! 0) { nxt.add(v); } } if (nxt.size() m) { return recursive(nxt, m, count); } else { StringJoiner sj new StringJoiner(,); for (Integer v : nxt) sj.add(v ); return sj.toString(); } } }JS算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on(line, (line) { const m parseInt(line); if (m 1 || m 100) { return console.log(ERROR!); } const arr new Array(100).fill().map((_, index) index 1); console.log(recursive(arr, m, 1)); }); // 1 2 3 4 5 6 7 8 9 10 // 1 2 _ 4 5 _ 7 8 _ 10 // 1 _ _ 4 5 _ _ 8 _ 10 // _ _ _ 4 5 _ _ _ _ 10 // _ _ _ 4 _ _ _ _ _ 10 /* 算法逻辑 */ function recursive(arr, m, count) { arr arr.filter(() { if (count m 1) count 1; return count % m; }); if (arr.length m) { return recursive(arr, m, count); } else { return arr.join(,); } }Python算法源码# 输入获取 m int(input()) def recursive(arr, m, count): nxt [] for v in arr: if count m 1: count 1 if count % m ! 0: nxt.append(v) count 1 if len(nxt) m: return recursive(nxt, m, count) else: return ,.join(map(str, nxt)) # 算法入口 def getResult(): if m 1 or m 100: return ERROR! arr [i for i in range(1, 101)] return recursive(arr, m, 1) # 算法调用 print(getResult())解法三双端队列还有一种非常简单非常好理解的做法就是双端队列。双端队列本质也是维护一个循环结构。即当报数m时则队头出队报数重置为1对应此时新对头。当报数 ! m时则队头加入队尾报数对应此时新队头。Java算法源码import java.util.ArrayDeque; import java.util.Scanner; import java.util.StringJoiner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); System.out.println(getResult(m)); } public static String getResult(int m) { if (m 1 || m 100) return ERROR!; ArrayDequeInteger dq new ArrayDeque(); for (int i 1; i 100; i) dq.add(i); int idx 1; while (dq.size() m) { if (idx m) { dq.removeFirst(); idx 1; } else { dq.addLast(dq.removeFirst()); idx; } } StringJoiner sj new StringJoiner(,); dq.stream().sorted((a, b) - a - b).forEach(v - sj.add(v )); return sj.toString(); } }JS算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); rl.on(line, (line) { const m parseInt(line); if (m 1 || m 100) { return console.log(ERROR!); } const dq new Array(100).fill(0).map((_, idx) idx 1); let idx 1; while (dq.length m) { if (idx m) { dq.shift(); idx 1; } else { dq.push(dq.shift()); idx; } } console.log(dq.sort((a, b) a - b).join()); });Python算法源码# 输入获取 m int(input()) # 算法入口 def getResult(): if m 1 or m 100: return ERROR! dq [i for i in range(1, 101)] idx 1 while len(dq) m: if idx m: dq.pop(0) idx 1 else: dq.append(dq.pop(0)) idx 1 dq.sort() return ,.join(map(str, dq)) # 算法调用 print(getResult())总结上面三种解题思路循环链表的性能是最优的而基于数组filter的解法会创建大量零时数组造成内存浪费基于双端队列的解法本质也是基于数组队头出队对于数组来说会导致整体数组元素前移一位即每次队头出队都有一次O(n)时间复杂度的元素位置调整而同样的操作对应于循环链表删除节点的操作 只需要O(1)时间复杂度。