سؤال ۵
سه دستور $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)$$
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
