بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره
حمایت از وب‌گاه:
حمایت از این صفحه:
دنباله‌ی اعداد کاتالان و محاسبه‌ی آن - الگوریتمستان
الگوریتمستان
4214.125.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)$ محاسبه می‌شود.


این نوشته آخرین بار در تاریخ شنبه، ۲۰ شهریور ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 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