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

[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

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

[pepe]

Εργασία C (Hμ/νία λήξης δηλώσεων: 19/04/2010)

Εργασία C

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

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

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

Σημείωση: Για την καταχώρηση των αποστάσεων ανάμεσα στις πόλεις να οριστεί ένας πίνακας δύο διαστάσεων ο οποίος στην i γραμμή να περιέχει τις αποστάσεις των πόλεων από την υπ’ αριθμόν i πόλη.

[png]

έχει κάνει λάθος στην ημερομηνία παράδοσης...

[iason1907]

το ιδιο με το προηγουμενο πανω-κατω ε? δεν το διαβασα και ολο αλλα ετσι καταλαβα 

[Γιώργος]

Καλά που δεν έβαλε και το TSP
Πάρτε και ένα testcase για έλεγχο.


Είσοδος (πρώτος αριθμός το N, δεύτερος αριθμός η πόλη-αφετερία και μετά οι αποστάσεις):

Code:

5
3
00 54 29 13 34
54 00 34 12 42
29 34 00 13 47
13 12 13 00 12
34 42 47 12 00

Έξοδος:

Code:

3 -> 1 -> 2 -> 0 -> 4 
Total distance : 109

Φυσικά δεν είναι απαραίτητο να είναι και συμμετρικός ο πίνακας, εφόσον η εκφώνηση δεν το αναφέρει. Μπορεί πχ η απόσταση 1->2 να είναι 24 και η απόσταση 2->1 να είναι 29, γιατί ξέρω 'γω η πόλη 1 είναι σε βουνό.


ps : προς αποφυγή παρεξηγήσεων, το testcase δεν είναι λύση ή κάτι συναφές. Είναι ένας τρόπος να τσεκάρετε αν τα προγράμματά σας τρέχουν σωστά, ελέγχοντας αν όλοι βγάζετε την ίδια έξοδο για δεδομένη είσοδο.


disclaimer : το I/O format είναι όπως το έκανα εγώ, προφανώς και σε καμία περίπτωση δεν είναι δεσμευτικό.

[nohponex]

...
Πάρτε και ένα testcase για έλεγχο.
...

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

[Μάρω]

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

[Γιώργος]

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

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

[st0up]

Έχει κανει malloc στο μαθημα? Η παλι πρεπει να κανουμε χρηση #define?

[Orfikoss]

Νο molloc yet...

[The Stig]

Μπορώ να μάθω γιατί κρασάρει το πρόγραμμα με το testcase του Γιώργου (btw χρόνια πολλά για σήμερα) ενώ ο compiler δεν βγάζει error??

[Γιώργος]

Μπορώ να μάθω γιατί κρασάρει το πρόγραμμα με το testcase του Γιώργου (btw χρόνια πολλά για σήμερα) ενώ ο compiler δεν βγάζει error??

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

[The Stig]

Άκυρο το βρήκα! Μάλλον θα πρέπει να το ψάχνω πιο πολύ πριν ποστάρω...!

[SolidSNK]

Functions θέλει στην εργασία ο κορτέσης? Ενώ σίγουρα δε ζητά να γίνει με αναδρομή έτσι?

[st0up]

Μπερδευτηκα στο εξης: Ο χρηστης θα "γεμισει" τον πινακα με τις αποστασεις των πολεων και στη συνεχεια θα γινεται η αναζητηση της ελαχιστης? Ή θα δινει (οπως στην προηγουμενη εργασια) τις συντεταγμενες και μετα θα υπολογιζονται οι αποστασεις, θα εισαγονται στον πινακα και θα γινεται η αναζητηση της ελαχιστης???

[Orfikoss]

απ'ότι καταλαβαίνω αποστάσεις θέλει μόνο