[WI]Parkeerautomaat

[Jegor]

Hallo ik zit vast bij een oefening:

Er staat een parkeerautomaat in Utrecht, het uur tarief is 3,85.- euro.
Op hoeveel verschillende manieren kun je het uurtarief betalen.
Je kan munten van 10 cent tot en met 2 euro in stoppen.
Er passen maximaal 25 munten in de automaat.

Iemand die het antwoord heeft? Ik snap er namelijk echt niks van
Alvast bedankt!

[Dark_One]

De euromunten: 10,20,50 cent en 1 en 2 euro bieden allemaal geen mogelijkheid om iets op 5 cent nauwkeurig af te rekenen. Als dit de enige munten zijn die in de automaat passen zal het aantal mogelijkheden om precies het bedrag 3,85 (dus op 5 cent nauwkeurig) te maken vrij lastig worden...

[Jegor]

En wat als het 3,90 is, is er een makkelijke manier?

[Vinniebar]

Zit je een beetje zelf opdrachten te bedenken ofzo?

En een makkelijke manier kan ik niet bedenken.
Misschien iets met combinaties, maar dat zal alsnog behoorlijk lastig worden...

[Dark_One]

Dan zou ik zo ook geen makkelijke methode weten. Ik denk dat het aantal mogelijkheden boven de 1000 uitkomt dus alles uitproberen is ook geen optie. Misschien kan je een computer alles laten simuleren.
Een handige wiskundige truc om het aantal mogelijkheden te berekenen is er volgens mij echter niet.

[the unknown 1]

3.85 op hoeveel manieren kan je dit krijgen met ;
X0.1+Y0.2+Z0.5+U1.V2
=> alle munten die je hebt

=> onmogelijk om op 3.85 te komen, aangezien je 5 cent nodig hebt
Indien je er vanuit gaat dat 3.9 ook goed is zijn er verschillende manieren.
Om exact op 3.9 te komen heb je 2 mogelijkheden voor 2 euro stukken
Je gebruik deze 1x of 0x.
Voor 1 euro kan je net hetzelfde stellen, je gebruik deze 3x,2x,1x of 0x
Voor 0.5 euro kan je net hetzelfde stellen: je gebruikt deze 7x,6x,5x,4x,3x,2x,1x,0x
Voor 0.2 kan je hetzelfde stellen; 19x,18x,...,3x,2x,1x,0x
Voor 0.1 kan je dit stellen; gebruikt deze 22x,21x,20x,...,3x,2x,1x,0x ..
Voor 0,1 zie je dus een afwijking , waarom, omdat 24x0.1 + een keuze uit (0.2,0.5,1,2) nooit gelijk is aan 3.9

Als je nu net ziet op welke methode ik dit geschreven heb, kan je eruit afleiden dat je enorm veel mogelijkheden zijn, die je via een boomschema kan oplossen.
waarbij je neemt ; X0.1+Y0.2+Z0.5+U1.V2 = 3.9
x+y+z+u+v= 25 , waarbij x,y,z,u,v tussen 0 & 25 MOETEN behoren.

Het is misschien ook mogelijk om er te komen via matrixen/matricen

[the unknown 1]

Extra tip, overloop per aantal munten
Stel je gebruik voor
1 munt=> werkt niet
2 munten => werkt niet
3 munten => werkt niet
4 munten => werkt niet
5 munten => werkt wel, bv 2+1+0.5+0.2+0.2
6 munten =>..
..
22 munten =>
23 munten =>
24 munten =>
25 munten => werkt wel, combinatie van bepaalde 0.1 / 0.2 ..

Valt er al een heel simuleringsdeel weg..

[Vinniebar]

ik (5 vwo NT) snap niks van bovenstaand verhaal, dus het zal de TS ook niet veel helpen vermoed ik...

[Jegor]

Dank jullie wel voor de tips!.
Ik heb het uiteindelijk door een vader van een vriend laten doen

Er zijn 2048 mogelijkheden maar daar moeten nog 40 mogelijkheden af omdat die boven het maximum aantal van de 25 muntjes gingen. We komen hierdoor op een aantal van 2008 mogelijkheden.

Berekening:
De kleinste mogelijkheid is:
1 x €2 + 1 x €1 + €0,50 + €0,20 + €0,20
De €2 is weer op te delen in 16 mogelijkheden, de €1 in 8 mogelijkheden, de €0,50 in 4 mogelijkheden en de beide €0,20 in 2 mogelijkheden.
Doe je dit maal elkaar dan krijg je 16 x 8 x 4 x 2 x 2 en dat is 2048.
De 40 mogelijkheden die niet kunnen kregen we door gewoon te tellen.
Haal je dit dan van elkaar af kom je op een aantal van 2008 mogelijkheden.

[Dark_One]

the unknown 1 schreef:

3.85 op hoeveel manieren kan je dit krijgen met ;
X0.1+Y0.2+Z0.5+U1.V2
=> alle munten die je hebt

=> onmogelijk om op 3.85 te komen, aangezien je 5 cent nodig hebt
Indien je er vanuit gaat dat 3.9 ook goed is zijn er verschillende manieren.
Om exact op 3.9 te komen heb je 2 mogelijkheden voor 2 euro stukken
Je gebruik deze 1x of 0x.
Voor 1 euro kan je net hetzelfde stellen, je gebruik deze 3x,2x,1x of 0x
Voor 0.5 euro kan je net hetzelfde stellen: je gebruikt deze 7x,6x,5x,4x,3x,2x,1x,0x
Voor 0.2 kan je hetzelfde stellen; 19x,18x,...,3x,2x,1x,0x
Voor 0.1 kan je dit stellen; gebruikt deze 22x,21x,20x,...,3x,2x,1x,0x ..
Voor 0,1 zie je dus een afwijking , waarom, omdat 24x0.1 + een keuze uit (0.2,0.5,1,2) nooit gelijk is aan 3.9

Als je nu net ziet op welke methode ik dit geschreven heb, kan je eruit afleiden dat je enorm veel mogelijkheden zijn, die je via een boomschema kan oplossen.
waarbij je neemt ; X0.1+Y0.2+Z0.5+U1.V2 = 3.9
x+y+z+u+v= 25 , waarbij x,y,z,u,v tussen 0 & 25 MOETEN behoren.

Het is misschien ook mogelijk om er te komen via matrixen/matricen

Nice... Jammer dat het x+y+z+u+v<26 moet zijn. Dit is dus één vergelijking en 5 onbekenden dus 4 keuzemogelijkheden...
Als je Y,Z,U en V kiest heb je 2*4*8*20=1280 keuzemogelijkheden?(Het aantal 10 cent-stukken zou direct uit je keuzes voor de anderen moeten volgen (om het bedrag compleet te maken... en levert dus geen extra mogelijkheden) Hier moeten dan nog een aantal keuzemogelijkheden vanaf omdat het totaal aantal munten dan boven de 25 munten komt. Als die 40 die Jegor zelf geteld had klopt zouden er totaal dus 1240 mogelijkheden zijn.

[Vinniebar]

Jegor schreef:

de €1 in 8 mogelijkheden,

Hoe kom je bij dit getal? (8x)

[Dark_One]

Jegor schreef:

Dank jullie wel voor de tips!.
Ik heb het uiteindelijk door een vader van een vriend laten doen

Er zijn 2048 mogelijkheden maar daar moeten nog 40 mogelijkheden af omdat die boven het maximum aantal van de 25 muntjes gingen. We komen hierdoor op een aantal van 2008 mogelijkheden.

Berekening:
De kleinste mogelijkheid is:
1 x €2 + 1 x €1 + €0,50 + €0,20 + €0,20
De €2 is weer op te delen in 16 mogelijkheden, de €1 in 8 mogelijkheden, de €0,50 in 4 mogelijkheden en de beide €0,20 in 2 mogelijkheden.
Doe je dit maal elkaar dan krijg je 16 x 8 x 4 x 2 x 2 en dat is 2048.
De 40 mogelijkheden die niet kunnen kregen we door gewoon te tellen.
Haal je dit dan van elkaar af kom je op een aantal van 2008 mogelijkheden.

Krijg je zo geen dubbele mogelijkheden? Immers als je 50 cent verdeeld in 2 van 20 en 1 van 10 cent. En nog 1 van 20 opdeelt in 2 van 10 (dus uiteindelijk 2 van 20 3 van 10 voor 70 cent) is dat hetzelfde als dat je de 50 opdeelt in 1 van 20 en 3 van 10 cent en de andere 20 cent laat staan. (dus ook uiteindelijk 2 van 20 en 3 van 10 cent)

[Dark_One]

Vinniebar schreef:

Hoe kom je bij dit getal? (8x)

1 keer met 1 euro
4 keer met 50 cent en de andere 50 cent in 4 mogelijkheden opgedeelt (0*20,1*20,2*20) rest 10 cent of 1 van 50 cent
6 keer met 20 cent en rest 10 cent (0*20,1*20,2*20,3*20,4*20,5*20)

Geeft samen 11x ipv. 8x

[ILUsion]

Ik heb even vlug een brute-force simulatie laten doen voor je, als je 3.85 euro moet hebben, met munten van 5 cent tot en met 2 euro, dan zijn er 2278 combinaties mogelijk.

Voor 3.90 euro zijn er 214 combinaties (10 cent tot en met 2 euro).

De broncode voor deze simulatie is de volgende (in Python):

def Sum(munt):
    sum = 0
    values = [200,100,50,20,10,5]
    for i in range(6):
        sum += values[i] * munt[i]
    return sum

totaal = 385
poss = 0;
munt = [0,0,0,0,0,0]
for munt[0] in range(totaal//200+1):
    for munt[1] in range(totaal//100+1):
        for munt[2] in range (totaal//50+1):
            for munt[3] in range(totaal//20+1):
                for munt[4] in range(totaal//10+1):
                    for munt[5] in range(totaal//5+1):
                        if Sum(munt) == totaal:
                            print munt
                            poss += 1

print poss

[Dark_One]

ILUsion schreef:

Ik heb even vlug een brute-force simulatie laten doen voor je, als je 3.85 euro moet hebben, met munten van 5 cent tot en met 2 euro, dan zijn er 2278 combinaties mogelijk.

Voor 3.90 euro zijn er 214 combinaties (10 cent tot en met 2 euro).

De broncode voor deze simulatie is de volgende (in Python):

def Sum(munt):
    sum = 0
    values = [200,100,50,20,10,5]
    for i in range(6):
        sum += values[i] * munt[i]
    return sum

totaal = 385
poss = 0;
munt = [0,0,0,0,0,0]
for munt[0] in range(totaal//200+1):
    for munt[1] in range(totaal//100+1):
        for munt[2] in range (totaal//50+1):
            for munt[3] in range(totaal//20+1):
                for munt[4] in range(totaal//10+1):
                    for munt[5] in range(totaal//5+1):
                        if Sum(munt) == totaal:
                            print munt
                            poss += 1

print poss

Wow! Jammer dat ik geen python ken maar mooi staaltje! Enig idee wat er fout was aan mijn berekening aangezien ik toch een factor 6 hoger uitkwam ofzo (waarschijnlijk redundanties maar ik zie ze niet)

[ILUsion]

Hmm, maar ik zie juist dat ik met die 25 geen rekening gehouden heb, ik ga die er toch even bijsmijten. Voor de rest ben ik bijna zeker dat mijn simulatie vrij goed zou moeten werken, alleen doet hij er logischerwijs wel eventjes over (ik had geen zin om er backtracking in te steken).

Met die extra eis toch wat minder resultaten:
796 voor 3.85 euro in 5 cent tot 2 euro
176 voor 3.90 euro in 10 cent tot 2 euro (om dat te berekenen moet je een hash mark/spoorwegteken (#) voor de 17e lijn in de code zetten (laatste for-lus, zodat hij geen 5-centjes gebruikt, maar die steeds op 0 houdt).

Nieuwe broncode:

def SumMunten(munt):
    sum = 0
    values = [200,100,50,20,10,5]
    for i in range(6):
        sum += values[i] * munt[i]
    return sum

totaal = 385
maxMunt = 25
poss = 0;
munt = [0,0,0,0,0,0]
for munt[0] in range(totaal//200+1):
    for munt[1] in range(totaal//100+1):
        for munt[2] in range (totaal//50+1):
            for munt[3] in range(totaal//20+1):
                for munt[4] in range(totaal//10+1):
                    for munt[5] in range(totaal//5+1):
                        if (SumMunten(munt) == totaal) and (sum(munt) <= maxMunt):
                            print munt
                            poss += 1

print poss

En toch maar even uitleg daarbij: die def maakt een functie aan die van van munt (= aantal munten van elke soort) een som maakt, door rekening te houden met hun waardes. En sum (kleine letter!) telt gewoon de het aantal munten op. Verder vrij simpel: een hele hoop for-lussen met daarin een check plus weergave van hoe je alles kan samenstellen (hij drukt bv. [1,1,1,1,1,1] af, wat wilt zeggen 1x 2 euro + 1x 1 euro + ... + 1x 5 cent

[Gunkan]

Mooi werk ILUsion! You da man!

De eerste gedachte die ik had bij dit probleem was ook al: daar gaan we een stukje software bij schrijven. Dat ga je echt niet zomaar in je hoofd uitrekenen. Alleen het algoritme was nog een probleem, maar die heb jij nu dus! Nice

[ILUsion]

Ach, dat noem ik niet echt een algoritme; dit is gewoon puur brute-force lopen proberen, over de berekeningen doet hij bij mij ongeveer een halve minuut (wel met veel programma's open en nog een virtual machine). Een echt algoritme zou hetzelfde zijn maar dan met backtracking in op aantal munten of op de opgetelde waarde of een combinatie van beide criteria. En ik denk nu opeens dat ik de zoekruimte nog verder kan afbakenen, zeker voor de heel kleine muntjes en dat zal wel een performanceboost geven.

Hierzo de nieuwe code

def SumMunten(munt):
    sum = 0
    values = [200,100,50,20,10,5]
    for i in range(6):
        sum += values[i] * munt[i]
    return sum

totaal = 385
maxMunt = 25
poss = 0;
munt = [0,0,0,0,0,0]
for munt[0] in range(min(totaal//200,maxMunt)+1):
    for munt[1] in range(min(totaal//100,maxMunt)+1):
        for munt[2] in range (min(totaal//50,maxMunt)+1):
            for munt[3] in range(min(totaal//20,maxMunt)+1):
                for munt[4] in range(min(totaal//10,maxMunt)+1):
                    for munt[5] in range(min(totaal//5,maxMunt)+1):
                        if (SumMunten(munt) == totaal) and (sum(munt) <= maxMunt):
                            print munt
                            poss += 1
print poss

Voor mensen die dergelijke problemen leuk vinden: http://projecteuler.net/ (al is het juist de bedoeling om brute-force zo veel mogelijk links te laten liggen natuurlijk)