|
Title: [Δομημένος Πρ.] Εργασία C 09/10 Post by: pepe on April 20, 2010, 12:07:17 pm Εργασία C (Hμ/νία λήξης δηλώσεων: 19/04/2010)
Εργασία C Μια αεροπορική εταιρία καλύπτει έναν αριθμό από Ν πόλεις. Για να οργανώσει μια διαφημιστική καμπάνια θέλει να δρομολογήσει ένα ειδικό αεροπλάνο που θα επισκεφτεί διαδοχικά όλες τις πόλεις που εξυπηρετεί η εταιρία. Για να μειωθεί το κόστος της καμπάνιας πρέπει να επιλεγεί η σειρά με την οποία θα επισκεφτεί το αεροπλάνο τις πόλεις έτσι ώστε η διαδρομή που θα ακολουθηθεί να είναι όσο το δυνατόν συντομότερη. Για να βρεθεί μια καλή λύση (όχι η βέλτιστη) στο πρόβλήμα ακολουθείται ο εξής αλγόριθμος. Οι πόλεις αριθμούνται από το 0 έως το Ν-1. Το αεροπλάνο ξεκινά από την πόλη που έχει οριστεί ως αφετηρία και κατευθύνεται προς την πιο κοντινή πόλη. Η πόλη αφετηρία διαγράφεται από τη λίστα των πόλεων και η διαδικασία επαναλαμβάνεται με αφετηρία την πόλη στην οποία έφτασε το αεροπλάνο. Ο αλγόριθμος τερματίζεται όταν το αεροπλάνο επισκεφτεί όλες τις πόλεις. Να γραφεί το πρόγραμμα το οποίο να υλοποιεί τον πιο πάνω αλγόριθμο και το οποίο αφού διαβάσει τις αποστάσεις ανάμεσα στις πόλεις και τον αύξοντα αριθμό της πόλης που θα χρησιμοποιηθεί ως αφετηρία, να εκτυπώνει τη σειρά με την οποία θα τις επισκεφτεί το αεροπλάνο και το μήκος του συνολικού δρομολόγιου. Σημείωση: Για την καταχώρηση των αποστάσεων ανάμεσα στις πόλεις να οριστεί ένας πίνακας δύο διαστάσεων ο οποίος στην i γραμμή να περιέχει τις αποστάσεις των πόλεων από την υπ’ αριθμόν i πόλη. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: png on April 20, 2010, 13:46:54 pm έχει κάνει λάθος στην ημερομηνία παράδοσης...
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: iason1907 on April 20, 2010, 20:41:55 pm το ιδιο με το προηγουμενο πανω-κατω ε? δεν το διαβασα και ολο αλλα ετσι καταλαβα :D :D :D
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Γιώργος on April 20, 2010, 22:13:30 pm Καλά που δεν έβαλε και το TSP (http://en.wikipedia.org/wiki/Travelling_salesman_problem) :P
Πάρτε και ένα testcase για έλεγχο. Είσοδος (πρώτος αριθμός το N, δεύτερος αριθμός η πόλη-αφετερία και μετά οι αποστάσεις): Code: 5 Έξοδος: Code: 3 -> 1 -> 2 -> 0 -> 4 Φυσικά δεν είναι απαραίτητο να είναι και συμμετρικός ο πίνακας, εφόσον η εκφώνηση δεν το αναφέρει. Μπορεί πχ η απόσταση 1->2 να είναι 24 και η απόσταση 2->1 να είναι 29, γιατί ξέρω 'γω η πόλη 1 είναι σε βουνό. :P ps : προς αποφυγή παρεξηγήσεων, το testcase δεν είναι λύση ή κάτι συναφές. Είναι ένας τρόπος να τσεκάρετε αν τα προγράμματά σας τρέχουν σωστά, ελέγχοντας αν όλοι βγάζετε την ίδια έξοδο για δεδομένη είσοδο. disclaimer : το I/O format είναι όπως το έκανα εγώ, προφανώς και σε καμία περίπτωση δεν είναι δεσμευτικό. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: nohponex on April 21, 2010, 00:11:37 am ... Πάρτε και ένα testcase για έλεγχο. ... με την λύση που είχα κάνει κ βάζοντας τα δεδομένα αυτά βγάζω τα ίδια :), λογικά θα έχουμε και παρόμοιο τρόπο λύσης :P Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Μάρω on April 21, 2010, 14:14:06 pm Επειδή δεν έχω καταλάβει απόλυτα την εκφώνηση :P,
θα διαβάζει την αφετηρία κ τις αποστάσεις των άλλων πόλεων απ'την αφετηρία... βρίσκουμε την επόμενη αφετηρία, ξαναδιαβάζει τις αποστάσεις των άλλων πόλεων απ' αυτήν κ.ο.κ. ή καμία σχέση? Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Γιώργος on April 21, 2010, 14:53:31 pm Επειδή δεν έχω καταλάβει απόλυτα την εκφώνηση :P, θα διαβάζει την αφετηρία κ τις αποστάσεις των άλλων πόλεων απ'την αφετηρία... βρίσκουμε την επόμενη αφετηρία, ξαναδιαβάζει τις αποστάσεις των άλλων πόλεων απ' αυτήν κ.ο.κ. ή καμία σχέση? Μα προφανώς και μία φορά διαβάζεις τις αποστάσεις. :o Εκτός αν θεωρείς ότι έχουμε φαινόμενα μετακίνησης των τεκτονικών πλακών (http://en.wikipedia.org/wiki/Tectonic_plate) και οι αποστάσεις μεταξύ των πόλεων αλλάζουν κατά την εκτέλεση του προγράμματος. :P Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: st0up on April 21, 2010, 20:44:08 pm Έχει κανει malloc στο μαθημα? Η παλι πρεπει να κανουμε χρηση #define?
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Orfikoss on April 21, 2010, 21:51:35 pm Νο molloc yet...
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: The Stig on April 23, 2010, 00:33:36 am Μπορώ να μάθω γιατί κρασάρει το πρόγραμμα με το testcase του Γιώργου (btw χρόνια πολλά για σήμερα) ενώ ο compiler δεν βγάζει error??
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Γιώργος on April 23, 2010, 00:40:06 am Μπορώ να μάθω γιατί κρασάρει το πρόγραμμα με το testcase του Γιώργου (btw χρόνια πολλά για σήμερα) ενώ ο compiler δεν βγάζει error?? Δεν μπορούμε να βοηθήσουμε με τόσες λίγες πληροφορίες... Βρες σε ποια γραμμή σου σκάει αρχικά. Ίσως είναι θέμα μνήμης, δηλαδή πας να κάνεις πρόσβαση σε θέση μνήμης που δεν σου ανήκει. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: The Stig on April 23, 2010, 00:43:31 am Άκυρο το βρήκα! Μάλλον θα πρέπει να το ψάχνω πιο πολύ πριν ποστάρω...!
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: SolidSNK on April 23, 2010, 01:16:04 am Functions θέλει στην εργασία ο κορτέσης? Ενώ σίγουρα δε ζητά να γίνει με αναδρομή έτσι?
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: st0up on April 23, 2010, 11:39:03 am Μπερδευτηκα στο εξης: Ο χρηστης θα "γεμισει" τον πινακα με τις αποστασεις των πολεων και στη συνεχεια θα γινεται η αναζητηση της ελαχιστης? Ή θα δινει (οπως στην προηγουμενη εργασια) τις συντεταγμενες και μετα θα υπολογιζονται οι αποστασεις, θα εισαγονται στον πινακα και θα γινεται η αναζητηση της ελαχιστης???
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Orfikoss on April 23, 2010, 13:11:54 pm απ'ότι καταλαβαίνω αποστάσεις θέλει μόνο
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Lampros on April 25, 2010, 11:09:30 am Στον πίνακα η κύρια διαγώνιος θα είναι μηδενικά.Πρέπει να βάλουμε και έλεγχο γι'αυτό;Σε περίπτωση που ο χρήστης θέλει να μαλακιστεί, ας πούμε;
edit:Επίσης οταν λέει να διαβάζει τον αύξοντα αριθμός της πόλης,εννοεί να διαβάζει έναν αριθμό μιας πόλης έτσι;Δηλαδή η λέξη αύξοντας δεν έχει κάποιο νόημα εδώ Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: il capitano on April 25, 2010, 11:48:14 am 1.Γενικα αν το προγραμμα που θα εφτιαχνες θα το εδινες σε καποια εταιρια,θα κυκλοφορουσε στο εμποριο κλπ κλπ,θα επρεπε να βαλεις ελεγχο για τα παντα,γιατι πολλοι χρηστες μαλακιζονται ακουσια ή εκουσια (ελα δεν μπορει και συ θα το εχεις κανει :P)...Τωρα που ειναι μονο και μονο για τον κορτεση μπορεις και να μην βαλεις,δεν εγινε και τιποτα,ειναι τζαμπα παραπανω γραμμες κωδικα.
2.Οι πολεις θα αριθμουνται απο 0 ως Ν-1 ετσι πχ η πολη με α/α 10 θα βρισκεται στην θεση 10 του πινακα.Αυτο ειναι το νοημα το α/α. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: joal on April 25, 2010, 13:24:15 pm Ποιο το νοημα να χρησιμοποιησουμε πινακα 2 διαστασεων για τις αποστασεις?
1 γραμμη δεν ειναι αρκετη για να τις εκχωρησουμε.....? Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Μάρω on April 25, 2010, 15:39:51 pm Ποιο το νοημα να χρησιμοποιησουμε πινακα 2 διαστασεων για τις αποστασεις? 1 γραμμη δεν ειναι αρκετη για να τις εκχωρησουμε.....? σκέψου λίγο ότι θέλεις την απόσταση της πόλης 0 από τις 1,2,3,...,(ν-1) /* μόνο γι' αυτό χρειάζεται μια γραμμή */ στη συνέχεια, την απόσταση της πόλης 1 από τις 0,2,3,...,(ν-1) /* άλλη μια γραμμή */ κ.ο.κ. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: RaiDeR on April 25, 2010, 18:20:06 pm Καλά που δεν έβαλε και το TSP (http://en.wikipedia.org/wiki/Travelling_salesman_problem) :P Πάρτε και ένα testcase για έλεγχο. Είσοδος (πρώτος αριθμός το N, δεύτερος αριθμός η πόλη-αφετερία και μετά οι αποστάσεις): Code: 5 Έξοδος: Code: 3 -> 1 -> 2 -> 0 -> 4 Φυσικά δεν είναι απαραίτητο να είναι και συμμετρικός ο πίνακας, εφόσον η εκφώνηση δεν το αναφέρει. Μπορεί πχ η απόσταση 1->2 να είναι 24 και η απόσταση 2->1 να είναι 29, γιατί ξέρω 'γω η πόλη 1 είναι σε βουνό. :P ps : προς αποφυγή παρεξηγήσεων, το testcase δεν είναι λύση ή κάτι συναφές. Είναι ένας τρόπος να τσεκάρετε αν τα προγράμματά σας τρέχουν σωστά, ελέγχοντας αν όλοι βγάζετε την ίδια έξοδο για δεδομένη είσοδο. disclaimer : το I/O format είναι όπως το έκανα εγώ, προφανώς και σε καμία περίπτωση δεν είναι δεσμευτικό. το νουμερο 3 που δηλωνεις σαν αφετηρια εχει αποσταση απο το 1 και απο το 4 ιση οποτε δεν πιστευω να υπαρχει προβλημα αν το προγραμμα μας οδηγει αντι στην 1 στην 4 ... η συνολικη αποσταση βγαινει παλι ιδια :D:D:D Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Lampros on April 25, 2010, 19:01:33 pm Πως θα πάω την μια πόλη στην άλλη;Δηλαδή αν είμαι π.χ στη πόλη 1 και η πιο κοντινή είναι η 3,πως θα το γράψω αυτό;
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: nohponex on April 25, 2010, 19:09:21 pm Πως θα πάω την μια πόλη στην άλλη;Δηλαδή αν είμαι π.χ στη πόλη 1 και η πιο κοντινή είναι η 3,πως θα το γράψω αυτό; Αφαιρείς την 3 από τις διαθέσιμες , λες οτι η θέση σου τώρα είναι η 3 αντί για 1 π ήταν , το εκτυπώνεις αυτό και μετα φτου κ από την αρχή η διαδικασία ως που να τελειώσουν οι πόλεις.Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: RaiDeR on April 25, 2010, 20:49:43 pm να δωσω μια βοηθεια πως το εκανα εγω...
{ αρχικα βρηκα το μιμυμουμ για την αφετηρια ( εννοειτε με εναν ελεγχο που αποκλιει το 0 ;) ) μετα αποθηκευα τον αριθμο της πολης σε μια βοηθητικη μεταβλητη και μηδενιζα σε ολες τις γραμμες του πινακα την στηλη οπου βρισκετε η πολη ποιυ απεχει την ελαχιστη αποσταση ... και τυπωνα τον αριθμο της πολης ... επισης μου επεστρεφε τον αριθμο της πολης που απεχει την ελαχιστη αποσταση και το συνολικο δρομο που εχει διανυσει ως εκει } ΟΛΑ ΑΥΤΑ σε μια συναρτηση την οποια καλω Ν-2 φορες και στο τελος εκτυπωνα το συνολικο δρομο ... ελπιζω να βοηθησα σε γενικες γραμμες στον τροπο σκεψης ... Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Μάρω on April 25, 2010, 21:43:14 pm Χρειαζόμαστε στάνταρ συνάρτηση δηλ? ::)
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: giannaros on April 25, 2010, 22:20:24 pm ρε παιδια να ρωτισω κατι...την αφετηρια για αρχη την οριζουμε στην τυχη εμεις?
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Μάρω on April 25, 2010, 22:27:08 pm Να γραφεί το πρόγραμμα το οποίο να υλοποιεί τον πιο πάνω αλγόριθμο και το οποίο αφού διαβάσει τις αποστάσεις ανάμεσα στις πόλεις και τον αύξοντα αριθμό της πόλης που θα χρησιμοποιηθεί ως αφετηρία, να εκτυπώνει τη σειρά με την οποία θα τις επισκεφτεί το αεροπλάνο και το μήκος του συνολικού δρομολόγιου. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: RaiDeR on April 25, 2010, 22:27:57 pm ρε παιδια να ρωτισω κατι...την αφετηρια για αρχη την οριζουμε στην τυχη εμεις? νομιζω οτι θεωριτικα αν περιλμβανει μια επαναληψη οσα η συναρτηση ειναι σωστο συντακτικα αλλα και θα σου βγαλει τα σωστα αποτελεσματα .... οποτε δεν κρινω απαραιτητη την χρηση συναρτησης ... ωστοσο διευκολυνει και την λυση του προβληματος αλλα και ειναι σαφως πιο δομημενο το προγραμμα καθως και επαναχρησιμοποιησιμο ( το σκοτωσα :P ) .... @γιανναρος ναι την διαβαζει απο το πληκτρολογιο καθε φορα που τρεχει το προγραμμα ;) Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Lampros on April 26, 2010, 00:35:57 am Πως θα πάω την μια πόλη στην άλλη;Δηλαδή αν είμαι π.χ στη πόλη 1 και η πιο κοντινή είναι η 3,πως θα το γράψω αυτό; Αφαιρείς την 3 από τις διαθέσιμες , λες οτι η θέση σου τώρα είναι η 3 αντί για 1 π ήταν , το εκτυπώνεις αυτό και μετα φτου κ από την αρχή η διαδικασία ως που να τελειώσουν οι πόλεις.Δεν με βοηθάει και πολύ αυτό που είπες...εννοώ σε κώδικα πως θα το γράψω;Αν μπορεί κανείς να το γράψει θα είμαι υπόχρεος Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: RaiDeR on April 26, 2010, 01:14:31 am lambro
αρχικα βρηκα το μιμυμουμ για την αφετηρια ( εννοειτε με εναν ελεγχο που αποκλιει το 0 :) ) μετα αποθηκευα τον αριθμο της πολης σε μια βοηθητικη μεταβλητη και μηδενιζα σε ολες τις γραμμες του πινακα την στηλη οπου βρισκετε η πολη ποιυ απεχει την ελαχιστη αποσταση ... και τυπωνα τον αριθμο της πολης ... <-------- (Εδω απλως τυπωνεις τον αριθμο της πολης που απεχει ελαχιστη απο την προηγουμενη με μια πριντφ )... επισης μου επεστρεφε τον αριθμο της πολης που απεχει την ελαχιστη αποσταση και το συνολικο δρομο που εχει διανυσει ως εκει ΑΝ ΘΕΣ Code: ΚΩΔΙΚΑ Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: SolidSNK on April 26, 2010, 01:25:59 am jesus fucking christ..............................
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: iason1907 on April 26, 2010, 16:32:10 pm μεχρι σημερα το βραδυ δεν μπορουμε να την ανεβασουμε?? γτ μολις τωρα την ανεβασα εγω :P
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Μάρω on April 26, 2010, 16:40:00 pm μεχρι σημερα το βραδυ δεν μπορουμε να την ανεβασουμε?? γτ μολις τωρα την ανεβασα εγω :P ναι. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Sage on April 26, 2010, 16:54:54 pm Ρε παιδιά όταν πάω να κάνω RUN στον compiler (borland) σαυτήν και στη προηγούμενη άσκηση μ βγάζει σφάλμα..!!!
Εμφανίζει ένα νέο παραθυράκι π γράφει: "C0000 caused a Stack Fault in module C0000.EXE at 0001:0177." Τι παίζει..??? Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: τσαι-borg on April 26, 2010, 17:09:38 pm δεν ξερω γιατι το κανει αλλα το κανει και σε εμενα,
βασικα σε καποιο σημειο του κωδικα εχεις γραψει Code: ενα scanf("%f",&A[i][j]); Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Sage on April 26, 2010, 17:16:45 pm Ναι... εκεί που θα δημιουργείται ο 2σδιαστατος με τις αποστάσεις...!!
αλλά που κολλάει αυτό??? Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: τσαι-borg on April 26, 2010, 18:02:32 pm Α δεν ξερω.
απλα περασα ολο το μεσημερι μου προσπαθωντας να βρω που κολλαει η μαλακια. τελικα εκει κολλαει,το γιατι ομως δεν το εχω βρει ακομα. Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: Lampros on April 26, 2010, 19:42:10 pm Έχει κανείς σας χρησιμοποιήσει συνάρτηση;
υγ: γάμα το δεν βγάζω άκρη.Μπορεί κάποιος να μου στείλει τον κώδικα της εργασίας σε π.μ.;ευχαριστώ Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: kakashi on April 26, 2010, 20:39:19 pm Δεν είναι αναγκαστικό να χρησημοποιήσουμε συνάρτηση σωστά;Ρωτάω μπας και είπε τίποτα στο μάθημα ότι το θέλει συνάρτηση.Γιατί στην εκφώνηση δεν λέει τίποτα τέτοιο.
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: nohponex on April 26, 2010, 21:34:33 pm Ναι , βγαίνει και πολύ εύκολα χωρίς τη χρήση κάποιας συνάρτησης
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: pepe on April 26, 2010, 21:40:03 pm Ας μου πει κάποιος σας παρακαλώ ΤΙ ΣΤΟ ΚΕΡΑΤΟ κάνω λάθος!!!!!!!! Θέλω να αποθηκεύσω στο min την πρώτη μη μηδενική τιμή που θα βρει και μετά να βγαίνει απ' το do/while...
Code: i=0; Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: nohponex on April 26, 2010, 21:52:11 pm } while (min==0); 8))
και το break; δεν νμζ να είναι αναγκαίο Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: pepe on April 26, 2010, 21:54:51 pm } while (min==0); 8)) ΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑΑ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! >:( >:( >:( >:( >:( >:( >:( >:( >:( >:( >:( >:( >:( >:( >:(Και στην προηγούμενη εργασία το ίδιο λάθος έκανα και τώρα έψαχνα μην έχω κάνει κάτι τέτοιο στο if!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Τελικά είμαι πολύ μπούφος! ;D ;D ;D ;D Ευχαριστώ φίλε! Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: i.88 on April 27, 2010, 00:01:20 am γιατι δεν μπορω να μπω στο ethmmy να την ανεβάσω ?
τι να κανω ?? Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: τσαι-borg on April 27, 2010, 00:04:20 am εκτος απο το να μην περιμενεις να παει 12.03 για να την ανεβασεις,να κανεις λιγο υπομονη .
ουτως ή αλλως ο κορτεσης το πρωι "κλεινει" τα uploads.(ετσι μου ειπαν δηλαδη) Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: i.88 on April 27, 2010, 00:07:14 am θα δοκιμασω σε λιγο . . . πρωτη φορα την ανεβασω teleutea stigmi :)
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: iason1907 on April 27, 2010, 00:12:57 am αντε.. ακομα να ανεβει η D??? :P :P :P
Title: Re: [Δομημένος Πρ.] Εργασία C 09/10 Post by: png on April 27, 2010, 00:37:45 am αντε.. ακομα να ανεβει η D??? :P :P :P τώρα θα φταίω εγώ; :P ::) |