Scholieren.com forum

Scholieren.com forum (https://forum.scholieren.com/index.php)
-   Huiswerkvragen: Exacte vakken (https://forum.scholieren.com/forumdisplay.php?f=17)
-   -   [WI]Parkeerautomaat (https://forum.scholieren.com/showthread.php?t=1690604)

Jegor 14-05-2008 18:34
[WI]Parkeerautomaat
 
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!:y

Dark_One 14-05-2008 20:08
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 14-05-2008 21:31
En wat als het 3,90 is, is er een makkelijke manier?

Vinniebar 14-05-2008 22:10
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 14-05-2008 22:21
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 14-05-2008 22:28
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 14-05-2008 22:31
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 14-05-2008 22:32
ik (5 vwo NT) snap niks van bovenstaand verhaal, dus het zal de TS ook niet veel helpen vermoed ik... :P

Jegor 14-05-2008 22:36
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 14-05-2008 22:37
Citaat:
the unknown 1 schreef: (Bericht 27537634)
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 14-05-2008 22:45
Citaat:
Jegor schreef: (Bericht 27537717)
de €1 in 8 mogelijkheden,
Hoe kom je bij dit getal? (8x)

Dark_One 14-05-2008 22:46
Citaat:
Jegor schreef: (Bericht 27537717)
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 14-05-2008 22:50
Citaat:
Vinniebar schreef: (Bericht 27537790)
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 15-05-2008 15:19
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):
Code:
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 15-05-2008 18:03
Citaat:
ILUsion schreef: (Bericht 27540744)
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):
Code:
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 15-05-2008 20:16
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:
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(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 18-05-2008 11:14
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 18-05-2008 12:18
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
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)


Alle tijden zijn GMT +1. Het is nu 21:27.

Powered by vBulletin® Version 3.8.8
Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.