ΤΕΣΤ (ΑΣΚΗΣΕΙΣ) ONLINE
98 Tests / Διαγωνίσματα

Κεφάλαιο 03.8 – Σελίδα 67 – ΑΝΑΠΤΥΞΗ ΕΦΑΡΜΟΓΩΝ ΣΕ ΠΡΟΓΡΑΜΜΑΤΙΣΤΙΚΟ ΠΕΡΙΒΑΛΛΟΝ Γ΄ ΛΥΚΕΙΟΥ – Απαντήσεις – Λύσεις

Ερωτήσεις - Θέματα για συζήτηση

Ερώτηση 12 (σελ. 74)

Να περιγραφεί η λειτουργία της αναδρομής και να σχολιασθεί η χρησιμότητά της.

Σκέψη / Μεθοδολογία: Ερώτηση περιγραφής + σχολιασμός — απαντάται με τον ορισμό της αναδρομής και το σχόλιο για το κόστος/όφελός της από το §3.8.

Λύση:

Ορίζουμε τι είναι αναδρομική συνάρτηση, μετά σχολιάζουμε πλεονεκτήματα (απλότητα/φυσικότητα σύνταξης) και μειονεκτήματα (χρονικό κόστος κλήσεων).

Απάντηση: Μια συνάρτηση ή διαδικασία λέγεται αναδρομική (recursive) όταν καλεί τον εαυτό της, άμεσα ή έμμεσα, με μια απλούστερη περίπτωση του ίδιου προβλήματος — κάθε αναδρομικός αλγόριθμος χρειάζεται μια συνθήκη τερματισμού. Η αναδρομή κάνει συχνά τη λύση πιο κατανοητή και φυσική στη σύνταξη (π.χ. στον υπολογισμό παραγοντικού ή στον αλγόριθμο του Ευκλείδη). Ωστόσο, κάθε κλήση συνάρτησης έχει μη αμελητέο χρονικό κόστος, οπότε η αναδρομή μπορεί να είναι πιο αργή από μια ισοδύναμη επαναληπτική λύση· γι' αυτό, όταν ο χρόνος εκτέλεσης είναι κρίσιμος, προτιμάται η επαναληπτική μέθοδος.

Πρόσεξε:

  • Να αναφερθούν και τα δύο σκέλη: τι είναι η αναδρομή ΚΑΙ ο σχολιασμός για πότε συμφέρει/δεν συμφέρει.

Ερώτηση 13 (σελ. 74)

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

Σκέψη / Μεθοδολογία: Ο αλγόριθμος δεν δίνεται αυτούσιος στο βιβλίο, αλλά η δύναμη x^n ορίζεται αναδρομικά με το ίδιο ακριβώς πρότυπο του παραγοντικού (§3.8.1): x^0=1, x^n = x · x^(n-1) για n>0. Κατασκευάζουμε τον αλγόριθμο ακολουθώντας πιστά αυτό το πρότυπο.

Λύση:

Γράφουμε πρώτα τον αναδρομικό ορισμό της δύναμης, μετά τον μεταφράζουμε σε αλγόριθμο με τη μορφή του Παραγοντικό από το §3.8.1.

Αλγόριθμος Δύναμη
Δεδομένα // x, n //
Αν n = 0 τότε
    power ← 1
αλλιώς
    power ← x * Δύναμη(x, n-1)
Τέλος_αν
Αποτελέσματα // power //
Τέλος Δύναμη

Απάντηση: Ορίζουμε: x^n = 1, αν n=0· x^n = x · x^(n-1), αν n>0. Ο παραπάνω αλγόριθμος καλεί τον εαυτό του με ολοένα μικρότερη τιμή του n, μέχρι να φτάσει στη συνθήκη τερματισμού n=0.

Πρόσεξε:

  • Να υπάρχει σαφής συνθήκη τερματισμού (n=0) — χωρίς αυτήν ο αλγόριθμος δεν τερματίζει ποτέ.
  • Ο αλγόριθμος υποθέτει μη αρνητικό ακέραιο εκθέτη n· δεν καλύπτει αρνητικές δυνάμεις.