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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۱۵

همه‌ی رشته‌های تولید شده از حروف a و b را به ترتیبِ طول رشته و در صورت مساوی بودن طول‌ها به ترتیب الفبایی مرتب می‌کنیم. مثلاً هشت رشته‌ی اول عبارت‌اند از: a,b,aa,ab,ba,bb,aaa,aab. رشته‌ی ۱۳۸۱ام کدام است؟

  1. ababbaabba
  2. bababbbab
  3. ababbaabab
  4. babaabbaab
  5. ababaaaba

پاسخ

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

معلوم است که تعداد رشته‌های به طول i برابر2i می‌باشد. بنابراین آخرین رشته ۹ حرفی که به صورت bbbbbbbbb می‌باشد رشته هزار و بیست و دوم می‌باشد زیرا:

2+4+8+16+32+64+128+256+512=1022

به تعداد 210 رشته ده حرفی می‌توان ساخت که نصف آن‌ها با حرف a و نصف دیگر با حرف b شروع می‌شوند و چون رشته ۱۳۸۱ ام به نصفه اول متعلق است٬ بنابراین آن رشته با حرف a شروع می‌شود. لازم به ذکر است که رشته مورد نظر سیصد و پنجاه و نهمین رشته ده حرف است٬ زیرا 13811022=359 در بین ۵۱۲ رشته‌ای که با a شروع می‌شوند ۲۵۶ تای اول آن‌ها حرف دوم a و ۲۵۶ تای دیگر(که ۳۵۹ نیز به همین دسته متعلق است) حرف دوم b دارند(چون 359256=103<128 ، بنابراین رشته مورد نظر به دسته اول تعلق دارد). اگر به همین ترتیب ادامه دهیم خواهیم داشت:

حرف اول=a 13811022=359<512

حرف دوم=b 359>256

حرف سوم=a 359256=103<128

حرف چهارم=b 103>64

حرف پنجم=b 10364=39>32

حرف ششم=a 3932=7<16

حرف هفتم=a 7<8

حرف هشتم=b 7>4

حرف نهم=b 74=3>2

حرف دهم=a 32=1<7


ابزار صفحه