约瑟夫问题变种 - 标准解法+批量删除解法
问题：100个人为成圈，从 1 - 100 编码，接收输入 M，从第一个人开始报数，报到 M 的人自动退出这个圈，下个人接着从1报数，直到剩余人数少于M，输出剩余人的编码
自己写的解法 - 比标准解法性能高
- 核心逻辑：每次都直接删除 M 的倍数 + 记录最后删除的 M 的下一项，移动到数组最前面，形成环状报数
function circle(M) {
if (M <= 1 || M >= 100) { return 'ERROR!' }
if (M === 2) return '1'; // 标准解在 2 时的处理
let origin = Array.from({ length: 100 }, (_, i) => i + 1);
while (origin.length > M) {
let i = 1;
for (; i * M <= origin.length; i++) {
origin[i * M - 1] = null
}
origin = origin.filter(it => it);
const last = (i - 1) * M - (i - 1); // 移除了 i - 1 个人
origin = origin.slice(last).concat(origin.slice(0, last));
// 更清晰 origin = [...origin.slcie(last), ...origin.slice(0, last)]
}
origin.splice(M - 1, 1);
return origin.sort((a, b) => a - b).join(',');
}
分析 - 典型的 约瑟夫问题，是一个经典的数学和计算机科学问题
- 场景：
N个人围成一圈，编号为1到N。 - 规则：从编号
1开始报数，数到M的人出局，下一个人重新从1开始报数，直到所有人出局或剩余人数小于M。 - 目标：求最终幸存者的编号（或剩余人员的列表）
1、标准模拟解法（逐次删除）
function josephusStandard(N, M) {
if (M === 2) return 1; // 经典约瑟夫问题的已知解
let people = Array.from({ length: N }, (_, i) => i + 1); // 初始化
let current = 0; // 当前报数起点
while (people.length >= M) {
current = (current + M - 1) % people.length; // 计算要删除的位置（环形取模）
people.splice(current, 1); // 删除该人
}
return people.sort((a, b) => a - b); // 返回剩余人员（升序）
}
2、数学递归解法（高效） - 快速求单个幸存者(只返回一人)
function josephusMath(N, M) {
if (N === 1) return 0; // 递归基
return (josephusMath(N - 1, M) + M) % N;
}
function getSurvivor(N, M) { // 转换为实际编号（从1开始）
return josephusMath(N, M) + 1;
}