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

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

0 Members and 1 Guest are viewing this topic.

Pages: [1]

Author

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

Vlassis

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

Posts: 2162

εφακ

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

« on: May 15, 2015, 16:50:19 pm »

Άσκηση F

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

Ένας αλγόριθμος που θα έδινε μια σχετικά καλή λύση, όχι τη βέλτιστη, επιλέγει την ακμή με το μικρότερο βάρος και καταχωρεί τη μια από τις κορυφές που συνδέει στην ομάδα Α και την άλλη στην Β. Στη συνέχεια διαγράφει από το γράφημα τις κορυφές αυτές και επαναλαμβάνει την διαδικασία με τις υπόλοιπες κορυφές. Οι διαδικασία σταματά όταν όλες οι κορυφές του γραφήματος καταχωρηθούν σε κάποια από τις δύο ομάδες.

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

Σημείωση

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

Για τους πίνακες connection και weight κοιτάξτε το παράδειγμα της άσκησης C.

Ο αλγόριθμος να ελέγχει μόνο ζεύγη κορυφών που συνδέονται μεταξύ τους. Να αγνοεί ζεύγη που δε συνδέονται αν και αυτά θα μπορούσαν να δώσουν καλύτερη λύση.


« Last Edit: May 26, 2015, 21:30:37 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: