PDA

View Full Version : حرفه ای: ژوزفوس



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

nodet07
پنج شنبه 07 مرداد 1389, 01:50 صبح
به ازای 2 به جواب 1 هستش !!! (بسيار ساده اثبات ميشود )

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



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

qwerty11
پنج شنبه 07 مرداد 1389, 06:07 صبح
با تشکر از دوست بالایی

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

http://fa.wikipedia.org/wiki/%D9%85%D8%B3%D8%A7%D9%84%D9%87_%DA%98%D9%88%D8%B2% D9%81%D9%88%D8%B3

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

armiya
پنج شنبه 07 مرداد 1389, 13:59 عصر
یه سوال اگه اولی 3 خورده بشه چی یعنی اگه این مسله به ازای 1 3 نفر یعنی از 3 شروع کنیم بعد یک در میان خورده بشه اونوقت به ازای 2200 میشه چقدر ؟؟؟؟

armiya
دوشنبه 11 مرداد 1389, 22:09 عصر
از دوستانکسی نیست جواب بده ؟؟؟؟؟؟؟//

Salar Ashgi
دوشنبه 11 مرداد 1389, 23:06 عصر
ببینید دوست عزیز ، اولا رابطه بازگشتی این الگوریتم زیادی Order بالایی ندارد ؛ با این حال روش بهینه و

سریع واسه حل مساله استفاده از تجزیه باینری عدد n میباشد که توسط دوست عزیز qwerty11 (http://www.barnamenevis.org/forum/member.php?u=97849) بیان شد ./



ظریف ترین شکل جواب نمایش دودویی (http://fa.wikipedia.org/wiki/%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C) n را دربرمی گیرد که توسط "آرمین شمس براق" دانشجوی دانشگاه مشهد پیشنهاد شده و مورد توجه طراحان الگوریتم (http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85) برجسته دنیا قرار گرفته است : اگر n را بصورت باینری بنویسیم و شماره فردی گه زنده می ماند را برابر Jn بگیریم , و n را یک بیت شیفت دورانی (http://fa.wikipedia.org/wiki/%D8%B4%DB%8C%D9%81%D8%AA_%D8%AF%D9%88%D8%B1%D8%A7% D9%86%DB%8C) دهیم Jn به دست می‌آید.
n=۱۰۰ = ۱۱۰۰۱۰۰
پس از یک شیفت دورانی داریم Jn=۱۰۰۱۰۰۱=۷۳



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