مسابقه شماره ۱۹۴
سه دستور A,B و C داده شده‌اند که هر کدام به عنوان وروديي زوج مرتب (X , Y) را مي‌گيرد و خروجي زير را توليد مي‌کند :
دستور A خروجي با مقدار (X + 3 , Y) را توليد مي‌کند.
دستور B خروجي با مقدار (X , Y – 2) را توليد مي‌کند.
دستور C خروجي با مقدار (X , Y) را توليد مي‌کند.
به تعدادي دستور پشت سرهم يک (( برنامه )) مي‌گوييم. هر برنامه به عنوان ورودي زوج مرتب (X , Y) را مي‌گيرد و خروجي آن به صورت زير تعيين مي‌شود:
دستور اول بر روي ورودي اجرا مي‌شود , سپس دستور دوم خروجي دستور اول را به عنوان ورودي دريافت مي‌کند و اجر مي‌شود , ... و دستور i + 1 ام خروجي دستور iام را به عنوان ورودي دريافت مي‌کند و اجرا مي‌شود. خروجي برنامه , خروجي دستور آخر است. به طور مثال برنامه AAC را در نظر بگيريد که ورودي آن (1 , 2) است . خروجي اين برنامه (2 , 7) خواهد بود ( دستورها از چپ به راست اجر مي‌شوند).
فرض کنيد يک برنامه داريم که ورودي آن (2 , 1) و خروجي آن (8 , 5) است. حداقل تعداد دستورهاي اين برنامه چندتاست؟
الف ) 5 ب ) 6
ج ) 7 د ) 8
هـ ) 9
پاسخ
چون مقدار هر دو مولفه افزايش يافته‌اند و از بين دو دستور A و B فقط دستور A مقدار مولفه را افزايش مي‌دهد معلوم مي‌شود که در طول برنامه حتما بايد از دستور C استفاده کرد. از طرف ديگر چون دو عدد 1 و 5 به اندازه 4 واحد از هم اختلاف دارند ( که مضرب 3 نيست) بنابراين لازم است از دستور B نيز حتما استفاده شود و در ضمن در هر مرحله حداکثر 3 واحد به مجموع مولفه‌ها ( که در ابتدا 2 + 1 يعني 3 و در انتها 5 + 8 يعني 13 مي‌باشد) اضافه مي‌شود. بنابراين حداقل 4 بار نيز بايد از دستور A استفاده کرد که در اين صورت حداقل 6 دستور نياز خواهد بود. با 6 دستو به شکل زير مي‌ميتوان به هدف رسيد:
