سؤال ۵

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

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

  1. ۵
  2. ۶
  3. ۷
  4. ۸
  5. ۹

پاسخ

گزینه (۲) درست است.

چون مقدار هر دو مولفه افزایش یافته اند و از بین دو دستور $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)$$