什么是約瑟夫環(huán)呢割岛？
約瑟夫環(huán)（約瑟夫問題）是一個(gè)數(shù)學(xué)的應(yīng)用問題：已知n個(gè)人（以編號(hào)1女器，2，3...n分別表示）圍坐在一張圓桌周圍浸遗。從編號(hào)為k的人開始報(bào)數(shù)猫胁，數(shù)到m的那個(gè)人出列；他的下一個(gè)人又從1開始報(bào)數(shù)跛锌，數(shù)到m的那個(gè)人又出列弃秆；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列髓帽。
image.png
例如：耶穌有13個(gè)門徒菠赚，其中有一個(gè)就是出賣耶穌的叛徒，請(qǐng)用排除法找出這位叛徒：13人圍坐一圈郑藏，從第一個(gè)開始報(bào)號(hào)：1衡查，2，3必盖，1拌牲，2，3…歌粥。凡是報(bào)到“3”就退出圈子塌忽，最后留在圈子內(nèi)的人就是出賣耶穌的叛徒。
思路：
- 首先假設(shè)失驶，當(dāng)數(shù)字為1的時(shí)候則表示活著的人土居，0為死了，這樣我們就可以用數(shù)組來表示嬉探；
- 要考慮的幾個(gè)問題擦耀，要形成一個(gè)環(huán)，就是說報(bào)數(shù)到第十三人的時(shí)候甲馋，從頭開始報(bào)數(shù)埂奈；
- 報(bào)數(shù)為3的時(shí)候，那個(gè)人退出游戲定躏，這里假設(shè)死了账磺，數(shù)值為0芹敌；
- 還有一個(gè)問題，就是當(dāng)報(bào)數(shù)到第四個(gè)人的時(shí)候垮抗，因?yàn)榈谌齻€(gè)人‘死了’氏捞，所以第四個(gè)人要從1開始報(bào)數(shù)；
5.當(dāng)最后只剩下一個(gè)人的時(shí)候冒版，則結(jié)束液茎。
<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){
// 開始計(jì)數(shù)
count++;
// 當(dāng)報(bào)數(shù)到第四個(gè)的時(shí)候，從第一個(gè)開始報(bào)數(shù)
if(count==4){
count = 1;
}
// 當(dāng)報(bào)數(shù)報(bào)到第三個(gè)人的時(shí)候辞嗡，第三個(gè)人就死了
if(count == 3){
arr[i]=0;
num++;
// 當(dāng)計(jì)數(shù)到最后的時(shí)候捆等，游戲結(jié)束
if(num == arr.length-1){
break;
}
}
}
// 當(dāng)數(shù)到最后一個(gè)人的時(shí)候，從第一個(gè)人重頭數(shù)续室，如果i=0的時(shí)候栋烤，i++就變成了2,所以i要為0
if(i==arr.length-1){
i = -1;
}
}
console.log(arr);
</script>
結(jié)果：
1.png
過了兩年，學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)挺狰，用隊(duì)列解決這種問題再簡(jiǎn)單不過明郭，特此補(bǔ)上
// 思路： 定義一個(gè)隊(duì)列，隊(duì)列先進(jìn)先出丰泊，故先進(jìn)來的數(shù)字先出去薯定，再定義個(gè)index用來記錄當(dāng)前元素在隊(duì)列中的位置，位置是3的倍數(shù)瞳购，則刪除
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(); // 將環(huán)中數(shù)據(jù)一一刪除
index += 1;
if (index % 3 !== 0) { // 不是3的倍數(shù)话侄，再?gòu)沫h(huán)尾加入
queue.push(item);
}
}
return queue[0];
}
// 測(cè)試
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];
isPt(arr);
