بابا و دخترش

بابا و دختراش

Sunday, May 28, 2006

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

برای اونهایی که علاقمندند بدونند چی شد تعدادی از راه حل ها و کامنت ها رو اینجا می آرم. اگر می خواهید ذهن خودتون رو آزمایش کنید این پست رو تکه تکه بخونید و ببینید آیا این راه حل ها و کامنت ها کمکی به شما می کنه یا نه. آخرین راه حل تقریبا جواب رو کامل گفته.
-------------
راه حل نیما عصیان:
خب اول گوی اول رو بر می‌داريم از پايين‌ترين طبقه می‌ندازيم. اگر شکست، که سر کاريم. اگر نشکست، می‌ريم طبقه n/2 می‌ندازيمش. اگر شکست، بايد بياييم وسط n/2 و طبقه صفر يعنی طبقه n/4 رو امتحان کنيم. اگر نشکست بايد بياييم وسط طبقه n/2 و n از اون جا امتحان کنيم. اين کار رو بايد ادامه بديم. به نظرم يک الگوريتم جست‌وجوی اين طوری نتيجه می‌ده. در قانون کلی اول پايين‌ترين طبقه، بعد طبقه وسط رو امتحان می‌کنيم. اگر نشکست بايد بريم وسط طبقه وسطی و آخرين طبقه. اگر شکست بايد بريم وسط طبقه وسطی و پايين‌ترين طبقه. اين نصف کردن‌ها رو بايد ادامه بديم تا طبقه مورد نظر در کم‌ترين آزمايش پيدا بشه

کامنت من :نيما جان راه حلت وقتی درسته که به تعداد کافی گوی داشته باشيم اينجا فقط دوتا داريم

-----------
راهنمایی ها دوگانه :
اول اينکه تعداد گوی هايی که داريم فقط دو تا ست و فقط می تونيد از اونها استفاده کنيد وگرنه اگر بيشتر بود ( مثلا ۷ تا ) می شد از روشی که نيما يا علی گفتند استفاده بکنيم.

راهنمايی دوم هم اينه که اگر فقط يک گوی داشتيم می تونستيم از طبقه اول شروع کنيم و گوی رو از اونجا بندازيم اگه شکست که جواب رو فهميديم و گر نه می ريم يه طبقه بالا تر و دوباره امتحان می کنيم. اينجوری در بدترين حالت ۱۰۰تا آزمايش لازمه. حالا که دوتا گوی داريم ببينيد می شه این تعداد رو کمتر کرد؟
-----------

راه حل زهره:

1. az tabagheie aval mindaazim agar shekast ke hich chi
2. agar nashkast mirim soaghe tabagheie 3
3. agar shekast baa gooie ba'di mirim 2
4. agar dar tabagheie 3 nashkast mirim 5 taa aakhar chon faghat 2 taa gooi daarim

کامنت من :زهره جان راه حل ات می تونه مدخلی به راه حل نهایی باشه. مثلا اگر 3تا 3تا یا شایدم 10 تا 10 تا بریم بالا می شه همین راه حل رو به کار بست و گوی اول رو در اون طبقات امتحان کرد و گر شکست با گوی دوم از آخرین طبقه ای که نشکسته بود شروع کنیم و یکی یکی بیام بالا . اینجوری مثلا در مورد راه حل تو در بدترین حالت نیاز به 50 تا تست داریم در حالیکه اگر 10 تا 10 تا تقسیم کنیم در بدترین حالت نیاز به 19 آزمایش هست!
-----------
راه حلVahid Yousefzadeh

ما دو تا گوي داريم و يک ساختمان 100 طبقه. از طبقه دهم شروع مي کنيم و گوي رو ميندازيم. حالا دو حالت داره:

1) اگه شکست پس احتمال داره در طبقات پايينتر از ده نيز بشکنه بنابراين گوي ديگه رو برميداريم و طبقات 1 تا 9 رو امتحان ميکنيم.

2) اگه نشکست از طبقه بيست ميندازيم و باز مثل قبل اگه شکست (چون در طبقات 1 تا 10 نشکسته بود) از طبقه 11 تا 19 امتحان ميکنيم. و همينطور تا 100.

اينم يک مثال: بر فرض اينکه طبقه مورد نظر، طبقه 87 ساختمان باشه و ما الان ميخواهيم که با آزمايش اون رو کشف کنيم.

گوي رو از طبقات 10، 20، 30، 40، 50، 60، 70، 80 پايين ميندازيم و ميبينيم که نشکست حالا از 90 پايين ميندازيم و گوي ميشکنه (تا اينجا 9 آزمايش) پس نتيجه ميگيريم که چون تا طبقه 80 نشکسته پس بازه اي که گوي در آن خواهد شکست ما بين هشتاد و نوده. حالا از 81 شروع ميکنيم گوي دوم رو ميندازيم تا ميرسيم به طبقه اي که در اون گوي ميشکنه.

يعني اگه در واقع ما با گوي اول مجموعه اي متشکل از ده طبقه متوالي رو که گوي در يکي از طبقات آن ميشکنه پيدا ميکنيم (حداکثر 10 آزمون با گوي اول بسته به شماره طبقه) و بعد با گوي دوم در اين بازه با حداکثر 9 آزمايش عدد يکان طبقه رو پيدا ميکنيم.

پس بر فرض اينکه در بدترين حالت طبقه مورد نظر طبقه 100 يا 99 باشه با 19 آزمايش شماره طبقه پيدا ميشه.
کامنت من :راه حل ات %99 جواب رو داره فقط دوتا چیز کوچولو می مونه:
1- چرا 10 تا 10 تا طبقه ها رو تقسیم کردی. مثلا اگه 15 تا 15 تا بریم بالا بهتر نیست؟

2- اگه تعداد طبقات متغیر باشه راه حل بهتر می شه یا نه؟ مثلا به جای 10- 20 - 30-40 و ... بیایم 14-27-39-50- 60-69-77-84-90-95-99-100
رو امتحان کنیم.

0 Comments:

Post a Comment

Links to this post:

Create a Link

<< Home

| مطلب را به بالاترین بفرستید: Balatarin


My blog is worth $11,855.34.
How much is your blog worth?