[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]