|
Title: [C++] 8η Εργασία 2010 Post by: Orfikoss on December 13, 2010, 13:15:49 pm Εργασία Η (Hμ/νία λήξης δηλώσεων: 09/01/2011) Ένα κλιμάκιο τεχνικών χρησιμοποιεί ένα αεροπλάνο για να επισκεφτεί μια σειρά από αεροδρόμια με σκοπό να ελέγξει τη σωστή λειτουργία των εγκαταστάσεών τους. Η σειρά με την οποία θα γίνουν οι επισκέψεις πρέπει να σχεδιαστεί κατάλληλα έτσι ώστε να ελαχιστοποιηθεί το κόστος για την πτήση του αεροπλάνου. Για το σκοπό αυτό σχεδιάζεται ένα πλήρες γράφημα σε κάθε κορυφή του οποίου αντιστοιχεί και ένα αεροδρόμιο. Κάθε κορυφή του γραφήματος συνδέεται με όλες τις άλλες κορυφές του με ακμές οι οποίες έχουν ως βάρος το κόστος της πτήσης ανάμεσα στα δύο αεροδρόμια που αντιστοιχούν σε αυτές. Το ζητούμενο σε αυτήν την περίπτωση είναι να βρεθεί ένα μονοπάτι το οποίο να περνά μια μόνο φορά από κάθε κορυφή και να έχει το μικρότερο συνολικό κόστος. (Πρόβλημα του περιοδεύοντος εμπόρου στη θεωρεία γραφημάτων.) Ένας απλός αλγόριθμος, ο οποίος δίνει μια σχετικά καλή λύση, (όχι τη βέλτιστη), ξεκινά από μια κορυφή και μετακινείται στην κορυφή με την οποία συνδέεται με την ακμή που έχει το μικρότερο βάρος. Η διαδικασία επαναλαμβάνεται έως ότου εξαντληθούν όλες οι κορυφές. Να γραφεί το λογισμικό στο οποίο να ορίζεται η κλάση node η οποία υλοποιεί μια κορυφή του γραφήματος. Για τα αντικείμενα στον τύπο της κλάσης να οριστεί ένας extractor με την κλήση του οποίου να διαβάζονται οι ταυτότητες των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο, καθώς και τα βάρη των αντίστοιχων ακμών. Ως μέλος της κλάσης node να οριστεί ακόμη μια επικάλυψη του τελεστή new η οποία να δεσμεύει την αναγκαία μνήμη για την καταχώρηση ενός πίνακα με αντικείμενα στον τύπο της κλάσης. Για κάθε αντικείμενο του πίνακα η επικάλυψη να ορίζει ως ταυτότητα τη θέση του στον πίνακα, να διαβάζει τον αριθμό των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο και να δεσμεύει την απαραίτητη μνήμη για την καταχώρηση των ταυτοτήτων των κορυφών αυτών και για την καταχώρηση των βαρών των ακμών που τις συνδέουν με την κορυφή που υλοποιεί το αντικείμενο. Τέλος η επικάλυψη να χρησιμοποιεί τον extractor για να εισάγει τα αντίστοιχα στοιχεία για κάθε ένα από τα αντικείμενα του πίνακα. Στο λογισμικό να οριστεί ακόμη η κλάση network η οποία υλοποιεί το γράφημα. Ως μέλος της κλάσης να οριστεί μια επικάλυψη του τελεστή new η οποία να δεσμεύει την απαραίτητη μνήμη για την καταχώρηση ενός αντικειμένου στον τύπο της κλάσης. Η επικάλυψη να διαβάζει τον αριθμό των κορυφών που αποτελούν το γράφημα και να δεσμεύει, χρησιμοποιώντας την επικάλυψη του τελεστή new που ορίστηκε για τα αντικείμενα τύπου node, την απαραίτητη μνήμη για την καταχώρηση των στοιχείων των κορυφών του γραφήματος. Η επικάλυψη να δεσμεύει ακόμη μνήμη για έναν πίνακα ακεραίων αριθμών στον οποίο θα καταχωρηθούν οι ταυτότητες των κορυφών του γραφήματος με τη σειρά με την οποία εμφανίζονται στο μονοπάτι με το μικρότερο κόστος. Τέλος, στην ίδια κλάση να οριστεί και η συνάρτηση calk_path η οποία να δέχεται ως όρισμα την ταυτότητα της κορυφής από την οποία θα αρχίσει ο υπολογισμός του μονοπατιού και η οποία να υπολογίζει, σύμφωνα με τον αλγόριθμο, το αντίστοιχο μονοπάτι καθώς και το συνολικό κόστος για την διαδρομή του. Η συνάρτηση main του προγράμματος να δεσμεύει δυναμικά μνήμη για ένα αντικείμενο τύπου network. Στη συνέχεια, για κάθε μια από τις κορυφές του γραφήματος να καλεί τη συνάρτηση calk_path για να υπολογίσει το μονοπάτι που θα προκύψει αν η εκκίνηση γίνει από την αντίστοιχη κορυφή. Η main να εκτυπώνει το μονοπάτι με το μικρότερό κόστος από όλα τα μονοπάτια που υπολογίστηκαν από την calk_path καθώς και το αντίστοιχο κόστος. Το λογισμικό να περιέχει τις κατάλληλες επικαλύψεις του τελεστή delete για την αποδέσμευση της μνήμης που έχει δεσμευτεί δυναμικά. Βοηθητικές παρατηρήσεις: Υπάρχουν διαφοροποιήσεις μεταξύ των μεταγλωττιστών όταν η επικάλυψη του τελεστή new καλείται να δεσμεύσει μνήμη για πίνακες. Στην περίπτωση αυτή ορισμένοι μεταγλωττιστές απαιτούν το πρότυπο της συνάρτησης επικάλυψης να είναι void *operator new[ ](size_t size) ενώ για επικαλύψεις οι οποίες θα δεσμεύουν μνήμη για ένα μόνο στοιχείο το πρότυπο είναιvoid *operator new(size_t size) Στην περίπτωση που δεν οριστεί συνάρτηση επικάλυψης με βάση το πρώτο πρότυπο και χρησιμοποιηθεί ο τελεστής new για δέσμευση πίνακα εκτελείται η έκδοση που ορίζεται από τον μεταγλωττιστή. Άλλοι μεταγλωττιστές και στις δύο περιπτώσεις, δέχονται το δεύτερο πρότυπο. Title: Re: [C++] 8η Εργασία 2010 Post by: Ex_Mechanus on December 16, 2010, 16:23:34 pm όπως το βλέπω μάλλον insertor θέλει και όχι extractor
Title: Re: [C++] 8η Εργασία 2010 Post by: il capitano on December 17, 2010, 02:24:47 am σας εστειλα στην στοα τον οφφτοπικ
μεινετε στο θεμα!...! Title: Re: [C++] 8η Εργασία 2010 Post by: nikitas350 on December 21, 2010, 22:05:57 pm Δεν μπορώ να καταλάβω ποιό είναι το νόημα της εργασίας. Συγκεκριμένα:
http://stackoverflow.com/questions/4502728/accessing-an-object-in-operator-new Title: Re: [C++] 8η Εργασία 2010 Post by: proud_metalhead on January 03, 2011, 14:38:24 pm Να γραφεί το λογισμικό στο οποίο να ορίζεται η κλάση node η οποία υλοποιεί μια κορυφή του γραφήματος. Για τα αντικείμενα στον τύπο της κλάσης να οριστεί ένας extractor με την κλήση του οποίου να διαβάζονται οι ταυτότητες των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο, καθώς και τα βάρη των αντίστοιχων ακμών. Ως μέλος της κλάσης node να οριστεί ακόμη μια επικάλυψη του τελεστή new η οποία να δεσμεύει την αναγκαία μνήμη για την καταχώρηση ενός πίνακα με αντικείμενα στον τύπο της κλάσης. Για κάθε αντικείμενο του πίνακα η επικάλυψη να ορίζει ως ταυτότητα τη θέση του στον πίνακα, να διαβάζει τον αριθμό των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο και να δεσμεύει την απαραίτητη μνήμη για την καταχώρηση των ταυτοτήτων των κορυφών αυτών και για την καταχώρηση των βαρών των ακμών που τις συνδέουν με την κορυφή που υλοποιεί το αντικείμενο. Τέλος η επικάλυψη να χρησιμοποιεί τον extractor για να εισάγει τα αντίστοιχα στοιχεία για κάθε ένα από τα αντικείμενα του πίνακα.
Εχω ενα προβλημα κατανοησης: Αφου δινουμε στον extractor την ταυοτιτα γιατι να την ξαναδινουμε στην επικαλυψη? Επισης αδυνατο να κατανωησω τι ζηταει στην επικαλυψη.Μπορει καποιος να εξηγησει με απλα ελληνικα?ισως με προτασεισ μικροτερες των 200λεξεων, αφου προφανως ο κορτεσης δν γνωριζει σημεια στιξης ωστε να κανει την κατανοηση τησ εργασιας ευκολοτερη επισης αν ισχυει οτι θελει insertor ασ γινει ενα αναλογο ποστ Title: Re: [C++] 8η Εργασία 2010 Post by: gareth on January 03, 2011, 15:17:11 pm Νομιζω οτι την ταυτοτητα την δινουμε στην επικαλυψη και οχι στον extractor.
Στον extractor θα διαβαζει τις ταυτοτητες των σταθμων που συνδεονται με τον συγκεκριμενο αεροδρομιο και το βαρος των μεταξυ τους ακμων. Τουλαχιστον ετσι το εκανα εγω.. Title: Re: [C++] 8η Εργασία 2010 Post by: Tracy_McGrady on January 03, 2011, 15:59:02 pm Ρε παιδια στο μάθημα δεν είπε οτι οταν δεσμεύουμε πίνακα με new μετα χάνονται τα στοιχεια του??για επικάλυψη μιλάω παντα!
Title: Re: [C++] 8η Εργασία 2010 Post by: nikitas350 on January 03, 2011, 22:21:20 pm Να γραφεί το λογισμικό στο οποίο να ορίζεται η κλάση node η οποία υλοποιεί μια κορυφή του γραφήματος. Για τα αντικείμενα στον τύπο της κλάσης να οριστεί ένας extractor με την κλήση του οποίου να διαβάζονται οι ταυτότητες των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο, καθώς και τα βάρη των αντίστοιχων ακμών. Ως μέλος της κλάσης node να οριστεί ακόμη μια επικάλυψη του τελεστή new η οποία να δεσμεύει την αναγκαία μνήμη για την καταχώρηση ενός πίνακα με αντικείμενα στον τύπο της κλάσης. Για κάθε αντικείμενο του πίνακα η επικάλυψη να ορίζει ως ταυτότητα τη θέση του στον πίνακα, να διαβάζει τον αριθμό των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο και να δεσμεύει την απαραίτητη μνήμη για την καταχώρηση των ταυτοτήτων των κορυφών αυτών και για την καταχώρηση των βαρών των ακμών που τις συνδέουν με την κορυφή που υλοποιεί το αντικείμενο. Τέλος η επικάλυψη να χρησιμοποιεί τον extractor για να εισάγει τα αντίστοιχα στοιχεία για κάθε ένα από τα αντικείμενα του πίνακα. Εχω ενα προβλημα κατανοησης: Αφου δινουμε στον extractor την ταυοτιτα γιατι να την ξαναδινουμε στην επικαλυψη? Επισης αδυνατο να κατανωησω τι ζηταει στην επικαλυψη.Μπορει καποιος να εξηγησει με απλα ελληνικα?ισως με προτασεισ μικροτερες των 200λεξεων, αφου προφανως ο κορτεσης δν γνωριζει σημεια στιξης ωστε να κανει την κατανοηση τησ εργασιας ευκολοτερη επισης αν ισχυει οτι θελει insertor ασ γινει ενα αναλογο ποστ Κατ' αρχήν θέλει extractor. Στον extractor διαβάζεις τις ταυτότητες των κορυφών με τις οποίες συνδέεται η τρέχουσα κορυφή. Στην επικάλυψη της new δίνεις για την κάθε κορυφή ως ταυτότητα την θέση του πίνακα. Title: Re: [C++] 8η Εργασία 2010 Post by: nikitas350 on January 03, 2011, 22:22:22 pm Ρε παιδια στο μάθημα δεν είπε οτι οταν δεσμεύουμε πίνακα με new μετα χάνονται τα στοιχεια του??για επικάλυψη μιλάω παντα! Όταν λες χάνονται τι εννοείς; Title: Re: [C++] 8η Εργασία 2010 Post by: Tracy_McGrady on January 04, 2011, 04:22:24 am Ρε παιδια στο μάθημα δεν είπε οτι οταν δεσμεύουμε πίνακα με new μετα χάνονται τα στοιχεια του??για επικάλυψη μιλάω παντα! Όταν λες χάνονται τι εννοείς; Title: Re: [C++] 8η Εργασία 2010 Post by: proud_metalhead on January 04, 2011, 12:31:42 pm Να γραφεί το λογισμικό στο οποίο να ορίζεται η κλάση node η οποία υλοποιεί μια κορυφή του γραφήματος. Για τα αντικείμενα στον τύπο της κλάσης να οριστεί ένας extractor με την κλήση του οποίου να διαβάζονται οι ταυτότητες των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο, καθώς και τα βάρη των αντίστοιχων ακμών. Ως μέλος της κλάσης node να οριστεί ακόμη μια επικάλυψη του τελεστή new η οποία να δεσμεύει την αναγκαία μνήμη για την καταχώρηση ενός πίνακα με αντικείμενα στον τύπο της κλάσης. Για κάθε αντικείμενο του πίνακα η επικάλυψη να ορίζει ως ταυτότητα τη θέση του στον πίνακα, να διαβάζει τον αριθμό των κορυφών που συνδέονται με την κορυφή που υλοποιεί το αντικείμενο και να δεσμεύει την απαραίτητη μνήμη για την καταχώρηση των ταυτοτήτων των κορυφών αυτών και για την καταχώρηση των βαρών των ακμών που τις συνδέουν με την κορυφή που υλοποιεί το αντικείμενο. Τέλος η επικάλυψη να χρησιμοποιεί τον extractor για να εισάγει τα αντίστοιχα στοιχεία για κάθε ένα από τα αντικείμενα του πίνακα. Εχω ενα προβλημα κατανοησης: Αφου δινουμε στον extractor την ταυοτιτα γιατι να την ξαναδινουμε στην επικαλυψη? Επισης αδυνατο να κατανωησω τι ζηταει στην επικαλυψη.Μπορει καποιος να εξηγησει με απλα ελληνικα?ισως με προτασεισ μικροτερες των 200λεξεων, αφου προφανως ο κορτεσης δν γνωριζει σημεια στιξης ωστε να κανει την κατανοηση τησ εργασιας ευκολοτερη επισης αν ισχυει οτι θελει insertor ασ γινει ενα αναλογο ποστ Κατ' αρχήν θέλει extractor. Στον extractor διαβάζεις τις ταυτότητες των κορυφών με τις οποίες συνδέεται η τρέχουσα κορυφή. Στην επικάλυψη της new δίνεις για την κάθε κορυφή ως ταυτότητα την θέση του πίνακα. επομενως στον extractor αν εχουμε ν κορυφες δινουμε ν-1 ταυτοτητες, ενω στην new δινουμε ν. επισης στην new ζηταει να κανουμε πινακα με στοιχεια τυπου node? αν οχι τι τυπου στοιχεια θελει?????????????????? Title: Re: [C++] 8η Εργασία 2010 Post by: geor on January 04, 2011, 19:01:42 pm Όταν λέμε extractor τι ακριβώς εννοούμε?
Title: Re: [C++] 8η Εργασία 2010 Post by: gareth on January 04, 2011, 19:44:42 pm Όταν λέμε extractor τι ακριβώς εννοούμε? Μια επικαλυξη του '>>'... Διαβασε απο το βιβλιο σελ.470... Τα λεει αρκετα καλα ;) |