مسئله ژوزفوس

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

مساله ژوزفوس ( یا جایگشت ژوزفوس) یک مساله نظری درعلوم کامپیوترو ریاضیات است. افرادی را درنظر بگیرید که دایره وار ایستاده‌اند و منتظر اعدام هستند. بعد از آنکه اولین نفر اعدام می شود، تعداد مشخصی از افراد رد شده و یک نفر دیگر اعدام می شود. سپس دوباره به همان تعداد، افراد پرش شده و نفر بعد کشته می شود. این فرایند حذف، دور دایره ( که با برداشتن افراد کشته شده کوچک و کوچکتر می گردد)ادامه می یابد تا زمانی که تنها یک نفر باقی می ماند که آزاد می شود. مطلوب، یافتن جایگاهی در دایره اولیه است که شما با قرار گرفتن در آنجا نجات خواهید یافت.

تاریخچه[ویرایش]

این مساله منتسب به یوسفوس فلاویوس یک تاریخدان یهودی قرن اول میلادی است. آنگونه که داستان می گوید، او و ۴۰ سرباز همراه وی در یک غار زندانی شده‌اند که توسط رومی‌ها محاصره شده است. آنها خودکشی را بر اسیر شدن ترجیح می دهند و تصمیم می گیرند که یک دایره را تشکیل داده و سه تا سه تا خود را بکشند. چون ژوزفوس نمی‌خواهد کشته شود، و می تواند مکان امن دور دایره را پیدا کند با یکی از همراهانش زنده می ماند و به رومیها که آنها را دستگیر می کنند، می پیوندد. (تنها جمله ای که ژوزفوس بعداً گفت این بود که با خوش شانسی یا به یاری لطف خدا او و فرد دیگری باقی‌ماندند و تسلیم رومی‌ها شدند)

راه حل[ویرایش]

ما این مساله را درحالتی حل میکنیم که افراد دوتا دوتا کشته شوند:k=۲.(برای حالت کلی تر یک راه حل نشان خواهیم داد). راه حل را به صورت روابط بازگشتی ارائه می دهیم. فرض کنید (f(n، مکان نجات یابنده باشد در صورتیکه n تعداد اولیه افراد باشد و (k=۲). در اولین گردش دور دایره، تمام افراد با شماره زوج می میرند. در دومین چرخش، افراد جدید دوم کشته می شوند و در دور بعدی افراد جدید چهارم و الی آخر .

اگر تعداد افراد اولیه زوج باشد، آنگاه فردی که در دور دوم در مکان x قرار گرفته است ابتدا در مکان ۲x-۱ بوده است. بنابراین فردی که در مکان(f(n قرار دارد، ابتدا در مکان ۲f(n)-۱ بوده است. این ایده چنین رابطه بازگشتی را به ما میدهد:

f(۲n)=۲f(n)-۱

اگر تعداد افراد اولیه فرد باشد، آنگاه فرد شماره یک در اولین دور کشته خواهد شد. دوباره در دور دوم، افراد زوج جدید کشته خواهند شد. و در دور بعدی افراد چهارم جدید. این ایده نیز به چینن رابطه ای بازگشتی ای منجر می گردد: f(۲n+۱)=۲f(n)+۱

وقتی مقادیر n و (f(n را جدول بندی کنیم چنین الگویی را مشاهده میکنیم:

n ۱ ۲ ۳ ۴ ۵ ۶ ۷ ۸ ۹ ۱۰ ۱۱ ۱۲ ۱۳ ۱۴ ۱۵ ۱۶

f(n) ۱ ۱ ۳ ۱ ۳ ۵ ۷ ۱ ۳ ۵ ۷ ۹ ۱۱ ۱۳ ۱۵ ۱

این الگو نشان می دهد که (f(n یک دنباله فرد صعودی است که از f(n)=۱ شروع می شود؛ وقتی که اندیس n توانی از ۲ باشد. بنابراین اگر m و l را به گونه ای انتخاب کنیم که  n=2^m+l و 0\leq l<2^m باشد و آنگاه f(n)=۲l+۱. این واضح است که مقادیر در جدول این معادله را ارضا میکنند. اما ریاضیات نیازمند اثبات قطعی است. در زیر ما اثباتی را از طریق استقرا ارائه میکنیم.

قضیه: اگرn = ۲m + l و0\leq l<2^m، آنگاه f(n)=۲l+۱

اثبات: ما از استقرای ریاضی قوی روی n استفاده می کنیم. پایه n=۱ است که درست است.ما nهای فرد و زوج را جداگانه بررسی می نماییم. اگر n زوج باشد، آنگاه ماl_1 وm_1 را انتخاب میکنیم به گونه ای کهشکست در تجزیه (خطای lexing): n/2 = ۲^{m_1}+l_۱

و شکست در تجزیه (خطای lexing): 0\leq l_1 <2^{m_۱}

. توجه داشته باشید که شکست در تجزیه (خطای lexing): l_1=\frac{۱}{2} .داریم

شکست در تجزیه (خطای lexing): f(n)=2f(\frac{n}{۲})-1=۲(۲l_۱+۱)-۱=۲l+۱


که تساوی دوم از فرض استقرا به دست می آید.

حال اگر n فرد باشد ماm_1 وl_1 را به گونه ای انتخاب می کنیم کهشکست در تجزیه (خطای lexing): \frac{n-1}{2} = ۲^{m_۱}+l_۱

و شکست در تجزیه (خطای lexing): 0\leq l_1 <2^{m_۱}

. توجه داشته باشید که l_1=\frac{l}{2}.داریم شکست در تجزیه (خطای lexing): f(n) = 2f(\frac {n-1}{۲}) + ۱ = ۲((۲l_1) + ۱) + ۱ = ۲l + ۱ که تساوی دوم از فرض استقرا به دست می آید. و اثبات کامل می شود.
ظریف‌ترین شکل جواب نمایش دودویی n را دربرمی گیرد که توسط "آرمین شمس براق" دانشجوی دانشگاه مشهد پیشنهاد شده و مورد توجه طراحان الگوریتم برجسته دنیا قرار گرفته است : اگر n را بصورت باینری بنویسیم و شماره فردی گه زنده می ماند را برابر Jn بگیریم، و n را یک بیت شیفت دورانی دهیم Jn به دست می‌آید.

n=۱۰۰ = ۱۱۰۰۱۰۰

پس از یک شیفت دورانی داریم Jn=۱۰۰۱۰۰۱=۷۳

ساده‌ترین راه برای حل کلی این مساله استفاده از برنامه نویسی پویا است که به ما چنین رابطه بازگشتی ای را میدهد.

f(n،k)=(f(n-۱،k)+k) mod n، f(۱،k)=۰

که بدیهی است وقتی که ببینیم چگونه عدد نجات یابنده عوض می‌شود وقتی که n-۱به nتغییر می کند، چنین روشی از نظر پیچیدگی زمانی از (O(nاست، اما برای k کوچک و n بزرگ روش دیگری وجود دارد. روش دوم هم از برنامه نویسی پویا استفاده می کند؛ اما از (O(klgn است.

انواع[ویرایش]

بر اساس ریاضیات پیوسته ژوزفوس همدستی دارد. مساله یافتن مکان‌های دو نجات یابنده است(نقشه باید نجات یافتن هردو را تضمین نماید)

ادبیات[ویرایش]

گراهام گرین، دو رمان مرد دهم و دکتر فیشر ژنوی را بر اساس این مسئله ریاضی نگاشته است.

منابع[ویرایش]

۱-توماس کرمن، چارلز لیزرسون، رونالد ریوست، کلیفورد استین، مقدمه ای بر الگوریتم ها، چاپ دوم، ۲۰۰۱، شابک ۰-۲۶۲-۰۳۲۹۳-۷، فصل ۱۴، بحثی در مورد ساختمان داده ها، صفحه ۱۱۸

  • مشارکت‌کنندگان ویکی‌پدیا، «Josephus problem»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۶ آوريل ۲۰۱۱).

پیوند به بیرون[ویرایش]