المپدیا

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

ابزار کاربر

ابزار سایت


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

‎سوال ۲۶

یک رشته‌ی مخصوص به این صورت تعریف می‌شود:

  • $a$ یک رشته‌ی مخصوص است.
  • اگر $S$‎ یک رشته‌ی مخصوص باشد، ‎$Sa$‎ و $Sbb$‎ نیز رشته‌های مخصوص هستند.

تعداد رشته‌های مخصوصی که دقیقاً از ‎۷‎ حرف تشکیل شده‌اند چندتاست؟

  1. ۲
  2. ۷
  3. ۸
  4. ۱۳
  5. ۱۲۸

پاسخ

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

تعداد رشته‌های مخصوصی که دقیقا از ۷ حرف تشکیل شده‌اند عبارتند از:

$$aaaaaaa,aaaaabb,aaaabba,aaabbaa,aabbaaa,abbaaaa,aaabbbb,aabbbba, \\ aabbabb,abbabba,abbaabb,abbbbaa,abbbbbb$$

پس مجموعا ۱۳ رشته مخصوص ۷ حرفی می‌توان تولید کرد. اگر دقت کنید خواهید فهمید که اگر $f_n$ نشانگر تعداد رشته‌های مخصوص $n$ حرفی باشد آن‌گاه رابطه‌ی $f_n=f_{n-1}+f_{n-2}$ برقرار است.


ابزار صفحه