Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

‎سوال ۲۶

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

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

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

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

پاسخ

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

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

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

پس مجموعا ۱۳ رشته مخصوص ۷ حرفی می‌توان تولید کرد. اگر دقت کنید خواهید فهمید که اگر fn نشانگر تعداد رشته‌های مخصوص n حرفی باشد آن‌گاه رابطه‌ی fn=fn1+fn2 برقرار است.


ابزار صفحه