ژوزفوس

[armiya]

باسلام :
سوال من اینه که الگوریتم ژوزفوس رو تقریبا اونهایی که ساختمان داده خونند می دونند چیه ولی من یه بار توضییح میدم بعد سوالم رو میپرسم :
ببیند n نفر دور دایره ای قرار دارند حالا این n میتونه 2k+1 یا 2k باشه قرار که یک در میان خورده بشه و اخرین عددی که می مونه چیه ؟؟؟؟
مثلا اگر n=4 باشه یعنی 1,2,3,4 اول 2 بعد 4 بعد 3 اخرین که می مونه میشه 1
حالا سوالم :
برای اینکه n های بزرگ چه روشی وجود داره مثلا برای n=1000 یا n=789 یا .........
ببیند خودم فکر کردم برای این سوال رابطه بازگشتی داره ولی وقت گیره یعنی باید یکی یکی عدد هارو حساب کنید من میخوام برای n=1000 حداکثر زیر 3 دقیقه به جواب برسه

[nodet07]

به ازای 2 به جواب 1 هستش !!! (بسيار ساده اثبات ميشود )

و اگر n = 2^n+x
جواب = 2x+1

مثال : 40 برابر 2 به توان 5 + 8 هستش که جواب میشه 2*8 +1 = 17

[qwerty11]

با تشکر از دوست بالایی

بعضی وقت ها سرچ تو اینترنت راحت ترین و کم هزینه ترین راه برای پیدا کردن جواب سوالمون هستش !

http://fa.wikipedia.org/wiki/%D9%85%...81%D9%88%D8%B3

http://en.wikipedia.org/wiki/Josephus_problem

[armiya]

یه سوال اگه اولی 3 خورده بشه چی یعنی اگه این مسله به ازای 1 3 نفر یعنی از 3 شروع کنیم بعد یک در میان خورده بشه اونوقت به ازای 2200 میشه چقدر ؟؟؟؟

[armiya]

از دوستانکسی نیست جواب بده ؟؟؟؟؟؟؟//

[Salar Ashgi]

ببینید دوست عزیز ، اولا رابطه بازگشتی این الگوریتم زیادی Order بالایی ندارد ؛ با این حال روش بهینه و

سریع واسه حل مساله استفاده از تجزیه باینری عدد n میباشد که توسط دوست عزیز qwerty11 بیان شد ./

ظریف ترین شکل جواب نمایش دودویی n را دربرمی گیرد که توسط "آرمین شمس براق" دانشجوی دانشگاه مشهد پیشنهاد شده و مورد توجه طراحان الگوریتم برجسته دنیا قرار گرفته است : اگر n را بصورت باینری بنویسیم و شماره فردی گه زنده می ماند را برابر Jn بگیریم , و n را یک بیت شیفت دورانی دهیم Jn به دست می‌آید.
n=۱۰۰ = ۱۱۰۰۱۰۰
پس از یک شیفت دورانی داریم Jn=۱۰۰۱۰۰۱=۷۳

موفق و پیروز باشید ./