Ένας γρίφος θεωρίας αριθμών και μια άσκηση στον προγραμματισμό

                           

  
   Πολλές φορές  στην διάρκεια της προετοιμασίας στο ΑΕΕΠ,στην Β λυκείου,δεν έχω την πίεση των πανελληνίων και μπορώ και  τους δίνω προβληματάκια να σκεφτούν.

Πριν από περίπου δέκα μέρες τους έδωσα το ακόλουθο πρόβλημα:

  Το νομισματικό σύστημα της Λοξολάνδης αποτελείται από κέρματα των 1,5,10,50 λεπτών,1 ευρώ και χαρτονομίσματα  5 και 10 ευρώ. Σε ένα κατάστημα, ο καταστηματάρχης έχει στο ταμείο του 1 δεκάευρο,1 πεντάευρο,4 κέρματα του ευρώ,1 πενηντάλεπτο,4 δεκάλεπτα,1 πεντάλεπτο, 4 μονόλεπτα. 

Να γράψετε αλγόριθμο που να εμφανίζει  ποιο χρηματικό ποσό από 1 λεπτό έως 19,99 ευρώ δεν μπορεί να δοθεί ως ρέστα με χρήση κάποιων ή όλων από τα παραπάνω χρήματα στο ταμείο.
Να τρέξετε τον αλγόριθμο που θα κατασκευάσετε στον διερμηνευτή της ψευδογλωσσας.Τι παρατηρείτε;

 Τους είπα ότι θα το έκαναν εξετάζοντας κάθε χρηματικό ποσό από 1 εως 1999 λεπτά .

Χθες  δευτέρα,μου έφεραν τις λύσεις τους και μου είπαν ότι όλα τα ποσά από 1 έως 19,99 λεπτά μπορούν να δοθούν ως ρέστα.Μια από τις λύσεις ήταν η παρακάτω:
Με μια επανάληψη τσέκαρει όλους τους αριθμούς από 1 μέχρι 1999,εντός της επανάληψης,αρχικοποιεί τα 8 πλήθη των διαφορετικών χρηματικών αξίων στο ταμείο  και κατόπιν βρισκει τα ρέστα  όπως θα το έκανε και ο μπακάλης της γειτονιάς.

Για οποιαδήποτε χρηματική αξία,π.χ 1999 λεπτά  διαιρεί με το 1000 (δεκαευρο) με ακέραιο πηλίκο 1 και υπόλοιπο 999 λεπτά,κατόπιν διαιρεί το υπόλοιπο(999) με το 500 (πεντάευρο) ακέραιο πηλίκο 1 και υπόλοιπο 499 λεπτά κ.ο.κ

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

    Το ίδιο πρόβλημα- που είναι  παλιός γρίφος θεωρίας αριθμών- το ανέβασα ελαφρά τροποποιημένο σε γνωστό ιστότοπο και δοθήκαν δυο λύσεις που το έκαναν  «φραγκοδίφραγκα».

 http://omathimatikos.gr/%ce%bf-%ce%b3%cf%81%ce%af%cf%86%ce%bf%cf%82-%cf%84%ce%b7%cf%82-%ce%b7%ce%bc%ce%ad%cf%81%ce%b1%cf%82-%cf%84%ce%bf-%ce%bc%cf%80%ce%b1%ce%ba%ce%ac%ce%bb%ce%b9%ce%ba%ce%bf-%ce%b3%ce%b9%ce%b1/

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

Και οι δυο μαζί έχουν 19,99  ευρώ σε κέρματα και χαρτονομίσματα των 1,5,10,50 λεπτών,1 ,5 και 10 ευρώ. (τουλάχιστον ένα από το καθένα).

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

  Ο Τοτός δίνει όλα τα χρήματα του στον μπακάλη.Τα ρέστα που πρέπει να λάβει κυμαίνονται   από το 0  μέχρι 19,99 ευρώ. Θα πρέπει να δείξουμε ότι οποιοδήποτε ποσό από το 0 μέχρι 19,99 ευρώ  μπορεί να  δοθεί με τα χαρτονομίσματα και τα κέρματα που διαθέτουμε.Ότι χαρτονομίσματα και κέρματα αν έχουμε στο ταμείο αθροίζονται 19,99 ευρώ και μπορούν να αναχθούν στο έξης ελάχιστο-από άποψη πλήθους- σύνολο 16 χρηματικών στοιχείων.

Α={1 δεκάευρο,1 πεντάευρο,4 κέρματα του ευρώ,1 πενηντάλεπτο , 4 δεκάλεπτα ,1 πεντάλεπτο,4 μονόλεπτα}

  Πως το βρήκαμε; Όπως κάθε μπακάλης που σέβεται τον εαυτό του και θέλει να δώσει ρέστα με τον ελάχιστο πλήθος χαρτονομισμάτων –κερμάτων!Σκέπτεται, 19,99 ευρώ  ή 1999 λεπτά  διαιρούμε με το 1000 ( δεκαευρο) με ακέραιο πηλίκο 1 και υπόλοιπο 999 λεπτά  διαιρούμε με το 500 (πεντάευρο) ακέραιο πηλίκο 1  και υπόλοιπο 499 λεπτά κ.ο.κ

Τόσο αυτοματοποιημένο που το κάνει αλγοριθμικά κάθε μηχάνημα που δίνει ρέστα.

Ακόμα και αν έχω άλλο συνδυασμό χαρτονομισμάτων –κερμάτων  για παράδειγμα, ας πούμε 3 πεντάλεπτα και 3 δεκάλεπτα μπορώ να θεωρήσω τα 2 πεντάλεπτα ως ένα δεκάλεπτο  και να καταλήξω στο παραπάνω.

Με το παραπάνω σύνολο Α μπορούμε να σχηματίσουμε οποιοδήποτε ποσό από 0 έως 19,99 ευρώ.

Bonus τραγουδάκι απόThin  Lizzy