Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


36. Arithmetik



Übungen

  1. Polynome können auch in der Form r0(x - r1)(x - r2)...(x - rN) dargestellt werden. Wie würden Sie zwei Polynome bei dieser Darstellung multiplizieren?
  2. Erstellen Sie ein Pascal-Programm, das lichte Polynome multipliziert, wobei eine Darstellung mittels verketteter Listen ohne Knoten für Glieder, deren Koeffizient den Wert null hat, verwendet wird.
  3. Erstellen Sie eine Pascal-Prozedur, die den Wert des Elements in der i-ten Zeile und j-ten Spalte einer lichten Matrix auf v setzt, unter der Annahme, daß die Matrix mittels verketteter Listen ohne Knoten für Einträge mit dem Wert null dargestellt ist.
  4. Geben Sie ein Verfahren für die Auswertung eines Polynoms mit bekannten Wurzeln r1, r2, ..., rN an, und vergleichen Sie Ihr Verfahren mit dem Horner-Schema.
  5. Erstellen Sie ein Programm zur Auswertung von Polynomen unter Benutzung des Horner-Schemas, wenn die Polynome mittels verketteter Listen dargestellt sind. Gewährleisten Sie, daß Ihr Programm für lichte Polynome effizient arbeitet.
  6. Erstellen Sie ein Programm, das die Lagrange-Interpolation in ungefähr N2 Schritten ausführt.
  7. Kann x55 mit weniger als neun Multiplikationen berechnet werden? Wenn ja, geben Sie diese an; wenn nicht, begründen Sie es.
  8. Zählen Sie alle Multiplikationen von Polynomen auf, die ausgeführt werden, wenn das in diesem Kapitel beschriebene Verfahren mult zur Multiplikation von Polynomen nach dem Prinzip »Teile und Herrsche« angewandt wird, um 1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8 zu quadrieren.
  9. Die Effektivität des Verfahrens mult könnte für lichte Polynome erhöht werden, indem null zurückgegeben wird, falls alle Koeffizienten bei einer der Eingaben null sind. Wie viele Multiplikationen (bis auf einen konstanten Faktor genau) würde ein derartiges Programm ungefähr benutzen, um 1 + xN zu quadrieren?
  10. Implementieren Sie eine anwendungsfähige Variante von mult, die eine Darstellung mittels verketteter Listen verwendet, und bestimmen Sie empirisch einen Wert von N, für den sie schneller abläuft als die einfache Methode (bei Benutzung der gleichen Darstellung).


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]