Μάθημα : ΠΛΗΡΟΦΟΡΙΚΗ Γ ΓΥΜΝΑΣΙΟΥ (Γ3)

ΠΛΗΡΟΦΟΡΙΚΗ Γ ΓΥΜΝΑΣΙΟΥ (Γ3)

1901051489 - ΕΥΔΟΞΙΑ ΠΑΤΚΟΥ

Ενότητες μαθήματος

Πύργοι του Ανόι

Αναδρομικοί Αλγόριθμοι FRACTAL... Δημιουργία λογαριασμού και σύν...

Α)Δείτε περισσότερα από το βιβλίο (σελ 9 και 10) στη σελίδα της wikipedia

https://el.wikipedia.org/w/index.php?title=%CE%A0%CF%8D%CF%81%CE%B3%CE%BF%CF%82_%CF%84%CE%BF%CF%85_%CE%91%CE%BD%CF%8C%CE%B9&veaction=edit&section=2

 

 

Β) Κάνε την εργασία που ακολουθεί, χρησιμοποιώντας την εφαρμογή:

https://dsphinx.mysch.gr/games.php?id=hanoi.html

 

Γ) Μετά παίξε το παιχνίδι

https://pliroforikiatschool.blogspot.com/2013/10/blog-post.html

 

Εργασίες

Ανοιξε τον σύνδεσμο

https://dsphinx.mysch.gr/games.php?id=hanoi.html

Πρέπει να μετακινήσεις τους δακτύλιους από τον Α (πιο αριστερά) στύλο στον C (πιο δεξιά) με τον κανόνα ο μεγαλύτερος δίσκος να είναι πάντα κάτω από τον μικρότερο. Δεν μπορείς να τοποθετήσεις μεγαλύτερο δίσκο πάνω από μικρότερο. Γι αυτό υπάρχει ο μεσαίος στύλος (Β) που καρατάει προσωρινά  τον δίσκο που δεν μπορούμε να τοποθετήσουμε σωτά. 

Καθώς κάνεις με το παράδειγμα τις μετακινήσεις, κατέγραψέ τις

Να το κάνεις α) για 3 δίσκους και β) για 4 δίσκους

Να στείλεις Online τα βήματα και για τις δύο περιπτώσεις.

ΠΥΡΓΟΙ_ΤΟΥ_ΑΝΟΙ(3, 'Α', 'Γ', 'Β')

 

Μελετείστε τον ψευδοκώδικα για Ν δίσκους (γενικός αλγόριθμος για Ν δίσκους)

ΠΥΡΓΟΙ_ΤΟΥ_ΑΝΟΙ(αριθμός_δίσκων, πύργος_αφετηρία, πύργος_προορισμός, πύργος_βοηθητικός)
{
ΑΝ αριθμός_δίσκων = 1 ΤΟΤΕ
ΕΚΤΥΠΩΣΕ "Μετακίνησε το δίσκο από τον πύργο" πύργος_αφετηρία "στον πύργο" πύργος_προορισμός
ΑΛΛΙΩΣ
// Μετακίνησε Ν-1 δίσκους από τον πύργο αφετηρίας στον βοηθητικό πύργο
ΠΥΡΓΟΙ_ΤΟΥ_ΑΝΟΙ(αριθμός_δίσκων - 1, πύργος_αφετηρία, πύργος_βοηθητικός, πύργος_προορισμός)

// Μετακίνησε τον μεγαλύτερο δίσκο στον πύργο προορισμού
ΕΚΤΥΠΩΣΕ "Μετακίνησε το δίσκο από τον πύργο" πύργος_αφετηρία "στον πύργο" πύργος_προορισμός

// Μετακίνησε τους Ν-1 δίσκους από τον βοηθητικό πύργο στον πύργο προορισμού
ΠΥΡΓΟΙ_ΤΟΥ_ΑΝΟΙ(αριθμός_δίσκων - 1, πύργος_βοηθητικός, πύργος_προορισμός, πύργος_αφετηρία)
}

 

 

Επεξήγηση:

  1. Βασική περίπτωση: Αν έχουμε μόνο 1 δίσκο, τον μετακινούμε απευθείας στον πύργο προορισμού

  2. Αναδρομική περίπτωση:

    • Μετακινούμε τους Ν-1 δίσκους από τον πύργο αφετηρίας στον βοηθητικό πύργο

    • Μετακινούμε τον μεγαλύτερο δίσκο (τον τελευταίο) στον πύργο προορισμού

    • Μετακινούμε τους Ν-1 δίσκους από τον βοηθητικό πύργο στον πύργο προορισμού

Σημείωση: Ο αριθμός των βημάτων είναι 2^Ν - 1, οπότε για μεγάλα Ν το πρόβλημα γίνεται υπολογιστικά απαιτητικό.

Για 64 δίσκους οι Πύργοι του Ανόι έχουν ένα «θρυλικό» αποτέλεσμα:

  • Ο ελάχιστος αριθμός κινήσεων είναι

M(64)=264−1=18,446,744,073,709,551,615M(64) = 2^{64} - 1 = 18,446,744,073,709,551,615M(64)=264−1=18,446,744,073,709,551,615

κινήσεις!

Αυτός ο αριθμός είναι τεράστιος – αν μετακινούσες 1 δίσκο το δευτερόλεπτο, θα χρειαζόσουν πάνω από 584 δισεκατομμύρια χρόνια (περισσότερο κι από την ηλικία του Σύμπαντος ).