Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση

Ξεκίνησε από evry, 14 Απρ 2012, 11:13:06 ΠΜ

« προηγούμενο - επόμενο »

evry

Δίνω 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 στον αριθμό).
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Πανάγος94

δεν θα έπρεπε να εξασφαλίζεται ότι το πηλίκο (αριθμός βιβλίων/Ν) είναι ακέραιος, δηλαδή ότι υπάρχουν αρκετά βιβλία ώστε οι στοίβες να είναι ισουψείς??  :P .... να φανταστώ εννοείται???

evry

What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Anastasis13

Το βέλτιστο είναι και το διαισθητικό για την πρώτη άσκηση; Εξηγώ τον αλγόριθμο:

1.Βρίσκω την πρώτη σε σειρά στοιβα που έχει παραπάνω βιβλία από ότι πρέπει (A[σ] > N/πλήθος βιβλιων)
2.Βρίσκω την πρώτη σε σειρά στοίβα που έχει λιγότερα βιβλία από ότι πρέπει και αδειάζω από αυτή με τα περισσότερα μέχρις ότου αυτή με τα περισσότερα να φτάσει στον σωστό αριθμό βιβλίων η αυτή που έχει λιγότερα να φτάσει στον σωστό αριθμό βιβλίων 
3. Επανάλαβε 2,3 μέχρις ότου κάθε στοίβα να έχει τον σωστό αριθμό βιβλίων

Σχετικά με την δεύτερη ασκηση μπορούμε να χρησιμοποιήσουμε πινακα μεγέθους Ν που να κρατάμε μέχρι τώρα ποσά βιβλία έχουν τοποθετηθεί στην στοίβα i ;