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