資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學高效計算約瑟夫排列 (JavaScript)
這個問題的名字來源於古史學家約瑟夫斯生命中最重要的事情——根據他的故事，他和他的40名士兵在圍攻期間被羅馬人困在一個山洞裡。
他們拒絕向敵人投降，而是選擇集體自殺，但方式有所不同——他們圍成一個圓圈，每隔三個人就殺死一個人，直到只剩下一個人（然後這個人應該自殺以結束這場行動）。
約瑟夫斯和另一個人是最後兩個人，正如我們現在所知道的這個故事的所有細節一樣，你可能已經猜到他們並沒有完全按照最初的想法去做。
我們需要編寫一個 JavaScript 函式來返回約瑟夫排列。
將要排列的初始陣列/列表作為引數，就像它們在一個圓圈中一樣，每隔 k 個位置就數出一個，直到沒有剩餘為止。
例如，當 n=7 且 k=3 時，josephus(7,3) 應該這樣執行。
[1,2,3,4,5,6,7] − initial sequence [1,2,4,5,6,7] => 3 is counted out and goes into the result [3] [1,2,4,5,7] => 6 is counted out and goes into the result [3,6] [1,4,5,7] => 2 is counted out and goes into the result [3,6,2] [1,4,5] => 7 is counted out and goes into the result [3,6,2,7] [1,4] => 5 is counted out and goes into the result [3,6,2,7,5] [4] => 1 is counted out and goes into the result [3,6,2,7,5,1] [] => 4 is counted out and goes into the result [3,6,2,7,5,1,4]
因此，我們的最終結果是：
josephus([1,2,3,4,5,6,7],3)==[3,6,2,7,5,1,4];
示例
程式碼如下：
const arr = [1, 2, 3, 4, 5, 6, 7];
const num = 3;
const helper = (n, k, i, map) => {
if (map.hasOwnProperty([n, k, i]))
return map[[n, k, i]];
if (i === 1)
return map[[n, k, i]] = (k − 1) % n;
return map[[n, k, i]] =
(k + helper(n − 1, k, i − 1, map)) % n;
}
const josephus = (arr, k) => {
let n = arr.length;
let result = new Array(n);
let map = {};
for (let i=1; i<=n; i++)
result[i − 1] = arr[ helper(n, k, i, map) ];
return result;
};
console.log(josephus(arr, num));輸出
控制檯輸出：
[ 3, 6, 2, 7, 5, 1, 4 ]
更新於：2020年11月21日
273 次瀏覽
廣告