زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۰۳:۰۹ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سری کاتالان و مسائل مربوط به ان

ارسال:
  

rad.bahar پرسیده:

سری کاتالان و مسائل مربوط به ان

در کتاب مقسمی در پایان فصل برنامه نویسی پویا در مورد سری کاتالان صحبت شده
چه طور این مسئله با سری کاتالان حل میشه
می خواهیم بدانیم با n عدد ورودی که به ترتیب وارد پشته می شوندچند حالت خروجی می توان داشت

در ضمن دو مسئله ضرب ماتریس ها و تعداد درخت دودودیی هم با سری کاتالان حل میشه ولی نفهمیدم که چرا اولی برابر با T(n) (جمله n ام کاتالان ) و دومی برابر با T(n+1) (جمله n+1 ام کاتالان) هست.
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

Jooybari پاسخ داده:

RE: سری کاتالان و مسائل مربوط به ان

سلام. وقت بخیر.
برای محاسبه تعداد حالات جواب‌های این مساله بهتره از رابطه بازگشتی کاتالان استفاده کنید. برای مساله پشته با n شی فرض کنید اولین عددی که وارد پشته میشه چندمین عددیه که از پشته خارج میشست. میتونه به عنوان اولین یا آخرین عضو از پشته خارج بشه. حالا باید سعی کنید یه تطابق بین این n حالت و n جمله از رابطه بازگشتی پیدا کنید.
برای مساله درخت های دودویی باید به گره ریشه درخت توجه کنید که n حالت داره.
برای مساله ضرب n ماتریس هم n-1 عدد به عنوان بعد داخلی ماتریس‌ها داریم که باید حذف بشن.
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Saman پاسخ داده:

RE: سری کاتالان و مسائل مربوط به ان

عدد کاتالان یک حالت کلی هستش،
برای درک مسائل دیگه کافیه چند جمله ی اول رو بدست بیارید و در حالت ِ کلی فرمول اعداد کاتالان قرار بدید،
شبیه اسقرا میمونه با این فرض که شما فرمول اولیه ی اعداد کاتالان رو در اختیار دارید و با دستکاری اون میتونید نتیجه دلخواهتون رو بگیرید.
مثلا برای یک پشته با سه ورودی تمام حالات رو بدست بیارید،۵ حالت خروجی در میاد. حالا داخل فرمول کلی کاتالان که به صورت زیر هست :

[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 بگذارید تا تمام پاسخ ها با توجه به فرمول اعداد کاتالان به دست بیاد .

برای اثبات قسمت دوم هم باید برید روی منبع اصلی
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  دانلود حل نمونه مسائل پایگاه داده المصری jazana ۳ ۶,۱۸۹ ۱۱ آبان ۱۴۰۲ ۰۸:۰۳ ب.ظ
آخرین ارسال: M--mohammadi
  تست ۸۷ کامپیوتر مربوط به عامل ها Shekarchi_shab ۳ ۱,۶۳۸ ۲۰ بهمن ۱۴۰۱ ۰۷:۳۹ ب.ظ
آخرین ارسال: HamidReza1
Information فروش کتابهای گسسته گریمالدی ۴ جلد + راهنمای حل مسائل tabassomesayna ۱ ۳,۳۱۰ ۲۷ فروردین ۱۳۹۹ ۰۴:۵۶ ب.ظ
آخرین ارسال: tabassomesayna
  آخرین اخبار مربوط به مسابقات رباتیک کشوری javadjj ۲۴ ۲۱,۲۰۱ ۲۳ دى ۱۳۹۸ ۱۲:۵۶ ق.ظ
آخرین ارسال: marvelous
Star بهترین و پر درآمدترین شغل مربوط به کامپیوتر از نظر شما چیست؟ پشتکار ۶ ۱۳۲ ۱۴ آذر ۱۳۹۷ ۰۵:۱۴ ب.ظ
آخرین ارسال: jaweed88
  آیا امکان ارسال مجدد ایمیل مربوط به پذیرش مقاله در یک ژورنال isi وجود دارد؟ Autumngirl ۴ ۳,۷۷۱ ۱۱ مهر ۱۳۹۷ ۰۱:۲۱ ب.ظ
آخرین ارسال: Autumngirl
  فروش یک سری کتاب آمادگی برای آزمون آیلتس ، GRE و یک سری کتاب آموزشی انگلیسی و فرانسه niloo72 ۰ ۲,۲۸۵ ۰۸ مهر ۱۳۹۷ ۱۲:۱۹ ق.ظ
آخرین ارسال: niloo72
  فصل " حل معادله دیفرانسیل با کمک سری ها" در معادلات دیفرانسیل را نمی فهمم!! saeid4x ۳ ۵,۰۲۸ ۲۷ اردیبهشت ۱۳۹۷ ۱۰:۵۳ ق.ظ
آخرین ارسال: CSX
  چاپ کاتالوگ خلاقانه سخت نیست! (سری اول) fafaferdos ۰ ۱,۷۲۶ ۲۶ اردیبهشت ۱۳۹۷ ۰۳:۴۳ ب.ظ
آخرین ارسال: fafaferdos
  کدام گرایش به برنامه نویسی مربوط است؟ سیدرضا بازیار ۱ ۲,۳۶۹ ۰۹ اردیبهشت ۱۳۹۷ ۰۹:۰۵ ب.ظ
آخرین ارسال: kilookiloo

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close