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

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

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

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

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

       

بررسی روش‌های مختلف محاسبه‌ی ضرایب دوجمله‌ای نیوتن یا ترکیب دو عدد با قطعه کد به زبان برنامه‌نویسی ++C

تعریف ترکیب (Combination)

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

    تعداد حالت‌های انتخاب r (عدد صحیح و نامنفی) شیء از n (عدد صحیح و بزرگتر یا مساوی r) شیء را که ترتیب انتخاب اهمیت نداشته باشد، انتخاب r از n یا ترکیب r روی n گویند و به یکی از صورت‌های زیر نمایش می‌دهند:

      

\[C(n,r) = C_r^n= \begin{pmatrix} n \\ r \end{pmatrix} \]

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

    بر اساس اصل ضرب از اصول شمارش، ترکیب دو عدد از رابطه‌ی زیر قابل محاسبه است:

      

\[\begin{pmatrix} n \\ r \end{pmatrix} = \frac{n!}{(n-r)!\cdot r!} \]

      

    که منظور از !n، فاکتوریل عدد صحیح و نامنفی n است:

      

\[n! = n \times (n-1)! \;, \qquad 0! = 1 \]

\[n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1 \]

      

    ترکیب دو عدد کاربردهای بسیاری در محاسبات ریاضی دارد:

    1- تعداد زیرمجموعه‌های r عضوی یک مجموعه‌ی n عضوی برابر (C(n, r است.

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

      

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

      

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

      

\[{(a+b)}^n = \sum_{i=0}^{n} \begin{pmatrix} n \\ i \end{pmatrix} a^{n-i}b^i \]

      

    4- تعداد جواب‌های معادله‌ی سیاله‌ی (یا دیوفانت) X1 + X2 + X3 + ... + Xn = k با شروط Xi ≥ 0 و k ≥ 0 برابر با (C(n + k - 1, k  است.

    5- ...

    هر کدام از این کاربردها و مباحث مرتبط، به بیان‌های مختلف در سوالات مسابقات برنامه‌نویسی نیز به چشم می‌خورد. مسأله‌ی مربی ناامید نمونه‌ای از این سوالات است.

    با توجه به شرط n ≥ r ≥ 0، اگر ترکیب r روی هر n را در سطرهای زیر هم بنویسیم، جدولی مثلثی شکل به وجود می‌آید که به مثلث خیام - پاسکال مشهور است:

      

\[\begin{matrix} \begin{pmatrix}0\\0\end{pmatrix} & & & & \\ \begin{pmatrix}1\\0\end{pmatrix} & \begin{pmatrix}1\\1\end{pmatrix} & & & \\ \begin{pmatrix}2\\0\end{pmatrix} & \begin{pmatrix}2\\1\end{pmatrix} & \begin{pmatrix}2\\2\end{pmatrix} & & \\ \begin{pmatrix}3\\0\end{pmatrix} & \begin{pmatrix}3\\1\end{pmatrix} & \begin{pmatrix}3\\2\end{pmatrix} & \begin{pmatrix}3\\3\end{pmatrix} & \\ \begin{pmatrix}4\\0\end{pmatrix} & \begin{pmatrix}4\\1\end{pmatrix} & \begin{pmatrix}4\\2\end{pmatrix} & \begin{pmatrix}4\\3\end{pmatrix} & \begin{pmatrix}4\\4\end{pmatrix} \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix} = \begin{matrix} 1 & & & & \\ 1 & 1 & & & \\ 1 & 2 & 1 & & \\ 1 & 3 & 3 & 1 & \\ 1 & 4 & 6 & 4 & 1 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{matrix} \]

      

پیاده‌سازی محاسبه‌ی ترکیب دو عدد

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

بر اساس تعریف فوق، ترکیب دو عدد با استفاده از تابع combination_1 در زبان برنامه‌نویسی ++C قابل محاسبه است:

      

long factorial(int n){
  if(  n == 0)
     return 1;
  return n * factorial(n - 1);
}
  
long combination_1(int n, int r){
  long fn = factorial(n);
  long fr = factorial(r);
10   long fnr = factorial(n - r);
11   return (fn / (fr * fnr));
12 }

  

    محاسبه‌ی ترکیب دو عدد نیاز به محاسبه‌ی فاکتوریل سه عدد n ،n - r و r دارد. محاسبه‌ی این سه فاکتوریل از مرتبه‌ی اجرای خطی هستند. در نتیجه تابع combination_1 هم از مرتبه‌ی خطی $\theta(n)$ است.

    میزان رشد تابع فاکتوریل با افزایش مقدار ورودی آن بسیار زیاد است. به عنوان مثال، !10 یک عدد هفت رقمی و !100 یک عدد 158 رقمی است. در نتیجه امکان ذخیره کردن دقیق اعداد حاصل از فاکتوریل در متغیرهای معمول زبان‌های برنامه‌نویسی ممکن نیست. این در حالی است که ترکیب دو عدد، علیرغم بزرگ بودن فاکتوریل ورودی‌های آن، ممکن است عدد کوچکی باشد:

      

\[\begin{pmatrix}100\\99\end{pmatrix} = \frac{100!}{(100-99)! \times 99!} = \frac{100!}{99!}= 100 \]

  

    یک راه حل آن است که در صورت نیاز با استفاده از توابع و کلاس‌ها، ذخیره‌سازی اعداد صحیح بزرگ را تعریف و مدیریت کنیم. در این حالت می‌توان از بهینه‌سازی ضرب اعداد بسیار بزرگ و مسائل مربوطه هم استفاده کرد.

    راه حل دیگر استفاده از رابطه‌ی زیر است که از تعریف فوق به راحتی قابل اثبات است:

      

\[\begin{pmatrix}n\\r\end{pmatrix} = \begin{pmatrix}n-1\\r\end{pmatrix} + \begin{pmatrix}n-1\\r-1\end{pmatrix} \qquad , \qquad \begin{pmatrix}n\\0\end{pmatrix} = \begin{pmatrix}n\\n\end{pmatrix} = 1 \]

  

    این رابطه یک الگوریتم بازگشتی برای محاسبه‌ی ترکیب روی n بر اساس ترکیب روی n - 1 را نشان می‌دهد.

      

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

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

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

      

long combination_2(int n, int r){
  if(n == r || r == 0)
    return 1;
  return (combination_2(n - 1, r) + combination_2(n - 1, r - 1));
}

  

    این تابع فراخوانی بازگشتی را تا جایی ادامه می‌دهد که r برابر صفر یا n شود. در این حالت مقدار یک را باز می‌گرداند. پس می‌توان گفت خروجی نهایی از جمع زدن (C(n, r تا عدد یک به دست می‌آید که به C(n, r) - 1 عمل جمع نیاز دارد. بنابراین نیاز به ذخیره کردن اعداد بسیار بزرگ وجود ندارد. اما این روش معایبی نیز دارد.

    تعریف بازگشتی فوق به گونه‌ای است که محاسبات تکراری وجود دارد. فراخوانی تابع به صورت (combination_2(n, r، دو فراخوانی (combination_2(n - 1, r  و (combination_2(n - 1, r - 1 را به دنبال دارد. خود این دو فراخوانی هر کدام به صورت مجزا تابع را به صورت (combination_2(n - 2, r - 1 فراخوانی می‌کنند. یعنی (combination_2(n - 2, r - 1 دو بار به صورت تکراری محاسبه می‌شود. هر چقدر عمق فراخوانی‌های بازگشتی بیشتر باشد، این تکرارها بیشتر می‌شود. چنین حالتی را در اصطلاح همپوشانی گویند.

    ثابت شده است که برای محاسبه‌ی (C(n, r  با تابع combination_2، تعداد  C(n, r) * 2 - 1 بار تابع  فراخوانی می‌شود. چنین عددی در بدترین حالت از مرتبه‌ی نمایی است که چندان قابل قبول نیست.

    نکته: بدترین حالت این محاسبه‌ زمانی است که r برابر بزرگترین عدد صحیح کوچکتر یا مساوی نصف n (یا به اصطلاح جزء صحیح n / 2) باشد. در این حالت به ازای یک n ثابت، (C(n, r بیشترین مقدار خود را دارد (چرا؟).

    راه حلی که به نظر می‌رسد بتوان این همپوشانی را مهار کرد، ذخیره کردن محاسبات انجام شده در یک آرایه و استفاده‌ی مجدد از آنها در صورت نیاز است:

      

long comb[MAX][MAX] = { 0 };
  
long combination_3(int n, int r){
  if(r == n || r == 0)
    comb[n][r] = 1;
  if(comb[n][r] == 0)
    comb[n][r] = combination_3(n - 1, r) + combination_3(n - 1, r - 1);
  return comb[n][r];
}

  

    آرایه‌ی دو بعدی comb مقادیر ترکیب r روی n را در خود ذخیره می‌کند. در مقداردهی اولیه، تمامی عناصر آرایه را برابر صفر قرار می‌دهیم که مشخص می‌کند محاسبه‌ای انجام نشده است. در هر بار فراخوانی تابع، مقدار [comb[n][r بررسی می‌شود. اگر این مقدار برابر صفر باشد، نشان می‌دهد [comb[n][r قبلا محاسبه نشده است. چرا که (C(n, r عدد مثبت و غیر صفر است. اما اگر مقدار آن غیرصفر باشد، این مقدار به عنوان نتیجه‌ی بازگشت داده می‌شود.

    توجه: مقداردهی اولیه‌ی صفر به تمامی عناصر آرایه - یا حداقل قسمت مورد نیاز - خود یک فرآیند زمان‌بر است.

      

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

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

تابع combination_3 اگرچه محاسبات تکراری را انجام نمی‌دهد، اما همچنان فراخوانی‌های بازگشتی تو در تو وجود داشته و سربار زمانی و حافظه ایجاد می‌کند. علت این مسأله در ذات روش تقسیم و غلبه و حل کل به جزء مسأله است. بر اساس روش برنامه‌نویسی پویا، مسأله را به صورت جزء به کل نیز می‌توان حل کرد.

    با توجه به جدول خیام - پاسکال، در روش کل به جزء و تقسیم و غلبه، با فراخوانی‌های بازگشتی از (C(n, r به سمت مقادیر کوچکتر n حرکت کرده و با بازگشت مجدد از توابع، محاسبات انجام شده و مقدار (C(n, r به دست می‌آید. در روش جزء به کل و برنامه‌نویسی پویا، محاسبات از بالای جدول خیام - پاسکال به سمت پایین و محل (C(n , r انجام می‌شود. بنا به خاصیت مطرح شده برای ترکیب دو عدد، اعداد هر سطر از روی اعداد سطر بالاتر قابل محاسبه است. با پیش‌روی محاسبه‌ی این سطرها تا سطر nام - که (C(n, r در آن قرار دارد - محاسبه به پایان می‌رسد:

      

long combination_4(int n, int r){
  int i, j;
  for(i = 0 ; i <= n ; i++){
    comb[i][0] = 1;
    comb[i][i] = 1;
  }
  for(i = 2 ; i <= n ; i++)
    for(j = 1 ; j <= i - 1 ; j++)
      comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
10   }
11   return comb[n][r];
12 }

  

    تابع combination_4 نه تنها مقدار (C(n, r که تمام ترکیبات (C(m, r با شرط n ≥ m را محاسبه و در آرایه‌ی comb ذخیره می‌کند. به عبارت دیگر، این تابع n + 1 سطر اول مثلث خیام - پاسکال را در آرایه‌ی comb ذخیره کرده و مقدار (C(n, r را به عنوان خروجی تابع بازمی‌گرداند. پیچیده‌گی زمانی این الگوریتم $\theta(n^2)$ است (چرا؟).

    اگر هدف صرفا پیدا کردن مقدار (C(n, r باشد، می‌توان محاسبات را کمی محدودتر کرد. چرا که برای محاسبه‌ی (C(n, r نیاز به محاسبه‌ی تمام مقادیر سطرهای فوقانی مثلث خیام - پاسکال نیست:

      

long combination_5(int n, int r){
  int i, j, min, max;
  for(i = 0 ; i <= n - r ; i++)
    comb[i][0] = 1;
  for(i = 0 ; i <= r ; i++)
    comb[i][i] = 1;
  for(i = 2 ; i <= n ; i++){
    min =  (r + i - n > 1) ? (r + i - n) : 1;
    max = (i - 1 < r) ? i - 1 : r;
10     for(j = min ; j <= max ; j++)
11       comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
12   }
13   return comb[n][r];
14 }

  

    تعداد محاسبات حلقه‌ی داخلی این تابع برابر (r (n - r است که از شکل زیر نیز قابل استنباط است:

      

مثلث خیام - پاسکال و محاسبه‌ی ترکیب

      

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

    این الگوریتم را از نظر حافظه‌ی مصرفی نیز می‌توان بهینه کرد. همانگونه که بحث شد، هر سطر مثل خیام - پاسکال تنها به سطر قبلی خود وابسته است. بنابراین، اگر ذخیره کردن مقادیر غیر از (C(n, r اهمیت نداشته باشد، می‌توان به جای آرایه‌ی دوبعدی و ذخیره کردن مقادیر سطرهای مختلف، از یک آرایه‌ی خطی برای ذخیره کردن سطر قبلی استفاده کرد. مقادیر سطر جدید را هم می‌توان با شروع از انتهای سطر - و نه ابتدا - در همان آرایه محاسبه و ذخیره کرد. چنین الگوریتمی حافظه‌ی مصرفی را از $\theta(n^2)$ به $\theta(n)$ کاهش می‌دهد:

      

long combination_6(int n, int r){
  int i, j;
  long comb[MAX];
  for(i = 0 ; i <= n ; i++)
    for(j = i ; j >= 0 ; j--)
      if(j == 0 || j == i)
        comb[j] = 1;
      else
        comb[j] = comb[j] + comb[j - 1];
10   return comb[r];
11 }

  


این نوشته آخرین بار در تاریخ جمعه، ۸ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        بررسی مسأله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی 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

 


» مینا خدایی

سه‌شنبه، ۲۵ اسفند ماه ۱۳۹۴، ساعت ۰۸:۴۹
باسلام و عرض ادب
احتراما خواهشمند م به اینجانب جهت حل مسائل پژوهش عملیاتی 2 از طریق روش راسل کمک نمایید . باتشکر

» nafas

دوشنبه، ۲ آذر ماه ۱۳۹۴، ساعت ۱۵:۰۰
سلام من دنبالیه سایتی هستم که روی سوال بنویسم جوابو بهم نشون بده شایدبعضیا بخندن ولی خب چیکارکنم این درس مبانی خیلی خیلی سخته خواهشا کمکم کنین01


دوشنبه، ۲ آذر ماه ۱۳۹۴، ساعت ۱۷:۲۵
مسعود:
سلام
می‌تونید سوالتون رو از طریق موتورهای جستجو (مثل گوگل) بپرسید. محل‌هایی رو که در مورد اون مطلب بحث شده براتون می‌یاره. اما لزوما ممکنه جواب سوالتون رو اون جاها پیدا نکنید. در کل چنین سایتی که سوال رو بنویسید و جواب رو نشون بده وجود نداره.

» الناز

شنبه، ۲۵ مهر ماه ۱۳۹۴، ساعت ۲۰:۱۸
عرض سلام و خسته نباشید

در صورت موجود بودن الگوریتمی به غیر از روش هورنر برای محاسبه ی جواب یک چند جمله ای(با داشتن ضرایب ثابت ان) ممنون میشم معرفیش کنید.

با تشکر


شنبه، ۲۵ مهر ماه ۱۳۹۴، ساعت ۲۲:۲۸
مسعود:
سلام

تا جایی که خبر دارم و تحقیق مختصری که انجام دادم، الگوریتم بهتری از هورنر وجود نداره.

منطقی هم به نظر می‌رسه. وقتی 1 + n جمله داریم، حداقل هر کدوم رو یک بار باید بازدید و محاسبه‌ای روی اون انجام بدیم. پس امکان نداره مرتبه کمتر از n باشه. مزیت الگوریتم هورنر در این هست که نیازی به عملیات توان‌رسانی (و در نتیجه افزایش زمان یا مرتبه‌ی اجرایی) نیست.

» B

سه‌شنبه، ۲ تیر ماه ۱۳۹۴، ساعت ۱۰:۲۶
عالی بود

» Anonymous

چهارشنبه، ۱۲ آذر ماه ۱۳۹۳، ساعت ۱۹:۱۶
عالی!

» محمد

دوشنبه، ۱۸ دی ماه ۱۳۹۱، ساعت ۱۰:۰۰
آقا کرتون عالیه واقعا لذت بردم
خسته نباشید

» محمد

پنجشنبه، ۲ آذر ماه ۱۳۹۱، ساعت ۰۹:۰۵
دخترا اکثرشون دنبال لقمه آماده هستن !
لطفا روشی ارائه بفرمایید برای پیاده سازی آرایه های چند بعدی بصورت پویا در c++ .
سپاسگزارم
التماس دعا .

» علیرضا ملکوتی

سه‌شنبه، ۲۵ مهر ماه ۱۳۹۱، ساعت ۱۱:۱۸
الگوریتم جزئ صحیح رو میخواستم

» فاطمه

چهارشنبه، ۱۱ مرداد ماه ۱۳۹۱، ساعت ۱۳:۲۵
بسیار ممنون و سپاسگزارم بخاطر وبسایت خوبتون06060606

» nima.sh

دوشنبه، ۸ اسفند ماه ۱۳۹۰، ساعت ۰۸:۵۴
salam dooste aziz
mishe lotf konid kole amoozeshe c++ ro be soorate PDF baram mail konid
az web ziba va por mohtavatoon mamnoon

» بهادر محسنی تبار

شنبه، ۱۰ دی ماه ۱۳۹۰، ساعت ۱۵:۱۱
دمت گرم عالی بود06

» hossein

سه‌شنبه، ۱۰ آبان ماه ۱۳۹۰، ساعت ۰۲:۳۴
بسیار ممنون استاد
خیلی به دردم خورد
ممنون060112

» مرتضی

شنبه، ۷ آبان ماه ۱۳۹۰، ساعت ۱۳:۰۳
salam . babate in posti ke dadin kheyli mamnoon. jozve tamrinayi bood ke ostadam behem dade bood . enshalah hamishe movafagh va pirooz bashid .

» ندا

شنبه، ۲۸ خرداد ماه ۱۳۹۰، ساعت ۱۴:۳۷
خیلی ممنون خیلی به این لرنامه نیاز داشتم01
اگه میشه یه برنامه که ضرب دو ماتریس را انجام دهد رو برام بفرستین
واقعا ممنونم،موفق باشید

» ندا

شنبه، ۲۸ خرداد ماه ۱۳۹۰، ساعت ۱۴:۳۷
خیلی ممنون خیلی به این لرنامه نیاز داشتم01
اگه میشه یه برنامه که ضرب دو ماتریس را انجام دهد رو برام بفرستین
واقعا ممنونم،موفق باشید

» فرشته

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