Matematické Fórum

user91 · 26. 01. 2012 13:21

Jak násobit n-různých polynomů prvního stupně?
Děkuji

RePRO · 26. 01. 2012 16:25 — Editoval RePRO (26. 01. 2012 18:56)

Zdravím,
třeba takto (implementace je přes spojový seznam) v C++ (je to hodně lajdácký přístup a takto to profík v C++ samojistě neudělá):

Code:

 #inlude <conio.h>
 #include <iostream.h>
 #include <process.h>  

 // Přes spojový seznam
 // V každé struktuře se nám objevuje koeficient a exponent polynomu
 struct Hodnota
 {
   // Prvky našeho uzlu
   int koeficient, exponent;        
   // Odkaz na další prvek
   struct Hodnota * next;  
 };

 class Polynom
 {
   private:
           struct Hodnota *start, *ptrn, *ptrp;
   public:
           void getPoly(); 
           void show();   
           void multiply(Polynom p1, Polynom p2);
 };

 void Polynom :: getPoly() {
   
   char c = 'y';
   // Inicializujeme ukazatele
   ptrn = ptrp = start = NULL;
   
   while (c == 'y' || c == 'Y') {
      
      ptrn = new Hodnota;
      
      if (ptrp != NULL) {
         ptrp->next = ptrn;
      }
      
      if (start == NULL) {
         start = ptrn;
         ptrp = ptrn;
         cout << "\nZadej koeficient: ";
         cin >> ptrn->koeficient;
         cout << "Zadej exponent: ";
         cin >> ptrn->exponent;
         ptrn->next = NULL;
         cout << "Dalsi koeficient tohoto polynomu? Pokud ano, zmackni y: ";
         cin >> c;
      }
   }
   return;
 }
 
 void Polynom :: show() {
   
   struct Hodnota * ptr;
   ptr = start;
   
   // Dokud nejsme na konci spojového seznamu
   while (ptr != NULL) {
         
      cout << ptr->koeficient << "X^" << ptr->exponent << " + ";
      // Skočíme na další
      ptr = ptr->next;
   }
   cout << "\b\b ";
}

 void Polynom :: multiply(Polynom p1, Polynom p2) {
      
   struct Hodnota *p1ptr, *p2ptr, *ptri, *ptrj;
   int exp, coe;
   
   ptrn = ptrp = start = NULL;
   // Ukazatel pro první polynom
   p1ptr = p1.start;
   // Ukazatel pro druhý polynom
   p2ptr = p2.start;
   
   while (p1ptr != NULL) {
      
      p2ptr = p2.start;
      
      while (p2ptr != NULL) {
            ptrn = new Hodnota;
            ptrn->next = NULL;
            if (start == NULL) {
                     start = ptrn;
            }
            if (ptrp != NULL) {
                     ptrp->next = ptrn;
                     ptrn->koeficient = p1ptr->koeficient * p2ptr->koeficient;
                     ptrn->exponent = p1ptr->exponent + p2ptr->exponent;
                     ptrp = ptrn;
                     // Skok na další
                     p2ptr = p2ptr->next;
            }     
      }
      // Skok na další
      p1ptr = p1ptr->next;
   }             
   // Normalizování       
   ptri = ptrj = start;     
   ptrn = ptrp = start = NULL;
   
   while (ptri != NULL) {
         
      exp = ptri->exponent;
      coe = ptri->koeficient;
      ptrj = ptri->next;
      
      while (ptrj != NULL) {
                 if (ptrj->exponent == ptri->exponent) {
                        coe = coe+ptrj->koeficient;
                        ptrj->koeficient = 0;
                 }
      // Na další prvek
      ptrj = ptrj->next;
      }
      
      if (coe != 0) {
         ptrn = new Hodnota;
         ptrn->next = NULL;
         
         if (start == NULL) {
              start = ptrn;
         }
         if (ptrp != NULL) {
              ptrp->next = ptrn;
              ptrn->koeficient = coe;
              ptrn->exponent = exp;
              ptrp = ptrn;
         }
      }
      ptri = ptri->next;
   }
   return;
 }

 int main() {
 
   system("CLS");
   Polynom p1, p2, result;
   
   cout << " Prvni Polynom\n";
   p1.getPoly();
   
   cout << "\n Druhy Polynom\n";
   p2.getPoly();
   
   system("CLS");
   cout << "\n Prvni Polynom je: ";
   p1.show();
   
   cout << "\n Druhy Polynom je: ";
   p2.show();
   
   cout << "\n\n Vysledek po nasobeni dvou polynomu: \n";
   result.multiply(p1, p2);
   result.show();
   
   // getch();
   return 0;
}

Zašlu ještě jeden sample upravený, co mám v kódech, tak jak to má vypadat v C++. Udělá se to totiž krásně přes přetížený operátor *. :-)

RePRO · 26. 01. 2012 18:52 — Editoval RePRO (26. 01. 2012 18:54)

Algoritmus si lehce vyvodíme z uvedených kódů...

A takhle je to samozřejmě správně v C++:

Code:

 #include <iostream>
 #include <cctype>
 #include <cstring>
 #include <cstdlib>
 #include <string>

 using namespace std;

 class Polynom
 {
 private:
         
    int *coefficient;
    int  counter;    
 
 public:
        
    // Explicitní konstruktor
    Polynom();
    // Přetížený konstruktor
    Polynom(char *);
    // Kopírovací konstruktor
    Polynom(const Polynom &obj);
    // Destruktor
    ~Polynom();
    // Get Polynom
    void getPolynom() const;
    // Přetížený operátor *
    Polynom operator * (const Polynom &);
 };
 
 // Implementace - Explicitní konstruktor
 Polynom :: Polynom()
 {
    coefficient = new int[1];
    *coefficient = '\0';
 }
 
 // Implementace - Konstruktor s jedním přetíženým parametrem
 Polynom :: Polynom(char *s)
 {
    char *string;
    string = new char [strlen(s) + 1];
    int length = strlen(string);
    strcpy(string, s);
    
    char *copy;
    copy = new char [length];
    strcpy(copy, string);
    
    char *p = strtok(string, "  +-");
    counter = 0;
    while(p) 
    {
        p = strtok(NULL, "  +-");
        counter++;
    }
    
    coefficient = new int[counter];
    
    p = strtok(copy, "  +");
    int a = 0;
    while(p)
    {
        long int coeff;
        char *endptr;
        coeff = strtol(p, &endptr, 10); //stops at first non number
        if (*p == 'x')
           coeff = 1;

        coefficient[a] = coeff;
        p = strtok(NULL, "  +");
        a++;
    }
 }
 
 // Implementace - Kopírovací konstruktor
 Polynom :: Polynom(const Polynom &obj)
 {
    counter = obj.counter;
    coefficient = new int[counter];
    for (int i = 0; i < counter; i++) *(coefficient + i) = obj.coefficient[i];
 }
 
 // Implementace - Destruktor
 Polynom :: ~Polynom()
 {
    delete [] coefficient;
 }
 
 // Implementace - Dej mi Polynom
 void Polynom :: getPolynom() const
 {
    for (int i = 0; i < counter; i++)
    {            
        cout << coefficient[i] << "x^" << i;
        if (i != counter - 1)
        cout << " + ";
    }    
 }
 
 // Implementace - Přetížený operátor *
 Polynom Polynom :: operator * (const Polynom &right)
 {
    Polynom temp;
    
    int count = (counter + right.counter) - 1;
    temp.counter = count;
    temp.coefficient = new int[count];
    // Nutnost!
    std::memset(temp.coefficient, 0, count * sizeof(int));

    for (int i = 0; i < counter; i++)
    {
        for (int j = 0; j < right.counter; j++)
            temp.coefficient[i+j] += coefficient[i] * right.coefficient[j];
    }
    return temp;
 } 
 
 // Vše si vyzkoušíme v praxi :-)
 int main(int argc, char *argv[])
 {
    char input[50];
    char input2[50];
    
    cout << "Priklad: -4x^0 + x^1 + 0x^2+ 4x^3 + -3x^4" << endl;
    
    cout << "Nacist prvni polynom: ";
    cin.getline(input, 50);
    Polynom one(input);
    
    cout << "Nacist druhy polynom: ";
    cin.getline(input2, 50);
    Polynom two(input2); 
     
    cout << "Vysledek nasobeni \n";
    
    Polynom multiply = one * two;
    one.getPolynom();
    cout << " * (";
    two.getPolynom();
    cout << ") = ";
    
    multiply.getPolynom();
    cout << endl; 
     
    system("PAUSE");
    return EXIT_SUCCESS;
 }

Matematické Fórum

#1 26. 01. 2012 13:21

Lineární polynomy -> Algoritmus

#2 26. 01. 2012 16:25 — Editoval RePRO (26. 01. 2012 18:56)

Re: Lineární polynomy -> Algoritmus

Code:

#3 26. 01. 2012 18:52 — Editoval RePRO (26. 01. 2012 18:54)

Re: Lineární polynomy -> Algoritmus

Code:

Zápatí