PROG 2 – Aufgabe 1 (Klasse Polynom)

Alle Aufgaben und weiter Infos zu Programmiertechnik 2 findet ihr auf der Internetseite von Prof. Dr. Oliver Bittel unter http://www-home.fh-konstanz.de/~bittel/.

Hier wird eine Polynom Klasse erstellt, die ein dynamisches Feld nutzt.

Programmiertechnik 2 – Aufgabe 1 (Klasse Polynom)

Lösung:
mainAufgabe1.cpp:

// mainAufgabe1.cpp
// Hauptprogramm zu Aufgabe1
//
// O.Bittel; 9.4.2008
//

#include <iostream>
#include "polynom.h"

using namespace std;

int main()
{
  // Polynom p:
  cout << "===== Polynom p =====" << endl;
  Polynom p;
  p.set(5,1);
  p.set(2,3);
  p.set(3,-4);
  cout << "Ist:  "; p.print();
  cout << "Soll: 1x^5 - 4x^3 + 3x^2" << endl;
  cout << "Ist:  ";
  for (int i = 0; i <= p.getGrad(); i++)
    cout << i << ", " << p.get(i) << ", ";
  cout << endl;
  cout << "Soll: 0, 0, 1, 0, 2, 3, 3, -4, 4, 0, 5, 1" << endl;
  // cout << "Ist:  " << p.eval(2) << endl;
  // cout << "Soll: 12" << endl;
  cout << endl;

  // Polynom r:
  cout << "===== Polynom r =====" << endl;
  Polynom r;
  r.set(2,8);
  r.set(0,3);
  r.set(20,7);
  r.set(3,6);
  cout << "Ist:  "; r.print();
  cout << "Soll: 7x^20 + 6x^3 + 8x^2 + 3" << endl;
  cout << "Ist:  " << r.getGrad() << endl;
  cout << "Soll: 20" << endl;
  cout << endl;

  // Polynom s:
  cout << "===== Polynom s und r =====" << endl;
  Polynom s = r;
  s.set(20,0);
  s.set(3,0);
  s.set(2,5);
  cout << "Ist:  "; s.print();
  cout << "Soll: 5x^2 + 3" << endl;
  cout << "Ist:  " << s.getGrad() << endl;
  cout << "Soll: 2" << endl;
  cout << "Ist:  "; r.print();
  cout << "Soll: 7x^20 + 6x^3 + 8x^2 + 3" << endl;
  cout << endl;

  // Addition:
  cout << "===== Addition p + s =====" << endl;
  Polynom t;
  t = p;
  t.add(s);
  cout << "Ist:  "; t.print();
  cout << "Soll: 1x^5 - 4x^3 + 8x^2 + 3" << endl;
  cout << endl;
  cout << "===== Addition p + r =====" << endl;
  t = p;
  t.add(r);
  cout << "Ist:  "; t.print();
  cout << "Soll: 7x^20 + 1x^5 + 2x^3 + 11x^2 + 3" << endl;
  cout << endl;

  // Multiplikation:
  cout << "===== Multiplikation p * 2x^5 =====" << endl;
  t = p;
  t.multTerm(5,2);
  cout << "Ist:  "; t.print(); cout << endl;
  cout << "Soll: 2x^10 - 8x^8 + 6x^7" << endl;
  cout << endl;
  cout << "===== Multiplikation p * s =====" << endl;
  t = p;
  t.mult(s);
  cout << "Ist:  "; t.print();
  cout << "Soll: 5x^7 - 17x^5 + 15x^4 - 12x^3 + 9x^2" << endl;
  cout << endl;

  int i;
  cin >> i;
}

polynom.cpp:

// polynom.cpp
//
// O. Bittel; 8.10.2008
// Bearbeitet von Andreas Giemza; 17.03.2010

#include <iostream>
#include "polynom.h"

using namespace std;

Polynom::Polynom()
{
  // Lege das Null-Polynom an
  size = 0;
  a = new int[1];
  a[0] = 0;
}

Polynom::Polynom(const Polynom& x)
{
  // ��bernehme die gr�¶�Ÿe des x Feldes
  size = x.size;
  // Erstelle das Feld
  a = new int[size];

  // Kopiere den Inhalt von x zum neuen Feld
  for (int i = 0; i < size; i++)
    a[i] = x.a[i];
}

Polynom::~Polynom()
{
  // L�¶sche a, da dynamische Datenstruktur
  delete [] a;
}

Polynom& Polynom:: operator=(const Polynom& x)
{
  // Selbstzuweisung verhindern
  if (this != &x)
  {
    // L�¶sche altes Feld
    delete [] a;
    // siehe Copy-Konstruktor
    size = x.size;
    a = new int[size];
    for (int i = 0; i < size; i++)
      a[i] = x.a[i];
  }
  return *this;
}

void Polynom::set(int i, int c)
{
  // Schaue ob das Feld gro�Ÿ Genug ist und wenn nicht resize es
  if (i > size)
    resize(i+1);

  // Inhalt schreiben
  a[i] = c;
}

void Polynom::resize(int n)
{
  // Lege ein neues Tempfeld an
  int* temp = new int[n];

  // Schreibe alte in das neue Tempfeld
  for (int i = 0; i < n; i++)
  {
    if (i < size)
      temp[i] = a[i];
    // Neue Felder mit 0 f�¼llen
    else
      temp[i] = 0;
  }

  // Altes Feld l�¶schen
  delete [] a;

  // Tempfeld zum neuen Feld machen
  a = temp;

  // Neue Gr�¶�Ÿe �¼bernehmen
  size = n;
}

void Polynom::print()
{
  // Indikator f�¼r das erste Element
  bool erstesElement = true;

  // Gehe das Feld durch von hinten nach vorne
  for (int i = size-1; i >= 0; i--)
    // Gebe nur elemente aus wo der Koeffinzient nicht 0 ist
    if (a[i] != 0)
  {
    // Gebe das erste Element aus
    if (erstesElement)
    {
      cout << a[i] << "x^" << i;
      // Indikator auf false und rest �¼berspringen
      erstesElement = false;
      continue;
    }
    // Ausgeben ausser bis auf den letzte da das auch Sonderfall
    if (i != 0)
    {
      if (a[i] < 0)
        cout << " - " << a[i]*-1 << "x^" << i;
      else
        cout << " + " << a[i] << "x^" << i;
    }
    // Letztes Element wird ausgegeben
    else
    {
      if (a[i] < 0)
        cout << " - " << a[i]*-1;
      else
        cout << " + " << a[i];
    }
  }

  // Neue Zeile f�¼r die sch�¶nheit
  cout << 'n';
}

int Polynom::getGrad()
{
  // Gehe Feld von hinten durch und der erste Koeffizient der nicht Null ist, ist der Grad
  for (int i = size-1; i >= 0; i--)
    if (a[i] != 0)
      return i;

  return 0;
}

int Polynom::get(int i)
{
  // Easy ...
  return a[i];
}

void Polynom::add(const Polynom& x)
{
  // Schauen ob x nicht gr�¶�Ÿer als das Feld ist
  if (x.size > size)
    resize(x.size);

  // Addiere die Kpoeffizienten von x dazu.
  for (int i = 0; i < x.size; i++)
    a[i] += x.a[i];
}

void Polynom::multTerm(int i, int c)
{
  // Gehe Feld von hinten durch
  for (int j = size-1; j >= 0; j--)
    // Mach nur was wenn der Koeffizient nicht Null ist
    if (a[j] != 0)
  {
    // Schaue ob das neue Element nicht ein h�¶heren Grad hat als unser Feld
    if (j+i > size)
      resize(j+i+1);

    // Schreibe das neue Element
    a[j+i] = a[j]*c;

    // L�¶sche das alte
    a[j] = 0;
  }
}

void Polynom::mult(const Polynom& x)
{
  // Beim ersten Element wird die Feldgr�¶�Ÿe initalisiert und das nur einmal
  bool erstesElement = true;
  // sizetemp f�¼r die neue Feldgr�¶�Ÿe
  int sizetemp;
  // Tempfeld anlegen aber nicht initialisieren
  int* temp;

  // Gehe Feld von hinten durch
  for (int i = size-1; i >= 0; i--)
    // Mach nur was wenn der Koeffizient nicht Null ist
    if (a[i] != 0)
      // Gehe x Feld von hinten durch
      for (int j = x.size-1; j >= 0; j--)
        // Mach nur was wenn der x Feld Koeffizient nicht Null ist
        if (x.a[j] != 0)
        {
    // Erstes Element ist das gr�¶�Ÿte weil wir von hinten die Felder durchgehen
    if (erstesElement)
    {
      // Speichern f�¼r sp�¤ter
      sizetemp = i+j+1;

      // Tempfeld gr�¶�Ÿe festlegen
      temp = new int[sizetemp];

      // Neues Feld mit Bullen f�¼llen
      for (int k = 0; k < sizetemp; k++)
        temp[k] = 0;

      // So Feld wurde initialisiert, muss net nochmal gemacht werden
      erstesElement = false;
    }

    // Inhalt schreiben
    temp[i+j] = a[i]*x.a[j];
  }

  // Altes Feld l�¶schen
  delete [] a;

  // Tempfeld zum neuen Feld machen
  a = temp;

  // Neue Gr�¶�Ÿe �¼bernehmen
  size = sizetemp;
}

/*
void Polynom::mult(const Polynom& p)
{
Polynom prod;
for (int i = 0; i <= p.getGrad(); i++)
{
Polynom t = *this;
t.multTerm(i,p.a[i]);
prod.add(t);
}
*this = prod;
}
*/

polynom.h:

// polynom.h
// Andraes Giemza
// 17.03.2010

#ifndef POLYNOM_H
#define POLYNOM_H

class Polynom
{
  public:
    Polynom();
    Polynom(const Polynom& x);
    ~Polynom();
    Polynom& operator=(const Polynom& x);

    int getGrad();
    void set(int i, int c);
    int get(int i);
    void add(const Polynom& x);
    void mult(const Polynom& x);
    void multTerm(int i, int c);
    void print();

  private:
    void resize(int n);

    int* a;
    int  size;
};
#endif

Makefile:

# File: Makefile fuer Aufgabe1
#
# Aufruf:
#
#		make
#
# Author: Oliver Bittel
# Date: 12.09.2007

# Definitions:
CC = g++ -g   # -g wird nur fuer Debugger benoetigt!
OBJ = mainAufgabe1.o polynom.o
BIN = aufg1

# Rules:
$(BIN): $(OBJ)
	$(CC) -o $(BIN) $(OBJ)

mainAufgabe1.o: mainAufgabe1.cpp polynom.h
	$(CC) -c mainAufgabe1.cpp

polynom.o: polynom.cpp polynom.h
	$(CC) -c polynom.cpp