الگوریتمستان

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

تعریف ترکیب (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);

  long fnr = factorial(n - r);

  return (fn / (fr * fnr));

}

  

محاسبه ترکیب دو عدد نیاز به محاسبه فاکتوریل سه عدد 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];

  }

  return comb[n][r];

}

  

تابع 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;

    for(j = min ; j <= max ; j++)

      comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];

  }

  return comb[n][r];

}

  

تعداد محاسبات حلقه داخلی این تابع برابر (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];

  return comb[r];

}

  

مسعود اقدسی فام

مسعود اقدسی فام هستم.

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

algs.ir/spbzwlk     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
آخرین نوشته‌ها
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• آرزو
۱ بهمن ۱۳۸۵، ساعت ۰۷:۰۱

آقا مسعود ممنون از اینکه نظرمو حذف کردین....

مسعود اقدسی فام
۱ بهمن ۱۳۸۵، ساعت ۰۸:۰۴

دوستان عزیز

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

از این فرصت استفاده می کنم و از همه عزیزان عذر می خوام. بالاخص عزیزانی که نظر یا پیغامی این چند روزه ارسال کرده بودن. چون همه اونها متاسفانه از دست رفتن. آرزو خانم پیغام شما هم جزو این موارده.

موفق باشید.

• فاطمه
۱ بهمن ۱۳۸۵، ساعت ۰۸:۴۶

سلام آقا مسعود

چه عجب وبتون باز شد...

از كي قصد دارين تغييراتتونو اعمال كنين؟

راستي يه سوال كوچيك: شما مطالبتونو از چه منبعي مي گيرين؟

مسعود اقدسی فام
۱ بهمن ۱۳۸۵، ساعت ۱۱:۵۲

سلام فاطمه خانم

منم خوشحالم که سایت داره کار می کنه. البته موقتا. احتمالش زیاده که دوباره این پیغامها حذف بشن. امید زیادی دارم که تا فردا مشکل رفع بشه.

در مورد منبع مطالبم هم . . . من از هیچ منبعی استفاده نمی کنم. به غیر از این مطلب که دوست دیگه ای برام ارسال کردن بقیه رو خودم نوشتم.

مسعود اقدسی فام
۱ بهمن ۱۳۸۵، ساعت ۱۱:۵۸

در ضمن تغییرات هم به این زودی ها اعمال نمی شه. چون هم من فرصت کافی ندارم، هم اینکه چهارچوب کلی تغییرات فعلا مشخص نیست.

راستی . . . شما پیغام منو به آرزو حانم نرسوندین؟

• رضا
۲ بهمن ۱۳۸۵، ساعت ۱۴:۰۱

با سلام

لطفا کتابی مرجع و کامل در مورد ساختمان داده معرفی کنید

اگر قابل دانلود باشد چه بهتر؟!

از مطالب دیدنی و آموزنده شما متشکرم

رضا شاهورانی دانشجوی ریاضی کاربردی.

• بتول
۷ بهمن ۱۳۸۵، ساعت ۰۰:۲۹

سلام آقا مسعود.

خیلی قشنگ شده .امیدوارم موفق باشی.

• آرزو
۷ بهمن ۱۳۸۵، ساعت ۰۷:۱۵

دوباره سلام

خوب هستین؟

وبلاگ ماهم یه تغییر مهم کرد........ بگم؟ لوگوتونو اضافه کردم...خشگل شد...

• شاهرخ
۸ بهمن ۱۳۸۵، ساعت ۱۱:۲۹

سلام مهندس مسعود

چطوري؟ مي كوشي؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

آقا ما رو تو پيوندهاي دوستان اضافه كني ممنونت مي شم.

مرسي

مسعود اقدسی فام
۸ بهمن ۱۳۸۵، ساعت ۱۴:۵۲

شاهرخ خان

اولا که قراره شما بکوشی نه من!

دوما امرتون اجرا شد، شما هم لطف کن به سایت لینک بده.

سوما من امضای خودم رو گرفتم!!!

• شاهرخ
۹ بهمن ۱۳۸۵، ساعت ۱۳:۰۴

سلام

ممنون از لطفتان منم ان شاالله امضا رو مي گيرم.

.wwwshahrokh8000.blogfa.com

• Javad،دانشجوی کامپیوتر
۱۰ بهمن ۱۳۸۵، ساعت ۱۰:۵۷

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

مسعود اقدسی فام
۱۰ بهمن ۱۳۸۵، ساعت ۱۱:۳۰

جواد خان شما لطف داری

اگه یه کم بیشتر دقت کنی می بینی که قبلا همچین مراجعی معرفی شدن!

• فهیمه
۲۹ بهمن ۱۳۸۵، ساعت ۱۲:۵۳

خیلی ممنون

ببخشید در مورد مثالی که در بالا اشاره کردید این تابع چگونه)(n,r) را یدا می کند

مسعود اقدسی فام
۳۰ بهمن ۱۳۸۵، ساعت ۰۹:۵۹

فهیمه خانم

مقدار عبارت بر اساس رابطه بازگشتی که اشاره شده محاسبه می شه. شما کدوم قسمت رو خوب متوجه نشدید؟

• جواد
۱۶ اردیبهشت ۱۳۸۶، ساعت ۰۷:۲۵

سلام لطفا مثال هاي زيادي بگذاريد

• REZA
۱۹ شهریور ۱۳۸۶، ساعت ۲۱:۲۲

با سلام

زیاد وقتتان را نمیگیرم

میخواهم برنامه بنویسم اما نمیدانم از کجا وبا چه زبانی شروع کنم

• الهه
۶ دی ۱۳۸۶، ساعت ۲۱:۴۱

لطفا راههای مرتب سازی رو برام توضیح بدید.ممنون می شم

• RF
۲۴ مرداد ۱۳۸۷، ساعت ۱۷:۰۵

salam avalan az doostani ke in site ro edare mikonan be khatere matalebe zibashoon tashakor mikonam

dovoman mikhastam 1 chize koochik dar morede zarayebe baste niyoton begam khob age masale fagat be dast avardane in zarayeb bashe mishe az ravesh haye dige ke shayad behine tar bashan ham estefade kard 1 ki az in ravesh ha be vojood avordane MOSALASE KHAYAME adade marboot dar har satre in mosalas dagigan barabare zarayebe baste niyoton dar tavani hastand ke ba shomareye satre mosalas barabare (albate bayad shomare gozari az 0 bashe . ba in ravesh ham az share mohasebeye factorial ha ham rahat mishim va ham sarokaremoon ba amale jame ke kheyli behine tar az zarbe  

ba tashakor

• RF
۲۴ مرداد ۱۳۸۷، ساعت ۱۷:۲۸

ba arze mazerat email commente ghabli ro tasih mikonam

مسعود اقدسی فام
۲۴ مرداد ۱۳۸۷، ساعت ۲۳:۵۲

RF عزیز، در اینجا روش برنامه نویسی پویا پیاده سازی مثل خیام برای محاسبه ضرایب بسط نیوتن هستش.

• فرشته
۱ اردیبهشت ۱۳۹۰، ساعت ۲۲:۴۶

سلام یه برنامه میخواستم که دترمینان یه ماتریس 5*5 رو با استفاده از اشاره گرها در ارایه 2 بعدی محاسبه کنه .ممنون میشم اگه کدشو داشتین بهم بدین 03

• ندا
۲۸ خرداد ۱۳۹۰، ساعت ۱۴:۳۷

خیلی ممنون خیلی به این لرنامه نیاز داشتم01

اگه میشه یه برنامه که ضرب دو ماتریس را انجام دهد رو برام بفرستین

واقعا ممنونم،موفق باشید

• ندا
۲۸ خرداد ۱۳۹۰، ساعت ۱۴:۳۷

خیلی ممنون خیلی به این لرنامه نیاز داشتم01

اگه میشه یه برنامه که ضرب دو ماتریس را انجام دهد رو برام بفرستین

واقعا ممنونم،موفق باشید

• مرتضی
۷ آبان ۱۳۹۰، ساعت ۱۳:۰۳

salam . babate in posti ke dadin kheyli mamnoon. jozve tamrinayi bood ke ostadam behem dade bood . enshalah hamishe movafagh va pirooz bashid .

• hossein
۱۰ آبان ۱۳۹۰، ساعت ۰۲:۳۴

بسیار ممنون استاد

خیلی به دردم خورد

ممنون060112

• بهادر محسنی تبار
۱۰ دی ۱۳۹۰، ساعت ۱۵:۱۱

دمت گرم عالی بود06

• 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

• فاطمه
۱۱ مرداد ۱۳۹۱، ساعت ۱۳:۲۵

بسیار ممنون و سپاسگزارم بخاطر وبسایت خوبتون06060606

• علیرضا ملکوتی
۲۵ مهر ۱۳۹۱، ساعت ۱۱:۱۸

الگوریتم جزئ صحیح رو میخواستم

• محمد
۲ آذر ۱۳۹۱، ساعت ۰۹:۰۵

دخترا اکثرشون دنبال لقمه آماده هستن !

لطفا روشی ارائه بفرمایید برای پیاده سازی آرایه های چند بعدی بصورت پویا در c++ .

سپاسگزارم

التماس دعا .

• محمد
۱۸ دی ۱۳۹۱، ساعت ۱۰:۰۰

آقا کرتون عالیه واقعا لذت بردم

خسته نباشید

• Anonymous
۱۲ آذر ۱۳۹۳، ساعت ۱۹:۱۶

عالی!

• B
۲ تیر ۱۳۹۴، ساعت ۱۰:۲۶

عالی بود

• الناز
۲۵ مهر ۱۳۹۴، ساعت ۲۰:۱۸

عرض سلام و خسته نباشید

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

با تشکر

۲۵ مهر ۱۳۹۴، ساعت ۲۲:۲۸
• مسعود اقدسی فام

سلام

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

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

• nafas
۲ آذر ۱۳۹۴، ساعت ۱۵:۰۰

سلام من دنبالیه سایتی هستم که روی سوال بنویسم جوابو بهم نشون بده شایدبعضیا بخندن ولی خب چیکارکنم این درس مبانی خیلی خیلی سخته خواهشا کمکم کنین01

۲ آذر ۱۳۹۴، ساعت ۱۷:۲۵
• مسعود اقدسی فام

سلام

می‌تونید سوالتون رو از طریق موتورهای جستجو (مثل گوگل) بپرسید. محل‌هایی رو که در مورد اون مطلب بحث شده براتون می‌یاره. اما لزوما ممکنه جواب سوالتون رو اون جاها پیدا نکنید. در کل چنین سایتی که سوال رو بنویسید و جواب رو نشون بده وجود نداره.

• مینا خدایی
۲۵ اسفند ۱۳۹۴، ساعت ۰۸:۴۹

باسلام و عرض ادب

احتراما خواهشمند م به اینجانب جهت حل مسائل پژوهش عملیاتی 2 از طریق روش راسل کمک نمایید . باتشکر

• محمدیان
۳ خرداد ۱۳۹۹، ساعت ۱۱:۱۷

خیلی ممنون از زحمات و وبسایت عالیتون.

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

• علیرضا
۴ خرداد ۱۴۰۱، ساعت ۱۷:۳۳

سلام استاد خسته نباشید

چرا مرتبه اجرایی الگوریتم ضریب دو جمله ای nk است ؟

منظورم اینه یعنی چجوری اثبات میشه؟06