======سوال ۸ ======

دستگاه برش «الواربر» ابزاری برای برش الوارهای چوبی است. این دستگاه به عنوان ورودی تعدادی الوار هم اندازه‌ي $۱\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$ داریم). در نتیجه ۸ مرحله لازم است.


</پاسخ>
  * [[سوال ۹|سوال بعد]]
  * [[سوال ۷|سوال قبل]]