জোসেফাস সমস্যা#
সমস্যার বিবৃতি#
আমাদের স্বাভাবিক সংখ্যা $n$ এবং $k$ দেওয়া আছে। $1$ থেকে $n$ পর্যন্ত সকল স্বাভাবিক সংখ্যা একটি বৃত্তে লেখা আছে। প্রথমে, প্রথম সংখ্যা থেকে শুরু করে $k$-তম সংখ্যাটি গণনা করে মুছে ফেলা হয়। তারপর পরেরটি থেকে শুরু করে $k$টি সংখ্যা গণনা করা হয় এবং আবার $k$-তম সংখ্যাটি মুছে ফেলা হয়, এভাবে চলতে থাকে। যখন একটি মাত্র সংখ্যা অবশিষ্ট থাকে তখন প্রক্রিয়াটি থামে। শেষ সংখ্যাটি বের করতে হবে।
এই সমস্যাটি প্রথম শতাব্দীতে ফ্ল্যাভিয়াস জোসেফাস প্রস্তাব করেছিলেন (যদিও কিছুটা সংকীর্ণ আকারে: $k = 2$ এর জন্য)।
এই সমস্যাটি প্রক্রিয়াটি মডেলিং করে সমাধান করা যায়। ব্রুট ফোর্স মডেলিং $O(n^{2})$ সময়ে কাজ করবে। একটি সেগমেন্ট ট্রি ব্যবহার করে, আমরা এটিকে $O(n \log n)$ এ উন্নত করতে পারি। তবে আমরা আরও ভালো কিছু চাই।
$O(n)$ সমাধানের মডেলিং#
আমরা $J_{n, k}$ সমস্যার উত্তরকে আগের সমস্যাগুলোর সমাধানের মাধ্যমে প্রকাশ করার একটি প্যাটার্ন খুঁজে বের করার চেষ্টা করব।
ব্রুট ফোর্স মডেলিং ব্যবহার করে আমরা একটি মানের টেবিল তৈরি করতে পারি, উদাহরণস্বরূপ, নিচেরটি:
$$\begin{array}{ccccccccccc} n\setminus k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 & 2 & 1 \\ 3 & 3 & 3 & 2 & 2 & 1 & 1 & 3 & 3 & 2 & 2 \\ 4 & 4 & 1 & 1 & 2 & 2 & 3 & 2 & 3 & 3 & 4 \\ 5 & 5 & 3 & 4 & 1 & 2 & 4 & 4 & 1 & 2 & 4 \\ 6 & 6 & 5 & 1 & 5 & 1 & 4 & 5 & 3 & 5 & 2 \\ 7 & 7 & 7 & 4 & 2 & 6 & 3 & 5 & 4 & 7 & 5 \\ 8 & 8 & 1 & 7 & 6 & 3 & 1 & 4 & 4 & 8 & 7 \\ 9 & 9 & 3 & 1 & 1 & 8 & 7 & 2 & 3 & 8 & 8 \\ 10 & 10 & 5 & 4 & 5 & 3 & 3 & 9 & 1 & 7 & 8 \\ \end{array}$$এবং এখানে আমরা স্পষ্টভাবে নিম্নলিখিত প্যাটার্নটি দেখতে পাই:
$$J_{n,k} = \left( (J_{n-1,k} + k - 1) \bmod n \right) + 1$$$$J_{1,k} = 1$$এখানে, ১-ইনডেক্সিং সূত্রটিকে কিছুটা জটিল করে তোলে; আপনি যদি এর পরিবর্তে অবস্থানগুলোকে ০ থেকে সংখ্যায়ন করেন, তাহলে একটি অত্যন্ত সুন্দর সূত্র পাওয়া যায়:
$$J_{n,k} = (J_{n-1,k} + k) \bmod n$$সুতরাং, আমরা জোসেফাস সমস্যার একটি সমাধান পেলাম, যা $O(n)$ অপারেশনে কাজ করে।
ইমপ্লিমেন্টেশন#
সরল রিকার্সিভ ইমপ্লিমেন্টেশন (১-ইনডেক্সিং-এ)
int josephus(int n, int k) {
return n > 1 ? (josephus(n-1, k) + k - 1) % n + 1 : 1;
}নন-রিকার্সিভ রূপ :
int josephus(int n, int k) {
int res = 0;
for (int i = 1; i <= n; ++i)
res = (res + k) % i;
return res + 1;
}এই সূত্রটি বিশ্লেষণমূলকভাবেও বের করা যায়। আবারও এখানে আমরা ০-ইনডেক্সিং ধরে নিচ্ছি। প্রথম সংখ্যাটি মুছে ফেলার পর, আমাদের কাছে $n-1$ টি সংখ্যা অবশিষ্ট থাকে। যখন আমরা প্রক্রিয়াটি পুনরাবৃত্তি করি, আমরা সেই সংখ্যা দিয়ে শুরু করব যার মূল ইনডেক্স ছিল $k \bmod n$। $J_{n-1, k}$ হবে অবশিষ্ট বৃত্তের জন্য উত্তর, যদি আমরা $0$ থেকে গণনা শুরু করি, কিন্তু যেহেতু আমরা আসলে $k$ থেকে শুরু করি তাই $J_{n, k} = (J_{n-1,k} + k) \ \bmod n$।
$O(k \log n)$ সমাধানের মডেলিং#
তুলনামূলকভাবে ছোট $k$ এর জন্য আমরা উপরের $O(n)$ রিকার্সিভ সমাধানের চেয়ে আরও ভালো সমাধান বের করতে পারি। যদি $k$, $n$ এর তুলনায় অনেক ছোট হয়, তাহলে আমরা লুপ না করেই একবারে একাধিক সংখ্যা ($\lfloor \frac{n}{k} \rfloor$ টি) মুছে ফেলতে পারি। এরপর আমাদের কাছে $n - \lfloor \frac{n}{k} \rfloor$ টি সংখ্যা অবশিষ্ট থাকে, এবং আমরা $(\lfloor \frac{n}{k} \rfloor \cdot k)$-তম সংখ্যা থেকে শুরু করি। সুতরাং আমাদের সেই পরিমাণ শিফট করতে হবে। আমরা লক্ষ্য করতে পারি যে $\lfloor \frac{n}{k} \rfloor \cdot k$ আসলে $-n \bmod k$। এবং যেহেতু আমরা প্রতি $k$-তম সংখ্যা সরিয়েছি, তাই ফলাফল ইনডেক্সের আগে আমরা যতগুলো সংখ্যা সরিয়েছি সেগুলো যোগ করতে হবে। যা ফলাফল ইনডেক্সকে $k - 1$ দিয়ে ভাগ করে গণনা করা যায়।
এছাড়াও, আমাদের সেই ক্ষেত্রটি সামলাতে হবে যখন $n$, $k$ এর চেয়ে ছোট হয়ে যায়। এই ক্ষেত্রে, উপরের অপটিমাইজেশন একটি অসীম লুপ সৃষ্টি করবে।
ইমপ্লিমেন্টেশন (সুবিধার জন্য ০-ইনডেক্সিং-এ):
int josephus(int n, int k) {
if (n == 1)
return 0;
if (k == 1)
return n-1;
if (k > n)
return (josephus(n-1, k) + k) % n;
int cnt = n / k;
int res = josephus(n - cnt, k);
res -= n % k;
if (res < 0)
res += n;
else
res += res / (k - 1);
return res;
}এই অ্যালগরিদমের কমপ্লেক্সিটি অনুমান করা যাক। প্রথমেই লক্ষ্য করি যে $n < k$ ক্ষেত্রটি পুরানো সমাধান দিয়ে বিশ্লেষণ করা হয়, যা এই ক্ষেত্রে $O(k)$-তে কাজ করবে। এখন অ্যালগরিদমটি নিজে বিবেচনা করি। প্রকৃতপক্ষে, প্রতিটি ইটারেশনের পরে, $n$ টি সংখ্যার পরিবর্তে আমাদের কাছে $n \left( 1 - \frac{1}{k} \right)$ টি সংখ্যা অবশিষ্ট থাকে, তাই অ্যালগরিদমের মোট ইটারেশন সংখ্যা $x$ মোটামুটিভাবে নিম্নলিখিত সমীকরণ থেকে পাওয়া যায়:
$$ n \left(1 - \frac{1}{k} \right) ^ x = 1, $$উভয় পক্ষে লগারিদম নিলে, আমরা পাই:
$$\ln n + x \ln \left(1 - \frac{1}{k} \right) = 0,$$$$x = - \frac{\ln n}{\ln \left(1 - \frac{1}{k} \right)},$$লগারিদমকে টেইলর সিরিজে বিস্তৃত করে, আমরা একটি আনুমানিক অনুমান পাই:
$$x \approx k \ln n$$সুতরাং, অ্যালগরিদমের কমপ্লেক্সিটি আসলে $O (k \log n)$।
$k = 2$ এর জন্য বিশ্লেষণমূলক সমাধান#
এই বিশেষ ক্ষেত্রে (যেটিতে জোসেফাস ফ্ল্যাভিয়াস এই সমস্যাটি প্রস্তাব করেছিলেন) সমস্যাটি অনেক সহজে সমাধান করা যায়।
জোড় $n$ এর ক্ষেত্রে আমরা পাই যে সকল জোড় সংখ্যা কেটে যাবে, এবং তারপর $\frac{n}{2}$ এর জন্য একটি সমস্যা অবশিষ্ট থাকবে, তখন $n$ এর উত্তর $\frac{n}{2}$ এর উত্তর থেকে ২ দিয়ে গুণ করে ১ বিয়োগ করে পাওয়া যাবে (অবস্থান শিফট করে):
$$ J_{2n, 2} = 2 J_{n, 2} - 1 $$একইভাবে, বিজোড় $n$ এর ক্ষেত্রে, সকল জোড় সংখ্যা কেটে যাবে, তারপর প্রথম সংখ্যাটি, এবং $\frac{n-1}{2}$ এর জন্য সমস্যা অবশিষ্ট থাকবে, এবং অবস্থান শিফটের কথা বিবেচনা করে, আমরা দ্বিতীয় সূত্রটি পাই:
$$J_{2n+1,2} = 2 J_{n, 2} + 1 $$আমরা এই পৌনঃপুনিক নির্ভরশীলতা সরাসরি আমাদের ইমপ্লিমেন্টেশনে ব্যবহার করতে পারি। এই প্যাটার্নটি অন্য একটি রূপে রূপান্তরিত করা যায়: $J_{n, 2}$ সকল বিজোড় সংখ্যার একটি সিকোয়েন্স উপস্থাপন করে, যা $n$ যখনই ২ এর ঘাত হয় তখন এক থেকে “পুনরায় শুরু” হয়। এটি একটি একক সূত্র হিসেবে লেখা যায়:
$$J_{n, 2} = 1 + 2 \left(n-2^{\lfloor \log_2 n \rfloor} \right)$$$k > 2$ এর জন্য বিশ্লেষণমূলক সমাধান#
সমস্যার সরল রূপ এবং এই ও সংশ্লিষ্ট সমস্যাগুলোর উপর বিপুল সংখ্যক প্রবন্ধ থাকা সত্ত্বেও, জোসেফাস সমস্যার একটি সরল বিশ্লেষণমূলক উপস্থাপনা এখনও পাওয়া যায়নি। ছোট $k$ এর জন্য কিছু সূত্র বের করা হয়েছে, কিন্তু আপাতদৃষ্টিতে সেগুলো সবই বাস্তবে প্রয়োগ করা কঠিন (উদাহরণস্বরূপ দেখুন Halbeisen, Hungerbuhler “The Josephus Problem” এবং Odlyzko, Wilf “Functional iteration and the Josephus problem”)।