Finden Sie den Wert des Polynoms mithilfe der Horner-Regel in C++

1. Ermitteln Sie den Wert des Polynoms mithilfe der Horner-Regel in C++, indem Sie die Schleife rückwärts durchlaufen
2. Ermitteln Sie den Wert des Polynoms mithilfe der Horner-Regel in C++, indem Sie die Vorwärtsschleife durchlaufen
3. Verwenden Sie die Rekursion, um den Wert des Polynoms mithilfe der Horner-Regel in C++ zu finden
4. Abschluss

Die Horner-Regel ist ein effizienter Algorithmus zur Berechnung des Werts eines Polynoms.

Betrachten Sie das Polynom p(x) = 6x^3 - 2x^2 + 7x + 5 bei x = 4. Um ihn mit der Horner-Regel in C++ zu berechnen, wird der erste Koeffizient, 6, mit dem Wert bei x multipliziert, der 4 ist, und das Produkt der beiden, 24, wird zum nächsten Koeffizienten -2 addiert.

Das Ergebnis wird mit 4 multipliziert und zum nächsten Koeffizienten addiert.

Dieser Vorgang wird für die Anzahl der Koeffizienten in der Gleichung wiederholt. Das verbleibende Endprodukt ist der Wert des Polynoms.

In diesem Artikel wird erläutert, wie Sie den Wert eines Polynoms mithilfe der Horner-Regel in C++ finden, indem Sie die obigen Regeln in Computercode konvertieren.

Betrachten wir ein Polynom:

Wenn x = 4 ist, ist der Wert des Polynoms 385.

Ermitteln Sie den Wert des Polynoms mithilfe der Horner-Regel in C++, indem Sie die Schleife rückwärts durchlaufen

Schauen wir uns das Programm an, das den Wert eines Polynoms mithilfe der Horner-Regel in C++ durch Rückwärtsschleifen findet.

1. Die erste Codezeile importiert das Bibliothekspaket iostream; in der zweiten Zeile ist der Namensraum als std definiert.

2. Eine Methode int Horner() wird mit drei Parametern erstellt – ein Zeigerarray a, das die Liste der Koeffizienten übergibt, eine ganzzahlige Variable n, die den Grad des Polynoms speichert, und eine weitere ganzzahlige Variable x die den Wert des Polynoms bei x speichert.

   int Horner(int* a, int n, int x)
   

3. Hier wird erklärt, wie man das Produkt von Polynomen addiert. Es wird eine Integer-Variable Ergebnis erstellt, die mit dem letzten Element des Arrays a[n] initialisiert wird.

   int result = a[n];
   

   Hinweis: Verwechseln Sie es nicht mit der Größe des Arrays; es initialisiert die Variable result mit dem Element im Array a an der n-ten Position.

4. Es wird eine for-Schleife erstellt, die die Schleife vom letzten Element des Arrays a bis zum 0. Index umkehrt. Der Wert der Variable Ergebnis wird bei jedem Schleifendurchlauf aktualisiert.

   for (int i = n - 1; i >= 0; --i) 
   

   In der ersten Iteration wird der Wert von a[n] mit x multipliziert und dann zum vorherigen Element im Array addiert – a[n-1]. Bei einem Array – {2,3,4} nimmt die Schleife das letzte Element a[n], also 4, multipliziert es mit x und fügt es dann zum n-1-Element hinzu des Arrays, das ist 3.

   Aus diesem Grund müssen die Koeffizienten beim Initialisieren in der Funktion main umgekehrt werden. Der Wert von result wird am Ende der Methode zurückgegeben.

5. Innerhalb der Funktion main wird ein Array erstellt, um es an den ersten Parameter der Methode Horner zu übergeben. Beachten Sie, dass der Wert der Koeffizienten innerhalb des Arrays umgekehrt wird, da die Schleife rückwärts iteriert.

6. Eine Integer-Variable sol wird erstellt, um das Ergebnis zu speichern, das von der Methode namens Horner zurückgegeben wird.

   Im ersten Parameter wird das zu erstellende Array übergeben. Der zweite Parameter übergibt den Grad der Polynome in der Gleichung, 3, und der dritte Parameterwert bei x wird übergeben.

   int sol = Horner(arr, 3, 4);
   

Code:

#include <iostream>
using namespace std;
int Horner(int* a, int n, int x) {
  int result = a[n];
  for (int i = n - 1; i >= 0; --i) result = result * x + a[i];
  return result;
}

int main() {
  int arr[4] = {5, 7, -2, 6};
  int sol = Horner(arr, 3, 4);
  cout << sol;
}

Ausgabe (Rückwärtsschleifen der Horner-Regel in C++):

385

Ermitteln Sie den Wert des Polynoms mithilfe der Horner-Regel in C++, indem Sie die Vorwärtsschleife durchlaufen

Wenn wir die Schleife im Gegensatz zum letzten Beispiel vorwärts laufen lassen müssen, können wir den Zeiger des Arrays dereferenzieren, um sein erstes Element zu erhalten, und die Schleife vorwärts laufen lassen, anstatt sie umzukehren. Es ist eine weitere Möglichkeit, Schleifen zu verwenden, um die Horner-Regel in C++ zu implementieren.

Lassen Sie uns verstehen, was der Code tut:

1. Die erste Codezeile importiert das Bibliothekspaket iostream.

2. Ähnlich wie im vorherigen Beispiel wird eine Methode Horner mit drei Parametern erstellt.

   int Horner(int a[], int n, int x)
   

3. Durch Dereferenzieren des Pointers wird eine Variable result erzeugt und mit dem ersten Element des Arrays initialisiert. Der Zeiger *a entspricht dem Schreiben von arr[0].

   int result = *a;
   

   Im vorherigen Beispiel benötigte die Methode Horner eine an ihr Array angehängte Grössenkomponente: int result = a[n]; um auf das letzte Element zu zeigen. Hier wird nur dereferenziert.

4. Es wird eine for-Schleife erstellt, die von 1 bis n iteriert. Bei jeder Iteration wird der Wert der Variable Ergebnis mit dem Wert des Polynoms aktualisiert.

   Der Wert von result wird am Ende der Methode zurückgegeben.

   for (int i = 1; i < n; i++) result = result * x + a[i];
   return result;
   

5. Innerhalb der Funktion main wird ein Array mit dem Wert der Koeffizienten erstellt. Das hier verwendete Polynom lautet:

   $$
   p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2
   $$

   Das Array wird erstellt, indem die Koeffizienten der Polynome genommen werden - int arr[] = {5,3,-2,4,-6};.

6. Die Variable n enthält den Grad des Polynoms. Der Wert von n errechnet sich aus: n = Größe des Arrays -1.

   int n = (*(&arr + 1) - arr) - 1;
   //  n =	  size of the array		    -   1;
   

7. Die Methode Horner wird aufgerufen, indem das Array, der Wert von n und der Wert von x übergeben werden. Das zurückgegebene Ergebnis wird in einer neuen Integer-Variablen gespeichert und gedruckt.

   int sol = Horner(arr, n, -2);
   std::cout << "Value of polynomial = " << sol;
   

Code:

#include <iostream>
int Horner(int a[], int n, int x) {
  int result = *a;
  for (int i = 1; i < n; i++) result = result * x + a[i];
  return result;
}

int main() {
  int arr[] = {5, 3, -2, 4, -6};
  int n = (*(&arr + 1) - arr) - 1;
  int sol = Horner(arr, n, -2);
  std::cout << "Value of polynomial = " << sol;
}

Ausgabe (Vorwärtsschleifen-Horner-Regel in C++):

Value of polynomial = -20

Verwenden Sie die Rekursion, um den Wert des Polynoms mithilfe der Horner-Regel in C++ zu finden

Bisher haben wir gelernt, wie man den Wert eines Polynoms mit der Horner-Regel in C++ findet. Dies wurde durch Iterieren von Schleifen und Aktualisieren der Zählung unter Verwendung einer Akkumulatorvariablen durchgeführt.

In diesem Beispiel wird der Wert des Polynoms durch Rekursion berechnet. Schauen wir uns den Code an.

1. Die erste Codezeile importiert das Paket iostream und definiert den Namespace als std.

   #include <iostream>
   using namespace std;
   

2. Eine Methode Horner wird erstellt, die drei Parameter hat – einen ganzzahligen Zeiger *pi, eine weitere ganzzahlige Variable Grad, die der Grad des Polynoms ist (im vorherigen Beispiel als n verwendet), und x für die Wertübergabe bei x.

   int Horner(int* pi, int degree, int x)
   

3. Das Merkmal der rekursiven Funktion besteht darin, sich selbst wie eine Schleife aufzurufen, bis eine Bedingung erfüllt ist, was die Zeitkomplexität reduziert. Für die Bedingung gibt eine if-Anweisung den Wert von pi am 0. Index nur dann zurück, wenn der Gradwert auf 0 gesunken ist.

   if (degree == 0) {
     return pi[0];
   }
   

4. Um Rekursion anzuwenden, wird die Methode Horner erneut aufgerufen, anstatt einen Wert zurückzugeben.

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   Die obige Syntax behält die Horner-Methode bei, sich selbst wiederholt für den Grad des Polynoms aufzurufen. In einer Gleichung ist der Grad des Polynoms sein höchster Exponent.

   Betrachtet man die im letzten Beispiel verwendete Gleichung:

   $$ p(x) = 5x^4 + 3x^3 - 2x^2 + 4x - 6; x=-2 $$

   Der Grad des Polynoms ist 4.

   Dies bedeutet, dass die Rekursion sich selbst für n+1 = 5 Mal (Größe des Arrays) iteriert. Bei jeder Iteration ruft sich die Methode selbst auf, bis der Gradwert auf 0 reduziert ist.

   Sobald es 0 erreicht, nimmt die Rekursion das Element *p[0] und übergibt es an den vorherigen Methodenaufruf.

   return Horner(pi, degree - 1, x) * x + pi[degree];
   

   Es ist dasselbe, als würde man einen Umschlag in einem Umschlag öffnen, bis der letzte Umschlag erreicht ist und dann wieder zurückgefaltet werden. Der Wert beim letzten Methodenaufruf wird an den vorherigen Methodenaufruf übergeben, und die Berechnungen werden ausgeführt.

5. Innerhalb der Funktion main wird ein Integer-Array erstellt, um die Koeffizienten der Gleichung an die Methode Horner zu übergeben. Dann wird der Wert des Parameters an die Methode übergeben.

   int sol = Horner(arr, 4, -2);
   

   Das Array ist arr, Grad - 4 und Wert bei x, was -2 ist.

6. Zuletzt wird das zurückgegebene Ergebnis in einer Integer-Variablen sol gespeichert und ausgedruckt.

Code:

#include <iostream>
using namespace std;

int Horner(int* pi, int degree, int x) {
  if (degree == 0) {
    return pi[0];
  }
  return Horner(pi, degree - 1, x) * x + pi[degree];
}
int main() {
  int arr[] = {5, 3, -2, 4, -6};
  int sol = Horner(arr, 4, -2);
  cout << "Value of Polynomial using recursion = " << sol;
}

Ausgang:

Value of Polynomial using recursion = 34

Abschluss

In diesem Artikel wird erläutert, wie Sie den Wert von Polynomen mithilfe der Horner-Regel in C++ finden. Die drei Methoden haben unterschiedliche zeitliche Komplexitäten, was ein großartiges Lernwerkzeug für den Leser sein kann.

Es wird empfohlen, zu versuchen, die Codes selbst zu schreiben und dann zurückzukommen, um Hinweise zu erhalten. Der Leser wird die Konzepte zum Ermitteln des Werts von Polynomen unter Verwendung der Horner-Regel in C++ leicht verstehen.