Υπολογισμός δύναμης

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

Ας θεωρήσουμε , λοιπόν, ότι πρέπει να υπολογίσουμε την ακέραια δύναμη ενός πραγματικού αριθμού, ab. Μία πρώτη απλή προσέγγιση είναι ο επόμενος επαναληπτικός αλγόριθμος Δύναμη1, του οποίου η λειτουργία είναι ευνόητη.

Αλγόριθμος Δύναμη1 Δεδομένα // a, b // power ? 1 Για i από 1 μέχρι b power Τέλος_επανάληψης Αποτελέσματα // power // Τέλος Δύναμη1

Ο αλγόριθμος Δύναμη1 είναι μεν εύκολος στον προγραμματισμό και την κατανόηση του, αλλά δεν είναι ιδιαίτερα αποτελεσματικός, επειδή εκτελεί b πολλαπλασιασμούς για τον υπολογισμό της b-οστής δύναμης. Το ότι ο αλγόριθμος αυτός δεν είναι αποτελεσματικός, αποδεικνύεται με το απλό παράδειγμα ότι το a16 μπορεί να υπολογισθεί με τέσσερις πολλαπλασιασμούς ως εξής: (((α2) 2)2)2. Στη συνέχεια ακολουθεί ο νέος τρόπος επίλυσης του προβλήματος με χρήση της μεθόδου του δυναμικού προγραμματισμού, όπου η βασική ιδέα είναι η προσωρινή αποθήκευση κάποιων προηγούμενων δυνάμεων του αριθμού μέχρι τη σταδιακή κατάληξη στη δύναμη b. Συγκεκριμένα ο πίνακας power θα αποθηκεύει το αποτέλεσμα της ύψωσης στο τετράγωνο της προηγούμενης θέσης του πίνακα. Για παράδειγμα, αν θα υπολογιζόταν οι δυνάμεις του 2 (δηλαδή, έστω ότι a=2), τότε ο πίνακας στη θέση 0 θα είχε την τιμή 1, στη θέση 1 την τιμή 2, στη θέση 2 την τιμή 4, στη θέση 3 την τιμή 16 κοκ, όπως φαίνεται και στο επόμενο σχήμα.

0 12 34 20=1 21=2 22=424=16 28=256 … Δύναμη του 2 0-κή 1η2η 4η 8η …

Σχ.4.5 Αποθήκευση δυνάμεων του 2.

Για τον υπολογισμό, λοιπόν, κάποιας δύναμης απαιτούνται οι κατάλληλες θέσεις του πίνακα. Λόγου χάριν, για την ανεύρεση του 27 , αρκούν οι αποθηκευμένες δυνάμεις μέχρι και την 4η δύναμη του 2, διότι 27 = 24 *22 *21. Ο αλγόριθμος που ακολουθεί παρουσιάζει τον υπολογισμό του ab με τη νέα αυτή ευφυέστερη τεχνική, που βασίζεται στο λεγόμενο δυναμικό προγραμματισμό.

Αλγόριθμος Δύναμη 2 Δεδομένα // a, b // !Σχόλιο: αποθήκευση στοιχείων πίνακα power^[1] Όσο pow < b επανάλαβε i Τέλος_επανάληψης !Σχόλιο: ανεύρεση της δύναμης used Όσο used < b επανάλαβε Αν used + pow Τέλος_αν pow Τέλος_επανάληψης Αποτελέσματα // result // Τέλος Δύναμη2