Δευτέρα, 11 Φεβρουαρίου 2013

Η Μετατροπή

Με πόσους διαφορετικούς τρόπους μπορούμε να μετατρέψουμε  ένα χαρτονόμισμα των 100€ σε «ψιλά», έχοντας μόνο χαρτονομίσματα των 10€, 20€, και 50€; (Κατ.34/Νο.569)

Λύση

Με 10 τρόπους. 100€=2*50€, 100€=50€+5*10€=50€+50€, 100€=50€+1*20€+3*10€=50€+20€+30€=50€+50€, 100€=50€+2*20€+1*10€=50€+40€+10€=50€+50€, 100€=1*20€+8*10=20€+80€, 100€=2*20€+6*10€=40€+60€, 100€=3*20€+4*10€=60€+40€, 100€=4*20€+2*10€=80€+20€, 100€=5*20€, 100€=10€*10€

3 σχόλια:

Ευθυμιος Αλεξιου είπε...

1*100

2*50
1*50+2*20+1*10
1*50+1*20+3*10
1*50+5*10

5*20
4*20+2*10
3*20+4*10
2*20+6*10
1*20+8*10

10*10

Papaveri είπε...

@Ευθυμιος Αλεξιου
Συγχαρητήρια! Η απάντησή σας είναι σωστή.

RIZOPOULOS GEORGIOS είπε...

Kαλημέρα!
Aν βάλουμε και τα 5άρια στο πρόβλημα οι δυνατοί συνδυασμοί είναι 48. (τόσες βρήκα από τις ακέραιες λύσεις του συστήματος:
5n+10k+20m+50z=100
0<=n<=20
0<=k<=10
0<=m<=5
0<=z<=2

Το γενικό πρόβλημα των partitions (Ruecksack theorem, sub-sets,κλπ ) είναι πολύ ενδιαφέρον και δύσκολο.
Yπάγονται στα ΝP-complete/incomplete προβλήματα και είναι πονοκέφαλος ακόμη και για brute force υπολογιστικές και ευριστικές μεθόδους

Δίνω το λινκ της Βίκης για το Ruecksack(Knapsack στα εγγλέζικα)problem. http://de.wikipedia.org/wiki/Rucksackproblem

 

Papaveri48 © 2010

PSD to Blogger Templates by OOruc & PSDTheme by PSDThemes