رشته‌های شبه دودویی

[combinatorics]

تمامِ رشته‌هایی که تنها با حروفِ a , b ساخته‌می‌شوند و دستِ‌بالا n رقم دارند، درنظربگیرید. این رشته‌ها را به ترتیبِ الفبایی مرتب‌کرده و در یک دنباله بنویسید. مثلاً برایِ n=3، دنباله به صورتِ زیر است:
a, aa, aaa, aab, ab, aba, abb, b, ba, baa, bab, bb, bba, bbb
حال به روشنی قابلِ مشاهده است که رشته‌یِ aab در دنباله‌ی بالا در مکانِ 4ام قرار دارد. حال الگوریتم زیر را در نظر بگیرید که n را به همراهِ رشته‌ای از ورودی دریافت می‌کند و مکانِ آن رشته را در دنباله‌ تحویل می‌دهد:

1. n و رشته‌یِ R را از ورودی تحویل‌بگیر.
2. تعداد حرف‌های R را در k بریز.
3. مقدارِ sum را برابر با صفر قرار بده.
4. برایِ هر i از 1 تا k انجام بده:
1.4. اگر iام (از سمتِ چپ)، a بود
1.1.4. sum را با 1 جمع کن و حاصل را در sum بریز.
2.4. در غیرِ این صورت
1.2.4. sum را با دو به توان (n-i+1) جمع‌کن و حاصل را در sum بریز.
5. مقدارِ sum را به عنوانِ خروجی تحویل بده.

نشان‌دهید الگوریتمِ بالا درست کار می‌کند.

 

[mohsen2010]

پاسخ : رشته‌های شبه دودویی

اول ثابت ميكنيم كه اگر به bرسيديم و حرفiام بود مستقل از اعداد قبلي و بعدي دو به توان(n-i+1) مكان در جايگاه رشته اثر داره( a كه واضح است ارزشش روي جايگاه رشته 1هه)
واسه اين كار يك استقرا روي n مي زنيم .حالت پايه كه واضحه ،فرض كنيد واسه ي T-1درست باشه دو به توان(t-i)جايگاه تاثير داشته باشه آنگاه اگر bتوي رشته در مكانiقرار داشته باشه تاثيرش دو به توان(t-i+1)خواهد بود.
براي رسيدن به b درTبايد اولا از كل رشته هايي كه در T-1 براي رسيدن به bگذشته ايم بگذريم كه ميشه دو به توان(t-i) ‍،دوما بايد از رشته ايي به طول tكه اول آنها aاست نيز بگذريم كه تعداد اين اعداد نيزدو به توان(t-i) است
درنتيجه حكم استقرا ثابت شد.
پس ارزش مكاني bوaمعلوم شد و مي توانيم از آن ها در الگوريتم اسفاده كنيم(اميدوارم توضيحاتم كامل باشه )

پ.ن:راه حل كاملش با كمي تفكر راحت حل ميشه كه من فعلا حالش رو ندارم

 

[combinatorics]

پاسخ : رشته‌های شبه دودویی

راه حلت درسته. البته من این سوال سر حل کردن یکی از سوالات مرحله 1 دوره 11 کامپیوتر در سال دوم طرح کردم و طبیعی است که سوال ساده باشد.

 

[mohsen2010]

پاسخ : رشته‌های شبه دودویی

راه حلت درسته. البته من این سوال سر حل کردن یکی از سوالات مرحله 1 دوره 11 کامپیوتر در سال دوم طرح کردم و طبیعی است که سوال ساده باشد.

ساده بود ولي سوال جالبي هم بود.