====== سوالات ۱۲ و ۱۳ ======


یک کلمه درون یک پرونده‌ی متنی داده شده است و می‌خواهیم با کم‌ترین تعداد اعمال کپی (Copy) و درج (Paste) تعداد مشخصی نسخه از آن ایجاد کنیم.

در هر مرحله می‌توانیم تعداد دل‌خواهی از کلمات نوشته‌شده درون پرونده را در حافظه کپی کنیم و یا کلمات درون حافظه را در پرونده درج کنیم. (مثل کپی و پیست در ویرایشگرها، می‌توان یک بار کپی کرد و سپس چند بار درج کرد.) 

هر کپی 1 واحد و هر درج نیز ۱ واحد هزینه دارد. 

====== سوال ۱۲ ======

با حداقل چند واحد هزینه می‌توانیم دقیقا ۹۹ کلمه‌ی دیگر مشابه با کلمه‌ی اول ایجاد کنیم؟

  - ۲۰
  - ۱۰
  - ۱۳
  - ۲۲
  - ۱۴
<پاسخ>
گزینه (۳) درست است.

اگر یک بار کپی و یک بار پیست کنیم در نهایت با ۱۴ حرکت می‌توان به عدد صد رسید. اما اگر در ابتدا یک بار کپی و دو بار پیست کنیم، سپس یک بار کپی و دو بار پیست کنیم، و سپس یک بار کپی و سه بار پیست کنیم به عدد ۳۶ می‌رسیم. حال اگر ۳۲ کلمه را کپی کنیم و دو بار پیست کنیم ۱۰۰ کلمه خواهیم داشت و تعداد حرکات ۱۳ تا شده است. 

برای اثبات کمینه بودن پاسخ سوال بعدی را ببینید.

</پاسخ>
====== سوال ۱۳ ======

با ۱۴ واحد هزینه حداکثر چند کلمه (با احتساب کلمه‌ی اولیه) می‌توان ایجاد کرد؟

  - ۱۶۲
  - ۱۰۰
  - ۸۱
  - ۲۴۳
  - ۱۲۸

<پاسخ>
گزینه (۱) درست است.

کافی است $f(k)$ را بیش‌ترین تعداد کلمه با $k$ واحد هزینه تعریف کنیم. به سادگی می‌توان دید که:
$$f(2)=2, f(3)=3, \ldots, f(n)= \max_k\{⁡kf(n-k)\}$$
بنابراین به دست می‌آید:
$$f(12)=81,f(13)=108,f(14)=162$$

</پاسخ>

  * [[سوالات ۱۴ و ۱۵|سوال بعد]]
  * [[سوال ۱۱|سوال قبل]]