====== سؤال ۵======

سه دستور $A$، $B$ و $C$ داده شده‌اند که هرکدام به عنوان ورودی زوج مرتب $(x,y)$ را می‌گیرد و خروجی زیر را تولید می‌کند:
  * دستور $A$ خروجی با مقدار $(x+3,y)$ را تولید می‌کند.
  * دستور $B$ خروجی با مقدار $(x,y-2)$ را تولید می‌کند.
  * دستور $C$ خروجی با مقدار $(y,x)$ را تولید می‌کند.


به تعدادی دستور پشت سر هم یک «برنامه» می‌گوییم. هر برنامه به‌عنوان ورودی زوج مرتب $(x,y)$ را می‌گیرد و خروجی آن به‌صورت زیر تعیین می‌شود: دستور اول بر روی ورودی اجرا می‌شود، سپس دستور دوم خروجی دستور اول را به‌عنوان ورودی دریافت می‌کند و اجرا می‌شود، ... و دستور $i+۱ $ام خروجی دستور $i$ام را به‌عنوان ورودی دریافت می‌کند و اجرا می‌شود. خروجی برنامه، خروجی دستور آخر است. به‌طور مثال برنامه‌ی $AAC$ را در نظر بگیرید که ورودی آن (۱,۲) است. خروجی این برنامه (۲,۷) خواهد بود (دستورها از چپ به راست اجرا می‌شوند). فرض کنید یک برنامه داریم که ورودی آن (۲,۱) و خروجی آن (۸,۵) است. حداقل تعداد دستورهای این برنامه چند تاست؟

  - ۵
  - ۶
  - ۷
  - ۸
  - ۹

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


چون مقدار هر دو مولفه افزایش یافته اند و از بین دو دستور $A$ و $B$ فقط دستور $A$ مقدار مولفه را افزایش می‌دهد معلوم می‌شود که در طول برنامه حتما باید از دستور $C$ استفاده کرد. از طرف دیگر چون دو عدد ۱ و ۵ به اندازه ۴ واحد از هم اختلاف دارند(که مضرب ۳ نیستند) بنابراین لازم است از دستور $B$ نیز حتما استفاده شود و در ضمن در هر مرحله حداکثر ۳ واحد به مجموع مولفه‌ها(که در ابتدا ۲+۱ یعنی ۳ و در انتها ۵+۸ یعنی ۱۳ می‌باشد) اضافه می‌شود٬ بنابراین حداقل ۴ بار نیز باید از دستور $A$ استفاده کرد که در این صورت حداقل ۶ دستور نیاز خواهد بود. با ۶ دستور به شکل زیر می‌توان به هدف رسید:


$$(2,1) \xrightarrow{A} (5,1) \xrightarrow{B} (5,-1) \xrightarrow{C} (-1,5) \xrightarrow{A} (2,5) \xrightarrow{A} (5,5) \xrightarrow{A} (8,5)$$

</پاسخ>

  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]