WisFaq!

Re: Laagste gemiddelde berekenen voor munten

Welk computer programma zou je hier op los kunnen laten, of hoe zou een berekening voor een programma er uit zien om dit op te kunnen lossen ?

Frank
22-11-2004

Antwoord

Wel stel dat je de munten de waarden a,b,c,d,e,f geeft (in oplopende volgorde). Dan zou de pseudocode er zo uit kunnen zien (in TurboPascal of zoiets):

for i:=1 to 99 begin (i is dus de waarde waarvan je wil nagaan hoeveel munten je nodig hebt)
if i=a or i=b or i=c or i=d or i=e or i=f
then aantal := 1
else if i=a+a or i=a+b or ... or i=f+f (36 mogelijkheden)
then aantal := 2
else if i=a+a+a or ... or i=f+f+f (216 mogelijkheden)
then aantal := 3
...
teller := teller + aantal (deze teller houdt dus het aantal munten bij dat je in totaal nodig hebt)
end
gemiddelde := teller/99

Dit algoritme is nogal omslachtig, zeker als je voor een bepaald bedrag 6 munten of zo nodig zou hebben. Maar ik zie niet meteen hoe het veel vlugger zou kunnen. Je zou natuurlijk een aantal overbodige mogelijkheden kunnen schrappen, bijvoorbeeld als je grootste munt f=35 is, dan is het nutteloos om mogelijkheden te testen waarin f+f+f voorkomt. Of als je een munt a=1 en een munt b=3 hebt, is het nutteloos om mogelijkheden te testen waarin a+a+a voorkomt, want dan kan je beter b gebruiken.

Dat programma kan je dan gebruiken om de efficiëntie van een bepaalde set te testen. Als je de efficiëntste set wil vinden kan je ook nog eens een gigantische lus errond bouwen, namelijk a:=1, for b:=a+1 to 5, for c:=b+1 to enzovoort.

Groeten,
Christophe.

Christophe
27-11-2004