इस समस्या का नाम यकीनन प्राचीन इतिहासकार जोसेफस के जीवन की सबसे महत्वपूर्ण घटना के नाम पर रखा गया है - उनकी कहानी के अनुसार, वह और उनके 40 सैनिक एक घेराबंदी के दौरान रोमनों द्वारा एक गुफा में फंस गए थे।
दुश्मन के सामने आत्मसमर्पण करने से इनकार करते हुए, उन्होंने इसके बजाय सामूहिक आत्महत्या का विकल्प चुना, एक मोड़ के साथ - उन्होंने एक घेरा बनाया और हर तीन पर एक आदमी को मारना शुरू किया, जब तक कि एक आखिरी आदमी न बच जाए (और उसे खुद को मारकर कार्य को समाप्त करना चाहिए था)।
जोसेफस और एक अन्य व्यक्ति अंतिम दो थे और, जैसा कि हम अब कहानी का हर विवरण जानते हैं, आपने सही अनुमान लगाया होगा कि उन्होंने मूल विचार का बिल्कुल पालन नहीं किया।
हमें एक JavaScript फ़ंक्शन लिखना है जो जोसेफस क्रमचय लौटाता है।
पैरामीटर के रूप में वस्तुओं की प्रारंभिक सरणी/सूची लेना जैसे कि वे एक घेरे में थे और हर k स्थान पर गिने जाते थे जब तक कि कोई न रह जाए।
उदाहरण के लिए, n=7 और k=3 के साथ josephus(7,3) को इस तरह कार्य करना चाहिए।
[1,2,3,4,5,6,7] - प्रारंभिक क्रम [1,2,4,5,6,7] => 3 गिना जाता है और परिणाम में जाता है [3] [1,2,4,5,7] => 6 गिना जाता है और परिणाम में जाता है [3,6] [1,4,5,7] => 2 गिना जाता है और परिणाम में जाता है [3,6,2] [1,4,5] => 7 गिना जाता है और परिणाम में जाता है [3,6,2,7] [1,4] => 5 गिना जाता है और परिणाम में जाता है [3,6,2,7,5] [4] => 1 गिना जाता है और परिणाम में जाता है [3,6,2,7,5,1] [] => 4 गिना जाता है और परिणाम में जाता है [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
]
