مسئله ژوزفوس کیست؟ توضیح بده.
مسئله ژوزفوس ( یا جایگشت ژوزفوس) یک مسئله نظری درعلوم کامپیوترو ریاضیات است.افرادی را در نظر بگیرید که دایره وار ایستاده‌اند و منتظر اعدام هستند. بعد از آنکه اولین نفر اعدام می‌شود، تعداد مشخصی از افراد رد شده و یک نفر دیگر اعدام می‌شود. سپس دوباره به همان تعداد افراد پرش شده و نفر بعد کشته می‌شود. این فرایند حذف، دور دایره (که با برداشتن افراد کشته شده کوچک و کوچکتر می‌گردد) ادامه می‌یابد تا زمانی که تنها یک نفر باقی می‌ماند که آزاد می‌شود.مطلوب، یافتن جایگاهی در دایره اولیه است که شما با قرار گرفتن در آنجا نجات خواهید یافت.تاریخچه.این مسئله منتسب به یوسفوس فلاویوس یک تاریخدان یهودی قرن اول میلادی است. آنگونه که داستان می‌گوید، او و ۴۰ سرباز همراه وی در یک غار زندانی شده‌اند که توسط رومی‌ها محاصره شده‌است. آن‌ها خودکشی را بر اسیر شدن ترجیح می‌دهند و تصمیم می‌گیرند که یک دایره را تشکیل داده و سه تا سه تا خود را بکشند. چون ژوزفوس نمی‌خواهد کشته شود، و می‌تواند مکان امن دور دایره را پیدا کند با یکی از همراهانش زنده می‌ماند و به رومی‌ها که آن‌ها را دستگیر می‌کنند، می پیوندد. (تنها جمله‌ای که ژوزفوس بعداً گفت این بود که با خوش شانسی یا به یاری لطف خدا او و فرد دیگری باقی‌ماندند و تسلیم رومی‌ها شدند)راه حل.ما این مسئله را در حالتی حل می‌کنیم که افراد دوتا دوتا کشته شوند:formula_1.(برای حالت کلی تر یک راه حل نشان خواهیم داد). راه حل را به صورت روابط بازگشتی ارائه می‌دهیم. فرض کنید formula_2 ، مکان نجات یابنده باشد در صورتی‌که formula_3 تعداد اولیه افراد باشد و (formula_1). در اولین گردش دور دایره، تمام افراد با شماره زوج می‌میرند. در دومین چرخش، افراد جدید دوم کشته می‌شوند و در دور بعدی افراد جدید چهارم و الی آخر .اگر تعداد افراد اولیه زوج باشد، آنگاه فردی که در دور دوم در مکان formula_5 قرار گرفته‌است ابتدا در مکان formula_6 بوده‌است. بنابراین فردی که در مکان formula_2 قرار دارد، ابتدا در مکان formula_8 بوده‌است. این ایده چنین رابطه بازگشتی را به ما می‌دهد:اگر تعداد افراد اولیه فرد باشد، آنگاه فرد شماره یک در اولین دور کشته خواهد شد. دوباره در دور دوم، افراد زوج جدید کشته خواهند شد. و در دور بعدی افراد چهارم جدید. این ایده نیز به چینن رابطه‌ای بازگشتی ای منجر می‌گردد:وقتی مقادیر formula_3 و formula_2 را جدول بندی کنیم چنین الگویی را مشاهده می‌کنیم:این الگو نشان می‌دهد که formula_2 یک دنباله فرد صعودی است که از formula_14 شروع می‌شود؛ وقتی که اندیس formula_3 توانی از 2 باشد. بنابراین اگر formula_16 و formula_17 را به گونه‌ای انتخاب کنیم که formula_18 و formula_19 باشد و آنگاه formula_20 این واضح است که مقادیر در جدول این معادله را ارضا می‌کنند. اما ریاضیات نیازمند اثبات قطعی است. در زیر ما اثباتی را از طریق استقرا ارائه می‌کنیم.قضیه: اگر formula_21 و formula_19، آنگاه formula_20اثبات: ما از استقرای ریاضی قوی روی n استفاده می‌کنیم. پایه n=۱ است که درست است. ما formula_3 های فرد و زوج را جداگانه بررسی می نماییم.اگر formula_3 زوج باشد، آنگاه ما formula_26 و formula_27 را انتخاب می‌کنیم به گونه‌ای کهformula_28 و formula_29. توجه داشته باشید که formula_30. داریمformula_31که تساوی دوم از فرض استقرا به دست می‌آید.حال اگر n فرد باشد ماformula_27 و formula_26 را به گونه‌ای انتخاب می‌کنیم کهformula_34 و formula_29. توجه داشته باشید که formula_36. داریم formula_37 که تساوی دوم از فرض استقرا به دست می‌آید. و اثبات کامل می‌شود.ظریف‌ترین شکل جواب نمایش دودویی n را دربرمی گیرد: اگر formula_3 را به صورت باینری بنویسیم و شماره فردی گه زنده می‌ماند را برابر formula_39 بگیریم، و n را یک بیت شیفت دورانی دهیم formula_39 به دست می‌آید.formula_41پس از یک شیفت دورانی داریم:formula_42ساده‌ترین راه برای حل کلی این مسئله استفاده از برنامه نویسی پویا است که به ما چنین رابطه بازگشتی ای را می‌دهد.formula_43که بدیهی است وقتی که ببینیم چگونه عدد نجات یابنده عوض می‌شود وقتی که formula_44 به formula_3 تغییر می‌کند، چنین روشی از نظر پیچیدگی زمانی از formula_46 است، اما برای formula_47 کوچک و formula_3 بزرگ روش دیگری وجود دارد. روش دوم هم از برنامه‌نویسی پویا استفاده می‌کند؛ اما از formula_49 است.انواع.بر اساس ریاضیات پیوسته ژوزفوس همدستی دارد. مسئله یافتن مکان‌های دو نجات یابنده است(نقشه باید نجات یافتن هردو را تضمین نماید)ادبیات.گراهام گرین، دو رمان مرد دهم و دکتر فیشر ژنوی را بر اساس این مسئله ریاضی نگاشته است.منابع.۱-توماس کرمن، چارلز لیزرسون، رونالد ریوست، کلیفورد استین، مقدمه‌ای بر الگوریتم ها، چاپ دوم، ۲۰۰۱، شابک ۰-۲۶۲-۰۳۲۹۳-۷، فصل ۱۴، بحثی در مورد ساختمان داده‌ها، صفحه ۱۱۸