یه تحلیل مختصر از الگوریتم ضرب دو چند جمله ای به روش تقسیم و غلبه

[cjNet]

سلام به همه دوستان .
من یه برنامه برای طراحی الگوریتم نوشتم که دو چند جمله ای رو از ورودی می گیره و آنها را یک بار با روش معمولی و یه بار با روش تقسیم و غلبه در هم ضرب میکنه .
روش معمولی که سادست اما نحوه کار روش تقسیم و غلبه رو در این برنامه من درک نکردم .
روش کلی کار این برنامه به این صورت هست که ابتدا بزرگترین درجه چند جمله ای رو می گیره سپس ضریب هر درجه چند جمله ای رو تو یه آرایه ذخیره می کنه ( مثلا ضریب درجه 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]

با سلام. مهندس جان.الكوريتم هاي تقسيم وغلبه در كل كارشما به جند قسمت تفسيم ميكند و به روش بازكشتي حل ميشود . كجاش برات نامفهوم هست

[cjNet]

با سلام. مهندس جان.الكوريتم هاي تقسيم وغلبه در كل كارشما به جند قسمت تفسيم ميكند و به روش بازكشتي حل ميشود . كجاش برات نامفهوم هست
ممنون ازت مهندس .
مفهوم الگوریتم تقسیم و غلبه رو می دونم . اما نمی دونم در این برنامه چه مراحلی رو طی می کنه تا دو تا چند جمله ای رو در هم ضرب کنه و حاصل رو برگردونه .
من باید این برنامه رو به استاد ارئه کنم و بهش توضیح بدم . ( مشکل اینه :متفکر: )
ممنون میشم اگه یه توضیح کوچیک در این رابطه بدی @

[hjran abdpor]

دوست عزیز تا کی وقت دارید به استاداتون ارئه بدین ؟؟؟؟؟؟؟؟؟؟؟

[shahmohammadi]

سلام.
كافيه به يه فرمول رياضي توجه كنيم تا دركش راحت بشه ( كه هست).
[LTR][CPP](a+b)(c+d)=ac+ad+bc+bd
حالا اگه a,b,c,d همه خودشون يه چند جمله اي ديگه باشن بازم اين فرمول به كار مي ره. و همون طور كه ديدين حالت پايه اين بازگشتي حالتيه كه هر چند جمله اي يه جمله باشن.
البته همونطور كه خودتون هم نوشتين اين برنامه فقط براي حالتيه كه هر دو چند جمله اي اندازه شون بكي باشه.
باز اگه مشگلي بود ما در خدمتيم.

[cjNet]

دوست عزیز تا کی وقت دارید به استاداتون ارئه بدین ؟؟؟؟؟؟؟؟؟؟؟
بازم سلام دوست عزیز .
تا سه شنبه 17/3 وقت دارم . خیلی ممنون میشم اگه کمکم کنید .



سلام.
كافيه به يه فرمول رياضي توجه كنيم تا دركش راحت بشه ( كه هست).
[LTR][CPP](a+b)(c+d)=ac+ad+bc+bd
حالا اگه a,b,c,d همه خودشون يه چند جمله اي ديگه باشن بازم اين فرمول به كار مي ره. و همون طور كه ديدين حالت پايه اين بازگشتي حالتيه كه هر چند جمله اي يه جمله باشن.
البته همونطور كه خودتون هم نوشتين اين برنامه فقط براي حالتيه كه هر دو چند جمله اي اندازه شون بكي باشه.
باز اگه مشگلي بود ما در خدمتيم.

ممنون ازت دوست من .
دارم خودمم بررسی می کنم اگه سوالی بود بازم مزاحمت میشم @

[hjran abdpor]

با سلام............
ببخشید دیر جواب دادم خیلی سرم شلوغ بود.......
اگه صبر کنید
من براتون یه فایل میفرستم خوب بخونید متوجه میشد ............
البته اگه صبر کنید
باتشکر

[cjNet]

با سلام............
ببخشید دیر جواب دادم خیلی سرم شلوغ بود.......
اگه صبر کنید
من براتون یه فایل میفرستم خوب بخونید متوجه میشد ............
البته اگه صبر کنید
باتشکر

ممنون .
منتظرم @

[mortezamsp]

عرضم حضور انورتون که (البته ببخشید دیر شد) . . . این تابع داره هر دوتا دوجمله ای رو نصف میکنه و اونها رو در هم ضرب میکنه :
A * B = (a1+a2)*(b1+b2) = a1b1 + a1b2 + a2b1 + a2b2
عبارات اونقدر نصف میشن تا طولشون بشه یک ، اونقت دو تا عددو ضرب میکنه.