سلام این فرمول من در آوردی غلطه این مسئله یه راه حل بازگشتی داره که توی کتاب دکتر قدسی به نام مسئله ژزفیوس معرفی شده کتاب رو ندارید از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حل رو ببینید.

(۱۷ بهمن ۱۳۸۹ ۰۴:۰۷ ب.ظ)High_Voltage نوشته شده توسط:  سلام این فرمول من در آوردی غلطه این مسئله یه راه حل بازگشتی داره که توی کتاب دکتر قدسی به نام مسئله ژزفیوس معرفی شده کتاب رو ندارید از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حل رو ببینید.

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رو ببینید!

High_Voltage عزیز درست میگن، به علاوه‌ی این فرمول بازگشتی یک فرمول هم تو کتاب دکتر قدسی هستش که از طریق تبدیل اعداد به باینری و شیفت جواب بدست میاد، مشابه این تست یک بار تو امتحان آی تی ۸۸ (اگه اشتباه نکرده باشم!) و کامپیوتر ۷۶ (خیلی ساده تر) اومده بود، یک بار هم تو سوالات گسسته عین فرمول بازگشتی رو خواسته بودن

---

در مورد این سوال گزینه های ۱ و ۳ در نگاه اول حذف میشن چون تو دور اول همهی اعداد زوج حذف میشن

البته باید بگم کلید اولیه این سوال ۱ بود
حالا چرا تو اصلاحیه شد گزینه ۴ دو حالت داره
یا طراح محترم اشتباه کرده بود یا سازمان سنجش کلید رو اشتباه زده
که حالت اول امکان پذیر تره سال قبل یادمه خودم هم به گزینه ۴ رسیدم و موقعی که کلید‌ها اومد تعجب کردم که بعدش اصلاح شد-در کنکور it 88 هم ازین مورد سوال اومده بود

بله این مسئله جوزفه برای حلش هم عدد باینری خانه n‌ام رو مینویسیم بعد یه rotate به چپ می کنیم عددی که میاد همون جواب
سوال سال قبل به این شکل حل می شه
۷۲۹= ۱۰۱۱۰۱۱۰۰۱ که بعد از چرخش به چپ می شه ۰۱۱۰۱۱۰۰۱۱ = ۴۳۵ و
۲۲۰۰=۱۰۰۰۱۰۰۱۱۰۰۰ که بعد از چرخش به چپ ۰۰۰۱۰۰۱۱۰۰۰۱ = ۳۰۵
[/align]

(۱۷ بهمن ۱۳۸۹ ۱۲:۲۵ ب.ظ)arshad90 نوشته شده توسط:  تو کتاب ساختمان داده پارسه بلافاصله یه فرمول داده و ادعا کرده عددی که این قطعه کد تولید می کنه از این فرمول به دست میاد:

[tex]2\times (n-2^{\left \lfloor logn \right \rfloor}) 1[/tex]

در وهله اول اگر من با چنین سوالی برخورد کنم با مثال یه عدد فرد و یه عدد زوج حلش می کنم. اگر با عدد فردی مثل عدد ۳ تست کنم جواب می شه ۳/ اما اگر با عدد زوج امتحان کنم می شه ۱/ اما تو این فرمول این اعداد جواب نمی دن.
سوال اینجاست این فرمول قشنگ از کجا اومده؟ چطور محاسبه شده که رسیده به این؟

---

این فرمول دقیقاً با روشی که آقای یوسفی توی کتابشون استفاده کردن یکی هست! یعنی این فرمولی که نوشتید، یه عدد باینری رو یه بیت چرخش به چپ میده!
اگه از یه عدد [tex]2^{\left \lfloor \log n \right \rfloor}[/tex] رو کم کنیم، با ارزشترین یکش توی نمایش باینریش حذف میشه، وقتی عدد رو در ۲ ضرب کنیم یه بیت به چپ شیفت پیدا میکنه و وقتی با یک جمعش کنیم، اون یک باارزشش رو که از سمت چپ حذف کردیم به سمت راست اضافه میشه و این عملیات دقیقاً معادل یک چرخش به چپ هست!

دوستان عزیزم واقعا ممنونم که اینقدر خالصانه کمک می کنید و هر نکته ای که به ذهنتون میاد در بیانش دریغی ندارین.
انشالله امسال بهترین دانشگاه های ایران میزبان اعضای مانشت خواهند بود.

گاهی واقعا باز کردن یه فرمول پیچیده چقدر تو درک یه مساله می تونه مهم باشه. سمانه عزیز ممنون که فرمول رو ساده کردی.

آهااااااااااااااااااااااااااااااااااا !
تازه یادم اومد این سوال چیه و کجا خوندمش....
این سوال همون ماجرای چند تا یهودیه که در اثنای جنگ جهانی دوم از ترس آلمانها به یک غار پناه می برند.
و چون منابع غذایی شون تموم می شه و بهشون فشار می یاد تصمیم می گیرند خودکشی کنند.
همگی دور هم حلقه می زنند با یک اسلحه!
رئیس گروه(که احتمالا اسمش همون ژوزفیوس باشه)که دلش نمی خواست بمیره یه حقه ای می زنه!!
می گه:عزیزان بیاین از نفر اول شروع کنیم و یکی در میون اسلحه رو به نفر بعدی بدیم تا خودش رو بکشه این اسلحه چند بار در طول حلقه می چرخه تا به همه برسه....
و دیگران انجام می دند.
می دونید آخرش چی میشه؟؟؟
همه خودکشی می کنند.آخرین نفری که نوبت بهش می رسه خود رئیس گروهه که چون هیچ کس دیگه ای نمونده تا مجبورش کنه خودکشی کنه از غار می یاد بیرون و فرار می کنه
این سوال شماره(اندیس)نفر آخر رو می خواد.که به تعداد نفرات (یا تعداد نودهای یک لیست)بستگی داره


حالا راه حل:
همونطور که دوستان هم توی پست‌ها ذکر کردند:
این مسئله یک راه حل بازگشتی داره
ولی جالبه بدونید شخصی ایرانی به نام آروین شمس این روش را ابداع کرده که برای پیدا کردن نود بازمانده کافیست:
تعداد نودها یا نفرات را به صورت کد دودویی بنویسیم.
و بعد یک شیفت چپ سیکولار بدیم.
حالا عددی که به صورت دودویی بدست اومده رو بخونیم.
دینگ دینگ
عدد بدست اومده همون جواب مورد نظر ماست.

بسیار ممنون هستم از دوستان.
شیفت به چپ اگه عدد آخر فرد هم باشه جوابش درست در میاد؟

خوب این که همین سواله بالاست!

نقل قول:

(۱۹ بهمن ۱۳۸۹ ۰۲:۳۸ ب.ظ)afagh1389 نوشته شده توسط:  خوب این که همین سواله بالاست!

آخرین عددش مگه ۱۰۰۰ نیست .زوج میشه که .ماله آی تی که این بود

این سوال گسسته هم بوده

اگه سوال رو تغییر بدن مثلا به جای اینکه بین ۳ گره گره وسط حذف بشه‌، بین ۴ گره ۲ گره وسط حذف بشه چه جوری حل میشه؟!!

نه دیگه...اونوقت دیگه این راه حل جواب نمی ده
اون یکی فرمول رو آروین شمس زحمتش رو کشید این یکی رو شما پیدا کنید(البته بعد از کنکور)

یادمه اون روزی که استاد ساختمان داده داشت اون داستان رو تعریف می کرد و مسئله رو تشریح می کرد دقیقا همین سوال رو ازش پرسیدم.یاد آن دوران و استاد بخیر.......

سلااام
این ویژگی فقط برای مقدار k=2 جواب میده در این حالت با افزایش n تابع fn دارای این خاصیت هستش که به ازای وردوی های توان دو تابع صعودی متناوب هستش (با دوره تنباوب ۲^n )یعنی به ازاد مقادیر ورودی ۱ و ۲و۴و۸و۱۶و..... مقدار نفر اول یا ۱ اخرین بازمانده میباشد.

متاسفانه این ویژگی را نمیتوان برای مقدار k=3 و..... بسط داد
حالا یه سئوال؟به نظر شما میشه فرمولی تدوین کرد که برای هر مقدار از k بتوان مستقیما جواب رابه دست اورد؟؟؟؟
فکر کنم چنین فرمولی تا کنون ارائه نشده باشه یعنی حدااقل من بی اطلاع هستم اگر دوستانی دراین زمینه اطلاع دارن ممنون میشوم عنوان کنن.

یعنی اگه ما از ۵ تا گره داشته باشیم و از گره ی ۱ شروع کنیم باید گره ی ۳ باقی بمونه ؟
آیا نتیجه گیری من با توجه به عکس زیر درسته ؟