什么是约瑟夫环呢?
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
例如:耶稣有13个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛徒:13人围坐一圈,从第一个开始报号:1,2,3,1,2,3…。凡是报到“3”就退出圈子,最后留在圈子内的人就是出卖耶稣的叛徒。
思路:
- 首先假设,当数字为1的时候则表示活着的人,0为死了,这样我们就可以用数组来表示;
- 要考虑的几个问题,要形成一个环,就是说报数到第十三人的时候,从头开始报数;
- 报数为3的时候,那个人退出游戏,这里假设死了,数值为0;
- 还有一个问题,就是当报数到第四个人的时候,因为第三个人‘死了’,所以第四个人要从1开始报数;
5.当最后只剩下一个人的时候,则结束。
<script>
var arr = [1,1,1,1,1,1,1,1,1,1,1,1,1];
var count = 0;
var num = 0;
for(var i=0;i<arr.length;i++){
// 判断活着
if(arr[i]==1){
// 开始计数
count++;
// 当报数到第四个的时候,从第一个开始报数
if(count==4){
count = 1;
}
// 当报数报到第三个人的时候,第三个人就死了
if(count == 3){
arr[i]=0;
num++;
// 当计数到最后的时候,游戏结束
if(num == arr.length-1){
break;
}
}
}
// 当数到最后一个人的时候,从第一个人重头数,如果i=0的时候,i++就变成了2,所以i要为0
if(i==arr.length-1){
i = -1;
}
}
console.log(arr);
</script>
结果:
过了两年,学习了数据结构,用队列解决这种问题再简单不过,特此补上
// 思路: 定义一个队列,队列先进先出,故先进来的数字先出去,再定义个index用来记录当前元素在队列中的位置,位置是3的倍数,则删除
function isPt(arr) {
let queue = [];
let index = 0;
for (let i = 0; i < arr.length; i++) {
queue.push(arr[i]);
}
while (queue.length !== 1) {
let item = queue.shift(); // 将环中数据一一删除
index += 1;
if (index % 3 !== 0) { // 不是3的倍数,再从环尾加入
queue.push(item);
}
}
return queue[0];
}
// 测试
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];
isPt(arr);