سوال ۲۳

رشته‌ی $babababba$ را در نظر بگیرید. در هر مرحله می‌توانیم دو حرف متوالی از این رشته را با هم جابه‌جا کنیم. حداقل تعداد مراحل لازم برای این که بتوانیم به رشته‌ای برسیم که در آن همه‌ی ‎$a$‎ ها در کنار هم و همه‌ی $‎b$‎ ها نیز در کنار هم قرار گرفته باشند، چند مرحله است؟

  1. ۸
  2. ۹
  3. ۱۰
  4. ۱۱
  5. ۱۲‎

پاسخ

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

برای ساختن رشته‌ی $bbbbbaaaa$ از روی رشته‌ی $babababba$، ۹ مرحله لازم است زیرا $‎b$‎ ها از سمت چپ به ترتیب از روی ۳٬۲٬۱٬۰ و ۳ عدد ‎$a$ رد شده‌اند که مجموعا ۹ جابه‌جایی می‌شود. به همین ترتیب معلوم می‌شود که برای ساختن دنباله‌ی $aaaabbbbb$ از روی دنباله‌ی داده شده ۱۱ مرحله لازم است.