تمرین میز دایره ای دوره الگوریتم
سوال
یه سوال توی دوره الگوریتم از بچه ها پرسیده شد که جوابش رو پیدا نکردم.
اگر ۲۵ نفر مهمان دور یک میز دایره ای بشینن و هرکدوم یه شماره توی دستشون باشه (به ترتیب شماره نشینن) و شماره توی دستش رو با بغل دستی مقایسه کنه و به اندازه شماره بزرگتر شیرینی برداره، دربدترین حالت صاحبخونه باید چند شیرینی بخره؟
در حال بررسی
2
انجمن ACM و الگوریتم
2 سال
2 پاسخ ها
417 دیده شده
0
پاسخ ها ( ۲ )
با عرض معذرت بابت طولانی شدن جواب.چون قرار بود الگوریتمی باشه نه برنامه نویسی توضیحات فارسی زیاد داره.
من این سوال رو توی فیلم های آموزش الگوریتم شنیدم البته صورت سوال دو حالت دارد
حالت اول این که با هر دو نفر کنار دستیش مقایسه کنه (جواب این حالت ۵۳۳)
حالت دوم فقط با یکی از دو نفر مقایشه بشه.(فرقی نمیکنه سمت چپ یا راست فقط همه به همون ترتیب مقایسه کنن.مثلا همشون فقط با دست راستشون مقایسه کنن.) جواب این حالت ۴۸۱
برای حل و تفهیم بهتر مساله این شکلی بهتره اول با تعداد کوچیک برای خودمون مثال رو حل کنیم و بعد با همون روش تعداد رو زیاد کنیم.
فرض کنیم برای ۷ نفر میخوایم این مساله رو حل کنیم. اعداد ۱ تا ۷ تقسیم میشن.
اگر حالت اول باشه به صورت دسته های ۳ تایی جدا میشن تا بخوان مقایشه کنن یعنی هر کسی با شماره های چپ و راستش مقایسه میکنه. در این صورت بدترین حالت اینه که هر دوتا عدد کوچیکتر کنار عدد بزرگتر بشینن که هر سه نفر از اون عدد بزرگتر استفاده کنن. (مثلا ۷ بین ۱ و ۲ بیشنه که هر سه نفر ۷ عدد شیرینی بردارند.)بر این اسا میتونیم این شکلی تفسیم کنیم(۲و۷و۱و۴و۶و۳و۵)
دسته های ۳ تایی به این شکل تقسیم میشود
برای مقایسه نفر شماره ۲ (۵و۲و۷) = ۷
برای مقایسه نفر شماره ۷ (۲و۷و۱) = ۷
برای مقایسه نفر شماره ۱ (۷و۱و۴) = ۷
برای مقایسه نفر شماره ۴ (۱و۴و۶) = ۶
برای مقایسه نفر شماره ۶ (۴و۶و۳) = ۶
برای مقایسه نفر شماره ۳ (۶و۳و۵) = ۶
برای مقایسه نفر شماره ۵ (۳و۵و۲) = ۵
در این مثال ۵ آخرین عدد است و مجددا کنار ۲ میشینه. در این حال چون دسته مقایسه ما ۳ تایی است ۳ بار از عدد بزرگتر بعد ۳ بار از عدد یکی کمتر از بزرگترین و به همین ترتیب تا جایی که تعداد اعداد با تعداد نفرات مهمانی برابر شود. و برای سوال اصلی به این صورت میشود: ۲۵ مهمان داریم پس ۸ دسته ۳ تایی و یه عدد تکی داریم
(۳*۲۵)+(۳*۲۴)+(۳*۲۳)+(۳*۲۲)+(۳*۲۱)+(۳*۲۰)+(۳*۱۹)+(۳*۱۸)+۱۷ = ۵۳۳
حالا همان مثال ۷ نفر را برای حالت دوم حل میکنیم. در این حالت همه ی مهمانها فقط با یک نفر در یک سمت مشخص خود مقایسه میکنن. فرض میکنیم همه با فرد سمت چپ خود مقایسه میکنن.(سمت راست هم دقیقا همین شکلیه)
در این حالت بدترین مدل نشستن یکی در میان اعداد کوچک و بزرگ است: ۱و۷و۲و۶و۳و۵و۴
برای مقایسه نفر شماره ۱ (۱و۷) = ۷
برای مقایسه نفر شماره ۷ (۷و۲) = ۷
برای مقایسه نفر شماره ۲ (۲و۶) = ۶
برای مقایسه نفر شماره ۶ (۶و۳) = ۶
برای مقایسه نفر شماره ۳ (۳و۵) = ۵
برای مقایسه نفر شماره ۵ (۵و۴) = ۵
برای مقایسه نفر شماره ۴ (۴و۱) = ۴
در این مثال ۴ آخرین عدد است و مجددا کنار ۱ میشینه.در این حالت چون دسته های مقایسه ما ۲ تایی میشه ۲ تا عدد بزرگتر و بعد ۲ تا عدد یکی گوچکتر از بزرگترین عدد و و به همین ترتیب تا جایی که تعداد اعداد با تعداد نفرات مهمانی برابر شود. و برای سوال اصلی به این صورت میشود: ۲۵ مهمان داریم پس میشود ۱۲ دسته دوتایی و ۱ عدد تکی.
(۲*۲۵)+(۲*۲۴)+(۲*۲۳)+(۲*۲۲)+(۲*۲۱)+(۲*۲۰)+(۲*۱۹)+(۲*۱۸)+(۲*۱۷)+(۲*۱۶)+(۲*۱۵)+(۲*۱۴)+۱۳ = ۴۸۱
سلام وقت بخیر ممنون از پاسختون اگر میشه الگوریتمشم بنویسید ممنون میشم