لیوان ها

[armita]

دو تا لیوان داریم و یک برج 100 طبقه
لیوان ها اگر از طبقه ی n ام به بعد بیافتند می شکنند .
می خواهیم با کمترین تعداد انداختن لیوان ها n رو پیدا کنیم !
دقت کنید اگر یک لیوان بیافته و بشکنه دیگر نمی تونیم از اون استفاده کنیم .
چجوری n رو پیدا کنیم ؟


======================
مسعود :
دوستانی می خواهند اینو حل کنند
به سایر پست ها هم نیگا کنند مخصوصا صفحات آخر
===================================================================
حالا 3 لیوان داریم

 

[mahta_H]

پاسخ : لیوان ها

تو خود طبقه ی N امم میشکنن ؟

 

[armita]

پاسخ : لیوان ها

تو خود طبقه ی N امم میشکنن ؟

نه
n آخرین طبقه ایه که نمی شکنن .

 

[Sampadik]

پاسخ : لیوان ها

از طبقه 50 بندازیم!نمیشه ؟؟؟

 

[settareh]

پاسخ : لیوان ها

خب شاید از همون طبقه ی اول بشکنه...فک کنم خوبه یدونه رو تو طبقه ی اول امتحان کنیم.

 

[tiberium]

پاسخ : لیوان ها

یه راهی درآوردم ولی فکر نکنم درست باشه!

اول از همه میایم یه لیوانو از طبقه 50 میندازیم پایین
2 حالت داره
1-میشکنه
2-نمیشکنه

1-اگر شکست مجبور میشیم از طبقه 1 یکی یکی بیایم بالا..
مثلا اگر n=12 باشه
اول از 50 میندازیم پایین میبینیم میشکنه
بعد از طبقه 1 شروع میشه و یکی یکی طبقات رو میبریم بالا

حالا اگر نشکست:
از طبقه ی 75 که وسط طبقات 50 تا 100 هست میندازیمش
باز 2 حالت داره

1-بشکنه

که در این حالت از 51 شروع می کنیم به انداختن لیوان و هر دفعه یک طبقه میریم بالا
مثلا اگر n=52 باشه
از طبقه 50 میندازیم نمیشکنه
از 75 میندازیم میشکنه
از51 میندازیم نمیشکنه
از 52 میندازیم میشکنه
یعنی تو 4 بار انداختن فهمیدیم
اگر حالت عادی می خواستیم از طبقه 1 بندازیم باید 52 بار مینداختیم!!


2-نشکنه
که دوباره طبقه وسط رو توی اون طبقات باقیمانده انتخاب می کنیم و لیوانو میندازیم
باز همین الگوریتم ها تکرار میشه
یعنی ار شکست از 76 شروع می کنیم به انداختن و هر دفعه یه طبقه میریم بالا

اگر هم نشکست دوباره از طبقه ی وسط طبقات باقی مانده میندازیم و ........!!!

 

[Sampadik]

پاسخ : لیوان ها

یه راهی درآوردم ولی فکر نکنم درست باشه!

اول از همه میایم یه لیوانو از طبقه 50 میندازیم پایین
2 حالت داره
1-میشکنه
2-نمیشکنه

1-اگر شکست مجبور میشیم از طبقه 1 یکی یکی بیایم بالا..
مثلا اگر n=12 باشه
اول از 50 میندازیم پایین میبینیم میشکنه
بعد از طبقه 1 شروع میشه و یکی یکی طبقات رو میبریم بالا

حالا اگر نشکست:
از طبقه ی 75 که وسط طبقات 50 تا 100 هست میندازیمش
باز 2 حالت داره

1-بشکنه

که در این حالت از 51 شروع می کنیم به انداختن لیوان و هر دفعه یک طبقه میریم بالا
مثلا اگر n=52 باشه
از طبقه 50 میندازیم نمیشکنه
از 75 میندازیم میشکنه
از51 میندازیم نمیشکنه
از 52 میندازیم میشکنه
یعنی تو 4 بار انداختن فهمیدیم
اگر حالت عادی می خواستیم از طبقه 1 بندازیم باید 52 بار مینداختیم!!


2-نشکنه
که دوباره طبقه وسط رو توی اون طبقات باقیمانده انتخاب می کنیم و لیوانو میندازیم
باز همین الگوریتم ها تکرار میشه
یعنی ار شکست از 76 شروع می کنیم به انداختن و هر دفعه یه طبقه میریم بالا

اگر هم نشکست دوباره از طبقه ی وسط طبقات باقی مانده میندازیم و ........!!!

دوست عزیز ما فقط 2تا لیوان داریما!!!

 

[tiberium]

پاسخ : لیوان ها

خب میدونم دو تا لیوان داریم
اگر نشکنه ما هنوز 2 لیوان داریما....!

 

[Sampadik]

پاسخ : لیوان ها

آخه مثلا اون جاهایی که گفتی از فلان طبقه شوع میکنیم و میریم بالا چی؟

 

[tiberium]

پاسخ : لیوان ها

الان مثلا فرض کنید n=53 باشه خب؟

اول از طبقه 50 میندازیم
نمیشکنه
اان هنوز 2 تا لیوان داریم

حالا
از طبقه 75 میندازیم و میشکنه
الان 1 لیوان دارین
حالا از طبقه 51 میندازیم
نمشکنه
الان هنو1 لیوان داریم
از طبقه 52 میندازیم و نمیشکنه
هنوزم 1 لیوان داریم
از طبقه 53 میندازیم و مشکنه
معلوم میشه n=53 هست

 

[settareh]

پاسخ : لیوان ها

این می شه؟! از طبقه ی اول شروع می کنیم و یه لیوان رو هی طبقه به طبقه پایین می ندازیم. اون طبقه ای که پرت کردیم و شکست، طبقه ی قبلش n بوده.

 

[tiberium]

پاسخ : لیوان ها

البته شاید حرف من غلط باشه و حرف شما درست باشه ها....
مطمئن نیستم

 

[Sampadik]

پاسخ : لیوان ها

الان مثلا فرض کنید n=53 باشه خب؟

اول از طبقه 50 میندازیم
نمیشکنه
اان هنوز 2 تا لیوان داریم

حالا
از طبقه 75 میندازیم و میشکنه
الان 1 لیوان دارین
حالا از طبقه 51 میندازیم
نمشکنه
الان هنو1 لیوان داریم
از طبقه 52 میندازیم و نمیشکنه
هنوزم 1 لیوان داریم
از طبقه 53 میندازیم و مشکنه
معلوم میشه n=53 هست

اگه از طبقه ی 51 شکست چی؟

 

[tiberium]

پاسخ : لیوان ها

این می شه؟! از طبقه ی اول شروع می کنیم و یه لیوان رو هی طبقه به طبقه پایین می ندازیم. اون طبقه ای که پرت کردیم و شکست، طبقه ی قبلش n بوده.

میشه لطفا یکم توضیح بدید
نفهمیدم چی شد!

 

[tiberium]

پاسخ : پاسخ : لیوان ها

اگه از طبقه ی 51 شکست چی؟

n=53 بوده پس از طبقه 51 نمیشکنه

اگرم از طبقه 51 شکست میفهمیم n=51 هست حتما!

 

[settareh]

پاسخ : لیوان ها

منظورم اینه: لیوان رو برمی داریم. می ریم طبقه ی اول. از پنجره پرت می کنیم پایین. اگه نشکست، می ریم یه طبقه بالا تر. هنوز دوتا لیوان داریم. دوباره یکی رو می ندازیم پایین. اگه شکست، طبقه ی قبلش می شه n. اگه نشکست، می ریم طبقه ی بعدی. همین جوری طبقه طبقه می ریم تا بالاخره لیوانه بشکنه. مثلا تو طبقه 13 می شکنه. پس طبقه ی 12 n بوده. ینی آخرین طبقه ای که لیوان نشکسته.

 

[ترنم]

پاسخ : لیوان ها

دقیقا راه همینه
اول یکی رو از 25 میندازیم اگه شکست میایم 1 و طبقه به طبقه میریم بالا
اگه 25 نشکست از 50 میندازیم و طبقه طبقه میریم بالا تا بشکنه
اگه نشد 75...

 

[tiberium]

پاسخ : لیوان ها

منظورم اینه: لیوان رو برمی داریم. می ریم طبقه ی اول. از پنجره پرت می کنیم پایین. اگه نشکست، می ریم یه طبقه بالا تر. هنوز دوتا لیوان داریم. دوباره یکی رو می ندازیم پایین. اگه شکست، طبقه ی قبلش می شه n. اگه نشکست، می ریم طبقه ی بعدی. همین جوری طبقه طبقه می ریم تا بالاخره لیوانه بشکنه. مثلا تو طبقه 13 می شکنه. پس طبقه ی 12 n بوده. ینی آخرین طبقه ای که لیوان نشکسته.

تو این راه دارید از طبقه 1 شروع می کنید و دونه دونه میرید بالا دسته؟
یعنی اگر n=51 باشه شما 50 بار باید لیوان بندازید...در صورتی که اگر با الگوریتم من یا فرزند کوروش بزرگ پیش برید تو 2 3 بار انداختن n معلوم میشه

 

[tiberium]

پاسخ : لیوان ها

فرزند کورش بزرگ بزرگ شاید راه تو منطقی تر از من باشه....
تو اول از ۲۵ پرت می کنی....اگر نشکست از ۵۰ و اگر نشکست از ۷۵
ولی من اول از ۵۰ انداختم....
به نظر خودم این راه تو بهتر از راه من هست
شاید هم یکی دیگه بگه اول از ۱۰ میندازیم
اگر نشکست از ۲۰
اگر نشکست از ۳۰ و .....
ولی اصل راهمون یکیه....
حالا باید بررسی کنیم که کدوم حالت بهترین حالته

 

[tiberium]

پاسخ : لیوان ها

در این صورت تو راهی که من گفتم ۱ بار بیشتر لیوان پرت می کنیم
بله
اینجا راه شما یه پرتاب کمتر داره ...
اما باید یه الگوریتمی باشه که توحالات دیگه هم درست بشه