Υπολογισμός νομισμάτων

Το νομισματικό σύστημα της χώρας μας διαθέτει σε μορφή κέρματος 1, 2, 5, 10, 20, 50 και 100 δραχμές και σε χαρτονομίσματα 200, 500, 1000, 5000 και 10000 δραχμές. Το πρόβλημα είναι να βρεθεί αλγόριθμος με βάση τον οποίο, όταν δίδεται ένα ποσό, να βρίσκεται ο ελάχιστος αριθμός των απαιτούμενων κερμάτων και χαρτονομισμάτων. Για παράδειγμα για να σχηματιστεί το ποσό των 789 δρχ. απαιτούνται 1 πεντακοσάρικο, 1 διακοσάρικο, 1 πενηντάρικο, 1 εικοσάρικο, 1 δεκάρικο, 1 τάληρο και 2 δίδραχμα, δηλαδή συνολικά 8 νομίσματα.

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

Αλγόριθμος Νομίσματα Δεδομένα // C, n, poso // findposo coins Όσο (choice>0) και (find > 0) επανάλαβε Αν C[choice] Τέλος_Αν Τέλος_επανάληψης Αποτελέσματα // coins // Τέλος Νομίσματα

Στον αλγόριθμο αυτό ο πίνακας C διαθέτει όλες τις τιμές των n χρησιμοποιούμενων νομισμάτων από το μικρότερο προς το μεγαλύτερο. Ο αλγόριθμος υπολογίζει τον ελάχιστο αριθμό νομισμάτων για ένα συγκεκριμένο ποσό (μεταβλητή coins). Μπορεί να γίνει επέκτασή του, ώστε να έχει ως αποτέλεσμα τον αριθμό για κάθε είδος νομίσματος.