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

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

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

Ερώτηση 5 (σελ. 86)

Να περιγραφεί με βήματα η μέθοδος της προσέγγισης του Δυναμικού Προγραμματισμού για τη σχεδίαση αλγορίθμων.

Σκέψη / Μεθοδολογία: Κλειστή ερώτηση περιγραφής — τα βήματα δίνονται στο §4.4.

Λύση:

Ανατρέχουμε στα βήματα του §4.4 και τα αποδίδουμε με τη σειρά τους.

Απάντηση: Ο Δυναμικός Προγραμματισμός ακολουθεί προσέγγιση bottom-up: (1) ξεκινά από τα μικρότερα υποπροβλήματα, που λύνονται με τη βοήθεια ενός πίνακα ή τύπου, (2) αποθηκεύει τα προσωρινά αποτελέσματα σε αυτόν τον πίνακα ώστε να μην υπολογίζονται ξανά, (3) συνθέτει σταδιακά τις επιμέρους λύσεις μέχρι την τελική λύση του αρχικού προβλήματος. Χρησιμοποιείται κυρίως σε προβλήματα βελτιστοποίησης.

Πρόσεξε:

  • Να τονιστεί η κατεύθυνση bottom-up (από τα μικρά προς το μεγάλο πρόβλημα) και ο ρόλος του πίνακα αποθήκευσης — είναι το σημείο που διαφοροποιεί τη μέθοδο από τη Διαίρει-και-Βασίλευε.

Ερώτηση 7 (σελ. 86)

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

Σκέψη / Μεθοδολογία: Εφαρμόζουμε τη λογική του Δυναμικού Προγραμματισμού (πίνακας ενδιάμεσων αποτελεσμάτων) στον υπολογισμό n!: fact[0]=1, και κάθε επόμενη θέση προκύπτει πολλαπλασιάζοντας την προηγούμενη επί τον επόμενο ακέραιο.

Λύση:

  1. Ορίζουμε πίνακα fact[0..n] με fact[0] = 1 (ορισμός 0! = 1).
  2. Για κάθε i από 1 μέχρι n, υπολογίζουμε fact[i] = fact[i-1] * i, χρησιμοποιώντας το ήδη αποθηκευμένο αποτέλεσμα της προηγούμενης θέσης.
  3. Το ζητούμενο n! βρίσκεται στη θέση fact[n], χωρίς να χρειαστεί να ξαναϋπολογιστούν τα ενδιάμεσα γινόμενα.

Απάντηση:

Δεδομένα  n
fact[0] ← 1
Για i από 1 μέχρι n
    fact[i] ← fact[i-1] * i
Τέλος_επανάληψης
Αποτελέσματα  fact[n]

Πρόσεξε:

  • Η βασική περίπτωση fact[0]=1 είναι απαραίτητη — χωρίς αυτήν ο πίνακας δεν έχει από πού να ξεκινήσει.
  • Κάθε θέση του πίνακα χρησιμοποιεί την αμέσως προηγούμενη, όχι επανάληψη του πολλαπλασιασμού από την αρχή — αυτό είναι το σημείο που κάνει την τεχνική αποδοτική.

Ερώτηση 8 (σελ. 86)

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

Σκέψη / Μεθοδολογία: Για αρνητικό εκθέτη ισχύει \(a^{-b} = 1 / a^b\) (b θετικός ακέραιος). Αρκεί να υπολογίσουμε πρώτα το \(a^b\) με τη γνωστή τεχνική του πίνακα δυνάμεων (§4.4, αλγόριθμος «Δύναμη2») και μετά να αντιστρέψουμε το αποτέλεσμα.

Λύση:

  1. Μετατρέπουμε τον αρνητικό εκθέτη σε θετικό: αν ζητείται \(a^b\) με \(b < 0\), θέτουμε \(c = -b\) (θετικός) και υπολογίζουμε πρώτα το \(a^c\).
  2. Χρησιμοποιούμε τον πίνακα power όπως στο §4.4 (κάθε θέση = τετράγωνο της προηγούμενης) για να υπολογίσουμε το \(a^c\) αποδοτικά.
  3. Επιστρέφουμε ως τελικό αποτέλεσμα το \(1 / a^c\).

Ενδεικτική απάντηση:

Δεδομένα  a, b   ! b αρνητικός ακέραιος
c ← -b
power[1] ← a
i ← 1
pow ← 1
Όσο pow < c επανάλαβε
    i ← i + 1
    pow ← 2 * pow
    power[i] ← power[i-1] * power[i-1]
Τέλος_επανάληψης
used ← 0
result ← 1
Όσο used < c επανάλαβε
    Αν used + pow <= c τότε
        result ← result * power[i]
        used ← used + pow
    Τέλος_αν
    pow ← pow / 2
    i ← i - 1
Τέλος_επανάληψης
result ← 1 / result
Αποτελέσματα  result

Πρόσεξε:

  • Ο πυρήνας του αλγορίθμου είναι ακριβώς ο αλγόριθμος «Δύναμη2» του §4.4 — η μόνη προσθήκη είναι η μετατροπή του αρνητικού εκθέτη σε θετικό στην αρχή και η αντιστροφή (1/result) στο τέλος.
  • Να προσεχθεί ότι \(a\) δεν μπορεί να είναι 0, αφού θα προέκυπτε διαίρεση με το μηδέν.