freestuff.gr αρχική σελίδα
 FAQFAQ    ΑναζήτησηΑναζήτηση   Λίστα ΜελώνΛίστα Μελών   Ομάδες ΜελώνΟμάδες Μελών   <b>Εγγραφή Μέλους</b>Εγγραφή Μέλους 
 ΠροφίλΠροφίλ   Επιλογές μέλους Επιλογές   Τα bookmarks μου Τα bookmarks μου   Προσωπικά μηνύματαΠροσωπικά μηνύματα 
  διαφήμιση  

Καλώς ήρθατε στο forum μας! Για να συμμετάσχετε στις συζητήσεις θα πρέπει να είσαστε μέλος. Γίνετε μέλος τώρα!.

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


 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Moderators:  Super-Moderators, WebDev Moderators
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [5 Μηνύματα]      Bookmarks Tags: c Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
ΑποστολέαςΜήνυμα
giankar


Μέλος από: 01 Δεκ 2007
Μηνύματα: 110

View users profile Visit posters website
ΜήνυμαΣτις: 11 Ιαν 2008 22:59    Θέμα: Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων
Περιγραφή θέματος: πολλαπλασιασμός δυο πολυωνύμων σε C++
Απάντηση με παράθεση  Mark this post and the followings unread

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

_________________
geekhost.gr - Web Services
id12586
στις καρδιές μας

Μέλος από: 23 Ιουν 2003
Βοηθήματα: 6
Νέα: 1
Μηνύματα: 256+

Περιοχή: Far away
View users profile
blog deviantART 
ΜήνυμαΣτις: 12 Ιαν 2008 19:44    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

Ενδιαφέρει και εμένα αυτό..

_________________
Chris at your Services
Sacame de Aqui
papageorge


Μέλος από: 11 Ιαν 2006
Βοηθήματα: 2
Μηνύματα: 122

Περιοχή: HRAKLEIO
View users profile Send email to user
ΜήνυμαΣτις: 21 Ιαν 2008 05:50    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

xeroume ti vathmou einai h aorista?

_________________


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

Einstein
soteres2002
S. & H. Moderator

Μέλος από: 05 Μαρ 2004
Βοηθήματα: 1
Νέα: 1
Scripts: 1
Μηνύματα: 256+

Περιοχή: Ιωάννινα
View users profile
ΜήνυμαΣτις: 21 Ιαν 2008 09:53    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

μόλις σκέφτηκα μια πολύ 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 {
       foreach Q of S - {P} {
            if(P->power == Q->power) { // 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
            }
      }
    }
   
    return(tmp);
}


και τέλος, δοθέντος μιας στατικής δομής πίνακα (ή και με στοίβα αντίστοιχα) μπορούμε να υπολογίσουμε την τελική αριθμητική έκφραση που αναπαριστά το γινόμενο που υπολογίσαμε.

κώδικας:

void stringOf(structure S containing items of type oros) {
     foreach(item Q of S) {
         print Q->factor, "*X", Q->power, " ";
     }
}


Τέλος, η λειτουργία S-{item} = {όλα τα στοιχεία του S χωρίς το item} γίνεται σε χρόνο Ο(Ν) ώς εξής (ας την ονομάσουμε αυτή τη λειτουργία "SubsetX"):

κώδικας:

<dynamic array of elements of type oros> SubsetX(<dynamic array of elements of type oros> trunk, oros ptr) {
   <dynamic array of elements of type oros> retSet = NULL;
   foreach item Q of trunk {
       if Q not equals ptr {
            Add item Q to trunk
       }
  }
 
  return(retSet);
}


Οι απλοί αυτοί αλγόριθμοι μπορούν να βελτιστοποιηθούν και σε χρόνο εκτέλεσης, ανάλογα με την προσέγγιση που θα επιλέξει ο προγραμματιστής. Η βελτιστοποίηση του χώρου μνήμης είναι απαραίτητος, κι ας χάσουμε σε χρόνο, καθώς πολυώνυμα με εκατομύρια όρους θα καταναλώσουν γενικά τεράστιο χώρο μνήμης ειδικά σε συστήματα με μικρό χώρο μνήμης (φανταστείτε σε προγράμματα όπως τα Μatlab και Maple που χρησιμοποιούνται για rendering παραστασεων πχ. αλγεβρικών). Συγκερικριμένα η φάση απλούστευσης μπορεί να γίνει και με πιο δυναμικό και "on-line" τρόπο.

Last edited by soteres2002 on 21 Ιαν 2008 15:03, edited 8 times in total
soteres2002
S. & H. Moderator

Μέλος από: 05 Μαρ 2004
Βοηθήματα: 1
Νέα: 1
Scripts: 1
Μηνύματα: 256+

Περιοχή: Ιωάννινα
View users profile
ΜήνυμαΣτις: 21 Ιαν 2008 10:13    Θέμα: Re: Ερώτηση για C++ πολλαπλασιασμός δυο πολυωνύμων
Περιγραφή θέματος: πολλαπλασιασμός δυο πολυωνύμων σε C++
Απάντηση με παράθεση  Mark this post and the followings unread

giankar ανέφερε:
Μπορεί κάποιος να μου δώσει ένα υπόδειγμα για το πώς πολλαπλασιαζώ 2 πολυώνυμα σε C++? Ευχαριστώ προκαταβολικά


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

@<mods>: ας γίνει βοήθημα αν είναι δυνατόν (και ...μοδερατορικά δίκαιο).
Εμφάνιση Μηνυμάτων:   
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [5 Μηνύματα] Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++


Σχετικά θέματα
 Θέματα   Απ/σεις   Αποστολέας   Τελευταίο μήνυμα 
ενας κωδικας σε C που βγαζει μη αναμενομενο αποτεσμα 1 teresa92 13 Αυγ 2016 21:26
teresa92 Εμφάνιση τελευταίου μηνύματος
 
Τώρα είναι 16 Ιαν 2017 16:55 | All times are UTC + 2


Email This Page to Someone! add to Favorites

     Powered by p h p B B © 2001,2005 p h p B B Group
Για άμεση επικοινωνία με τον διαχειριστή του freestuff.gr στο email: freestuff.gr(παπάκι)gmail.com


Copyright © 1999-2013 Freestuff.gr All Rights Reserved  
Version Aegean, designed by N. Tsaganos