ปัญหานี้ได้รับการขนานนามว่าเป็นเหตุการณ์ที่สำคัญที่สุดในชีวิตของนักประวัติศาสตร์โบราณ ฟัสฟุส ตามเรื่องราวของเขา เขาและทหาร 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 ]
