بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی آنلاین 20 Quera

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسأله‌ی انتخابات

بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
بستن پنجره
وبگاه     این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
دنباله‌ی اعداد کاتالان و محاسبه‌ی آن - الگوریتمستان
الگوریتمستان
4314.145.00
  »  

       

آشنایی با دنباله‌ی عددی کاتالان، کاربردها و روش پیاده‌سازی آن به زبان برنامه‌نویسی ++C

دنباله‌ی اعداد کاتالان (Catalan Numbers) یکی از دنباله‌های عددی مشهور ریاضیات است که برای عدد نامنفی n به صورت $C_n$ نمایش داده می‌شود.

  

$C_n:\qquad 1,\;1,\;2,\;5,\;14,\;42,\;132,\;429,\;1430,\;4862,\;16796,\;\cdots$

  

    این دنباله کاربردهای بسیاری در مسائل شمارشی دارد. از جمله:

    1- تعداد درخت‌های دودویی با n رأس داخلی برابر $C_n$ است:

      

اعداد کاتالان و درخت دودویی

      

    2- تعداد درخت‌ها با n یال برابر $C_n$ است:

      

اعداد کاتالان و شمارش درخت

      

    3- تعداد پرانتزبندی‌های صحیح با استفاده از n جفت پرانتز باز و بسته برابر $C_n$ است:

      

n = 1:    ()

n = 2:    (())    ,    () ()

n = 3:    ((()))    ,    (()) ()    ,    () (())    ,    (() ())    ,    () () ()

  

    4- تعداد پرانتزبندی‌های صحیح n عبارت ریاضی برابر $C_{n-1}$ است:

      

n = 1:    (A)

n = 2:    (A B)

n = 3:    ((A B) C)    ,    (A (B C))

n = 4:    (((A B) C) D)    ,    ((A (B C)) D)    ,    ((A B) (C D))    ,    (A ((B C) D)    ,     (A (B (C D)))

  

    5- تعداد روش‌های مثلث‌بندی یک چندضلعی محدب با n + 2 ضلع برابر $C_n$ است:

      

اعداد کاتالان و مثلث‌بندی چندضلعی محدب

      

    6- ...

    با بررسی تحلیلی این مسائل، رابطه‌ی بازگشتی زیر برای محاسبه‌ی جملات دنباله‌ی اعداد کاتالان به دست آمده است:

      

\[ C_n = \sum_{i=0}^{n-1} \; C_i \; C_{n-i-1} \qquad , \qquad C_0 = 1 \]

      

    این تعریف، مقدار جمله‌ی nام دنباله را به مقادیر تمام جملات قبلی وابسته می‌کند. به عنوان مثال:

      

$C_1 = C_0 \times C_0 = 1 \times 1 = 1$

$ C_2 = C_0 \times C_1 + C_1 \times C_0 = 1 \times 1 + 1 \times 1 = 2 $

$ C_3 = C_0 \times C_2 + C_1 \times C_1 + C_2 \times C_0 = 1 \times 2 + 1 \times 1 + 2 \times 1 = 5 $

  

پیاده‌سازی به روش تقسیم و غلبه

  [بازگشت به فهرست]

اولین و ساده‌ترین پیاده‌سازی برای محاسبه‌ی اعداد کاتالان، پیاده‌سازی بازگشتی رابطه‌ی فوق است:

      

long catalan_1(int n){
  if(n == 0)
    return 1;
  long i, sum = 0;
  for(i = 0 ; i < n ; i++)
    sum += (catalan_1(i) * catalan_1(n - i - 1));
  return sum;
}

  

    این قطعه کد یک پیاده‌سازی تقسیم و غلبه برای محاسبه است که تعداد اعمال ضرب و جمع مورد نیاز آن از مرتبه‌ی اجرای نمایی $ \theta( 3^n)$ است (چرا؟). چنین مرتبه‌ای نشان از عدم کارایی محاسبه با این روش دارد.

      

پیاده‌سازی به روش برنامه‌نویسی پویا

  [بازگشت به فهرست]

روش تقسیم و غلبه را کنار گذاشته و روش برنامه‌نویسی پویا را امتحان می‌کنیم. در این روش به جای حرکت از کل به جزء و محاسبه‌ی بازگشتی، از جزء به کل حرکت کرده و جملات دنباله از مقادیر کوچکتر به مقادیر بزرگتر محاسبه می‌شود:

      

long catalan_2(int n, long catalan[]){
  int i, j;
  catalan[0] = 1;
  for(i = 1 ; i <= n ; i++){
    catalan[i] = 0;
    for(j = 0 ; j < i ; j++)
      catalan[i] += catalan[j] * catalan[i - j - 1];
  }
  return catalan[n];
10 }

  

    همانگونه که از ساختار حلقه‌های تکرار مشخص است، مرتبه‌ی اجرای این پیاده‌سازی $\theta(n^2)$ است که در مقایسه با تابع قبلی بهبود چشم‌گیری دارد. علاوه بر این، با استفاده از این تابع تمام جملات کوچکتر یا مساوی n محاسبه شده و در آرایه‌ی catalan ذخیره می‌شود.

      

رابطه‌ی غیربازگشتی اعداد کاتالان

  [بازگشت به فهرست]

تا به این جا با تعریف بازگشتی دنباله‌ی کاتالان سر و کار داشتیم. اما این دنباله‌ی بازگشتی را می‌توان با استفاده از روابط ریاضی حل کرده و به یک رابطه‌ی غیربازگشتی دست یافت.

    حل تحلیلی دنباله‌ی کاتالان با استفاده از توابع مولد رابطه‌ی زیر را نتیجه می‌دهد:

      

\[ C_n=\frac{1}{n+1} \begin{pmatrix} 2n \\ n \end{pmatrix} \]

      

    این رابطه اعداد کاتالان را مستقل از جملات قبلی محاسبه می‌کند. اما نیاز به محاسبه‌ی ترکیب دو عدد دارد:

      

long catalan_3(int n){
  long c = combination(2 * n, n);
  return (c / n + 1);
}

  

    پیاده‌سازی تابع combination روش‌های مختلفی دارد که ترکیب $C(2n, n)$ را در بهترین حالت از مرتبه‌ی اجرای $\theta(n^2)$ محاسبه می‌کند. در نتیجه این روش مزیتی نسبت به روش برنامه‌نویسی پویا ندارد. اما بر اساس این رابطه، می‌توان رابطه‌ی بازگشتی زیر را نتیجه گرفت:

      

\[ C_n=\frac{2(2n-1)}{n+1}C_{n-1} \qquad , \qquad C_0=1 \]

      

    و آنرا به صورت زیر پیاده‌سازی کرد:

      

long catalan_4(int n){
  if(n == 0)
    return 1;
  return (((4 * n - 2) * catalan_4(n - 1)) / (n + 1));
}

  

    چنین تابعی اعداد کاتالان را به صورت بازگشتی و با مرتبه‌ی اجرای $\theta(n)$ محاسبه می‌کند. این بهبود در مرتبه را می‌توان با پیاده‌سازی به روش برنامه‌نویسی پویا تعمیم داد و علاوه بر پیاده‌سازی غیربازگشتی، تمامی جملات کوچکتر یا مساوی n را ذخیره کرد:

      

long catalan_5(int n, long catalan[]){
  int i;
  catalan[0] = 1;
  for(i = 1 ; i <= n ; i++)
    catalan[i] =  (((4 * i - 2) * catalan[i - 1]) / (i + 1));
  return catalan[n];
}

  

    به این ترتیب تمامی جملات دنباله‌ی کاتالان تا یک n دلخواه با مرتبه‌ی اجرای $\theta(n)$ محاسبه می‌شود.


این نوشته آخرین بار در تاریخ شنبه، ۲۰ شهریور ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        معرفی کتاب Concrete Mathematics برای علاقه‌مندان حل سوالات الگوریتمی و شرکت‌کنندگان مسابقات برنامه‌نویسی
        بررسی مسأله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
        آشنایی با الگوریتم استراسن برای محاسبه‌‌ی حاصلضرب ماتریس‌ها
        بررسی الگوریتم‌های محاسبه‌ی دنباله‌ی اعداد فیبوناچی و کارایی آنها
        بررسی روش‌های بسط لاپلاس، گاوس، فرمول تحویل و ساروس، برای محاسبه‌ی دترمینان ماتریس مربعی و پیچیده‌گی زمانی آنها
        آشنایی با الگوریتم فلوید-وارشال برای یافتن کوتاهترین مسیرهای گراف با قطعه کد نمونه به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی ادغامی با قطعه کدهایی به زبان برنامه‌نویسی ++C
        بحث در مورد ضرب زنجیره‌ای ماتریس‌ها و روش پیاده‌سازی الگوریتم پرانتزبندی بهینه‌ی آن با روش تقسیم و حل و روش برنامه‌نویسی پویا
        آشنایی با روش مرتب‌سازی سریع، همراه با قطعه کدهای نمونه به زبان برنامه‌نویسی ++C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» پوریا

شنبه، ۲۴ فروردین ماه ۱۳۹۲، ساعت ۰۰:۰۶
ارائه الگوریتم های مختلف محاسبه خیلی عالی بود.
پیشرفت روز افزون رو برای سایت آرزومندم.03

» مریم

دوشنبه، ۱۵ آبان ماه ۱۳۹۱، ساعت ۱۶:۴۰
باسلام
ازاطلاعات بسیار خوب وزحمت های فراوان شما تشکر   میکنم.یک سوال داشتم در صورت امکان جواب ان را به ایمیلم بفرستید:روش محاسبه دومین بزرگترین ودومین کوچکترین با استفاده از ارایه

» taha

شنبه، ۷ آبان ماه ۱۳۹۰، ساعت ۲۱:۲۹
سایت خوبی دارید.01 امتیاز5

» کاتالان

پنجشنبه، ۲۹ اردیبهشت ماه ۱۳۹۰، ساعت ۲۰:۵۹
05