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

[مینو_ا]

سلام
من الگوریتم ضرب دو چند جمله ای به روش تقسیم و غلبه رو می خواستم.
ممنون میشم کمکم کنید؟؟؟؟

 

[مینو_ا]

هیچ کس نمی تونه برای نوشتن این الگوریتم به من کمک کنه؟

 

[www.ahvazcity.net]

فرمول ریاضیش رو بنویسید نوشتن الگوریتمش خیلی سخت نیست .(شرمنده یکم ریاضیاتم ضعیفه)

 

[مینو_ا]

A(X)= a0 X^0+ a1X^1+a2X^2+…+anX^n
B(X)=b0 X^0+ b1X^1+b2X^2+…+bmX^m
A(X)*B(X)=( a0 X^0)*( b0 X^0+ b1X^1+b2X^2+…+bmX^m)+( a1X^1)*( b0 X^0+ b1X^1+b2X^2+…+bmX^m)+…+( anX^n)*( b0 X^0+ b1X^1+b2X^2+…+bmX^m)


an و bm هم که اعداد طبیعین

 

[www.ahvazcity.net]

واقعیتش از این فرمولت چیزی نفهمیدم می دم یه نفر این فرمولتو واسم توضیح بده تا فردا برات می نویسم

 

[مینو_ا]

 

[مینو_ا]

1. If n = 1 or n = 2 solve the problem directly; Otherwise:
2. Construct four half-size polynomials a, b, c and d, of degree n/2 - 1, out of X and Y. Divide X up into parts, a and b, and divide Y up into parts c and d -- so a and c will have the low order coefficients (indices 0 through n/2 -1) of X and Y, and b and d will have the high order coefficients (indices n/2 through n -1).
3. Calculate the sums x' = a + b and y' = c + d -- note that x' and y' are also polynomials of degree n/2 - 1.
4. Calculate temp = x' . y' recursively. 5. Calculate ac, and bd recursively.
6. Let temp = temp - ac - bd;
7. Combine ac, bd, and temp, which are all polynomials of degree n - 1, into a new polynomial of degree 2n -1, placing ac in indices 0 through n - 1, bd in indices n through 2n - 1, and adding temp to the values now in indices n/2 through 3n/2 -1. Notice that the highest coefficient will be 0.

من این الگوریتم و پیدا کردم، میخوام با ++c بنویسم. اما هیچی ازش نمی فهمم. یعنی نمی فهمم این چند جمله ای رو چطوری ضرب میکنه!

 

[missa]

salam,begu daghighan be onvane vooroodi khuruji chi migire?

 

[مینو_ا]

اول درجه ی چند جمله ای رو میگیره(n) بعد ضرایب دو تا چند جمله ای رو! (a0 , a1, ... , an) بعدم ضربشونو چاپ میکنه!

 

[مینو_ا]

[LTR]

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

void polynomial(int low1,int high1,int low2,int high2)
{
int n,k;
n=high1-low1+1;
if(n==1)
C[low1+low2]=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);
}
}
int main()
{
int m,p,num,q,i,j,k;
num=1;
cout<<"enter the degree of polynomial:";
cin>>m;
p=m+1; //tedade jomalate chand jomleyi
while(){
if(num>=p)
break;
else
num=num*2;
} //tedade khanehaye array ra tavani az 2 gharar midahim ta harbar ke bar 2 taghsim mikonim baz ham darajeye chandjomleyi haye hasel barabar bashad
q=num-1;
public int A[0..q];
public int B[0..q];
public int C[0..q];
cout<<"A:"<<endl;
for(i=0;i<=m;i++){
cout<<"a"<<i<<"[x^"<<i<<"]:";
cin>>A;
cout<<endl;
}
cout<<"B:"<<endl;
for(j=0;j<=m;i++){
cout<<"b"<<j<<"[x^"<<j<<"]:";
cin>>B;
cout<<endl;
}
for(k=m+1;k<=q;k++){
A[k]=0;
B[k]=0;
}
polynomial(0,q,0,q);
cout<<"the result is:"<<endl;
for(i=q,i>0,i--)
cout<<C[q]<<"x^"<<q<<"+";
cout<<C[0];
return 0;
}

​

اما موقع اجرا شونصد تا ارور عجیب غریب میده که تا حالا ندیدم!
به نظر شما مشکلش کجاست؟

 

[مینو_ا]

دستتون درد نکنه، خیلی زحمت کشیدید! خودم بالاخره درستش کردم!
[LTR]#include<iostream.h>
void polynomial(int,int,int,int);
int A[100];
int B[100];
int C[200];
int main()
{
int m,p,num,q,i,j,k;
num=1;
cout<<"enter the degree of polynomial:";
cin>>m;
p=m+1; //tedade jomalate chand jomleyi
while(num<p){
num=num*2;
} //tedade khanehaye array ra tavani az 2 gharar midahim ta harbar ke bar 2 taghsim mikonim baz ham darajeye chandjomleyi haye hasel barabar bashad
q=num-1;

cout<<"A:"<<endl;
for(i=0;i<=m;i++){
cout<<"a"<<i<<"[X^"<<i<<"]:";
cin>>A;
cout<<endl;
}
cout<<"B:"<<endl;
for(j=0;j<=m;j++){
cout<<"b"<<j<<"[X^"<<j<<"]:";
cin>>B[j];
cout<<endl;
}
for(k=m+1;k<=q;k++){
A[k]=0;
B[k]=0;
}
polynomial(0,q,0,q);
cout<<"the result is:"<<endl;
for(i=2*m;i>0;i--)
cout<<"("<<C<<")"<<"X^"<<i<<"+";
cout<<"("<<C[0]<<")";
return 0;
}
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);
}
}
[/LTR]