Αποστολέας Θέμα: Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση  (Αναγνώστηκε 1661 φορές)

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3282
  • to Iterate is human to Recurse divine
Δίνω 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 στον αριθμό).
« Τελευταία τροποποίηση: 14 Απρ 2012, 12:27:30 μμ από evry »
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

Πανάγος94

  • Βετεράνος
  • ****
  • Μηνύματα: 65
  • what doesn't kill you only makes you pissed off..
Απ: Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση
« Απάντηση #1 στις: 14 Απρ 2012, 12:27:09 μμ »
δεν θα έπρεπε να εξασφαλίζεται ότι το πηλίκο (αριθμός βιβλίων/Ν) είναι ακέραιος, δηλαδή ότι υπάρχουν αρκετά βιβλία ώστε οι στοίβες να είναι ισουψείς??  :P .... να φανταστώ εννοείται???

evry

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 3282
  • to Iterate is human to Recurse divine
Απ: Ασκήσεις με Στοίβες που αναζητούν Αποδοτική Λύση
« Απάντηση #2 στις: 14 Απρ 2012, 12:27:47 μμ »
ναι εννοείται
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr