یه تحلیل مختصر از الگوریتم ضرب دو چند جمله ای به روش تقسیم و غلبه
سلام به همه دوستان .
من یه برنامه برای طراحی الگوریتم نوشتم که دو چند جمله ای رو از ورودی می گیره و آنها را یک بار با روش معمولی و یه بار با روش تقسیم و غلبه در هم ضرب میکنه .
روش معمولی که سادست اما نحوه کار روش تقسیم و غلبه رو در این برنامه من درک نکردم .
روش کلی کار این برنامه به این صورت هست که ابتدا بزرگترین درجه چند جمله ای رو می گیره سپس ضریب هر درجه چند جمله ای رو تو یه آرایه ذخیره می کنه ( مثلا ضریب درجه 3 رو در خانه شماره 3 و ضریب درجه 0 رو در خانه شماره 0 آرایه ذخیره می کنه ) .
از همه دوستان اگه یه توضیح ( هر چند کلی ) در رابطه با روش کار الگوریتم تقسیم و غلبه در این برنامه بدن ممنون میشم ...
روش معمولی ضرب دو چند جمله ای
Algorithm (A, B, C)
{
for i=0 to 2n
C[i]=0;
for i=0 to n
for j=0 to n
C[i+j]=C[i+j]+A[i]*B[j];
}
روش تقسیم و غلبه ضرب دو چند جمله ای :
void polynomial(int low1,int high1,int low2,int high2)
{
int n,k;
n=high1-low1+1;
if(n==1)
C[low1+low2]+=A[low1]*B[low2];
else{
k=n/2;
polynomial(low1,low1+k-1,low2,low2+k-1);
polynomial(low1,low1+k-1,low2+k,high2);
polynomial(low1+k,high1,low2,low2+k-1);
polynomial(low1+k,high1,low2+k,high2);
}
A آرایه ای شامل ضرایب چند جمله ای اول به طول n
B آرایه ای شامل ضرایب چند جمله ای اول به طول n
C آرایه ای شامل حاصل ضرب دو چند جمله ای با طول 2n
ممنون از همتون @
پاسخ با نقل قول
نوشته شده توسط hjran abdpor
)
