الگوریتم ضریب دو جمله‌ای با استفاده از یک آرایه

[mehr83]

الگوریتم ضریب دو جمله‌ای با استفاده از برنامه نویسی پویا و آرایه دو بعدی به صورت زیر است



int bin (int n , int k)
{
index i,j ;
int B[0..n][0..K];
for (i=1 ; j<=n ; i++)
for(j=0 ; j<=minimum(i,k) ; j++)
if (j==0 || j==i)
B[i][j]=1;
else
B[i][j]=B[i-1][j-1]+B[i-1][j];
return B[n][k];
}

حال با دانستن

( n ) = ( n )
k n-kچطور می‌توانیم الگوریتم را طوری اصلاح کنیم که از آرایه یک بعدی استفاده کند؟

----------------------------------------------------------------------
فروش ويژه مجموعه كامل محصولات آموزش برنامه نويسي AppDev
Asp.NET , Visual Basic.NET , Visual C#.NET , SQL Server 2008 , Web Service , LINQ , Html , Xml , SharePoint
اطلاعات بيشتر در
http://sadrasystem.org (http://sadrasystem.org/)

[mehr83]

کسی راه حلی به ذهنش نمیرسه؟

----------------------------------------------------------------------
فروش ويژه مجموعه كامل محصولات آموزش برنامه نويسي AppDev
Asp.NET , Visual Basic.NET , Visual C#.NET , SQL Server 2008 , Web Service , LINQ , Html , Xml , SharePoint
اطلاعات بيشتر در
http://sadrasystem.org (http://sadrasystem.org/)

[ironclip]

منم دنبال این موضوع هستم کسی هست کمک کنه ؟؟

[qwerty11]

تو هر مرحله عناصر آرایه ی B[i-1] I رو توی یه آرایه به نام X ذخیره کن. در این صورت میشه گفت :


B[j] = B[j-1]+ X[j] I


البته اون فرمولی که بالا نوشته شده بود هم اشتباه بود !
---------------------------------------------------------------------
اما اگر میخوای فقط از یه آرایه ی یه بعدی استفاده کنی باید از مثلث خیام استفاده کنی :


1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


که خونه ی j ام ردیف i ام به ما تعداد راه های انتخاب j عنصر از بین i عنصر رو نشون میده.

[mehmir]

سلام
با استفاده از مثلث خیام به کد زیر میرسیم که این کار رو با یک آرایه انجام میده

برای بدست آوردن (c(n,k


int index(n,k){
int sum = 0;
for(int i= 0 ;i<=n ; i++)
sum = sum + i;
return (sum + k)
}
int c(n,k){
int j=0;
int x[index(n,k)];
for(int i =0;j<=n;){
i++;
j=j+i;
x[j]=1;
x[j-1]=1;
}
x[index(n,k)] = c(n-1,k-1) + C(n-1,k);
return x[index(n,k)]
}