سؤال ۵

سه دستور $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)$

المپدیا

ابزار کاربر

ابزار سایت

سؤال ۵

ابزار صفحه