سوال ۳۹
تعداد زیادی از هرکدام از وزنه‌های ۲،۱، ۵، ۱۰ و ۲۰ کیلوگرمی روی میز داریم. یک جسم با وزن نامشخص در یک کفه‌ی ترازوی ساده‌ی دوکفه‌ای قرار می‌دهیم. در هر «توزین» فقط می‌توانیم یک وزنه را از روی میز در کفه‌ی دوم قرار دهیم یا یک وزنه را از روی کفه بر روی میز بگذاریم. توجه کنید که مجاز به گذاردن وزنه در کفه‌ای که جسم قرار دارد نیستیم.
برای مشخص کردن وزن دقیق جسم مطابق الگوریتم زیر عمل می‌کنیم:
• تعدادی وزنه‌ی ۲۰ کیلوگرمی را یک‌به‌یک در کفه‌ی دوم قرار می‌دهیم تا کفه‌ی دوم سنگین‌تر از جسم شود سپس آخرین وزنه را برمی‌داریم.
• کار فوق را به ترتیب با وزنه‌های ۱۰، ۲،۵ و ۱ انجام می‌دهیم تا ترازو کاملاً متوازن شود، که در آن صورت کار را متوقف می‌کنیم.
دقت کنید که در انجام این مراحل به‌محض این که ترازو کاملاً متوازن شود، الگوریتم پایان می‌یابد. اگر وزن جسم حداکثر ۱۰۰ کیلوگرم باشد، الگوریتم فوق حداکثر پس از چند توزین پایان می‌یابد؟
- ۱۶
- ۱۵
- ۱۸
- ۶
- ۲۰
پاسخ
گزینه (۱) درست است.
اگر $x$ نشان‌دهنده‌ی آن باشد که وزنه‌ی $x$ را در کفه‌ی دوم قرار دهیم و نیز $\not{x}$ نشان‌دهنده‌ی آن باشد که وزنه $x$ را از آن کفه برداریم٬ آن‌گاه الگوریتم توزین به شکل زیر خواهد بود:
$$20 , 20 , ... , 20 , \not{20} , 10 , 10 , ... , 10 , \not{10} , 5 , 5 , ... , 5 , \not{5} , 2 , 2 , ... , 2 , \not{2} , 1$$
چون وزنه ۲۰ کیلویی آخر برداشته می‌شود. بنابراین تعداد ۱۰ها نمی‌تواند بیش از ۲ باشد٬ به‌همین دلیل تعداد ۵ها و ۲ها نیز نمی‌تواند بیش از ۲ باشد. بنابراین الگوریتم بیش‌ترین توزین به شکل زیر می‌باشد:
$$20,20,20,20,20,\not{20},10,10,\not{10},5,5,\not{5},2,2,\not{2},1$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
