Sist endret: 23.09.2016  
 

Praksisoppgave - Pengeveksling

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 16.10.2017 15:00

Denne øvingen er ikke laget ferdig ennå.

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
pengeveksling.py, pengeveksling_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
pengeveksling.py Funksjonene minCoinsGreedy(coins, value), minCoinsDynamic(coins, value) og canUseGreedy(coins)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 3
8
2
input_eksempel_02.txt 6
8
4

Pengeveksling

Det er ikke nødvendig å lese historien for å løse oppgaven.

Dr. Gewalt er som vanlig i gang med å klekke ut en genial plan for å ta over verden. Han gjør selvfølgelig grundig arbeid, og nå har han kommet til punktet hvor han skal bestemme seg for myntsystemet som skal innføres etter at han har kommet til makten. Etter lang drøfting med sine rådgivere har han kommet frem til en rekke myntsett som han kan velge mellom (blanke mynter er mye penere enn sedler, synes han, så det finnes bare mynter, ikke sedler). Nå har det seg slik at Dr. Gewalt har visse faste pengesummer som han ofte bruker (f.eks. som bestikkelser av statsansatte, hvitvasking av penger eller innsats i poker), og han ønsker å finne ut hvor mange mynter som vil kreves for å dele ut hvert beløp med de forskjellige myntsettene.

Oppgave

Du får oppgitt et myntsett, og så skal du finne det minste antallet mynter som kreves for å dele ut en rekke oppgitte beløp. Utdelingen skal gjøres med en grådig algoritme på noen datasett, og med dynamisk programmering på andre.

Første linje i inputfilen inneholder myntverdiene (kun heltall).
Andre linje inneholder én av tre strenger: "graadig", "dynamisk" eller "velg". Står det "graadig", betyr det at en grådig algoritme vil produsere riktig resultat for dette myntsettet, og at programmet derfor bør bruke den grådige algoritmen siden den er mye raskere. Står det "dynamisk", betyr det at den grådige algoritmen ikke fungerer for dette myntsettet, og at dynamisk programmering derfor må benyttes. Står det "velg", betyr det at programmet selv skal velge algoritme. Det kan derfor lønne seg å finne ut hvordan man kan avgjøre ut i fra et gitt myntsett hvorvidt den grådige algoritmen vil fungere eller ikke. Klarer man dette, kan man la programmet velge basert på det; ellers må man bare kjøre dynamisk programmering, siden det fungerer på alle myntsett. Hver korrekthetstest vil inneholde enten "graadig" eller "dynamisk", mens eksempeloppgaven og alle tidstestene vil inneholde "velg".
De resterende linjene inneholder myntbeløpene som skal deles ut, ett på hver linje.

Alle myntsettene inneholder mynten 1, slik at det vil være mulig å dele ut alle beløp.

For hvert myntbeløp (ett på hver inputlinje unntatt de to første) skal du skrive ut, på en egen linje, det minimale antallet mynter som kreves for å dele ut dette beløpet.

Rammeverk

from sys import stdin

Inf = 1000000000


def min_coins_greedy(coins, value):
    # SKRIV DIN KODE HER


def min_coins_dynamic(coins, value):
    # SKRIV DIN KODE HER


def can_use_greedy(coins):
    # bare returner False her hvis du ikke klarer aa finne ut
    # hva som er kriteriet for at den graadige algoritmen skal fungere
    # SKRIV DIN KODE HER

coins = []
for c in stdin.readline().split():
    coins.append(int(c))
coins.sort()
coins.reverse()
method = stdin.readline().strip()
if method == "graadig" or (method == "velg" and can_use_greedy(coins)):
    for line in stdin:
        print(min_coins_greedy(coins, int(line)))
else:
    for line in stdin:
        print(min_coins_dynamic(coins, int(line)))

Variabelbeskrivelse

Rammeverket i denne oppgaven gir to variabler. 'coins' er en liste over de forskjellige myntene man har tilgjengelig. Disse er sortert i synkende rekkefølge. 'value' er beløpet man skal prøve å veksle.

Input-eksempel

1000 20 500 1 100 50 5 10 200 4
velg
1024
2567
8

Tilhørende output

3
8
2

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit