THMMY.gr

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

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


εδιτ: τιτλος

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

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

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

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

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

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

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

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

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

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

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

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

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

Αν έχω 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?

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

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

Εχει καποιες ιδεες σε ποστ παραπανω,εγω παντως το εκανα με shift του πινακα στις θεσεις που γινοταν αντικατασταση,Θα μπορουσες επισης να φτιαχνεις εναν νεο πινακα,παραλειπωντας τις θεσεις οπου αντικαθαστεις,και να αντιγραφεις το νεο πινακα πανω στον παλιο μειωνοντας το Ν κατα 2.

καθως κανω compile το προγραμμα με dev μου βγαζει απο κατω λαθη του τυπου stray'\204' in program..και τα εμφανιζει εκει που κανω τη δηλωση της join και γραφω τα ορισματα της..μηπως ξερει κανεις τι μπορει να συμβαινει?

πως σκατα θα βγάζει τα δεδομένα η find_pair και γιατί πρεπει να φτιαξω την join όταν μπορω να την εχω μεσ'τη main με 2 σειρες;

παίζει κανείς να ανεβάσει κανενα ψευδοκώδικα ή μια προτυπη λυση για να παρουμε καμια ιδεα;

Eλα ντε. Δε μπορω να καταλαβω το σκεπτικο του κορτεση. Και ολο συντεταγμενες με πυλωνες. Βαλε κατι διαφορετικο ...

νομιζω αν κανετε pass by reference η find_pair επιστρεφει ο,τι θελετε.Πρεπει να το εχει και στις σημειωσεις του κορτεση σαν κληση με αναφορα

Den mporoume ston pinaka me tis apostaseis na midenisoume tn apostasi ap tous radiofarous pou antika8istountai???

αν μηδενισεις αυτες τις αποστασεις ,σαν μηδεν θα ειναι οι μικροτερες

Den mporoume meta na kanoume elegxo gia na mn dexetai to 0 san elaxisto?

olo kai pio dusnoites oi ergasies  tou kortesi :o

enw oli i ergasia einai swsti otan kanw compile mou vgazei"expected primary expression before int" kai "expected ; before int"
sti grammi pou exw to int main()
KSEREI KANEIS TI NA KANW???

για το "expected ; before int" σημαινει οτι θελει ; στην δηλωση της συναρτησης που εβαλες μαλλον στην προηγουμενη σειρα.
νομιζω βασικα οτι και το πρωτο το ιδιο εννοει.