در کتاب مقسمی در پایان فصل برنامه نویسی پویا در مورد سری کاتالان صحبت شده
چه طور این مسئله با سری کاتالان حل میشه
می خواهیم بدانیم با n عدد ورودی که به ترتیب وارد پشته می شوندچند حالت خروجی می توان داشت
در ضمن دو مسئله ضرب ماتریس ها و تعداد درخت دودودیی هم با سری کاتالان حل میشه ولی نفهمیدم که چرا اولی برابر با T(n) (جمله n ام کاتالان ) و دومی برابر با T(n+1) (جمله n+1 ام کاتالان) هست.
عدد کاتالان یک حالت کلی هستش،
برای درک مسائل دیگه کافیه چند جمله ی اول رو بدست بیارید و در حالت ِ کلی فرمول اعداد کاتالان قرار بدید،
شبیه اسقرا میمونه با این فرض که شما فرمول اولیه ی اعداد کاتالان رو در اختیار دارید و با دستکاری اون میتونید نتیجه دلخواهتون رو بگیرید.
مثلا برای یک پشته با سه ورودی تمام حالات رو بدست بیارید،۵ حالت خروجی در میاد. حالا داخل فرمول کلی کاتالان که به صورت زیر هست :
[tex]T(n)\: =\sum^{n-1}_{i=1}T(i)\: T(n-i)\: ,\: T(1)=1\: \Longleftrightarrow\: \frac{1}{n}(^{2n-2}_{n-1})[/tex]
به جای n باید n+1 بگذارید تا تمام پاسخ ها با توجه به فرمول اعداد کاتالان به دست بیاد .
برای اثبات قسمت دوم هم باید برید روی منبع اصلی
سلام. وقت بخیر.
برای محاسبه تعداد حالات جواب‌های این مساله بهتره از رابطه بازگشتی کاتالان استفاده کنید. برای مساله پشته با n شی فرض کنید اولین عددی که وارد پشته میشه چندمین عددیه که از پشته خارج میشست. میتونه به عنوان اولین یا آخرین عضو از پشته خارج بشه. حالا باید سعی کنید یه تطابق بین این n حالت و n جمله از رابطه بازگشتی پیدا کنید.
برای مساله درخت های دودویی باید به گره ریشه درخت توجه کنید که n حالت داره.
برای مساله ضرب n ماتریس هم n-1 عدد به عنوان بعد داخلی ماتریس‌ها داریم که باید حذف بشن.