Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳۳

یک «عبارت جالب» از نویسه‌های a و b به صورت زیر تعریف‌ می‌شود:

  • ab,a و ba هرکدام یک عبارت جالب‌اند.
  • اگر S1 و S2 دو عبارت جالب باشند S1S2 نیز جالب است.

کدام یک از عبارات زیر جالب است؟

  1. abbaaaabba
  2. aaabbabbab
  3. bababbaab
  4. گزینه‌های ۱ و ۲
  5. گزینه‌های ۲ و ۳

پاسخ

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

به راحتی قابل درک است که در یک عبارت جالب تعداد bها نمی‌تواند از تعداد a بیش‌تر باشد بنابراین گزینه‌ی ۳ نمی‌تواند صحیح باشد. همچنین یک عبارت جالب نمی‌تواند به صورت ...bbabb باشد زیرا اگر a به همراه b سمت راست خود آمده باشد آن‌گاه در سمت چپ آن bb و اگر a به همراه b ی سمت چپ خود آمده باشد آن‌گاه در سمت راست آن bb نمی‌تواند تولید شود.


ابزار صفحه