مساله ژوزفوس
ارسال شده: پنجشنبه ۳۰ مهر ۱۳۸۸, ۱:۴۷ ق.ظ
مساله ژوزفوس ( يا جايگشت ژوزفوس) يك مساله نظري درعلوم كامپيوترو رياضيات است. افرادي را درنظر بگيريد كه دايره وار ايستاده اند و منتظر اعدام هستند. بعد از آنكه اولين نفر اعدام مي شود، تعداد مشخصي از افراد رد شده و يك نفر ديگر اعدام مي شود. سپس دوباره به همان تعداد،افراد پرش شده و نفر بعد كشته مي شود. اين فرآيند حذف، دور دايره ( كه با برداشتن افراد كشته شده كوچك و كوچكتر مي گردد)ادامه مي يابد تا زماني كه تنها يك نفر باقي مي ماند كه آزاد مي شود. مطلوب، يافتن جايگاهي در دايره اوليه است كه شما با قرار گرفتن در آنجا نجات خواهيد يافت.
تاريخچه
اين مساله منتسب به فلاويوس ژوزفوس يك تاريخدان يهودي قرن اول ميلادي است. آنگونه كه داستان مي گويد، او و 40 سرباز همراه وي در يك غار زنداني شده اند كه توسط رومي ها محاصره شده است. آنها خودكشي را بر اسير شدن ترجيح مي دهند و تصميم مي گيرند كه يك دايره را تشكيل داده و سه تا سه تا خود را بكشند. چون ژوزفوس نمي خواهد كشته شود، و مي تواند مكان امن دور دايره را پيدا كند با يكي از همراهانش زنده مي ماند و به روميها كه آنها را دستگير مي كنند، مي پيوندد.(تنها جمله اي كه ژوزفوس بعدا گفت، اين بود كه با خوش شانسي يا به ياري لطف خدا او و فرد ديگري باقي ماندند و تسليم رومي ها شدند)
راه حل
ما مساله را درحالتي حل ميكنيم كه افراد دوتا دوتا كشته شوند:k=2.(براي حالت كلي تر يك راه حل نشان خواهيم داد). راه حل را به صورت روابط بازگشتي ارائه مي دهيم. فرض كنيد (f(n، مكان نجات يابنده باشد در صورتيكه n تعداد اوليه افراد باشد و (k=2). در اولين گردش دور دايره، تمام افراد با شماره زوج مي ميرند. در دومين چرخش، افراد جديد دوم كشته مي شوند و در دور بعدي افراد جديد چهارم و الي آخر .
اگر تعداد افراد اوليه زوج باشد، آنگاه فردي كه در دور دوم در مكان x قرار گرفته است ابتدا در مكان 2x-1 بوده است. بنابراين فردي كه در مكان(f(n قرار دارد، ابتدا در مكان 2f(n)-1 بوده است. اين ايده چنين رابطه بازگشتي را به ما ميدهد:
f(2n)=2f(n)-1
اگر تعداد افراد اوليه فرد باشد، آنگاه فرد شماره يك در اولين دور كشته خواهد شد. دوباره در دور دوم، افراد زوج جديد كشته خواهند شد. و در دور بعدي افراد چهارم جديد. اين ايده نيز به چينن رابطه اي بازگشتي اي منجر مي گردد: f(2n+1)=2f(n)+1
وقتي مقادير n و (f(n را جدول بندي كنيم چنين الگويي را مشاهده ميكنيم:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
تاريخچه
اين مساله منتسب به فلاويوس ژوزفوس يك تاريخدان يهودي قرن اول ميلادي است. آنگونه كه داستان مي گويد، او و 40 سرباز همراه وي در يك غار زنداني شده اند كه توسط رومي ها محاصره شده است. آنها خودكشي را بر اسير شدن ترجيح مي دهند و تصميم مي گيرند كه يك دايره را تشكيل داده و سه تا سه تا خود را بكشند. چون ژوزفوس نمي خواهد كشته شود، و مي تواند مكان امن دور دايره را پيدا كند با يكي از همراهانش زنده مي ماند و به روميها كه آنها را دستگير مي كنند، مي پيوندد.(تنها جمله اي كه ژوزفوس بعدا گفت، اين بود كه با خوش شانسي يا به ياري لطف خدا او و فرد ديگري باقي ماندند و تسليم رومي ها شدند)
راه حل
ما مساله را درحالتي حل ميكنيم كه افراد دوتا دوتا كشته شوند:k=2.(براي حالت كلي تر يك راه حل نشان خواهيم داد). راه حل را به صورت روابط بازگشتي ارائه مي دهيم. فرض كنيد (f(n، مكان نجات يابنده باشد در صورتيكه n تعداد اوليه افراد باشد و (k=2). در اولين گردش دور دايره، تمام افراد با شماره زوج مي ميرند. در دومين چرخش، افراد جديد دوم كشته مي شوند و در دور بعدي افراد جديد چهارم و الي آخر .
اگر تعداد افراد اوليه زوج باشد، آنگاه فردي كه در دور دوم در مكان x قرار گرفته است ابتدا در مكان 2x-1 بوده است. بنابراين فردي كه در مكان(f(n قرار دارد، ابتدا در مكان 2f(n)-1 بوده است. اين ايده چنين رابطه بازگشتي را به ما ميدهد:
f(2n)=2f(n)-1
اگر تعداد افراد اوليه فرد باشد، آنگاه فرد شماره يك در اولين دور كشته خواهد شد. دوباره در دور دوم، افراد زوج جديد كشته خواهند شد. و در دور بعدي افراد چهارم جديد. اين ايده نيز به چينن رابطه اي بازگشتي اي منجر مي گردد: f(2n+1)=2f(n)+1
وقتي مقادير n و (f(n را جدول بندي كنيم چنين الگويي را مشاهده ميكنيم:
n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1