پیاده سازی مسئله ژوزفیوس (اسیران رومی)

[dadafarid]

با سلام و درود ...
از اساتید کسی در رابطه با پیاده سازی مسئله ژوزفیوس (اسیران رومی) چیزی میدونه؟!
اصلا نمیدونم کارش چیه !!! و چطوری باید پیاده سازی بشه!!! (انگلیسیه ژوزفیوس چطوریه ! هر جور مینویسم گوگل چیزی نمیاره:بامزه:)
هر چی تو نت و انجمن سرچ کردم چیزی پیدا نکردم !!!
ممنون میشم اگه راهنمایی کنید....
با تشکر .....................

[MRHagh]

این یک مسئله قدیمی و گونه ای از مسئله باستانی , منتسب به " فلاویوس ژوزفوس " تاریخ دان یهودی است .
او در زمان جنگ رومیان و یهودیان یکی از 41 یهودی بود که توسط رومیان در یک غار محاصره شدند و به جای تسلیم , همه تصمیم گرفتند به این شکل خودکشی کنند که در یک دایره بنشینند و با شروع از نفر اول هر بار (بصورت یک در میان) نفر دوم زنده ها خود را بکشد . ولی ژوزفوس با محاسبه , در مکانی نشست که آخرین فردی باشد که خودش را میکشد (بنابراین کسی متوجه خیانتش نمیشد , که او خود را نمیکشد و تسلیم میشود)
مسئله در حالت کلی این است که اگر n نفر با شماره های 1 تا n دور دایره ای قرار بگیرند و با شروع از شماره 1 و در جهت ساعت گرد هر بار دومین (kامین) نفر خودش را بکشد , آخرین نفر چه شماره ای دارد ؟!!
مثلا برای n=10 به تر تیب افراد 9,1,7,3,10,8,6,4,2 خودکشی میکند و 5 زنده میماند .
جواب این مسئله بصورت ریاضی قابل محاسبه است و میتوان جواب را از رابطه بازگشتی به دست آورد ...
را حل ساده آن توسط آقای "آرمین شمس براق" دانشجوی دانشگاه مشهد به صورت زیر پیشنهاد شده و مورد توجه طراحان الگوریتم برجسته دنیا قرار گرفته است :
اگر n را بصورت باینری بنویسیم و شماره فردی گه زنده میماند را برابر Jn بگیریم , و n را یک بیت شیفت دورانی دهیم Jn به دست می آید :
n=100 = 1100100 پس از یک شیف دورانی داریم Jn=1001001=73
بهتر بود سوال خود را در بخش طراحی الگوریتم و ساختمان داده ها مطرح میکردید .
موفق باشید ...

[Sepidar]

شيفت دوراني؟

[MRHagh]

شيفت دوراني؟
همانطورکه میدانید ,هر عمل شیف به چپ , بیت ها را یک موقعیت به طرف چپ جابجا میکند (قابل ذکر است که با این عمل , مقدار عدد اولیه دو برابر میشود). روش کار به این صورت است که به تعداد بیتهایی که از سمت چپ و طی عمل شیفت جابجا میکنیم , از سمت راست به همان تعداد صفر وارد میکنیم (علت دو برابر شدن عدد هم همین است) . با توجه به این موضوع , در شیفت دورانی (Revolving) وقتی بیتی طی عمل شیفت از سمت چپ خارج میشود , از سمت راست دوباره وارد میشود .
مثال زیر را توجه کنید :


11001000 <------شیفت به چپ ساده ---- 1100100
1001001 <---- شیفت به چپ دورانی ---- 1100100


(در پست قبلی من یک اشتباه تایپی وجود داشت ... !!! n = 100 = 1100100 که اصلاح شده )

[Sepidar]

حدس زدن معنی شیفت دورانی مشکل نبود. مشکل مثال شما بود که تصحیح کردید. متشکرم.