Επιλογή Σελίδας

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

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

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

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

ΠΡΟΓΡΑΜΜΑ Πύργοι_του_Ανόι 
! ΣΤΑΘΕΡΕΣ
! Στύλος1 = 'Α'
! Στύλος2 = 'Β'
! Στύλος3 = 'Γ'
ΜΕΤΑΒΛΗΤΕΣ 
ΑΚΕΡΑΙΕΣΧΑΡΑΚΤΗΡΕΣ: Στύλος1 ,Στύλος2, Στύλος3 
ΑΡΧΗ
Στύλος1<-- 'Α'
Στύλος2<-- 'Β'
Στύλος3<-- 'Γ'
ΓΡΑΨΕ 'δώσε τον αριθμό των δίσκων' 
ΔΙΑΒΑΣΕ Ν 
! Παρόραμα ή ασάφεια - Είναι δυνατή η χρήση σταθερών ως παράμετρων υποπρογράμματος;
! Δεν υποστηρίζεται από τη Γλωσσομάθεια
ΚΑΛΕΣΕ Μετακίνησε(Ν, Στύλος1, Στύλος2, Στύλος3) 
ΤΕΛΟΣ_ΠΡΟΓΡΑΜΜΑΤΟΣ

ΔΙΑΔΙΚΑΣΙΑ Μετακίνησε(Ν, ΣτύλοςΑ, ΣτύλοςΒ, ΣτύλοςΓ) 
ΜΕΤΑΒΛΗΤΕΣ 
ΑΚΕΡΑΙΕΣ
ΧΑΡΑΚΤΗΡΕΣ: ΣτύλοςΑ, ΣτύλοςΒ,ΣτύλοςΓ 
ΑΡΧΗ 
ΑΝ Ν=1 ΤΟΤΕ  
   ΓΡΑΨΕ 'Μετακίνησε από τον', ΣτύλοςΑ, ' στον' , ΣτύλοςΓ 
ΑΛΛΙΩΣ
   Ν<-- Ν-1 ! Η γλωσσομάθεια δεν υποστηρίζει πράξη μέσα στις παραμέτρους
   ΚΑΛΕΣΕ Μετακίνησε(Ν, ΣτύλοςΑ, ΣτύλοςΓ,ΣτύλοςΒ)  
   ΓΡΑΨΕ 'Μετακίνησε από τον', ΣτύλοςΑ, ' στον' , ΣτύλοςΓ  
   ΚΑΛΕΣΕ Μετακίνησε(Ν, ΣτύλοςΒ, ΣτύλοςΑ, ΣτύλοςΓ) 
ΤΕΛΟΣ_ΑΝ ! ΠΑΡΟΡΑΜΑ - Λείπει η εντολή
ΤΕΛΟΣ_ΔΙΑΔΙΚΑΣΙΑΣ 
Share This