Полином - изчисляване на стойност, сума, разлика, умножение и делене на полиноми

Алгоритъм за изчисляване стойност на полином - 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 

Обяснени и решени задачи с подобни алгоритми, функции и служебни думи са разгледани в страницата с електронни уроци по информатика - програмиране.
Илюстриране работата на характерни алгоритми можете да намерите в предоставените електронни помагала съдържащи решени задачи, примери.

 
Размер на шрифта
Increase Font Size Option 3 Reset Font Size Option 3 Decrease Font Size Option 3
Bulgarian Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish
Търсене в сайта: