Η εταιρεία “Ελληνικές υαλόσφαιρες” κατασκευάζει γυάλινες μπάλες από ειδικό γυαλί. Κάθε μέρα παράγει ένα σύνολο από μπάλες ίδιας αντοχής. Ωστόσο, διαφορετικά σύνολα μπορεί να έχουν διαφορετική αντοχή. Για να μετρήσει την αντοχή κάθε συνόλου, ο μηχανικός παραγωγής ακολουθεί την εξής διαδικασία: Αφήνει σε ελεύθερη πτώση κάποιες μπάλες (από ένα σύνολο) από διαφορετικά επίπεδα ενός κτιρίου και, επομένως, παριστάνει την αντοχή τους με το χαμηλότερο επίπεδο στο οποίο η μπάλα θα σπάσει στην ελεύθερη πτώση. Κάθε επίπεδο καθορίζεται από ένα όροφο. Στην αρχή αποφασίζει να ανεβαίνει ένα – ένα τα πατώματα και να εκτελεί το πείραμα διαδοχικά. Επομένως αν μια μπάλα έχει αντοχή 10, θα εκτελέσει 10 προσπάθειες. Μετά αποφάσισε να κάνει κάτι πιο γρήγορο, με κόστος να χρησιμοποιεί περισσότερες μπάλες. Έτσι αποφάσισε να εκτελεί τυχαία πειράματα από διαφορετικούς ορόφους ώστε να περιορίζει τους ορόφους που θα κάνει προσπάθειες. Το «αφεντικό» του όμως βρίσκει ότι σπάει πολλές μπάλες έτσι και του προτείνει να βρίσκει την αντοχή χρησιμοποιώντας μόνο δύο μπάλες από κάθε σύνολο. Μετά από σκέψη ο μηχανικός αποφασίζει να κάνει το εξής. Θα χρησιμοποιήσει την πρώτη μπάλα για μια προσπάθεια από τον μεσαίο όροφο. Αν η μπάλα σπάσει, είναι σίγουρο ότι η αντοχή της είναι μικρότερη ή ίση από αυτή που αντιστοιχεί στο μεσαίο επίπεδο. Επομένως, θα χρησιμοποιήσει την δεύτερη μπάλα για να ελέγξει την αντοχή σειριακά ξεκινώντας από το πρώτο επίπεδο και δοκιμάζοντας διαδοχικά κάθε επίπεδο. Αν όμως δεν σπάσει όταν αφεθεί σε ελεύθερη πτώση από το μεσαίο επίπεδο, τότε θα αποκλείσει το κάτω μισό του κτιρίου και θα συνεχίσει με τον ίδιο τρόπο για το άνω μισό. Δηλαδή χρησιμοποιώντας πάλι την πρώτη μπάλα θα προσπαθήσει να βρει την αντοχή της συνεχίζοντας από το μεσαίο επίπεδο του πάνω μισού του κτιρίου. Παρόμοια, θα εκτελεί ένα βήμα τύπου δυαδικής αναζήτησης αν η πρώτη μπάλα αντέχει στην ελεύθερη πτώση ή ένα βήμα γραμμικής αναζήτησης μετά από το σπάσιμο της πρώτης μπάλας.
Πρόβλημα:
Να αναπτύξετε ένα πρόγραμμα σε Γλώσσα, το οποίο αφού καταχωρήσει σε έναν Πίνακα [20 Χ 2] θέσεων τα επίπεδα ελέγχου και την αντοχή κάθε μπάλας στη συνέχεια, θα υπολογίζει και θα εμφανίζει για κάθε μπάλα το μικρότερο αριθμό προσπαθειών που απαιτείται για να υπολογιστεί η αντοχή της (Καμιά μπάλα δεν σπάει στο ισόγειο). ΕΠΥ, 19* Π.Δ.Π. (2007) Τελική Φάση (2° θέμα)
Λύση:
ΠΡΟΓΡΑΜΜΑ ΑΣΚ3_ΠΑΡ_Β_ΙΕΠ_ΠΙΝ_ΜΠΑΛΕΣ_ΥΑΛΟΥ ΣΤΑΘΕΡΕΣ n=1 ! πλήθος μπαλών ΜΕΤΑΒΛΗΤΕΣ ΑΚΕΡΑΙΕΣ: i,j, b[n,2], c[n], count, epipeda, antoxi, top, bottom, middle, dif ΛΟΓΙΚΕΣ: broken ΑΡΧΗ ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n ΓΙΑ j ΑΠΟ 1 ΜΕΧΡΙ 2 ΔΙΑΒΑΣΕ b[i,j] ! Επίπεδα ελέγχου, αντοχή ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n count <-- 0 top <-- b[i,1] ! επίπεδα bottom <-- 1 middle <-- 0 antoxi <-- b[i,2] broken <-- ΨΕΥΔΗΣ ΟΣΟ broken = ΨΕΥΔΗΣ ΕΠΑΝΑΛΑΒΕ middle <-- (top + bottom) DIV 2 ! 'δυαδική' ΑΝ antoxi <= middle ΤΟΤΕ ! έσπασε ή σπάει στην επόμενη δοκιμή broken <-- ΑΛΗΘΗΣ ΓΙΑ j ΑΠΟ bottom ΜΕΧΡΙ antoxi+1 ! σειριακή από την αρχή του τρέχοντος επιπέδου count <-- count + 1 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΑΛΛΙΩΣ count <-- count + 1 bottom <-- middle + 1 ! 'δυαδική' ΤΕΛΟΣ_ΑΝ ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ c[i] <-- count ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΓΙΑ i ΑΠΟ 1 ΜΕΧΡΙ n ΓΡΑΨΕ b[i,1], b[i,2], c[i] ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ ! Παράδειγμα: (επίπεδα, αντοχή) ! 7 2 ! (δυαδική) ! top=7, bottom=1, middle=4 > αντοχή ! από bottom = 1: (σειριακή) ! 1η δοκιμή στο 1 ! 2η δοκιμή στο 2 ! 3η δοκιμή στο 3 σπάει! ! 7 5 ! (δυαδική) ! top=7, bottom=1, middle=4, ! 1η δοκιμή, στο επίπεδο 4 ! top=7 bottom=5 middle=6 > αντοχή ! από bottom = 5: (σειριακή) ! 2η δοκιμή στο 5 ! 3η δοκιμή στο 6 σπάει!
Πρόσφατα σχόλια