المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۶

سؤال ۶

همان سؤال قبل، با این تفاوت که خروجی دستورهای $A$، $B$ و $C$ به‌صورت زیر است:

  • دستور $A$ خروجی $(x+1,y)$ را تولید می‌کند.
  • دستور $B$ خروجی $(x,y+1)$ را تولید می‌کند.
  • دستور $C$ خروجی $(y,x)$ را تولید می‌کند.

تعداد برنامه‌هایی را پیدا کنید که از دستور $C$ دقیقاً یک‌بار استفاده کرده باشد و به ازای ورودی (۰,۰) خروجی (۲,۲) را تولید کند.

  1. ۶
  2. ۱۸
  3. ۲۴
  4. ۳۰
  5. ۳۲

پاسخ

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

اگر مجاز نبودیم از دستور $C$ استفاده کنیم٬ آن‌گاه تعداد برنامه‌های مطلوب برابر با ۶ می‌شد که به شکل زیر می‌باشند:

$$AABB \longrightarrow ABAB \longrightarrow ABBA \longrightarrow BBAA \longrightarrow BABA \longrightarrow BAAB$$

حال که قرار است دقیقا یک عدد دستور $C$ در لابه‌لای دستورها قرار داده شود٬ آن را در جای دلخواه قرار داده و تمام دستورهای بعد از آن را تعویض می‌کنیم($A$ را به $B$ و $B$ را به $A$ تبدیل می‌کنیم)٬ که در این صورت هر برنامه به‌دست آمده برنامه مطلوب خواهد شد. به عنوان مثال اگر حرف $C$ را به عنوان دومین حرف از سمت چپ برنامه $ABAB$ قرار دهیم آن برنامه به شکل $ACBAB$ تغییر خواهد یافت که نقطه $(0,0)$ را به $(2,2)$ تبدیل می‌کند.

چون در هر مورد برای $C$ پنج جای متمایز وجود دارد. بنابراین تعداد دنباله‌های مطلوب $6\times5$ یعنی ۳۰ خواهد شد.


ابزار صفحه