Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۶

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

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

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

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

پاسخ

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

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

AABBABABABBABBAABABABAAB

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

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


ابزار صفحه