जोसेफस समस्या
जोसेफस समस्या
कंप्यूटर विज्ञान और गणित में, जोसेफस समस्या (या जोसेफस क्रमचय) एक निश्चित गिनती-आउट खेल से संबंधित एक सैद्धांतिक समस्या है।
लोग एक सर्कल में खड़े हैं जो निष्पादित होने की प्रतीक्षा कर रहे हैं। गणना सर्कल में एक निर्दिष्ट बिंदु पर शुरू होती है और एक निर्दिष्ट दिशा में सर्कल के चारों ओर आगे बढ़ती है। एक निर्दिष्ट संख्या में लोगों को छोड़ दिए जाने के बाद, अगले व्यक्ति को मार दिया जाता है। प्रक्रिया शेष लोगों के साथ दोहराई जाती है, अगले व्यक्ति के साथ शुरू होती है, उसी दिशा में जा रही है और समान संख्या में लोगों को छोड़ रही है, जब तक कि केवल एक व्यक्ति ही रहता है, और मुक्त हो जाता है।
समस्या - लोगों की संख्या, प्रारंभिक बिंदु, दिशा और छोड़ दी जाने वाली संख्या को देखते हुए - निष्पादन से बचने के लिए प्रारंभिक चक्र में स्थिति चुनना है।
इतिहास
इस समस्या का नाम 1 शताब्दी में रहने वाले यहूदी इतिहासकार फ्लेवियस जोसेफस के नाम पर रखा गया है। यूसुफफ की घेराबंदी के जोसेफस के खाते के अनुसार, वह और उसके 40 सैनिक रोमन सैनिकों द्वारा एक गुफा में फंस गए थे। उन्होंने कब्जे में आत्महत्या को चुना, और बहुत से चित्र बनाकर आत्महत्या करने की एक धारावाहिक विधि पर बस गए। जोसेफस कहते हैं कि भाग्य या संभवतः भगवान के हाथ से, वह और एक अन्य व्यक्ति अंत तक बने रहे और खुद को मारने के बजाय रोमनों के सामने आत्मसमर्पण कर दिया।[१]
उपाय
निम्नलिखित में, n प्रारंभिक चक्र में लोगों की संख्या को दर्शाता है, और k प्रत्येक चरण के लिए गिनती को निरूपित करता है, अर्थात, k - 1 लोगों को छोड़ दिया जाता है और kth को निष्पादित किया जाता है। सर्कल में लोगों को 1 से n तक गिना जाता है।
उदाहरण के लिए, यदि n = 5 और k = 2 है, तो सुरक्षित स्थिति 3 है। सबसे पहले, स्थिति 2 के व्यक्ति को मार दिया जाता है, फिर स्थिति 4 के व्यक्ति को मार दिया जाता है, फिर स्थिति 1 के व्यक्ति को मार दिया जाता है। अंत में, स्थिति 5 वाला व्यक्ति मारा जाता है। तो स्थिति 3 वाला व्यक्ति बच जाता है।
यदि n = 7 और k = 3 है, तो सुरक्षित स्थिति 4 है। 3, 6, 2, 7, 5, 1 स्थानों पर व्यक्ति क्रम में मारे जाते हैं, और स्थिति 4 पर व्यक्ति जीवित रहता है।
समस्या में पुनरावर्ती संरचना है।
<math>F(n, k)=F (n - 1, k) + k-1) \% n + 1</math>
<math>F(1, k) = 1</math>
पहले व्यक्ति (शुरुआत से kth) मारे जाने के बाद, n-1 व्यक्तियों को छोड़ दिया जाता है। इसलिए हम n-1 व्यक्तियों के साथ स्थिति प्राप्त करने के लिए F(n - 1, k) कहते हैं। लेकिन F(n - 1, k) द्वारा लौटाई गई स्थिति k% n + 1 से शुरू होने वाली स्थिति पर विचार करेगी। इसलिए, हमें F(n - 1, k) द्वारा लौटाए गए स्थान पर समायोजन करना चाहिए।
निम्नलिखित जोसेफस समस्या का सरल पुनरावर्ती कार्यान्वयन है। कार्यान्वयन केवल ऊपर वर्णित पुनरावर्ती संरचना का अनुसरण करता है।
#include <iostream>
using namespace std;
int F(int n, int k)
{
if (n == 1)
return 1;
else
return (F(n - 1, k) + k-1) % n + 1;
}
int main()
{
int n=5;
int k = 2;
cout << "The chosen place is : " <<F(n, k);
return 0;
}
k =2
नीचे कुछ रोचक तथ्य दिए गए हैं।
- यदि लोगों की प्रारंभिक संख्या समान थी, तो सर्कल के चारों ओर दूसरी बार स्थिति x में व्यक्ति मूल रूप से 2x-1 (x की हर पसंद के लिए) की स्थिति में था। n = 2j के लिए F (j) में वह व्यक्ति जो अब जीवित रहेगा, मूल रूप से 2F(j) -1 की स्थिति में था। इससे हमें पुनरावृत्ति होती है : <math> f(2j)=2f(j)-1\;.
</math>
- यदि लोगों की प्रारंभिक संख्या विषम थी, तो हम सर्कल के चारों ओर पहली बार के अंत में व्यक्ति 1 के बारे में सोचते हैं। दोबारा, सर्कल के चारों ओर दूसरी बार, नए 2 व्यक्ति की मृत्यु हो जाती है, फिर नए 4 वें व्यक्ति आदि। इस मामले में, स्थिति x में व्यक्ति मूल रूप से 2x + 1 की स्थिति में था। इससे हमें पुनरावृत्ति होती है : <math> f(2j+1)=2f(j)+1\;.</math>