X
تبلیغات
آموزش کامپیوتر - بسط دوجمله ای نیوتن به دو روش

آموزش کامپیوتر

بسط دوجمله ای نیوتن به دو روش

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

 

برنامه نویسی به روش تقسیم و حل:

در برنامه نویسی به روش تقسیم و حل (divide and conqure) مسأله مفروض به قسمت های کوچک تقسیم می شود. در صورتی که این قسمت های کوچک قابل تجزیه شدن نباشند پاسخ آنها با هم ترکیب می شود، و در نهایت جواب مسأله از ترکیب پاسخ مراحل مختلف به دست می آید. تقسیم و حل در برخورد با محاسبات تکراری بارها آنها را انجام می دهد. در واقع می توان گفت تقسیم و حل برای پاسخ دهی به مسأله درخت ترسیم می کند. برنامه نویسی به روش تقسیم و حل برای مسأله هایی که نیاز به محاسبات تکراری دارند مناسب نیست. برای این سری از مسأله ها روش برنامه نویسی پویا توصیه می شود.

 

برنامه نویسی به روش پویا:

برنامه نویسی به روش پویا (dynamic) شباهت هایی به تقسیم و حل دارد. در برنامه نویسی به روش پویا نیز مسأله به قسمت های کوچکتر تقسیم می شود. با این تفاوت که در برنامه نویسی به روش پویا آرایه ای در نظر می گیریم و پاسخ هر مرحله در آرایه ذخیره می شود، تا در صورت برخورد با محاسبات تکراری به جملات محاسبات قبل که در آرایه ذخیره شده اند رجوع کنیم. هدف در برنامه نویسی پویا حذف محاسبات تکراری است.

 

در ادامه با ارائه مثالی به بررسی اجمالی این دو روش می پردازیم: برنامه محاسبه ضرایب بسط دو جمله ای نیوتن.

اگر عبارت زیر را داشته باشیم محاسبه ضریب جمله سوم وقتی توان 2 است به راحتی قابل مشاهده و محاسبه است:

 

(a + b)² = a² + 2ab + b²

 

اما اگر توان عبارت بالا n باشد، و n را عددی مانند 10 فرض کنیم، بدست آوردن ضریب جمله jام کار مشکلی خواهد بود. همانطور که می دانید ضریب جمله jام بسط نیوتن برابر است با:

 

C(n , j) = n! / ( j! (n - j)! )

 

پس از دیدگاه ریاضی هدف ما بدست آوردن مقدار ترکیب j روی n است. اما برای اینکار از ضابطه فوق استفاده نمی کنیم، بلکه از رابطه بازگشتی زیر بهره می بریم:

 

C(n , r) = C(n - 1 , r) + C(n - 1 , r - 1)

 

با این شرط که

اگر r = 0 یا r = n آنگاه C(n , r) = 1

 

برای این محاسبه از تابع C با دو ورودی استفاده می کنیم. ورودی اول مقدار n و ورودی دوم مقدار r.

 

به روش تقسیم و حل:

int C( int n , int r )

{

 if ( r == 0 || r == n )

  return 1 ;

 else

  return C( n - 1 , r - 1 ) + C( n - 1 , r ) ;

}

 

با یک محاسبه ساده مشخص می شود که مرتبه (order) به روش این روش (تقسیم و حل) از جنس فاکتوریل است!!!

 

به روش برنامه نویسی پویا :

int C( int n , int r )

{

 int arr[10][10] , i , j ;

 for ( i = 0 ; i <= n ; i++ )

  for ( j = 0 ; j <= min( i , r ) ; j++)

   if ( j == 0 || j == i )

    arr[i][j] = 1 ;

   else

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

 return arr[n][r] ;

}

در این قطعه کد تابع فرعی min کوچکترین مقدار در بین ورودی های خود را بازمی گرداند، که می تواند به صورت زیر پیاده سازی شود:

 

int min ( int a , int b )

{

 return ( a < b ? a : b ) ;

}

 

با استفاده از این روش مرتبه از جنس فاکتوریل خارج شده و به فرم n*k در می آید! اما . . .

در برنامه ضریب دوجمله ای به روش برنامه نویسی پویا همواره یک ماتریس 10 در 10 در حافظه مقیم است. در این حالت مرتبه زمانی نسبت به روش تقسیم و حل بهبود پیدا کرده، اما باید فکری به حال مرتبه مکانی هم کرد. در واقع حافظه زیادی در روش ارائه شده بی مصرف باقی می ماند. علاوه بر این تنها قادر به محاسبات برای حداکثر n = 10 هستیم. پیشنهاد شما برای رفع این مشکل چیست؟

+ نوشته شده در  هفدهم آذر 1386ساعت 18:12  توسط طاهر  | 

 


طراحی سایت و بهینه سازی سایت توسط : گروه طراحان نگاه تازه