[Δομημένος Προγραμματισμός] Άσκηση C (Hμ/νία λήξης :03/05/2015)

THMMY.gr > Forum > Μαθήματα Βασικού Κύκλου > 1ο Εξάμηνο > Δομημένος Προγραμματισμός (Moderator: Parlapipis) > [Δομημένος Προγραμματισμός] Άσκηση C (Hμ/νία λήξης :03/05/2015)

0 Members and 1 Guest are viewing this topic.

Pages: [1]

Author

Topic: [Δομημένος Προγραμματισμός] Άσκηση C (Hμ/νία λήξης :03/05/2015) (Read 955 times)

Vlassis

Veteran
Μόνιμος κάτοικος ΤΗΜΜΥ.gr

Posts: 2162

εφακ

[Δομημένος Προγραμματισμός] Άσκηση C (Hμ/νία λήξης :03/05/2015)

« on: April 27, 2015, 00:24:42 am »

Ασκηση C

Σε ένα γράφημα, που αποτελείται από Ν κορυφές, οι οποίες συνδέονται με ακμές με δοθέντα βάρη, θέλουμε να βρούμε μια διαδρομή που να συνδέει δύο δοθείσες κορυφές. Η διαδρομή πρέπει να μην περνά δυο φορές από την ίδια κορυφή και να έχει το μικρότερο κόστος. Το κόστος της διαδρομής ισούται με το άθροισμα των βαρών των ακμών που συνδέουν τις κορυφές που ορίζουν τη διαδρομή. Για να βρούμε μια καλή διαδρομή (όχι τη βέλτιστη) εφαρμόζουμε τον πιο κάτω αλγόριθμο. Από τις κορυφές που συνδέονται με την κορυφή εκκίνησης επιλέγουμε αυτή με την οποία το βάρος της ακμής που την συνδέει είναι το ελάχιστο. Η κορυφή αυτή ενσωματώνεται στη διαδρομή, ενώ η κορυφή εκκίνησης αφαιρείται από το γράφημα. Η διαδικασία επαναλαμβάνεται θεωρώντας ως νέα κορυφή εκκίνησης την κορυφή που έχει επιλεγεί. Ο αλγόριθμος τερματίζεται όταν, με την πιο πάνω διαδικασία, επιλεγεί η κορυφή προορισμού ή διαπιστωθεί ότι δεν υπάρχουν κορυφές για επιλογή.

Να γραφεί το πρόγραμμα το οποίο να υλοποιεί τον πιο πάνω αλγόριθμο. Το πρόγραμμα να εκτυπώνει τη διαδρομή που βρέθηκε καθώς και το συνολικό της κόστος. Σε περίπτωση που ο αλγόριθμος δε μπόρεσε να τερματίσει τη διαδρομή να τυπώνεται σχετικό μήνυμα.

Για την καταχώρηση του γραφήματος οι κορυφές να αριθμούνται από το 0 έως το Ν-1. Στο πρόγραμμα να οριστούν οι πίνακες connection και weight, δύο διαστάσεων, τύπου Ν x Ν-1. Ο πίνακας connection να ορίζει μια γραμμή για κάθε κορυφή του γραφήματος και να καταχωρεί ως τιμές για τα στοιχεία της γραμμής τους αριθμούς των κορυφών με τις οποίες συνδέεται η κορυφή που αντιστοιχεί στην γραμμή. Ο πίνακας weight να είναι ίδιος με τον πίνακα connection με τη διαφορά ότι αντί για τους αύξοντες αριθμούς των κορυφών, στις ίδιες θέσεις, να καταχωρούνται τα βάρη των ακμών οι οποίες συνδέουν τις κορυφές με την κορυφή στην οποία ανήκει η αντίστοιχη γραμμή του πίνακα.

Παράδειγμα

(φωτο απο κατω)

Η διαδρομή από την κορυφή 0 έως την κορυφή 2 θα είναι η 0,1,3,2 με κόστος 3.

Η διαδρομή από την κορυφή 0 έως την κορυφή 4 δε θα τερματιστεί από τον αλγόριθμο.


« Last Edit: May 05, 2015, 23:25:48 pm by Vlassis »	Logged

πρόπελ
Is any of it real? I mean, look at this. Look at it! A world built on fantasy! Synthetic emotions in the form of pills, psychological warfare in the form of advertising, mind-altering chemicals in the form of food, brainwashing seminars in the form of media, controlled isolated bubbles in the form of social networks. mr.robot s01e10

Pages: [1]

Jump to: