یادتون باشه آخرین سوال ساختمان داده پارسال در مورد یه لیست حلقوی بود. سوال رو کامل می نویسم تا روشن شه:
با توجه به تابع روبرو و لیست حلقوی مذکور به ازای مقادیر n برابر 729 و 2200 خروجی به ترتیب برابر چند خواهد بود؟
1) 1 و 40[tex]}[/tex]
2)1 و 1
3) 729 و 2200
4) هیچ کدام
کدش هم اینه:
[tex]int SO(LIST *L){[/tex]
[tex]while (L->next!=L){[/tex]
[tex]L->next= L->next->next[/tex]
[tex]L=L->next;[/tex]
[tex]}[/tex]
[tex]return L->data[/tex]
[tex]}[/tex]
تو کتاب ساختمان داده پارسه بلافاصله یه فرمول داده و ادعا کرده عددی که این قطعه کد تولید می کنه از این فرمول به دست میاد:
[tex]2\times (n-2^{\left \lfloor logn \right \rfloor}) 1[/tex]
در وهله اول اگر من با چنین سوالی برخورد کنم با مثال یه عدد فرد و یه عدد زوج حلش می کنم. اگر با عدد فردی مثل عدد 3 تست کنم جواب می شه 3. اما اگر با عدد زوج امتحان کنم می شه 1. اما تو این فرمول این اعداد جواب نمی دن.
سوال اینجاست این فرمول قشنگ از کجا اومده؟ چطور محاسبه شده که رسیده به این؟
شکل لیست رو هم یه لیست حلقوی فرض کنید که L به گره اول اشاره می کنه. در ضمن دستور return خارج از حلقه while قرار داره.
سلام این فرمول من در آوردی غلطه این مسئله یه راه حل بازگشتی داره که توی کتاب دکتر قدسی به نام مسئله ژزفیوس معرفی شده کتاب رو ندارید از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حل رو ببینید.
High_Voltage عزیز درست میگن، به علاوه‌ی این فرمول بازگشتی یک فرمول هم تو کتاب دکتر قدسی هستش که از طریق تبدیل اعداد به باینری و شیفت جواب بدست میاد، مشابه این تست یک بار تو امتحان آی تی 88 (اگه اشتباه نکرده باشم!) و کامپیوتر 76 (خیلی ساده تر) اومده بود، یک بار هم تو سوالات گسسته عین فرمول بازگشتی رو خواسته بودن
در مورد این سوال گزینه های 1 و 3 در نگاه اول حذف میشن چون تو دور اول همهی اعداد زوج حذف میشن
البته باید بگم کلید اولیه این سوال 1 بود
حالا چرا تو اصلاحیه شد گزینه 4 دو حالت داره
یا طراح محترم اشتباه کرده بود یا سازمان سنجش کلید رو اشتباه زده
که حالت اول امکان پذیر تره سال قبل یادمه خودم هم به گزینه 4 رسیدم و موقعی که کلید‌ها اومد تعجب کردم که بعدش اصلاح شد-در کنکور it 88 هم ازین مورد سوال اومده بود
بله این مسئله جوزفه برای حلش هم عدد باینری خانه nام رو مینویسیم بعد یه rotate به چپ می کنیم عددی که میاد همون جواب
سوال سال قبل به این شکل حل می شه
729= 1011011001 که بعد از چرخش به چپ می شه 0110110011 = 435 و
2200=100010011000 که بعد از چرخش به چپ 000100110001 = 305
[/align]
(17 بهمن 1389 12:25 ب.ظ)arshad90 نوشته شده توسط: [ -> ]تو کتاب ساختمان داده پارسه بلافاصله یه فرمول داده و ادعا کرده عددی که این قطعه کد تولید می کنه از این فرمول به دست میاد:
[tex]2\times (n-2^{\left \lfloor logn \right \rfloor}) 1[/tex]
در وهله اول اگر من با چنین سوالی برخورد کنم با مثال یه عدد فرد و یه عدد زوج حلش می کنم. اگر با عدد فردی مثل عدد 3 تست کنم جواب می شه 3. اما اگر با عدد زوج امتحان کنم می شه 1. اما تو این فرمول این اعداد جواب نمی دن.
سوال اینجاست این فرمول قشنگ از کجا اومده؟ چطور محاسبه شده که رسیده به این؟
این فرمول دقیقاً با روشی که آقای یوسفی توی کتابشون استفاده کردن یکی هست! یعنی این فرمولی که نوشتید، یه عدد باینری رو یه بیت چرخش به چپ میده!
اگه از یه عدد [tex]2^{\left \lfloor \log n \right \rfloor}[/tex] رو کم کنیم، با ارزشترین یکش توی نمایش باینریش حذف میشه، وقتی عدد رو در 2 ضرب کنیم یه بیت به چپ شیفت پیدا میکنه و وقتی با یک جمعش کنیم، اون یک باارزشش رو که از سمت چپ حذف کردیم به سمت راست اضافه میشه و این عملیات دقیقاً معادل یک چرخش به چپ هست!
دوستان عزیزم واقعا ممنونم که اینقدر خالصانه کمک می کنید و هر نکته ای که به ذهنتون میاد در بیانش دریغی ندارین.
انشالله امسال بهترین دانشگاه های ایران میزبان اعضای مانشت خواهند بود.
گاهی واقعا باز کردن یه فرمول پیچیده چقدر تو درک یه مساله می تونه مهم باشه. سمانه عزیز ممنون که فرمول رو ساده کردی.
آهااااااااااااااااااااااااااااااااااا !
تازه یادم اومد این سوال چیه و کجا خوندمش....
این سوال همون ماجرای چند تا یهودیه که در اثنای جنگ جهانی دوم از ترس آلمانها به یک غار پناه می برند.
و چون منابع غذایی شون تموم می شه و بهشون فشار می یاد تصمیم می گیرند خودکشی کنند.
همگی دور هم حلقه می زنند با یک اسلحه!
رئیس گروه(که احتمالا اسمش همون ژوزفیوس باشه)که دلش نمی خواست بمیره یه حقه ای می زنه!!
می گه:عزیزان بیاین از نفر اول شروع کنیم و یکی در میون اسلحه رو به نفر بعدی بدیم تا خودش رو بکشه این اسلحه چند بار در طول حلقه می چرخه تا به همه برسه....
و دیگران انجام می دند.
می دونید آخرش چی میشه؟؟؟
همه خودکشی می کنند.آخرین نفری که نوبت بهش می رسه خود رئیس گروهه که چون هیچ کس دیگه ای نمونده تا مجبورش کنه خودکشی کنه از غار می یاد بیرون و فرار می کنه
این سوال شماره(اندیس)نفر آخر رو می خواد.که به تعداد نفرات (یا تعداد نودهای یک لیست)بستگی داره
حالا راه حل:
همونطور که دوستان هم توی پست‌ها ذکر کردند:
این مسئله یک راه حل بازگشتی داره
ولی جالبه بدونید شخصی ایرانی به نام آروین شمس این روش را ابداع کرده که برای پیدا کردن نود بازمانده کافیست:
تعداد نودها یا نفرات را به صورت کد دودویی بنویسیم.
و بعد یک شیفت چپ سیکولار بدیم.
حالا عددی که به صورت دودویی بدست اومده رو بخونیم.
دینگ دینگ
عدد بدست اومده همون جواب مورد نظر ماست.
(17 بهمن 1389 08:11 ب.ظ)54m4n3h نوشته شده توسط: [ -> ] (17 بهمن 1389 04:07 ب.ظ)High_Voltage نوشته شده توسط: [ -> ]سلام این فرمول من در آوردی غلطه این مسئله یه راه حل بازگشتی داره که توی کتاب دکتر قدسی به نام مسئله ژزفیوس معرفی شده کتاب رو ندارید از
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
حل رو ببینید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
رو ببینید!
اصلاح میکنم این فرمول من درآوردی غلط نیست.
ولی خوب حفظ کردن اون توابع بازگشتی از دو روش دیگه راحت تره (حداقل برای من که راحتر بود)
بسیار ممنون هستم از دوستان.
شیفت به چپ اگه عدد آخر فرد هم باشه جوابش درست در میاد؟
خوب این که همین سواله بالاست!
اگه سوال رو تغییر بدن مثلا به جای اینکه بین 3 گره گره وسط حذف بشه، بین 4 گره 2 گره وسط حذف بشه چه جوری حل میشه؟!!