Να περιγραφεί με βήματα η μέθοδος της προσέγγισης του Δυναμικού Προγραμματισμού για τη σχεδίαση αλγορίθμων.
Σκέψη / Μεθοδολογία: Κλειστή ερώτηση περιγραφής — τα βήματα δίνονται στο §4.4.
Λύση:
Ανατρέχουμε στα βήματα του §4.4 και τα αποδίδουμε με τη σειρά τους.
Απάντηση: Ο Δυναμικός Προγραμματισμός ακολουθεί προσέγγιση bottom-up: (1) ξεκινά από τα μικρότερα υποπροβλήματα, που λύνονται με τη βοήθεια ενός πίνακα ή τύπου, (2) αποθηκεύει τα προσωρινά αποτελέσματα σε αυτόν τον πίνακα ώστε να μην υπολογίζονται ξανά, (3) συνθέτει σταδιακά τις επιμέρους λύσεις μέχρι την τελική λύση του αρχικού προβλήματος. Χρησιμοποιείται κυρίως σε προβλήματα βελτιστοποίησης.
Πρόσεξε:
Να δοθεί αλγόριθμος για την εύρεση του παραγοντικού ακεραίου με χρήση της από πάνω προσέγγισης, όπου τα προσωρινά αποτελέσματα αποθηκεύονται σε έναν πίνακα.
Σκέψη / Μεθοδολογία: Εφαρμόζουμε τη λογική του Δυναμικού Προγραμματισμού (πίνακας ενδιάμεσων αποτελεσμάτων) στον υπολογισμό n!: fact[0]=1, και κάθε επόμενη θέση προκύπτει πολλαπλασιάζοντας την προηγούμενη επί τον επόμενο ακέραιο.
Λύση:
Απάντηση:
Δεδομένα n
fact[0] ← 1
Για i από 1 μέχρι n
fact[i] ← fact[i-1] * i
Τέλος_επανάληψης
Αποτελέσματα fact[n]
Πρόσεξε:
Να δοθεί αλγόριθμος για την ανεύρεση της δύναμης πραγματικού σε αρνητικό ακέραιο εκθέτη με Δυναμικό Προγραμματισμό.
Σκέψη / Μεθοδολογία: Για αρνητικό εκθέτη ισχύει \(a^{-b} = 1 / a^b\) (b θετικός ακέραιος). Αρκεί να υπολογίσουμε πρώτα το \(a^b\) με τη γνωστή τεχνική του πίνακα δυνάμεων (§4.4, αλγόριθμος «Δύναμη2») και μετά να αντιστρέψουμε το αποτέλεσμα.
Λύση:
power όπως στο §4.4 (κάθε θέση = τετράγωνο της προηγούμενης) για να υπολογίσουμε το \(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
Πρόσεξε:
