>> [Predvaja glasba]
>> ZAMYLA CHAN: Zdaj pa dosti požrešen.
Povejte, da ste blagajnik, in ti morali dati svoj stranka
določena količina sprememb.
No, če ste bili pohlepni blagajna, ki ste jo želeli obdržati vse
kovanci zase.
Torej boš dal stranki svoj sprememb s čim manj kovancev, kot je mogoče.
>> Vaša naloga v tej p-set je izvajanje Pohlepni, program, ki
izračunava z najmanjšim številom kovancev, ki se uporabljajo, da bi katerikoli
glede na znesek sprememb.
Pred potopom v programiranju koncepti in C sintaksa za požrešen,
dajmo najprej govoriti s požrešen programa, in videli, če bomo
lahko identificira algoritem.
Ne pozabite, da algoritem je le niz
Navodila za reševanje problemov.
Algoritem za požrešen bi bilo samo skupek logičnih pravil in ukrepov, ki jih
lahko sledimo.
In bodo vedno dobili najmanj število kovancev, ki so potrebni.
>> Prva stvar, ki jo je potrebno vedeti je, kako veliko sprememb
dolguje stranki.
Za ta primer, recimo 0,32 $.
Obstaja veliko načinov, da bi dobili nazaj 0,32 $.
Lahko uporabo, na primer, 32 penijev.
Ali pa, če ste bili malo greedier v izbiranju kovancev, lahko uporabite
pet kovancev, namesto 32 jih daje kupcev tri dimes -
0,10 $ vsak - in dva penijev - 0,01 $ vsak.
>> Vendar pa lahko storimo bolje kot petih kovancev?
Smo lahko še greedier?
Precej verjetno.
>> Pojdimo naprej hoja skozi požrešen program in videli.
Če je vaš končni cilj je, da uporabite nekaj kovancev je to mogoče, potem bi bilo najbolj
preudarno uporabiti največji možnih kovancev.
Raje bi dal eno četrtino back - 0,25 $ vsak -
kot pet nickels -
0,05 $ vsak.
Torej, morda naša ureja pravilo Požrešen lahko vedno uporabite
mogoče največji kovanec.
Od četrtletjih, dimes, nikelj, in penijev, naša
Največji kovanec četrtletje.
Zato bomo poskušali, da jih najprej uporabiti.
>> Nazaj na našo 0,32 $.
Bomo lahko uporabili četrtino, da bi Stranka 0,32 $?
Da.
To bi nas pustijo pri 0,07 $ levo.
>> Moremo uporabiti drugo četrtino?
Ne, ker 25 je večje od sedmih.
Ne želimo, da bi stranki nič bolj, kot smo jim dolžni.
>> Vse je v redu.
Zdaj, ko smo izčrpali svoje prostore, gremo na naslednjo, večjo
kovanec, dime.
Moremo uporabiti niti centa, da bi Stranka njihovo 0,07 $ nazaj?
Ne, ker 10 je večje od sedmih.
>> Torej dostopni naslednji največji kovanec za nas je nikelj.
Smo lahko uporabite kovanec?
Da.
In potem bomo imeli $ 0,02 levo čez.
>> Ne moremo uporabljati niklja vrniti 0,02 $.
Zato smo se preselili zadnji kovanec na naša odstranjevanje - penija.
In po uporabi dveh penijev, bi morali biti levo z nič centov, kar pomeni, da
smo uspešno vrniti Uporabnik njihova sprememba dolguje
uporabljajo le štiri kovance -
ena četrtina, en nikelj, in dveh penijev.
>> Lahko zaženete rešitev osebja, ki bi videli, če naša pravila, ki urejajo postopek in dal
nam pravi odgovor.
Za večino problematičnih sklopov, morda ne boste mogli teči rešitev osebja, ki bi videli, kako
svoj program bi moral delati.
In posebna navodila bodo biti problema postavlja očala.
>> Ko tečemo rešitev osebja, je nas vpraša, kako je veliko sprememb dolguje
Opozarjamo pa, da zahteva Znesek v dolarjih.
Vnesemo 0,32 $, 0.32.
To nam pove, da so štirje kovanci dolguje, v skladu z našim odgovorom.
Fantastično.
>> Torej, zdaj začnimo išče pri izvajanju
od pohlepnih algoritma.
Vemo, da nekaj stvari.
Ena, da se bomo morali spodbuditi Uporabnik za znesek sprememb.
>> Dva, da bomo želeli slediti našim ureja pravilo, da vedno uporabljate
mogoče največji kovanec.
In tretjič, da moramo slediti koliko kovancev, ki jih uporabljamo.
Ker nenazadnje, moramo natisniti število kovancev, ki jih imamo.
>> Prvič, da bi od uporabnika za znesek sprememb.
Vsakič, ko se ukvarjajo s prispevki uporabnikov, da prepričajte, da misliš, da vse
Zahteve iz vhoda, in le sprejemajo vhoda, ki ustreza tisti,
zahteve.
V tem primeru želimo, da se ukvarjajo z denarna vrednost v dolarjih.
>> Funkcije GetFloat in GetInt zagotovi da je vhod številčna.
Vendar uporabnik lahko vložek negativne številčne vrednosti.
Torej, ne pozabite uporabljati samo ne-negativna vložki, ki vključuje vse negativne
številke in nič.
>> V tem primeru, vhod mora biti float.
Z drugimi besedami, številka.
Ker problem niz spec zahteva vas zahteva vnos v dolarjih.
>> Ampak v C, s plavajočo vejico ne more se pravilno predstavljeno.
Ker obstaja končno število bitov, s katerimi bi
predstavljajo neskončne vrednosti.
Vzemite številko 0.1.
Če bi vas prosil, da napišete 0,1 s roko na stoti decimalno mesto,
bi napisal 1, ki ji sledi z 99 ničlami.
Mi bi pričakovali, da bi naš računalnik natisnite točno isto stvar
če jo prosil.
>> Pa poglejmo, kaj počne.
Bom pregledala vrednosti tiskanje proti konec tega sprehod skozi.
Za zdaj vidite tukaj, da je f% Ograda za plavajočo vejico.
Vendar smo opredeliti vnaprej, da želimo 100 decimalk prikaže, in nato novo
linija za lepše oblikovanje.
>> Po nizu, smo izbrali kot 0,1 float, da želimo natisniti.
In rezultat, enega, ki mu sledi z nekaterimi ničel, potem pa
Cel kup številke.
Zagotovo ne, kot je bilo pričakovano.
>> Plavajočo vejico nenatančnost lahko uvedejo zaokroževanja napake v vašem
Izračuni, ki jih bo zagotovo želeli izogniti.
Če si želite ogledati več primerov, ki jih Lahko prenesete imprecision.ce od
sprehod skozi kodo, ki je preprosta Program, ki prosi plavajo in jo natisne
nazaj na stoti decimalno mesto.
Seveda, če želite prikazati bolj ali manj decimalna mesta
lahko spremenite sebe.
>> Kot boste videli, čeprav je razlika med njima je majhna, ko prideš
za razmnoževanje in dodal, boje, da neskladje lahko sčasoma seštevajo.
Nazaj na požrešen.
Bomo želeli, da bi se izognili napakam pri zaokroževanju ukvarjanje s celimi števili.
Torej, ko smo dobili veljavno prispevke uporabnik, dajmo spremeniti to
vrednost dolarja do centa.
>> Duševno, to storimo tako, da se vrednost dolarja za 100.
Ampak zapomni si, ker s plavajočo vejico nenatančnost, želimo, da bi
prepričani, da bomo s pomočjo prave vrednosti.
Pomnoži s 100 bo v bistvu premikajo decimalno mesto dve prostori za
Dobro, sekal ali krajšanju kaj potem.
>> Če ste igral z nekaj več Primeri, boste videli, da vam ne bo
Vedno imaš pravo številko, če ste uporabiti to metodo pri krajšanju.
Na primer, 12,59 natisnjena na 100 decimalni mesti, ki vam daje
12,5899, et cetera.
Ti bi dobili 12,58, če obrezana, ne 12.59, kot ga potrebujete.
>> Namesto tega, je najbolje, da zaokrožujejo prva številka.
Na srečo, C prihaja z Funkcija se imenuje Round.
To je v knjižnici matematike.
>> Če želite vedeti, kako uporabljati krog, potem lahko bruhati priročnik ali
man stran za to funkcijo.
To storite tako, tipkanje človeka, okrajšava za Navodilo, nato pa funkcijo, ki jo
želite poiskati.
Torej tipkanje človek krog v terminal ukazni vrstici bo odprlo priročnik.
>> Morda bi bilo malo težko razvozlati, ampak na koncu boste
dobili visi za to.
Strani man ti pokazal, kaj funkcije ne, in nato nekaj
Možnosti uporabe njo.
Pustil vas bom, da razišče Stran človek za krog.
Vendar vem, da ga lahko uporabite za zaokrožitev vrednost v času vašega pretvorbo iz
dolarjev za centov.
>> Okrogla vam bo dala nazaj številko podatkovni tip double.
In lahko pretvorite ali litega to, da notr kasneje.
Super.
Do sedaj smo pozove uporabnika za denarni znesek, in
jo pretvori v centov.
Sedaj lahko izvaja algoritem da vedno uporablja
Največji voljo kovanci.
>> Imejte v mislih, da obstaja več načine za izvajanje požrešen, tako kot
obstaja več načinov za pristop vsak računalnik problem znanosti.
Najti najbolj eleganten način, To je zabaven del.
V teh p-sprejemnikov, če je vaš program ne povsem ujema z mojim
razlaga v walkthroughs, da je v redu.
Ampak se prepričajte, da prehaja preveri 50 izpolnjuje vse
Zahteve za oblikovanje specifikacij, in da se preuči, ali si
pristop ima dober dizajn.
>> Z drugimi besedami, kako učinkovito je to?
Na primer, ste tip ponavljajoče vrstic kode, namesto z zanko?
Pisanje kode z boljšim načrtovanjem bo Spoznajte, kako napredujete
skozi tečaj.
>> Za ta sprehod skozi, bom šel čez dva načina, ki se lahko uporabljajo za
dokončati požrešen.
Prvi način je z uporabo metode zank in odštevanje.
Prej, ko smo se pogovarjali z Požrešen proces, smo nenehno
preveriti, ali bi lahko uporabili četrtino, in se uporablja četrtino, dokler
Preostala vrednost je manj kot 0,25 $.
>> To tudi pomeni, da medtem ko zanka.
Medtem ko smo lahko še vedno uporabljate četrtletje uporabljate.
To pa zanka treba izvesti, dokler kot je preostalo vrednost večja od
ali enaka četrtletnim odstotno vrednost.
To pomeni, da boste prav tako želeli slediti preostalim denarjem
vrednost, in ga vsako posodobitev Čas je, da uporabite kovanec.
>> Prav tako ne pozabite, da je konec, si izhod je število kovancev, ki se uporabljajo.
Torej, še ena stvar, da bi spremljali, je število kovancev, ki jih uporabljate.
Lahko spremljate to uporabo dobro imenom spremenljivke.
In v telesu zanke bi bo posodobitev teh spremenljivk.
Ko se zanka za četrtino konča, vas lahko uporabite podobno enega za centov,
in tako naprej in tako naprej, dokler ste vrne vse denarne.
>> Sem napisal nekaj psevdo-kodo tukaj vam pomaga vizualizirati, kako
Proces smo razpravljali morda prevesti C. Kot vidite tu, jaz sem še vedno uporabljajo
Angleške besede.
To ni C še.
Vendar sem začel alinea stvari.
Sem dal pogoje znotraj moji oklepaje.
Začenja pogledati malo nekaj podobnega programsko kodo.
>> Psevdo-koda je odličen način da bi sami začeli.
Vizualizirati svojo kodo, preden pogledaš gor sintakso.
Ker pogosto najtežji del o Problem je res razume, kaj
točno to, kar morate storiti.
Ko pišete, da se, potem je to Veliko lažje iskanje funkcije
in skladnjo specifičen za vašo Linija psevdo-kodo
>> Imejte v mislih, da to morda ne bo identičen vrste skeletu
kodo, ki ste napisali.
Vedno obstajajo optimizacije je treba izvesti.
In še posebej v mojem psevdo-kodo tukaj, vidim, če lahko na kraju samem.
>> Toda v bistvu postopek in način razmišljanja
je tako kot sva se dogovorila.
Prva vrstica nam pove, da pridobi določen znesek v dolarjih.
In drugič nam pove, da spremeniti to centov.
>> In lahko potem uporabljati med četrtine smo želijo povečati število kovanec in
zmanjšajte količino gotovine.
Enako velja za Dimes, nickels, in penijev.
In končno, uporabniku povemo, koliko kovancev smo uporabili.
>> Super.
Tako, da zaključi postopek z zanko.
Zdaj pa govoriti o modularni metodi, kar je več, kot so delitev.
>> Vsi smo seznanjeni s plus, minus, množenje in deljenje operaterje
nam na voljo.
C ima vse štiri od teh, ampak ima tudi operator modula, ki ga zastopa
znak za odstotek.
Modul je res lepo.
To vam daje ostanek iz delitvijo dveh številk.
>> Zapomni si dolgo delitev sporočilo, ko si razdeliti, recimo, 74 za tri?
Začenši z več deset mestu, bi si vem, da 3 gre v sedmih
dvakrat, da bi s šest Preostanek ena.
Ti bi napisali dva na vrhu, nato pa odštejemo 6 od sedmih, prenašanje
Preostanek 14 do ponovite postopek.
>> Tri gre v 14 štirikrat za bo 12, s preostalo dva.
In drugič, ne prenesejo več.
Zato bi se dva levo na spodnji kot ostanek.
>> In to je tisto, kar daje modulu, ki jih ta številka na dnu.
Torej bi 74 modulu tri dam dva.
In 10 modulu dva, dobro, da bi dal nič.
Ker ni vsaka preostanek ko si delimo 10 z dva.
>> Šest modulu pet, tudi pet gre v šestih enkrat.
In potem je bil eden levo čez.
Torej šest modulu pet je ena.
>> Potem, če imate sedem modulu devet, ki ste jo dobili sedem.
Ker je devet je večji od sedmih.
Torej ne vse razdeliti na sedem, odhodu sedem kot vaš odgovor.
>> Če menite, da o modulu malo več, ne pozabite, da ste, da daje
Preostanek po delite nekaj.
Pomislite, kako bi bilo lahko ga uporabljate v požrešen.
Recimo, da uporabnik prosi za $ 400,11.
Kaj je način, da ugotovimo, koliko prostori, ki jih potrebujete, ne da bi
šteje vsak enega?
>> Ko ste ugotovili, koliko četrtine lahko uporabite, da bi $ 400,11, koliko
spremenite ostanke?
Morda kombinacija tukaj med modulu in delitev bi prišli v
priročno, da vam kul, elegantno pristopiti k Greedy problem.
Ampak ne pozabite, da urejajo pravilo še vedno velja.
Vedno uporabljajte čim večje kovanec.
>> Ko ste naredili izračun, kako veliko kovancev za uporabo, zadnji korak
je izpisal število kovanci, ki jih izračunati.
Doslej smo se s pomočjo printf delujejo izključno za godala.
Toda, če želite natisniti In, ali Pravkar vse vrste podatkov, ki je shranjena
v spremenljivko, boste morali navesti da se z uporabo ogrado.
>> Tukaj sem vključena le nekaj nasvetov kako natisniti vrednosti.
Če imate celo, bi si napišite niz uporabljate% d kot
Ograda.
Po zaključnem tečaju mark, vnesite vejico.
In nato dal v celo, da bo prevzame mesto% d ob izpisu.
>> Torej po prikazovanje števila rabljenih kovanci, si
končal z požrešen.
Poskrbite, da preverite vse primere iz kota počistiti vaš stil malo, in ste
Vse je pripravljeno za pošiljanje.
Ob koncu tega problema, ki si boste biti bolj seznanjeni z CS50
aparat, terminal in zanke strukture in spremenljivke v C
>> Ste na dobri poti.
Krivulja učenja lahko zdi težka.
Torej, da se korak za korakom.
Poskrbite, da napišete iz psevdo-kodo Pred potapljanje pregloboko
v neznanem sintakso.
>> Naredite seznam opravkov, in break up Razporeditev v manjše, bolj
obvladljive naloge.
Raziščite vse CS50 virov.
Poleg predavanj, rewatch ta sprehod skozi.
>> Pozornost na oddelku.
Oglejte si hlače.
Preberite vprašanja sošolci " na Pogovorite se in objavite svoje.
>> Veliko sreče z p-set.
In hvala za gledanje.
To je bil požrešen.
>> [Predvaja glasba]