یک سکه سبک!
در یک جمع دوستانه میون بچه های دانشگاه ما همچین سوالی مطرح شده:
فرض کنید 9 تا سکه طلا داریم و یک ترازوی دو کفه,از بین این 9 سکه یکیش سبک تره,حداقل با چند بار وزن کردن می شه فهمید که کدام سکه سبکتر هست؟
پاسخ چهاز گزینه ای هست:
1 حالت
2 حالت
3 حالت
4 حالت
دوستی پاسخ داد:
من پاسخ دادم:اول سه تا سکه این طرف سه تا سکه اون طرف
هر طرف که سبک تر بود سکه تو اون کفه است
بار دوم از اون سه سکه یکی این طرف یکی اون طرف و یکی بیرون. هر کدوم سبک تر بود اون سکه سبکتره. اگه مساوی شد سکه ای که بیرون گزاشتیم
اگه بار اول مساوی شد سه سکه ای که بیرونه رو یکی این طرف یکی اون طرف یکی بیرون میزاریم
هر کدوم سبک تر شد همونه. اگه مساوی شد سکه بیرونیه.
دوست دیگری گفت:برای حل این مسئله باید از روش جستجو خطی استفاده کنیم.
برای درک بهتر مسئله ما اون رو تبدیل به یک مسئله برنامه نویسی می کنیم.
فرض کنید که ما می خواهیم هر بار یک سکه در هر کفه ترازو قرار بدیم. اگر دو طرف با هم برابر بودند که حلقه ما ادامه پیدا می کنه و اگر یک طرف پایین تر بیاد اون جواب ماست و برنامه به پایان میرسه و جستجو با موفقیت انجام میشه. پس در همچین حالتی ما یک آرایه به طول 72 خونه (طبق علم آمار ما باید 9 ضرب در 8 بار (یعنی 72 بار) عمل وزن کردن رو انجام بدیم.) خواهیم داشت که باید جستجو خطی طبق اون انجام بشه. (در واقع در بدترین حالت 72 بار!) ولی در بهترین حالت طبق گفته های بالا چه اتفاقی می افته؟ در بهترین حالت با اولین وزن کردن، ما به جواب خواهیم رسید! (پس از گذروندن اولین حلقه!)
شاید شما بگید که همچین روش جستجویی به هیچ شکل منطقی نیست، ولی مهم اینه که با این روش شانس پیدا کردن جواب به حداقل، یعنی 1 بار می رسد! :)
خلاصه اینکه هر کسی یک نظری داره ولی من فکر می کنم که پاسخم درست هست!شما برداشتت کلا از کلمه ی حده اقل که در این سوال مطرح شده اشتباهه :D
حالا می خواستم از شما این سوال رو بپرسم. نظر شماها چیه؟!!
پاسخ با نقل قول
نوشته شده توسط shahmohammadi
