Το Στέκι των Πληροφορικών

Γενικό Λύκειο => Γ΄ Λυκείου => Μονοδιάστατοι πίνακες => Μήνυμα ξεκίνησε από: evry στις 14 Απρ 2012, 11:13:06 πμ

Τίτλος: Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση
Αποστολή από: evry στις 14 Απρ 2012, 11:13:06 πμ
Δίνω 2 ασκήσεις που έχουν πολύ ενδιαφέρον αν ψάξουμε για την αποδοτική λύση.
Λύσεις που εξετάζουν διεξοδικά όλες τις περιπτώσεις (brute force) είναι μη αποδεκτές  >:D
Οι λύσεις είναι αρκετά απλές και βασίζονται σε μια απλή σκέψη ή παρατήρηση. Τέτοιου είδους ασκήσεις είναι αρκετά εκτός κλίματος ΑΕΠΠ, έχουν όμως πολύ ενδιαφέρον.
Η διαφορά με την ΑΕΠΠ είναι ότι εδώ ζητείται από τον μαθητή να κάνει Ανάλυση Προβλήματος και να σχεδιάσει τη λύση σε αντίθεση με το μάθημά μας όπου η λύση δίνεται και ζητείται απλά η κωδικοποίηση.

Άσκηση 1 (Ξαναφτιάξε τις στοίβες)
Στην αρχή της χρονιάς οι καθηγητές ενός σχολείου έχουν ταξινομήσει τα βιβλία σε στοίβες έτσι να είναι όλες ισοϋψείς μεταξύ τους. Η διανομή των βιβλίων μπορεί να ξεκινήσει μόνο αν οι στοίβες είναι ισοϋψείς (με βάση κάποιον πολύ παλιό νόμο της εκπαίδευσης) και αυτό το ξέρουν οι μαθητές. Έτσι κάποιοι μαθητές που θέλουν να "καθυστερήσουν" λίγο την παραλαβή των βιβλίων κάνουν τις στοίβες άνω κάτω, μεταφέροντας βιβλία από την μια στοίβα στην άλλη.

Να γράψετε αλγόριθμο ο οποίος θα βοηθάει τους καθηγητές να υπολογίσουν πόσες είναι οι λιγότερες δυνατές μετακινήσεις βιβλίων που χρειάζονται ώστε οι στοίβες να γίνουν πάλι ισοϋψείς.
Έστω Ν οι στοίβες και Α[Ν] ο πίνακας του οποίου το τυχαίο στοιχείο Α[σ] περιέχει το ύψος της σ στοίβας.

Άσκηση 2 (Εκτύπωση βιβλίων)
Στις αποθήκες του ΟΕΔΒ τα βιβλία της επόμενης σχολικής χρονιάς έχουν εκτυπωθεί αλλά οι εργαζόμενοι δεν έχουν πολύ χρόνο γιατί είναι ήδη Σεπτέμβρης και πρέπει να κινηθούν γρήγορα.
Επειδή το υπερσύγχρονο σύστημα ταξινόμησης βιβλίων έχει χαλάσει είναι αναγκασμένοι να τα τοποθετούν με το χέρι στις στοίβες.

Κάθε στοίβα βιβλίων είναι αριθμημένη με αριθμούς από 1 εώς Ν. Θεωρήστε το Ν δεδομένο.
Αρχικά όλες οι στοίβες είναι άδειες. Η τοποθέτηση των βιβλίων γίνεται ως εξής:
Σε κάθε εργαζόμενο δίνονται επαναληπτικά οδηγίες. Κάθε οδηγία περιέχει δύο αριθμους Χ, Υ που αντιστοιχούν σε 2 στοίβες βιβλίων την Χ και την Υ. Ο εργαζόμενος θα πρέπει να τοποθετήσει από ένα βιβλίο σε όλες τις στοίβες από την Χ μέχρι και την Υ. Για παράδειγμα αν δοθούν οι αριθμοί 19 και 23 θα πρέπει να προσθέσουμε από ένα βιβλίο στις στοίβες 19, 20, 21, 22, 23.

Να γράψετε αλγόριθμο ο οποίος αφού διαβάσει 1.000.000 οδηγίες (κάθε οδηγία είναι ζεύγος 2 αριθμών) θα υπολογίζει και θα εμφανίζει τη στοίβα με τα περισσότερα βιβλία, αφού γίνουν όλες οι τοποθετήσεις.

π.χ. αν οι οδηγίες είναι οι παρακάτω
11 13
12 14
13 15

τότε η στοίβα νο 13 είναι αυτή με τα περισσότερα βιβλία (3 στον αριθμό).
Τίτλος: Απ: Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση
Αποστολή από: Πανάγος94 στις 14 Απρ 2012, 12:27:09 μμ
δεν θα έπρεπε να εξασφαλίζεται ότι το πηλίκο (αριθμός βιβλίων/Ν) είναι ακέραιος, δηλαδή ότι υπάρχουν αρκετά βιβλία ώστε οι στοίβες να είναι ισουψείς??  :P .... να φανταστώ εννοείται???
Τίτλος: Απ: Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση
Αποστολή από: evry στις 14 Απρ 2012, 12:27:47 μμ
ναι εννοείται