Полином - изчисляване на стойност, сума, разлика, умножение и делене на полиноми
Алгоритъм за изчисляване стойност на полином - polynomial
Алгоритъм за сума / разлика на полиноми
Алгоритъм за умножение на полиноми
Алгоритъм за делене на полиноми
Многочлен или полином, polynomial на реална променлива x е функция, е сума от степени на неизвестното x, умножени с реални числа.
Даден полином, многочлен f(x) се нарича нормиран, ако коефициентът пред най-високата степен на неизвестното е 1.
Полиноми със степен равна на 0 (константите) се наричат тривиални, а тези от степен по-голяма или равна на 1 - нетривиални.
Максималната степен или просто степен на полинома е равна на максималната степен на неизвестното имаща ненулев коефициент. Два полинома от една и съща степен са равни, ако коефициентите пред съответните им степени са равни.
Коренът q на уравнението Р(х) = 0 се нарича нула на полинома Р(х).
Един полином от степен n има най-много n реални корени.
Всеки полином Рn(х) с реални коефициенти може да се представи в каноничен вид - като произведение от двучлени:
Рn(х) = аn(х – х1)(х – х2)…(х - хn), където х1, х2,…, хn са нулите на Рn(х).
Полином от степен >0 с реални или комплексни коефициенти има поне един комплексен корен.
Изчисляване стойност на полином - polynomial
Всяка програма съдържаща цикличен алгоритъм може да се реализира, както с итерация, така и с рекурсия При изчисляване на полином може да се приложи циличен алгоритъм за изчисляване стойност по двучлени.
Нека разгледаме два начина за представяне на следния примерен полином: 5x^3 + 4x^2 + 3x + 2 = ( ( (5x + 4)x + 3)x + 2)
Вторият начин ни дава определени предимства при изчисляване на полинома посредством програма. Ако има изградена функция за изчисляване на двучлен, то стойността на целия полином може да бъде изчислена чрез итерация или рекурсия като на всяка стъпка се изчислява само един двучлен от многочлена.
Тук целта е да се представят успоредно двата варианта.
Задачата е следната да се изчисли стойност на полином, polynomial по въведени брой и стойност на коефициентите му и стойност на неизвестното:
Следващата примерна програма дава решена задача за изчисляване на
полином - polynomial чрез итерация
#include <iostream>
using namespace std;
double polinom (double koef[],int n,double x)
{int i;
// polinom P(x) = 5x^3 + 4x^2 + 3x + 2 move da se predstawi kato
//5x^3 + 4x^2 + 3x + 2 = ( ( (5x + 4)x + 3)x + 2)
double p=koef[0];
for(i=1;i<n;i++)
{p=p*x+koef[i];}//poetapno izchislqwane na stojnostta
return p;//izchislenata krajna stojnost na tozi polinom
}//polinom
void whod(double koef[],int n)
{int i;
for(i=0;i<n;i++)
{cout<<"Koeficient pred stepen ["<<n-i-1<<"] = "; cin>>koef[i];
}
}
int main()
{double koef[50],x;
int n;
char ose;
cout<<"Da se systawi programa za izchislqwane stojnost na polinom pri\n";
cout<<"wywedeni: broj chlenowe, koeficienti pred wsqka ot stepenite, kakto i\n";
cout<<"stojnost na neizwestnoto. Stepenta na wywedeniq polinom e ot interwala [2..22],\n";
cout<<"a koeficientite i neizwestnoto ot interwala[-9.9..9.9].\n";
cout<<"Primer: 4; 1,2,3,4; 1 Izhod: 10\n";
do {
do{
cout<<"Wywedete broj koeficienti n = "; cin>>n;
} while(n<1||n>22);
whod(koef,n);
cout<<"stojnost na neizwestnoto x = ";cin>>x;
cout<<"stojnost na polinom P(x) = "<< polinom (koef,n,x)<<endl;
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
} while (ose=='y' || ose=='Y');
system("pause");//chaka natiskane na klawish
return 0;//oswobovdawa zaetite sistemni resursi
}//kraj na programa polinom
Следващата примерна програма дава решена задача за изчисляване на
полином - polynomial чрез рекурсия
#include <iostream>
using namespace std;
double koef[50];
double polinom (int n,double x)
{// polinom P(x) = 5x^3 + 4x^2 + 3x + 2 move da se predstawi kato
//5x^3 + 4x^2 + 3x + 2 = ( ( (5x + 4)x + 3)x + 2)
if (n>0)
{ return polinom (n-1,x)*x+koef[n] ; }
//p=p*x+koef[n]
else { return koef[0];}//dyno na rekursiqta
} //polinom
void whod(int n)
{ if (n>0)//dyno na rekursiqta
{cout<<"Koeficient pred stepen ["<<n-1<<"] = "; cin>>koef[n-1];
whod(n-1);//rekursiwno izwkwane
}
}
int main()
{double x;
int n;
char ose;
cout<<"Da se systawi programa za izchislqwane stojnost na polinom pri\n";
cout<<"wywedeni: broj chlenowe, koeficienti pred wsqka ot stepenite, kakto i\n";
cout<<"stojnost na neizwestnoto. Stepenta na wywedeniq polinom e ot interwala [2..22],\n";
cout<<"a koeficientite i neizwestnoto ot interwala[-9.9..9.9].\n";
cout<<"Primer: 4; 1,2,3,4; 1 Izhod: 10\n";
do {
do
{cout<<"Wywedete broj koeficienti n = "; cin>>n;
} while(n<1||n>22);
whod(n);
cout<<"stojnost na neizwestnoto x = ";cin>>x;
cout<<"stojnost na polinom P(x) = "<<polinom (n-1,x)<<endl;
cout<<"She wywevdate li drugi danni <y/n>: ";cin>>ose;
} while (ose=='y' || ose=='Y');
system("pause");//chaka natiskane na klawish
return 0;
}//kraj na programa polinom
Начало на страницата
Алгоритъм за сума / разлика на полиноми
Алгоритъмът за намиране сума на два полинома
може да се сведе до сума, респективно разлика между елементи с еднакви индекси
от два едномерни масива. Не се извършва пренос. Крайният резултат може да бъде
полином с равна или по-ниска степен от полиномите събираеми.
Да се състави програма, чрез която се въвеждат
максималната степен и коефициентите на два полинома.
Числата за степен на полиномите са естествени
от интервала [2..20], а за коефициенти пред съответните степени цели числа от
интервала [-20..20]. Степените и коефициентите на двата полинома не са
непременно равни.
Като резултат да се изведе сумата и разликата на двата полинома.
Пример: polynomial: 4,5,6,7,8,9; polynomial: 1,2
Изход:
сума: 4*x^5 + 5*x^4 + 6*x^3 + 7*x^2 + 9*x^1 + 11*x^0
разлика: 4*x^5 + 5*x^4 + 6*x^3 + 7*x^2 + 7*x^1 + 7*x^0
#include <iostream>
using namespace std;
const int Max=30;
//int p[Max];
void vhod(int p[], int &br)
{ int a;
//koeficientite pred stepenite a neizwestnoto se syhranqwat w masiw
//kato redyt na stepenite e ot 0 do wywedenata stepen
cout<<"She wywevdate koeficientite pred syotwetnite stepeni na \n";
cout<<"neizwestnoto za polinom "<<br<<endl;
cout<<"Wywedete stepen na polinom [2..20]: ";cin>>br;
br%=Max;//zashita po whod
for (a=0;a<=br;a++)
{cout<<"Wywedete koeficienta pred stepen "<<a<<": ";cin>>p[a];
}//for za posledowatelno wywevdane na koeficientite pred wsqka stepen
}//vhod
void pechat(int p[], int br)
{ int a;
for (a=br;a>=0;a--) {
if (p[a]!=0) //ako syotwetniq koeficient e <>0
{ cout<<" "<<p[a]<<"*x^"<<a<<" ";//ako ima takyw chlen
if (a>0 && p[a]>0) cout<<"+";//ako ne e posleden chlen i e >0
}//if
}//for
cout<<endl;
}//pechat
void suma(int p1[], int p2[],int p[],int br, int koe)
{ int a;
for (a=0;a<=br;a++) //koeficientite se sybirat/izwavdat w treti masiw
{if (koe==0) p[a]=p1[a]+p2[a];//suma
if (koe==1) p[a]=p1[a]-p2[a];//razlika
}//for
}//suma polinom
int main()
{ int p1[Max],p2[Max],p3[Max],br1,br2,brm,a;
cout<<"Da se systawi programa, chrez koqto se wywevdat maksimalnata \n";
cout<<"stepen i koeficientite na dwa polinoma. Wywevdanite stojnosti\n";
cout<<"sa estestweni chisla, kato za stepen saot interwala [2..20], \n";
cout<<"a za koeficientite sa celi chisla ot interwala [-20..20].\n";
cout<<"Kato rezultat da se izwede sumata i razlikata na dwata polinoma.\n";
for (a=0;a<Max;a++) {p1[a]=p2[a]=p3[a]=0;}//nachalna inicializaciq
br1=1;vhod(p1,br1);//broj chlenowe i stojnost na koeficienti za polinom 1
br2=2;vhod(p2,br2);
brm=br1; if (brm<br2) brm=br2;
cout<<" polinomite sa:\n";
pechat(p1,br1);
pechat(p2,br2);
cout<<"Sumata na dwata polinoma e:\n";
suma(p1,p2,p3,brm,0);
pechat(p3,brm);
cout<<"Razlikata na dwata polinoma e:\n";
suma(p1,p2,p3,brm,1);
pechat(p3,brm);
system("pause");//ochakwa natiskane na klawish
return 0;//oswobovdawa zaetite resursi i wrysha kod za greshka 0
}//kraj na programa polinom
Начало на страницата
Алгоритъм за умножение на полиноми - polynomial
Тук ще разгледаме алгоритъм на
непосредственото умножение, който е аналогичен с умножение на многоцифрени
числа. Подобно на умножението на числа и броя цифри на резултата и тук
максималната степен на крайния полином е сума от степените на полиномите
множители.
Дадени са два полинома: Pn(x) и Qn(x), съответно със степени n и m.
Алгоритъмът започва с въвеждане на
максималната степен на полинома и със следващ цикъл всички коефициенти от
степен 0 до най-високата.
При умножението (чрез вложен цикъл от интервала между максималните степени до 0)
се натрупва в допълнителен масив коефициентите пред съответната степен на полинома резултат.
При извеждането се започва от най-високата степен на полинома.
Следва примерна програма даваща решена задача за умножение на два полинома:
#include <iostream>
using namespace std;
int const max_b=40;
int wywevda (int mas_10[], int nom)
{int i,j;
cout<<"Koq e maksimalnata stepen za polinom "<<nom<<": ";cin>>j;
j%=max_b;
for (i=0;i<=j;i++)
{ cout<<"Wywedete koeficient pred stepen "<<i<<": ";cin>>mas_10[i];
}
return j;//maksimalnata stepen na polinom
}
int main ()
{ int mas0[max_b],mas1[max_b],mas2[max_b];
int i,j,k, br_0,br_1,br_2;
for (i=0;i<max_b;i++) mas2[i]=0;
br_0=wywevda(mas0,1);
br_1=wywevda(mas1,2);
br_2=br_1 + br_0 ;
for (i=0;i<=br_1;i++)
{ for (j=0;j<=br_0;j++)
{ mas2[i+j]+=mas1[i]*mas0[j]; }
// for (k=0;k<br_2;k++) cout<<mas2[k]<<"; ";
// cout<<endl;
}
cout<<"Nowiqt polinom e s koeficienti: \n";
for (i=br_2;i>=0;i--)
{ if (mas2[i]<0) cout<<" "; else cout<<" + ";
cout<<mas2[i]<<"*x^"<<i;
}
cout<<endl;
system("pause");
return 0;
} //kraj na programa polinom
Начало на страницата
Алгоритъм за делене на полиноми
Полиномът Рn(х) се дели без остатък на х - q тогава и само тогава, когато х = q е нула на полинома.
Полиномът g(x) дели f(x), ако съществува полином h(x), такъв че f(x) = g(x)* h(x). В този аспект при делене на полиноми само операцията "делене с остатък" е винаги възможна и може да бъде представена във вида:
f(x) / g(x)= h(x) + k(x), където:
полиномът h(x) се нарича частно
полиномът k(x) се нарича остатък при деленето f(x) / g(x).
Деленето може да се извърши по няколко начина: примерно да приведем и двата
полинома в каноничен вид и ако е възможно да извършим съкращение. За целта трябва да се приложи
метод на Хорнер
за намиране нулите на двата полинома.
Тук ще разгледаме алгоритъма на непосредственото делене, който е аналогичен с делене на многоцифрени числа.
Дадени са два полинома: Pn(x) и Qn(x), съответно със степени n и m. Да се намерят други два полинома, наречени частно и остатък.
В разглежданият пример: числителят може да се представи като: (x-3)(x-2)(x-2)(x-2), а знаменателят като (x-2)(x-2).
Алгоритъмът започва с въвеждане на коефициентите от степен 0 до най-високата.
При деленето (чрез цикъл от интервала разликата между максималните степени до
0) се редуцира последователно най-високата степен на числителя.
При извеждането се започва от най-високата степен в частното и остатъка.
Следва примерна програма даваща решена задача за делене на два полинома - polynomial:
#include <iostream>
using namespace std;
const int stepen=32;//maksimalna stepen za chislitel, znamenatel
void vhod (double koef[], int max_step)
{int i;
//wywevdane koeficientite na polinom, zapochwajki ot stepen 0
for (i=0; i<=max_step;i++)
{cout<<"Wywedete koeficient pred stepen "<<i<<": ";cin>>koef[i];
} //for i
}//vhod
void izhod (double koef[], int max_step)
{int i;
for (i =max_step; i>=0; i--)
{ if (koef[i]>=0) cout<<"+";//samo da izwede znaka + pred poredniq koeficient
cout << koef[i]<<"*x^"<<i<<" ";
}//for
// cout<<endl;
}//izwevda polinom
void polynomial ()
{ double Chislit[stepen], Znamen[stepen], Rezult[stepen];
int max_Chi, max_Zna, i,j;
cout<<"Wywedete maksimalnata stepen na chislitelq [3..13]: ";cin>>max_Chi;
vhod (Chislit, max_Chi);//wywevda danni za chislitelq polinom
cout<<"Wywedete maksimalnata stepen na znamenatelq [2..4]: ";cin>>max_Zna;
vhod (Znamen, max_Zna);//wywevda danni za znamenatelq polinom
//deleneto na polinom se izwyrshwa kato delene na chisla
for ( i = max_Chi - max_Zna; i>=0;i--)//cqla chast na rezultata
{ Rezult[i] = Chislit[i +max_Zna] / Znamen[max_Zna];//poredniq koeficient
for (j = max_Zna; j>=0;j--)
{ Chislit[i + j] = Chislit[i + j] - Znamen[j] * Rezult[i];}//for j
}//for i
//Izwevdane na rezultata
cout<<"Cqla chast - chastno: ";
//razlikata mevdi maksimalnite stepeni w polinom chislitel / polinom znamenatel
izhod (Rezult, max_Chi - max_Zna);
cout<<"\n";
cout<<"Drobna chast - ostatyk: ";
// ostatykyt ima stepen s 1 po-malyk ot stepenta na znamenatelq
cout<<"(";
izhod (Chislit, max_Zna - 1);
cout<<") / (";
izhod (Znamen, max_Zna);
cout<<" )\n";
}// polynomial ()
int main()
{char ose;
cout<<"Imate wywedeni maksimalnata stepen i koeficientite na 2 polinoma.\n";
cout<<"Da se systawi programa, chrez koqto se izwevda rezultatyt ot deleneto\n";
cout<<"na dwata polinoma. Dannite se wywevdat zapochwajki ot swobodniq chlen.\n";
cout<<"Primer: 5: -24,68,-74,39,-10,1; 2: 4,-4,1 Izhod: 1,-6,11,-6; 0,0\n";
do {
polynomial ();// wywevda koeficienti, delene, izwevda rezultata
cout<<"She wywevdate li drugi danni: <y/n>: ";cin>>ose;
} while (ose=='y');
system ("pause");
return 0;
}//kraj na programa polinom
Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.
