>> [Muusika mängib]
>> ZAMYLA chan Nüüd lahendada ahne.
Ütle, et sa oled kassast, ja sa pead andma oma klientide
teatud muutusi.
Noh, kui sa olid ahned kassapidaja, sa tahad, et hoida kõiki
mündid ise.
Nii et sa anda kliendile nende muutuste kasutades võimalikult vähe münti kui võimalik.
>> Sinu ülesandeks selles p-set on rakendada Ahne, programm,
arvutab minimaalne arv münte saab teha iga
antud muutuse summa.
Enne sukeldudes programmeerimine mõisted ja C süntaks ahne,
Vaatame kõigepealt rääkida läbi ahne programmi ja vaata, kas me
tunda algoritm.
Pea meeles, et algoritm on lihtsalt kogum
juhised probleemide lahendamine.
Algoritm ahne oleks lihtsalt loogikareeglite ja meetmeid,
saame jälgida.
Ja nad on alati saades minimaalne müntide arvu vaja.
>> Esimene asi, mida sa pead tean, on see, kui palju muutus
võlgneb kliendile.
Selle näite puhul oletame, $ 0,32.
On palju viise, kuidas saada tagasi $ 0,32.
Sa võid kasutada näiteks 32 penni.
Või kui, siis olid natuke greedier sisse Valides oma mündid, mida võiks kasutada
viis müntide asemel 32, andes kliendi kolm dimes -
$ 0,10 iga - ja kaks penni - $ 0,01 iga.
>> Aga me saame teha paremini kui viis münti?
Kas me saame olla isegi greedier?
Üsna võimalik.
>> Jätkame jalgsi läbi Ahne programm ja näha.
Kui teie lõppeesmärk on kasutada mõned mündid kui võimalik, siis oleks kõige
mõistlik kasutada suurimat võimalik münte.
Sa soovid anda veerand tagasi - $ 0,25 iga -
kui viie viiesendist -
$ 0,05 iga.
Nii et ehk meie valitsemise reegel Ahne saab alati kasutada
suurim münt võimalik.
Pole kvartali pakikesed, viiesendist, ja penne, meie
suurim münt on kvartal.
Me saame proovida kasutada neid esimesena.
>> Tagasi meie $ 0,32.
Kas me kasutame veerandi anda klient 0,32 $?
Jah.
See jätab meile $ 0,07 vasakule.
>> Kas me kasutame teise kvartali?
Ei, sest 25 on suurem kui seitse.
Me ei taha anda kliendile rohkem kui me neile võlgu.
>> Hea küll.
Nüüd, kui oleme ammendanud oma kvartalite Liigume edasi järgmisesse suurim
münt, peenraha.
Kas me kasutame peenraha anda klient oma 0,07 $ tagasi?
Ei, sest 10 on suurem kui seitse.
>> Nii siis järgmine suurim münt kättesaadav meile on niklit.
Kas me kasutame nikkel?
Jah.
Ja siis me tahaks olla $ 0,02 jäänud.
>> Me ei saa kasutada nikli tagasi $ 0,02.
Nii kolisime viimase münti meie käsutuses - teenari.
Ja pärast kahe penni, me tahaks olla vasakult null senti, mis tähendab, et
oleme edukalt tagasi maksta kasutaja oma muutus võlgu
kasutades ainult neli münti -
veerandi, üks niklit, ja kaks penni.
>> Võite käivitada personal lahendus, kas meie valitsemise reegel ja protsess andis
meile õige vastus.
Enamiku probleem komplekti, saate käivitada töötajate lahendus, kuidas
oma programm peaks töötama.
Ja konkreetsed juhised olla probleem seab specs.
>> Kui võtame personal lahendus, see küsib meilt, kui palju muutusi on ees
tähele, et see nõuab, et summa dollarites.
Me sisend $ 0,32, 0,32.
See ütleb meile, et nelja mündid võlgu, kooskõlas meie vastus.
Fantastiline.
>> Nüüd lähme otsima on rakendada
ahne algoritm.
Me teame, paar asja.
Üks, et me peame küsima kasutaja muutuse summa.
>> Kaks, et me tahame järgida oma reguleeritakse reeglina alati kasutada
suurim münt võimalik.
Ja kolm, et meil on vaja jälgida kui palju münte me kasutame.
Sest lõpuks on meil vaja printida müntide arvu, mida me.
>> Esiteks sunnib kasutaja jaoks muutuse summa.
Kui teil tegeleda kasutaja sisend, teha kindel, et sa arvad, et kõik
nõuetele sisend, ja ainult aktsepteerida sisend, mis vastab nende
nõuetele.
Sellisel juhul me tahame tegeleda rahaline väärtus dollarites.
>> GetFloat ja GetInt funktsioonide tagamiseks et sisend on numbriline.
Aga kasutaja suudab sisend negatiivsed arvväärtused.
Seega pidage meeles, kasutada ainult mitte-negatiivne sisendeid, mis sisaldab kõiki negatiivseid
numbrid ja nulli.
>> Sel juhul sisend peaks olema sularahaga.
Teisisõnu kümnendmurruna.
Kuna probleem komplekt spec eeldab sa küsida sisendina dollarit.
>> Kuid C, ujukoma väärtuste saa esindab täpselt.
Kuna meil on piiratud arv bittide kellega
esindama lõpmatu väärtused.
Võtke number 0,1.
Kui ma palun teil kirjutada 0,1 poolt käe sajandat kümnendkohani
sa oleks kirjutada 1, millele 99 nullidega.
Tahame loota, et meie arvuti oleks printida täpselt sama asi
kui küsisime seda.
>> Vaatame, mida ta teeb.
Ma vaadata trükkimine väärtused suunas lõpuks see läbi kõndida.
Praegu näeme siin, et f% on kohatäide ujukoma.
Aga me määrata eelnevalt, et me tahame 100 komakohad ekraanil, ja siis uus
rida kenamaks vormingut.
>> Pärast string valime 0,1 float, et me tahame välja printida.
Ja tulemus, üks, millele järgneb mõned nullid, kuid siis
terve hunnik numbreid.
Kindlasti mitte ootuspäraselt.
>> Ujukomajagamist ebatäpsus võib kehtestada Ümardamise oma
arvutused, et te Kindlasti soovime vältida.
Kui soovite näha rohkem näiteid, siis saate laadida imprecision.ce alates
kõndida läbi kood, mis on lihtne programm, mis küsib float ning prindib
tagasi sajandat kümnendkohani.
Muidugi, kui sa tahad, et näidata rohkem või vähem pärast koma
saate muuta ise.
>> Nagu näete, kuigi erinevus nende kahe vahel on väike, kui sa saad
korrutades ja lisades ujukid, mis Vastuolu lõpuks tõusta.
Tagasi ahne.
Me tahame vältida ümardamisvigu käsitledes täisarvudega.
Nii et pärast saame kehtiv sisend kasutaja, olgem muuta see
dollar väärtust senti.
>> Vaimselt, me teeme seda, korrutades dollari väärtuses 100ga.
Kuid pidage meeles, sest ujukoma ebatäpsuse, me tahame teha
kindel, et me kasutame õige väärtus.
Korrutades 100ga sisuliselt liikuda kümnendkohani kaks ruumid
õige, tükeldamine ära või ürita midagi hiljem.
>> Kui teil mängida mõned rohkem näiteid, siis näed, et sa ei
alati sain õige number kui te kasutada seda meetodit ürita.
Näiteks 12,59 trükitud 100 pärast koma, mis annab teile
12,5899, jne.
Sa saad 12,58 kui sa kärbitud, mitte 12,59, nagu te vajate.
>> Selle asemel, et see on parim ümardada number esimene.
Õnneks C kaasas funktsiooni nimetatakse vooru.
See on matemaatika raamatukogu.
>> Kui soovite teada, kuidas kasutada vooru siis võite tuua need käsitsi või
mees lehekülg, funktsioon.
Saate seda teha kirjutades mees, lühike käsitsi ja seejärel funktsioonile
soovite otsida.
Nii kirjutades mees ringi terminali käsurea avab kasutusjuhend.
>> See võib olla veidi raske dešifreerida, kuid lõpuks teid
aru saama sellest.
Man lehekülge näidata, mida funktsioon ei, ja siis mõned
võimalikke kasutusviise see.
Ma jätan teid uurida man-leheküljelt vooru.
Aga tean, et te saate seda kasutada ümardada väärtus ajal konverteerimine
dollarit senti.
>> Round teile tagasi number Andmete tüüp double.
Ja saate teisendada või valatud see int hiljem.
Suur.
Nüüdseks oleme küsitakse kasutaja jaoks rahaline väärtus ja
teisendatakse see senti.
Nüüd saame rakendada algoritmi et kasutab alati
Suurim mündid.
>> Pea meeles, et seal on mitu kuidas rakendada ahne, nagu
seal on mitu võimalust lähenemine iga arvutiteadus probleem.
Leida kõige elegantsem viis, see on lõbus osa.
Kogu nende p-komplekti, kui teie programm täpselt ei sobi minu
selgitus walkthroughs, see on OK.
Aga veenduge, et see läbiks vaadake 50, vastab kõikidele
nõuded moodustavad kirjeldused, ja mis te arvate, kas teie
lähenemine on hea disain.
>> Teisisõnu, kui tõhus see on?
Näiteks, kas sa kirjutad korduvad koodiridades kasutamise asemel loop?
Kirjutamine kood parem disain tulema kogemus nagu te arengut
kaudu muidugi.
>> Selle läbi kõndida, ma lähen üle kaks meetodit, mida saab kasutada
lõpule ahne.
Esimene meetod on meetod, kasutades silmuseid ja lahutamine.
Varem, kui me rääkisime läbi Ahne protsessi me pidevalt
kontrollida, kas me võiksime kasutada kvartalis ja kasutatud veerand kuni
väärtus ülejäänud oli alla $ 0,25.
>> See tähendab ka, et samas loop struktuuri.
Kuigi me saame veel kasutada kvartali kasutate.
Et kuigi loop peaks rahuldama nii kaua kui järelejäänud väärtus on suurem kui
või võrdne kvartali protsenti väärtusest.
See tähendab, et sa ka tahad jälgida allesjäänud raha
väärtus, ja ajakohastab seda iga aeg, et te kasutate mündi.
>> Samuti pidage meeles, et lõpus, teie väljund on müntide arvu, mida kasutatakse.
Nii teine ​​asi jälgida on müntide arvu, mida saate kasutada.
Saad jälgida nende abil hästi nimega muutujaid.
Ja kehas oma loop oleks olema uuendatud need muutujad.
Kui ahel kvartalis lõpeb, kuvatakse saab kasutada sarnaste üks pakikesed,
ja nii edasi ja nii edasi, kuni olete tagastatakse kõik raha.
>> Olen kirjutanud mõned pseudo-koodi siia aitab teil visualiseerida, kuidas
protsess arutasime võiks tõlkida C. Nagu näete siin, ma ikka kasutada
Ingliskeelseid sõnu.
See ei ole C veel.
Aga ma olen hakanud taane asju.
Ma panin tingimused sees minu sulgudes.
See on hakanud otsima natuke natuke nagu programmeerimine kood.
>> Pseudo-kood on suurepärane võimalus saada ise alustada.
Kujutle oma kood enne sa vaatad üles süntaks.
Sest sageli kõige raskem osa umbes Probleem on tegelikult mõista, mida
täpselt, mida vaja teha.
Kui sa selle üles kirjutama, siis on palju lihtsam otsida funktsioonid
ja süntaks konkreetselt teie rida pseudo-kood
>> Pea meeles, et see ei pruugi olla identne objekti skelett
koodi, mis sa kirjutad.
Alati on optimeerimisest tehakse.
Ja eriti minu pseudo-kood siin, vaata, kas saate kohapeal ta.
>> Aga sisuliselt protsessi ja mõtteviis
just nagu me arutasime.
Esimene rida ütleb meile, et saada teatud summa dollarites.
Ja teine ​​ütleb, et teisendada see senti.
>> Ja seejärel, samas neljandikku saab kasutada, me soovivad suurendada mündi arvu ja
väheneb rahasumma.
Sama kehtib pakikesed, viiesendist, ja penni.
Ja lõpuks, me öelda kasutaja kui palju münte me kasutasime.
>> Suur.
Nii et lõpetame loop meetod.
Nüüd räägime modulaarne meetod, mis on rohkem nagu rajoon.
>> Me oleme kõik tuttavad pluss, miinus, korrutada ja jagada ettevõtjad
meile kättesaadav.
C on kõik neli nendest, kuid on ka moodul operaator, keda esindab
protsendimärk.
Modulo on tõesti puhas.
See annab sulle ülejäänu jagamisel kahe arvuga.
>> Mäleta pikk jaotus sõnum sa jagad, ütleme, 74 kolme?
Alustades kümneid koht, siis oleks tean, et 3 läheb seitse
kaks korda teha kuus koos Ülejäänud üks.
Sa kirjutad kaks ülaosas ja seejärel lahutama 6 seitsmest, mis veavad üle
Ülejäänud 14 kuni korrake protsessi.
>> Kolm läheb 14 neli korda tee 12, koos ülejäänud kaks.
Ja kaks ei kanna üle enam.
Nii kaks oleks jäänud alt kui ülejäänud.
>> Ja see moodul annab, siis et number allosas.
Nii 74 mooduli kolm annaks sulle kaks.
Ja 10 moodul kaks, hästi, et annaks teile null.
Sest seal ei ole ühtegi järelejäänud kui sa jagad 10 kahega.
>> Kuus moodul viis, samuti viis läheb kuus korda.
Ja siis on üks üle jäänud.
Nii kuus moodul viis on üks.
>> Siis kui sul on seitse moodul üheksa, siis tahaks saada seitse.
Kuna üheksa on suurem kui seitse.
Seega ei jaga see kõik seitse, jättes seitse nagu teie vastus.
>> Kui sa arvad, moodul veidi rohkem, pidage meeles, et see annab teile
Ülejäänud pärast jagate midagi.
Mõtle, kui sa võiksid olla võimalik kasutada seda ahne.
Oletame, et kasutaja küsib $ 400,11.
Mis viis välja selgitada, kui palju kvartalites sa vajad, ilma et
loe iga üks?
>> Kui oled nuputada, kuidas mitmel pool saate teha $ 400,11, kui palju
Muudatus jääb?
Ehk kombinatsioon siin vahel mooduli ja jaotus oleks tulnud
mugav teile jahe, elegantne lähenemine ahne probleem.
Kuid pidage meeles, et EKP reegel kehtib endiselt.
Kasutage alati suurim münt võimalik.
>> Kui oled seda teinud arvutamisel kuidas palju münte kasutada, viimane samm
on välja trükkida arvu mündid, mis sa arvutada.
Siiani oleme kasutanud printf toimida ainult stringe.
Aga kui sa tahad välja printida In, või lihtsalt igat liiki andmeid, mis on salvestatud
aastal erinev, pead näitama et kasutades kohatäide.
>> Siin olen lisanud vaid mõned nipid kuidas printida välja väärtused.
Kui teil on täisarv, siis oleks kirjutage string kasutades% d kui
kohatäide.
Pärast sulgemist tsitaat mark, sisestage komaga.
Ja seejärel panna täisarv, mis võtta koht% d kui välja trükkida.
>> Nii et pärast väljapanek number münte kasutatakse, oled
viimistletud ahne.
Veenduge, et kontrollida kõik nurk juhtudel koristama oma stiili natuke, ja sa oled
kõik seatud esitama.
Lõpus see probleem komplekti, saate rohkem tuttavad CS50
aparaat, terminal ja loop struktuuride ja muutujate C.
>> Sa oled ka oma viis.
Õppimiskõver võib tunduda raske.
Nii et see samm-sammult.
Veenduge, et te kirjutada pseudo-kood Enne sukeldumist liiga sügav
arvesse harjumatu süntaks.
>> Tee seda nimekirja ning lõhkuda ülesande väiksemateks
juhitavuse ülesandeid.
Avasta kogu CS50 ressursse.
Lisaks loeng, rewatch Selle läbi kõndida.
>> Pöörake tähelepanu jagu.
Tutvu püksid.
Loe oma klassikaaslaste küsimused edasi Arutle ja lisada oma.
>> Palju õnne p-set.
Ja tänu vaadates.
See oli ahne.
>> [Muusika mängib]