Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
giankar
Δημοσιεύσεις: 110
Εγγραφή: 01 Δεκ 2007 16:22
Επικοινωνία:

Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων

Δημοσίευση από giankar » 11 Ιαν 2008 22:59

Μπορεί κάποιος να μου δώσει ένα υπόδειγμα για το πώς πολλαπλασιαζώ 2 πολυώνυμα σε C++? Ευχαριστώ προκαταβολικά
geekhost.gr - Web Services

id12586
στις καρδιές μας
Δημοσιεύσεις: 8387
Εγγραφή: 23 Ιουν 2003 23:28
Τοποθεσία: Far away
Επικοινωνία:

Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων

Δημοσίευση από id12586 » 12 Ιαν 2008 19:44

Ενδιαφέρει και εμένα αυτό..
Chris at your Services
ΕικόναSacame de Aqui

Άβαταρ μέλους
papageorge
Δημοσιεύσεις: 122
Εγγραφή: 11 Ιαν 2006 20:54
Τοποθεσία: HRAKLEIO

Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων

Δημοσίευση από papageorge » 21 Ιαν 2008 05:50

xeroume ti vathmou einai h aorista?
Εικόνα

Δύο πράγματα είναι άπειρα το σύμπαν και η ανθρώπινη βλακεία.

Einstein

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων

Δημοσίευση από soteres2002 » 21 Ιαν 2008 09:53

μόλις σκέφτηκα μια πολύ trivial λύση που είναι εφαρμόσημη γενικότερα (για αυθαίρετο βαθμό πολυωνύμων και αυθαίρετο πλήθος πολυωνύμων). Την τεκμηριώνω παρακάτω θεωρητικά και μετά την υλοποιώ με απλό αλγόριθμο (αυτό είναι το υπόδειγμα για τον giankar, και όχι η υλοποίηση σε C++). Ο καθένας μπορεί να μεταφέρει αυτή τη λογική σε οποιαδήποτε γλώσσα εκτός από λογικές και συναρτησιακές. Οι αλγοριθμοι μπορούν να βελτιστοποιηθούν εκμεταλλευόμενοι άλλες ιδιότητες (μπορεί να μειωθεί και σε λογαριθμική χρονική πολυπλοκότητα), αλλα ποιος κάθεται να το κανει τωρα (ειδικά αν έχεις και εξεταστική);;; :-)

Θεωρητική τεκμηρίωση: Έστω ν πολυώνυμα του χ, καλούμαστε να υπολογίσουμε παραστάσεις της μορφής
Φ_1(Χ) * Φ_2(Χ) * .... * Φ_Ν(Χ). Για τον υπολογισμό αυτής, χρησιμοποιούμε Ν στατικές δομές δεδομένων (στατικοί πίνακες με κ + 1 στοιχεία, δηλαδή κ όροι με παράγοντα δύναμη του χ και έναν σταθερό όρο > 0 ή μηδέν αν είναι ανύπαρκτος) ή μια στοίβα. Ας ονομάσουμε Σ1, Σ2, ..., ΣΝ αυτούς τους υποχώρους του διανυσματικού πεδίου των πραγματικών συναρτήσεων (φ(Χ), χ ε R). Η ίδια λογική επεκτείνεται και σε πραγματικές συναρτησεις πολλών μεταβλητών, όπως και διανύσματα συναρτήσεων αλλά και μιγαδικές συναρτήσεις. Ώς στοιχεία σε όποια δομή και αν επιλέξουμε, πρέπει να έχουμε μια δομή (σε υπολοποίηση δομής, κλάσης κτλ ανάλογα) ας την ονομάσουμε "oros" η οποία θα περιέχει 2 πεδία έστω μη μοναδικά σε ολόκληρη αρχικά τη συλλογή των δεδομένων: 1 αριθμητικό όρο και έναν άλλον την αριθμητική τιμή της δύναμης της μεταβλητής του πολυωνύμου. Άρα το απλό πολυώνυμο 2*Χ^2 + 0*χ + 1 αναπαρίσταται γενικά ώς {(2, 2), (0, 1), (1, 0)} (είναι λογικό αφού 2*χ^2 + 0*χ^1 + 1*χ^0 = ... = το γνωστό). Στον αλγόριθμο υπολογισμού θα εισάγουμε και μια απλή διαδικασία απλοποίησης του σωρού των δεδομένων, βρίσκοντας τους όρους με ίδια δύναμη της παραμέτρου ώστε να μειωθεί το μέγεθός του, πριν πάμε να υπολογίσουμε την τελική τιμή της αλγεβρικής παράστασης. Είναι γνωστό από την επιμεριστική ιδιότητα, ότι η λογική που εξάγεται από τον πολλαπλασιασμό των Φ_1(χ) * Φ_2(χ) *.... *Φ_Ν(Χ) αντίστοιχα με αντίστοιχα μ1, μ2, ..., μΝ αντίστοιχα στοιχεία στις δομές δεδομένων Σ1, Σ2, ..., ΣΝ προκύπτει μια μη δομή αποθήκευσης εστω Σ με στοιχεία το καρτεσιανό γινόμενο των Σ1, Σ2, ..., ΣΝ. Στην μη απλουστευμένη μορφή του, θα περιέχει αυτός ένα μέγιστο πλήθος από |Σ1|*|Σ2|*...*|ΣΝ| στοιχεία. Κατά την φάση απλούστευσής του, θα περιέχει τουλάχιστον ένα λιγότερο (γιατί?). Ένα απλό παράδειγμα είναι το εξής: έστω τα πολυώνυμα 2*χ + 1 και 2*χ^2 με αναπαράσταση Σ1={(2, 1), (1, 0)} και Σ2={(2, 2)}, τότε καρτεσιανό γινόμενο Σ1ΧΣ2={(2, 1)*(2, 2), (1, 0)*(2, 2)} (όπου έχουμε λογικά 2χ1=2 το πλήθος στοιχεία). Σημειώνω ότι (α, β) * (γ, δ) = (α*β, γ*δ) [1] (!) (που δεν είναι αυτό που ορίζει ο λογικός πολλαπλασιασμός που ξέρουμε για 2 διατεταγμένα σημεία) άρα θεωρήστε την πράξη * που σημειώνω σαν τον κανονικό πολλάπλασιασμό με την μόνη διαφορά για αυτήν ισχύει η ιδιότητα [1]. Οι αλγόριθμοι παρακάτω, είναι η πρακτική υλοποίηση με βελτιστοποίηση του χώρου μνήμης (η βελτιστοποίηση αφορά περισσότερο την μνήμη, και οι αλγόριθμοι υπολογισμού λειτουργούν με μέγιστη πολυπλοκότητα Ο(Ν^2)). Στην τελική θα μπορέσουμε να τυπώσουμε μια συμβολοσειρά με το πολυώνυμο που προκύπτει.


* Για πρακτικούς λόγους δεν θα μετατρέψω από string σε αναπαράσταση με την δομή που περιέγραψα ένα πολυώνυμο, αλλά θα το αρχικόποιήσω αυστηρά. Κάλλιστα μπορεί να γράψει κάποιος μια απλή συνάρτηση που δυναμικά αναλύει ένα string και επιστρέφει μια δυναμική δομή Σ (πχ στην C, ... -- ο τρόπος υλοποίησης διαφέρει, άρα δεν συμφέρει να δείξω κάτι).

Υλοποίηση των αλγορίθμων
Θα υπολογίσουμε το (2*χ^2 + 1) * (5*χ - 2)

Αρχικοποίηση των δομών δεδομένων

Κώδικας: Επιλογή όλων

Αρχικοποίησης δομής Σ1, με σύνολο στοιχείων Σ1={(2, 2), (1, 0)}, |Σ1| = 2
Αρχικοποίησης δομής Σ2, με σύνολο στοιχείων Σ2={(5, 1), (-2, 0)}, |Σ2| = 2
Αρχικοποίησης δομής Σ, με σύνολο στοιχείων Σ={(5, 1), (-2, 0)} |Σ|=|Σ1 χ Σ2| = 4
Επαναληπτικός υπολοσμός του καρτεσιανού γινομένου:

Κώδικας: Επιλογή όλων

Αρχικοποίησης κενής δομής τύπου oros, έστω tmp
Foreach oros1 of Σ1
    Foreach oros2 of Σ2
          tmp = multiply(oros1, oros2)
Υπολογίσαμε την μη απλουστευμένη αλγεβρική έκφραση μέχρι τώρα. Δεν ορίσαμε όμως την multiply().

Κώδικας: Επιλογή όλων

oros multiply(oros ptr1, oros ptr2) {
    oros retVal;
    retVal->power = ptr1->power*ptr2->power;
    retVal->factor = ptr1->factor * ptr2->factor;
    return(retVal); 
}
Μέχρι τώρα ορίσαμε πρακτικά την φάση υπολογισμού, επόμενο βήμα είναι να απλουστεύσουμε την αλγεβρική έκφραση (γιατι?). Γιατί αν δεν την απλοποιήσουμε, θα περιέχει όρους με ίδια δύναμη της μεταβλητής χ, που σημαίνει ότι θα υπάρχουν παραστάσεις του τύπου 2*χ + 1*χ^2 - 10*χ, ενώ εμείς θα υπολογίζουμε την πιο απλουστευμένη έκφραση, δηλαδή -8*χ + χ^2. Η μέθοδος optimize() πέρνει μια δομή oros και επιστρέφει μια βελτιστοποιημένη παραλλαγή της αρχικής με οικονομία χώρου (βελτιστοποίηση στον χώρο) απλοποίηση του τελικού αποτελέσματος που θα βλέπει ο χρήστης.

Κώδικας: Επιλογή όλων

oros optimize(structure oros S: by reference) { // by reference: destroy unoptimized structure
    # declaration an array or stack of structure named tmp, type oros
    # declaration a item structure named item of type oros
    
    tmp <-- S
    foreach P of ptr &#123;
       foreach Q of S - &#123;P&#125; &#123;
            if&#40;P->power == Q->power&#41; &#123; // optimize
                   item->power = P->power = Q->power;
                   item->factor = P->factor + Q->factor;
                   
                   Locate first item with power equal to ptr->power
                   Update located item with value of item
                   Delete other items with this power that equals ptr->power
            &#125;
      &#125;
    &#125;
    
    return&#40;tmp&#41;;
&#125;
και τέλος, δοθέντος μιας στατικής δομής πίνακα (ή και με στοίβα αντίστοιχα) μπορούμε να υπολογίσουμε την τελική αριθμητική έκφραση που αναπαριστά το γινόμενο που υπολογίσαμε.

Κώδικας: Επιλογή όλων

void stringOf&#40;structure S containing items of type oros&#41; &#123;
     foreach&#40;item Q of S&#41; &#123;
         print Q->factor, "*X", Q->power, " ";
     &#125;
&#125;
Τέλος, η λειτουργία S-{item} = {όλα τα στοιχεία του S χωρίς το item} γίνεται σε χρόνο Ο(Ν) ώς εξής (ας την ονομάσουμε αυτή τη λειτουργία "SubsetX"):

Κώδικας: Επιλογή όλων

<dynamic array of elements of type oros> SubsetX&#40;<dynamic array of elements of type oros> trunk, oros ptr&#41; &#123;
   <dynamic array of elements of type oros> retSet = NULL;
   foreach item Q of trunk &#123;
       if Q not equals ptr &#123;
            Add item Q to trunk
       &#125;
  &#125;
  
  return&#40;retSet&#41;;
&#125; 
Οι απλοί αυτοί αλγόριθμοι μπορούν να βελτιστοποιηθούν και σε χρόνο εκτέλεσης, ανάλογα με την προσέγγιση που θα επιλέξει ο προγραμματιστής. Η βελτιστοποίηση του χώρου μνήμης είναι απαραίτητος, κι ας χάσουμε σε χρόνο, καθώς πολυώνυμα με εκατομύρια όρους θα καταναλώσουν γενικά τεράστιο χώρο μνήμης ειδικά σε συστήματα με μικρό χώρο μνήμης (φανταστείτε σε προγράμματα όπως τα Μatlab και Maple που χρησιμοποιούνται για rendering παραστασεων πχ. αλγεβρικών). Συγκερικριμένα η φάση απλούστευσης μπορεί να γίνει και με πιο δυναμικό και "on-line" τρόπο.
Τελευταία επεξεργασία από το μέλος soteres2002 την 21 Ιαν 2008 15:03, έχει επεξεργασθεί 8 φορές συνολικά.

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων

Δημοσίευση από soteres2002 » 21 Ιαν 2008 10:13

giankar έγραψε:Μπορεί κάποιος να μου δώσει ένα υπόδειγμα για το πώς πολλαπλασιαζώ 2 πολυώνυμα σε C++? Ευχαριστώ προκαταβολικά
giankar, έχεις όλο τον αλγόριθμο σε ψευδοκώδικα άρα λογικά μπορείς τώρα εύκολα να το μετατρέψεις σε C++! και επειδή η C++ έχει κατάλληλες διευκολύνσεις όπως υπερφόρτωση τελεστών (έτσι μπορείς να όρίσεις πράξεις μεταξύ αντικειμένων), η διαδικασία υλοποίησης θα είναι ευκολότερη. Δηλαδή μόλις τώρα οδηγήθηκες στην πηγή, πίες νερό! :)

@<mods>: ας γίνει βοήθημα αν είναι δυνατόν (και ...μοδερατορικά δίκαιο). :)

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες