مسئله ژوزفوس ( یا جایگشت ژوزفوس ) یک مسئله نظری درعلوم کامپیوترو ریاضیات است. افرادی را در نظر بگیرید که دایره وار ایستاده اند و منتظر اعدام هستند. بعد از آنکه اولین نفر اعدام می شود، تعداد مشخصی از افراد رد شده و یک نفر دیگر اعدام می شود. سپس دوباره به همان تعداد افراد پرش شده و نفر بعد کشته می شود. این فرایند حذف، دور دایره ( که با برداشتن افراد کشته شده کوچک و کوچکتر می گردد ) ادامه می یابد تا زمانی که تنها یک نفر باقی می ماند که آزاد می شود. مطلوب، یافتن جایگاهی در دایره اولیه است که شما با قرار گرفتن در آنجا نجات خواهید یافت.
این مسئله منتسب به یوسفوس فلاویوس یک تاریخدان یهودی قرن اول میلادی است. آنگونه که داستان می گوید، او و ۴۰ سرباز همراه وی در یک غار زندانی شده اند که توسط رومی ها محاصره شده است. آن ها خودکشی را بر اسیر شدن ترجیح می دهند و تصمیم می گیرند که یک دایره را تشکیل داده و سه تا سه تا خود را بکشند. چون ژوزفوس نمی خواهد کشته شود، و می تواند مکان امن دور دایره را پیدا کند با یکی از همراهانش زنده می ماند و به رومی ها که آن ها را دستگیر می کنند، می پیوندد. ( تنها جمله ای که ژوزفوس بعداً گفت این بود که با خوش شانسی یا به یاری لطف خدا او و فرد دیگری باقی ماندند و تسلیم رومی ها شدند )
ما این مسئله را در حالتی حل می کنیم که افراد دوتا دوتا کشته شوند: k = 2 . ( برای حالت کلی تر یک راه حل نشان خواهیم داد ) . راه حل را به صورت روابط بازگشتی ارائه می دهیم. فرض کنید f ( n ) ، مکان نجات یابنده باشد در صورتی که n تعداد اولیه افراد باشد و ( k = 2 ) . در اولین گردش دور دایره، تمام افراد با شماره زوج می میرند. در دومین چرخش، افراد جدید دوم کشته می شوند و در دور بعدی افراد جدید چهارم و الی آخر .
اگر تعداد افراد اولیه زوج باشد، آنگاه فردی که در دور دوم در مکان x قرار گرفته است ابتدا در مکان 2 x − 1 بوده است. بنابراین فردی که در مکان f ( n ) قرار دارد، ابتدا در مکان 2 f ( n ) − 1 بوده است. این ایده چنین رابطه بازگشتی را به ما می دهد:
اگر تعداد افراد اولیه فرد باشد، آنگاه فرد شماره یک در اولین دور کشته خواهد شد. دوباره در دور دوم، افراد زوج جدید کشته خواهند شد. و در دور بعدی افراد چهارم جدید. این ایده نیز به چینن رابطه ای بازگشتی ای منجر می گردد:
وقتی مقادیر n و f ( n ) را جدول بندی کنیم چنین الگویی را مشاهده می کنیم:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین مسئله منتسب به یوسفوس فلاویوس یک تاریخدان یهودی قرن اول میلادی است. آنگونه که داستان می گوید، او و ۴۰ سرباز همراه وی در یک غار زندانی شده اند که توسط رومی ها محاصره شده است. آن ها خودکشی را بر اسیر شدن ترجیح می دهند و تصمیم می گیرند که یک دایره را تشکیل داده و سه تا سه تا خود را بکشند. چون ژوزفوس نمی خواهد کشته شود، و می تواند مکان امن دور دایره را پیدا کند با یکی از همراهانش زنده می ماند و به رومی ها که آن ها را دستگیر می کنند، می پیوندد. ( تنها جمله ای که ژوزفوس بعداً گفت این بود که با خوش شانسی یا به یاری لطف خدا او و فرد دیگری باقی ماندند و تسلیم رومی ها شدند )
ما این مسئله را در حالتی حل می کنیم که افراد دوتا دوتا کشته شوند: k = 2 . ( برای حالت کلی تر یک راه حل نشان خواهیم داد ) . راه حل را به صورت روابط بازگشتی ارائه می دهیم. فرض کنید f ( n ) ، مکان نجات یابنده باشد در صورتی که n تعداد اولیه افراد باشد و ( k = 2 ) . در اولین گردش دور دایره، تمام افراد با شماره زوج می میرند. در دومین چرخش، افراد جدید دوم کشته می شوند و در دور بعدی افراد جدید چهارم و الی آخر .
اگر تعداد افراد اولیه زوج باشد، آنگاه فردی که در دور دوم در مکان x قرار گرفته است ابتدا در مکان 2 x − 1 بوده است. بنابراین فردی که در مکان f ( n ) قرار دارد، ابتدا در مکان 2 f ( n ) − 1 بوده است. این ایده چنین رابطه بازگشتی را به ما می دهد:
اگر تعداد افراد اولیه فرد باشد، آنگاه فرد شماره یک در اولین دور کشته خواهد شد. دوباره در دور دوم، افراد زوج جدید کشته خواهند شد. و در دور بعدی افراد چهارم جدید. این ایده نیز به چینن رابطه ای بازگشتی ای منجر می گردد:
وقتی مقادیر n و f ( n ) را جدول بندی کنیم چنین الگویی را مشاهده می کنیم:
wiki: مسئله ژوزفوس