Παράδειγμα 2, Κεφάλαιο 10, Τετράδιο μαθητή (εργασιών), Πύργος του Ανόι

Ένα χαρακτηριστικό πρόβλημα το οποίο λύνεται εύκολα με τη χρήση αναδρομής, ενώ είναι πολύ δύσκολο με επαναληπτική διαδικασία, είναι οι πύργοι του Ανόι. Στο πρόβλημα των πύργων του Ανόι υπάρχουν τρεις στύλοι και στον πρώτο από αυτούς βρίσκονται περασμένοι δίσκοι διαφορετικής διαμέτρου, έτσι ώστε οι διάμετροι των δίσκων να μικραίνουν από κάτω προς τα πάνω. Όλοι οι δίσκοι, που βρίσκονται στον πρώτο στύλο, πρέπει να μεταφερθούν στο τρίτο ακολουθώντας τους εξής κανόνες:

  • Όταν ένας δίσκος μεταφέρεται, πρέπει να τοποθετηθεί σε έναν από τους τρεις στύλους.
  • Μόνο ένας δίσκος μπορεί να μεταφερθεί κάθε φορά και πρέπει να βρίσκεται στην κορυφή του στύλου.
  • Ένας μεγαλύτερος δίσκος δεν πρέπει να τοποθετηθεί πάνω από ένα μικρότερο.

Το παιγνίδι είναι σχετικά εύκολο να λυθεί για μικρό αριθμό δίσκων, τρεις-τέσσερις, αλλά δυσκολεύει εξαιρετικά όσο ο αριθμός των δίσκων αυξάνεται. Η γενική διατύπωση της λύσης όμως με χρήση αναδρομικής διαδικασίας είναι αρκετά απλή και περιγράφεται από τα παρακάτω βήματα:

  • Αν υπάρχει μόνο ένας δίσκος, τότε μεταφέρεται από το Στύλο1 στο Στύλο3. Το πρόβλημα λοιπόν έχει λύση για Ν = 1.
  • Αν υπάρχουν δύο δίσκοι, τότε χρειάζονται τρεις απλές κινήσεις:
    • Ο πρώτος δίσκος από το Στύλο1 μεταφέρεται στο Στύλο2.
    • Ο δεύτερος δίσκος από το Στύλο2 μεταφέρεται στο Στύλο3.
    • Ο δίσκος από το Στύλο2 μεταφέρεται στο Στύλο3.
  • Υποθέτουμε ότι η λύση υπάρχει για Ν-1 δίσκους, τότε για Ν δίσκους η λύση δίνεται αναδρομικά: l
  • Οι Ν-1 δίσκοι μεταφέρονται από το Στύλο1 στο Στύλο2, χρησιμοποιώντας το Στύλο3 ως βοηθητικό. l
  • Ο τελευταίος δίσκος, που είναι ο τελευταίος άρα και ο μεγαλύτερος, μεταφέρεται από το Στύλο1 στο Στύλο3.
  • Οι Ν-1 δίσκοι μεταφέρονται από το Στύλο2 στο Στύλο3, χρησιμοποιώντας το Στύλο1 ως βοηθητικό. Το πρόγραμμα που λύνει τους Πύργους του Ανόι είναι το ακόλουθο:

(περισσότερα…)

Ερώτημα 4, Θέμα A, 2006, Μαΐου-Ιουνίου, Ημερήσια

Να γράψετε στο τετράδιό σας τους αριθμούς της Στήλης Α και δίπλα το γράμμα της Στήλης Β που αντιστοιχεί σωστά. Στη Στήλη Β υπάρχει ένα επιπλέον στοιχείο.

Στήλη Α Στήλη Β
1. “ΑΛΗΘΗΣ” α. λογικός τελεστής
2. ΚΑΙ β.   μεταβλητή
3. α > 12 γ.   αλφαριθμητική σταθερά
4. αριθμός_παιδιών δ.   λογική σταθερά
5. ε.   συγκριτικός τελεστής
στ. συνθήκη

Μονάδες 5

Τα θέματα σε pdf, 2006, Μαΐου-Ιουνίου, Ημερήσια