سوال ۸
دستگاه برش «الواربر» ابزاری برای برش الوارهای چوبی است. این دستگاه به عنوان ورودی تعدادی الوار هم اندازه‌ی $۱\times n$ و یک عدد $k$ (کوچکتر از $n$ و بزرگتر از صفر) را می‌گیرد. سپس به طور همزمان و با یک برش عظیم هرکدام از الوارها را به دو تکه با اندازه‌های $۱\times k$ و $۱ \times (n-k)$ تبدیل می‌کند. برای مثال می‌توانیم به این دستگاه سه الوار $۱ \times ۵ $ بدهیم تا در یک حرکت آن ها را به سه تکه‌ی $۱ \times ۱ $ و سه تکه‌ی $۱ \times ۴ $ تبدیل کند.
سهراب یک الوار چوبی $۱ \times ۱۰۰ $ به عنوان کادوی تولد از رستم هدیه گرفته است! او می‌خواهد با کمترین تعداد دفعه استفاده از دستگاه٬ این الوار طویل را به ۱۰۰ تکه‌ی ٰ$۱ \times ۱ $ تبدیل کند. کمترین تعداد دفعه استفاده از دستگاه برای این منظور چند است؟
دقت کنید که همه‌ی الوارهای ورودی به دستگاه در یک مرحله٬ باید با هم هم‌اندازه باشند.
- ۱۰
- ۸
- ۷
- ۹
- ۹۹
پاسخ
گزینه‌ی «۲» درست است.
$100*1 \rightarrow 50*2\rightarrow 25*4 \rightarrow 12*4 + 13*4 \rightarrow 12*8 +1*4\rightarrow 6*16+1*4\rightarrow 3*32+1*4 \rightarrow$
$2*32+1*36 \rightarrow 1*100$
($x*y$ یعنی $x$ چوب به طول $y$ داریم). در نتیجه ۸ مرحله لازم است.
| ▸ سوال قبل | سوال بعد ◂ |