پرش به محتویات

مسئله یوسف

صورت مسئله

اعداد طبیعی $n$ و $k$ به ما داده شده‌اند. تمام اعداد طبیعی از ۱ تا $n$ در یک دایره نوشته شده‌اند. ابتدا، با شروع از عدد اول، $k$-امین عدد را شمرده و آن را حذف می‌کنیم. سپس با شروع از عدد بعدی، دوباره $k$ عدد شمرده شده و $k$-امین عدد حذف می‌شود و این روند ادامه می‌یابد. این فرآیند زمانی متوقف می‌شود که تنها یک عدد باقی بماند. مطلوب است که آخرین عدد باقی‌مانده را پیدا کنیم.

این مسئله توسط یوسف فلاویوس در قرن اول میلادی مطرح شد (هرچند در فرمول‌بندی محدودتری: برای $k = 2$).

این مسئله را می‌توان با شبیه‌سازی روند حل کرد. شبیه‌سازی با روش brute force با پیچیدگی $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}$ پاسخ دایره باقی‌مانده خواهد بود اگر شمارش را از ۰ شروع کنیم، اما چون در واقع از $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» مراجعه کنید).