[Δομημένος Πρ.] Εργασία C

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[ονόματα των αρχείων]

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads

με προσοχή στα ονόματα των αρχείων!

[c0ndemn3d]

Συζήτηση και απορίες για την τρίτη εργασία.


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

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

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


Υ.Γ Στο ethmmy θα βρείτε και ένα παράδειγμα.

[Jim D. Ace]

Ο συγκεκριμενος αλγοριθμος βρισκει τη διαδρομη που θελουμε αλλα οχι παντα τη βελτιστη. Εμεις θα πρεπει να τον μετατρεψουμε καπως ωστε να βρισκει τη βελτιστη;

[Exomag]

Ο συγκεκριμενος αλγοριθμος βρισκει τη διαδρομη που θελουμε αλλα οχι παντα τη βελτιστη. Εμεις θα πρεπει να τον μετατρεψουμε καπως ωστε να βρισκει τη βελτιστη;

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

[Σαλτιμπάγκος]

Ολα αυτα (το γραφημα, δηλαδη τον αριθμο των κορυφων,τον αριθμο των ακμων που περναν απο καθε κορυφη κ το βαρος τους κτλ) πρεπει να τα βαζει ο χρηστης;;

[Eragon]

Ολα αυτα (το γραφημα, δηλαδη τον αριθμο των κορυφων,τον αριθμο των ακμων που περναν απο καθε κορυφη κ το βαρος τους κτλ) πρεπει να τα βαζει ο χρηστης;;

τον αριθμο των ακμων που περναν απο καθε κορυφη κ το βαρος τους πρέπει σίγουρα να τα βάζει ο χρήστης.Με τον αριθμό των συνολικών κορυφών υπάρχει ένα μικρό πρόβλημα καθώς σε ορισμένους compilers(π.χ. Visual Studio,Quincy) δεν επιτρέπεται να δηλώσεις πίνακα μεταβλητου μεγέθους.Αν ο compiler δε σου  το επιτρέπει,κανε ένα define και εισαι μια χαρα.Εξάλλου δεν ειναι εκεί η δυσκολία του προγράμματος.
Υ.Γ.O dev το κάνει οπότε dev FTW

[WashAndGo]

Υπάρχει κάποιο πρόβλημα με το παράδειγμα στο ετημμυ ή μόνο εγω δε μπορώ να το δω?

[Jim D. Ace]

κατεβασε την εργασια απο την ενοτητα Εργασιες

[Exomag]

κατεβασε την εργασια απο την ενοτητα Εργασιες

Ή απλά χρησιμοποίησε Internet Explorer

[c0ndemn3d]

κατεβασε την εργασια απο την ενοτητα Εργασιες

Ή απλά χρησιμοποίησε Internet Explorer

NOOOOOOOOOOOOOOOOOOES

[Jim D. Ace]

Ο χρηστης ξερει οτι τις κορυφες εμεις τις αριθμουμε απο το 0 εως το Ν-1 ή θα μας δινει αριθμους απο 1 εως Ν;

[d0do]

Υπάρχει κάποιο πρόβλημα με το παράδειγμα στο ετημμυ ή μόνο εγω δε μπορώ να το δω?

 +1

[Niobe]

Υπάρχει κάποιο πρόβλημα με το παράδειγμα στο ετημμυ ή μόνο εγω δε μπορώ να το δω?

 +1

κατεβασε την εργασια απο την ενοτητα Εργασιες

[Infinite Loop]

κατεβασε την εργασια απο την ενοτητα Εργασιες

Ή απλά χρησιμοποίησε Internet Explorer

Για να κατεβασεις την τελευταια εκδοση του Firefox, φυσικα. Ειναι το μονο πραμα για το οποιο ειναι χρησιμος ο Explorer.

[Mr8]

Τι χρειάζεται για την εργασία; Θέλει Pointers; Ξέρει κανείς τι είπε στο μάθημα;

[Exomag]

Τι χρειάζεται για την εργασία; Θέλει Pointers; Ξέρει κανείς τι είπε στο μάθημα;

Δεν έχει αναφέρει τίποτα στο μάθημα σχετικά με την 3η εργασία. Επειδή οι τρόποι υλοποίησης είναι πολλοί, το αν θέλει Pointers ή όχι θα εξαρτηθεί από τον τρόπο που θα διαλέξεις για να λύσεις την άσκηση...