[ΔΟΜΗΜΕΝΟΣ ΠΡ] ΕΡΓΑΣΙΑ Ε

[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 με προσοχή στα ονόματα των αρχείων!

Για οποιοδήποτε πρόβλημα με register/login, στείλτε email στο contact@thmmy.gr.

[pepper ann]

Εργαστήριο Ε
Για τον έλεγχο της εναέριας κυκλοφορίας, σε μια περιοχή, υπάρχουν εγκατεστημένοι Ν ραδιόφαροι για τους οποίους είναι γνωστές οι συντεταγμένες x,y της θέσης στην οποία βρίσκονται. Μια νέα τεχνολογία επιτρέπει την αντικατάσταση ενός ζεύγους ραδιόφαρων από έναν ραδιόφαρο της νέας τεχνολογίας. Η απόδοση του ραδιόφαρου νέας τεχνολογίας είναι αντιστρόφως ανάλογη με την απόσταση που υπάρχει ανάμεσα στους δύο ραδιόφαρους που θα αντικαταστήσει. Για να εντοπιστούν τα ζεύγη των ραδιόφαρων που θα αντικατασταθούν χρησιμοποιείται μια αναδρομική διαδικασία. Σε κάθε βήμα της αναδρομικής διαδικασίας εντοπίζονται από τη λίστα των ραδιόφαρων οι δύο ραδιόφαροι που απέχουν τη μικρότερη μεταξύ τους απόσταση οι οποίοι και σχηματίζουν ένα ζεύγος που θα αντικατασταθεί. Στη συνέχεια οι ραδιόφαροι αυτοί αφαιρούνται από τη λίστα και η διαδικασία επαναλαμβάνεται με τους υπόλοιπους ραδιόφαρους.
Να γραφεί το πρόγραμμα στο οποίοι να ορίζονται:
α) Η συνάρτηση void find_pair() η οποία να δέχεται, μέσα από τα ορίσματά της, τις συντεταγμένες των θέσεων των ραδιόφαρων και να βρίσκει το ζεύγος των ραδιόφαρων που απέχουν μεταξύ τους την μικρότερη απόσταση.
β) Η συνάρτηση join() η οποία, μέσα από μια αναδρομική διαδικασία (recursion), καλώντας τη συνάρτηση find_pair(), εκτυπώνει τις συντεταγμένες των ζευγών των ραδιόφαρων που θα συγχωνευτούν.    
Η συνάρτηση main() του προγράμματος, αφού διαβάσει τον αριθμό Ν των ραδιόφαρων, να δεσμεύει δυναμικά μνήμη για την καταχώρηση των συντεταγμένων των θέσεών τους και στη συνέχεια να καλεί τη συνάρτηση join() για να εκτυπωθούν οι συντεταγμένες των ζευγών των ραδιόφαρων που θα συγχωνευτούν.

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


εδιτ: τιτλος

[Άντι ιστ κρίιγκ]

Οι πίνακες θα είναι με Pointer/malloc? Επειδή η εκφώνηση δεν αναφέρει κάτι.

Επίσης, πώς θα γίνεται η "αφαίρεση" των ραδιοφάρων που έχουν ήδη ζευγαρωθεί μεταξύ τους; Σκέφτομαι μερικούς τρόπους αλλά είναι πολύ περίπλοκοι και λίγο 'μπακαλικοι', σίγουρα υπάρχει κάποιος άλλος τρόπος και μου διαφεύγει, εχει σκεφτεί κάποιος τίποτα;

[teslaaaa]

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

[Άντι ιστ κρίιγκ]

Κι εγώ κάτι παρόμοιο έκανα τώρα, βασικά βρήκα πρώτα max distance και τους "ζευγαρωμένους" τους δίνω τιμή max distance+1. Ευχαριστώ!

[titan1]

Μήπως λύνεται με συνδεδεμένες λίστες; (Linked list)
Αυτά τα έχει παραδώσει;

[Asborampage]

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

Πώς ακριβώς το κάνεις αυτό; Θα έχεις και έναν τρίτο πίνακα με τον αύξοντα αριθμό του κάθε ραδιοφάρου;

[stathisss]

εγώ έτσι το έκανα,δημιούργησα ένα πίνακα με τον αύξοντα αριθμό του ραδιοφάρου και σε όσους ήθελα να διαγράψω έβαζα αριθμό= Ν+1 και στην επανάληψη έκανα τον σχετικό έλεγχο...........
Έχω και μια ερώτηση.....Μπορεί κάποιος να μου εξηγήσει με 2-3 λόγια πως θα περάσουμε τα ορίσματα από την main μέσω της join στην Find_pair.Ή  αν έχει την καλοσύνη να μας γράψει πώς τις κάλεσε κ πως τις όρισε τις 2 συναρτήσεις!!
ΕΥΧΑΡΙΣΤΩ 

[elen//]

Μήπως λύνεται με συνδεδεμένες λίστες; (Linked list)
Αυτά τα έχει παραδώσει;

ξερει κανεις που ειναι στην υλη?

[ΚΗΜΜΥ]

Μήπως λύνεται με συνδεδεμένες λίστες; (Linked list)
Αυτά τα έχει παραδώσει;

ξερει κανεις που ειναι στην υλη?

Στις δομες δεδομενων

[mamalos]

Παιδιά, μην το μπερδεύετε το πράγμα στο μυαλό σας. Άκουσα διάφορα για realloc, με ρωτήσανε πως χρησιμοποιούμε τη malloc για pointer σε pointer, βλέπω να μιλάτε για linked lists...ΜΗΝ κάνετε τη ζωή σας δύσκολη!! Αρκεί να δίνετε σε κάθε κλήση της αναδρομικής συνάρτησης -2 ραδιοφάρους σε σχέση με την προηγούμενη κλήση της. Δε νομίζω ότι χρειάζεστε καινούριο πίνακα για να το κάνετε αυτό, ούτε διδιάστατο, ούτε linked lists κλπ...:-). Δεν είναι εύκολο, αλλά λύνεται. Βάλτε χαρτί και μολύβι και δείτε τα ενδεχόμενα σενάρια.

Ο Κορτέσης αναφέρει στην εργασία "Στη συνέχεια οι ραδιόφαροι αυτοί αφαιρούνται από τη λίστα και η διαδικασία επαναλαμβάνεται με τους υπόλοιπους ραδιόφαρους", εννοώντας αυτό ακριβώς που γράφει. ΔΕΝ εννοεί τον πίνακα που θα έχετε δεσμεύσει εσείς με malloc, μιλάει αλγοριθμικά όχι προγραμματιστικά.

@Άντι ιστ κρίιγκ: Δε θα σας λέει πότε χρησιμοποιείτε malloc και πότε πίνακα, αν σου λέει δυναμικά σημαίνει malloc και πάπαλα. "...Ν των ραδιόφαρων, να δεσμεύει δυναμικά μνήμη ...". Έτσι είναι και στις εξετάσεις.
 

[yellow tsif]

Να ρωτήσω κάτι άλλο...

Αν έχω 4 ραδιόφαρους και έχουν ας πούμε συντεταγμένες
R0:(0,0)
R1:(2,0)
R2:(4,0)
R3:(7,0)

η distance[0][1] είναι ίδια με την distance[1][2].

To πρόγραμμα αν ξεκινήσει από το ζεύγος R0-R1 (απόσταση=2) τότε θα προχωρήσει με το R2-R3 (απόσταση=3).
Αν όμως ξεκινήσει με το ζεύγος R1-R2 (απόσταση=2 πάλι) τότε θα προχωρήσει με το ζεύγος R0-R3 (απόσταση=7 (!)).

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

Δηλαδή,για παράδειγμα στο δικό μου πρόγραμμα, αν τους δηλώσω ως
R0:(4,0)
R1:(7,0)
R2:(2,0)
R3:(0,0)
τότε  παίρνω τη βέλτιστη λύση, ενώ όταν τους δηλώνω όπως στην αρχή τότε παίρνω την άλλη λύση.

 
Αυτό σημαίνει ότι πρέπει να βρω και σε περίπτωση ίσων ελαχίστων αποστάσεων, ποιο "μονοπάτι" είναι το βέλτιστο,ε...?
Κρίμα, και νόμιζα ότι την κατάφερα...

[christineL]

Και πως θα το κανουμε αυτο ? Ας το διευκρινιζε στην ασκηση ! Τώρα απλα θα του δωσουμε μια λυση σωστη μεν(αλλα αν ειναι τυχερος θα ειναι και  η βελτιστη δε!!!).

[Silvershot]

Να ρωτήσω κάτι άλλο...

Αν έχω 4 ραδιόφαρους και έχουν ας πούμε συντεταγμένες
R0:(0,0)
R1:(2,0)
R2:(4,0)
R3:(7,0)

η distance[0][1] είναι ίδια με την distance[1][2].

To πρόγραμμα αν ξεκινήσει από το ζεύγος R0-R1 (απόσταση=2) τότε θα προχωρήσει με το R2-R3 (απόσταση=3).
Αν όμως ξεκινήσει με το ζεύγος R1-R2 (απόσταση=2 πάλι) τότε θα προχωρήσει με το ζεύγος R0-R3 (απόσταση=7 (!)).

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

Δηλαδή,για παράδειγμα στο δικό μου πρόγραμμα, αν τους δηλώσω ως
R0:(4,0)
R1:(7,0)
R2:(2,0)
R3:(0,0)
τότε  παίρνω τη βέλτιστη λύση, ενώ όταν τους δηλώνω όπως στην αρχή τότε παίρνω την άλλη λύση.

 
Αυτό σημαίνει ότι πρέπει να βρω και σε περίπτωση ίσων ελαχίστων αποστάσεων, ποιο "μονοπάτι" είναι το βέλτιστο,ε...?
Κρίμα, και νόμιζα ότι την κατάφερα...

Πολυ σωστη παρατηρηση και σιγουρα θα υπαρχει τροπος να το καταφερεις( δηλαδη να γραψεις μια βελτιστη λυση ), αλλα δεν νομιζω οτι χρειαζεται τοσο ψαξιμο. Η ασκηση απο μονη της εχει μια alpha δυσκολια , ε τωρα αν ηθελε και αυτο που λες νταξ το γ*μαει το πραγμα. Παντως θα γινεται με καποιου ειδους ταξινομηση απο οτι καταλαβα αλλα μονο που το σκεφτομαι φαινεται πολυ περιπλοκο. Ισως και να μην ειναι ομως, αλλα σε αυτη τη φαση δεν πιστευω πως θεωρειται ελειπης η λυση αν δε το λαβουμε υποψην.

Να κανω μια ερωτηση, αφου γινει η ολη διαδικασια, πως θα μπορουσα να τερματισω το recursion?

[Faros]

Η διαδικασια σταματαει οταν ο πινακας σου μεινει με 1 στοιχειο,η κανενα.Οποτε η το κανεις με ενα If (n<1),η με μια σημεα.

[Silvershot]

Η διαδικασια σταματαει οταν ο πινακας σου μεινει με 1 στοιχειο,η κανενα.Οποτε η το κανεις με ενα If (n<1),η με μια σημεα.

H εκφωνηση λεει να αφαιρουνται απο τη λιστα αλλα πως γινεται να τα αφαιρεις απο πινακα?