>> [MUSIC Playing]
>> ZAMYLA Chan: Most hadd kezelni mohó.
Mondjuk te egy pénztáros, és kell, hogy az ügyfél a
bizonyos mennyiségű változás.
Nos, ha volt egy kapzsi pénztáros, azt szeretné, hogy az összes
Az érmék magad.
Tehát azt, hogy az ügyfél a változás felhasználásával néhány érme lehetséges.
>> Az Ön feladata e p-set, hogy végre Greedy, egy program, amely
kiszámítja a minimális érmék használt, hogy minden
adott mennyiségű változás.
Mielőtt búvárkodás a programozási koncepciók és C szintaxist Greedy,
nézzük először beszél a Greedy programot, hátha
azonosítani egy algoritmus.
Ne feledje, hogy az algoritmus csak egy sor
utasítások a problémák megoldására.
Az algoritmus a Greedy ez csak egy beállított logikai szabályokat és lépéseket, amelyek
tudjuk követni.
És mindig így a minimum számú érmét szükséges.
>> Az első dolog, amit meg kell tudja, hogy mennyi változás
áll fenn az ügyfél.
Ebben a példában, mondjuk 0,32 $.
Nagyon sok módja van, hogy újra 0,32 $.
Lehet használni, például, 32. fillérekért.
Vagy, ha te egy kicsit greedier a választotta a pénzeteket, akkor használja
öt érmét helyett 32 azáltal, hogy az ügyfél három Dimes -
0,10 $ minden -, valamint két fillérekért - 0,01 $ minden.
>> De vajon mi a jobb, mint öt érmét?
Lehetünk még greedier?
Nagy valószínűséggel.
>> Nézzük tovább séta A Greedy programot, és nézd meg.
Ha a végső cél az, hogy egy pár érmét lehetséges, akkor ez lenne a leginkább
körültekintő használata a legnagyobb lehetséges érméket.
Inkább ad negyede Back - 0,25 $ minden -
mint öt nickels -
0,05 $ minden.
Így talán az irányító szabály Greedy lehet, hogy mindig a
legnagyobb érme lehetséges.
Out of negyedévben, Dimes, Nickels, és fillérekért, a
legnagyobb érme a negyedévben.
Tehát megpróbáljuk használni őket először.
>> Vissza a 0,32 $.
Használható-negyed, hogy az ügyfél 0,32 $?
Igen.
Ez teret minket 0,07 $ maradt.
>> Használhatunk egy negyed?
Nem, mert a 25 nagyobb, mint hét.
Nem akarjuk, hogy az ügyfél többet, mint mi tartozunk nekik.
>> Rendben van.
Most, hogy már kimerítette a negyedévben, menjünk tovább a következő legnagyobb
érme, az érmét.
Tudunk egy érmét, hogy a ügyfél a 0,07 $ vissza?
Nem, mivel a 10 nagyobb, mint hét.
>> Tehát akkor a következő legnagyobb érme elérhető számunkra a nikkel.
Használhatjuk a nikkel?
Igen.
És akkor mi lenne 0,02 $ marad.
>> Azt nem tudja használni a nikkel return $ 0,02.
Így költözött az utolsó érme rendelkezésünkre áll - a penny.
És miután két pennyt, mi lenne maradt nulla cent, ami azt jelenti, hogy
már sikeresen fizetik vissza a felhasználó változásuk tartozott
amelyek csak négy érmét -
egynegyede, egy nikkel, és két fillérekért.
>> Futtathatja a személyzet megoldás, hogy ha az irányító a szabály és a folyamat adott
mi a helyes válasz.
A legtöbb probléma készletek, akkor képes lesz arra, futtatni a személyzet megoldás, hogy milyen
Saját program működik.
És adott utasítások lehet a probléma beállítja szemüveg.
>> Amint fut a személyzet megoldás, kéri tőlünk, hogy mennyi változás tartozott
ne feledje, hogy kéri a összege dollárban.
Mi input $ 0,32, 0,32.
Azt mondja, hogy a négy érmék tartozott, összhangban van a válasz.
Fantasztikus.
>> Tehát most kezdjük keres a végrehajtás
A mohó algoritmus.
Tudjuk, hogy egy-két dolgot.
Az egyik, hogy mi kell, hogy jelezzen a felhasználó olyan mértékű változás.
>> Kettő, hogy mi szeretnénk követni a irányadó szabály, hogy mindig a
legnagyobb érme lehetséges.
És a harmadik, hogy meg kell nyomon követni hány érmét használjuk.
Mert végül, meg kell nyomtatni száma az érmék, hogy mi is.
>> Először is, a felhasználó megkérdezése összegben a változás.
Amikor foglalkozik felhasználótól, hogy meg arról, hogy úgy gondolja, minden a
követelmények a bemenet, és csak akkor bevitel elfogadásához, amely megfelel azok
követelményeket.
Ebben az esetben szeretnénk foglalkozni a pénzbeli értékét dollárban.
>> A getFloat és getInt funkció biztosítja, hogy a bemenet numerikus.
De a felhasználó képes input negatív számértékek.
Úgy emlékszem, hogy csak a nem-negatív bemenet, amely magában foglalja az összes negatív
számok és a nulla.
>> Ebben az esetben, a bemeneti kell egy úszó.
Más szóval, egy decimális szám.
Mivel a probléma meg spec igényel , hogy kérjen be dollárban.
>> De a C, lebegőpontos értékek nem képviselteti magát pontosan.
Mert van egy véges számú bitek, amellyel
képviselnek végtelen értékeket.
Vegye ki a szám 0,1.
Ha megkérdezném, hogy írjon 0,1- kezét, hogy a századik tizedes
akkor írj egy 1, majd 99 nullák.
Azt várná, hogy a számítógép is nyomtassa ki pontosan ugyanaz a dolog
ha azt kérte, hogy.
>> Akkor lássuk, mit csinál.
Én felülvizsgálja nyomtatás értékek felé a végén ez a séta.
Most láthatjuk, hogy f%-a helyőrző helyett lebegőpontos.
De mi határozza meg előre, hogy mi szeretnénk 100 tizedes jelenik meg, majd az új
sor szebb formázás.
>> Után a húr, úgy döntünk, 0,1, mint a úszó, hogy szeretnénk kinyomtatni.
És az eredmény, egy, ezt követi néhány nullák, de aztán egy
csomó számot.
Természetesen nem a várt módon.
>> A lebegőpontos pontatlanság lehet bevezetni kerekítési hibák be a
számításokat, hogy lesz mindenképpen el akarja kerülni.
Ha szeretne többet látni példákat, akkor letölthető imprecision.ce a
séta kódot, amely egy egyszerű program, amely kéri úszó és kinyomtatja
vissza a századik tizedes.
Természetesen, ha meg akarja mutatni több vagy kevesebb tizedesjegy
meg tudod változtatni magát.
>> Mint látni fogod, bár ez a különbség a két kicsi, ha kap
kell szorozni, és hozzátéve, úszók, hogy a eltérés végül összeadódnak.
Vissza a Greedy.
Azt akarja, hogy ne a kerekítési hibák by foglalkozó egész számokkal.
Így aztán kapunk érvényes bemenet a felhasználó, nézzük konvertálni a
dollár értéket cent.
>> Szellemileg, mi ezt megszorozzuk A dollár értéke 100-zal.
De ne felejtsd el, mert a lebegőpontos pontatlanság, azt akarjuk, hogy
arról, hogy mi a megfelelő értéket.
Megszorozzuk 100 lényegében mozogni A tizedes két szünetet
jobb, darabolás le vagy csonkolt semmit utána.
>> Ha a játék körül néhány további példákat, látni fogja, hogy nem fogsz
Mindig megvan a megfelelő számot, ha használja ezt a módszert csonkolása.
Például, a nyomtatott 100 12.59 tizedes, hogy megadja neked
12,5899, et cetera.
Meg lennék 12,58 ha csonka, nem 12.59, mint amire szüksége van.
>> Ehelyett, a legjobb, ha kerek A szám első.
Szerencsére a C jön a nevű függvényt Round.
Ez a matematikai könyvtárral.
>> Ha meg szeretné tudni, hogyan kell használni Round, akkor hozza fel a kézi vagy
man oldal ezt a funkciót.
Ugye ezt írja az ember, rövid kézi, majd a funkció, amelyet
akarom nézni.
Így gépelés férfi körül a terminál parancs hozza létre a kézi.
>> Lehet, hogy egy kicsit nehéz megfejteni, de végül akkor
kap a nyitjára.
A Man megmutatja, mi a funkciója csinál, majd néhány
lehetséges felhasználásáról.
Elmegyek, hogy tárja fel a man oldalt Round.
De tudom, hogy tudod használni, hogy kerek az érték alatt konverzió
dollár cent.
>> Kerek kapsz vissza egy számot Az adattípus dupla.
És akkor konvertálni vagy öntött azt egy int utána.
Remek.
Mára már kéri a felhasználó a pénzösszeg, és a
át azt cent.
Most végre egy algoritmust hogy mindig használja a
legnagyobb rendelkezésre álló érmék.
>> Ne feledje, hogy van több módon végrehajtani Greedy, mint
van több módon megközelíteni Minden számítógép-tudomány problémát.
Megtalálni a legelegánsabb módja, ez a vicces rész.
Ezekben p-hoz, ha a program nem egyezik meg pontosan a
magyarázat a walkthroughs, ez rendben van.
De csak arról, hogy halad ellenőrzése 50, megfelel az összes
követelmények alkotják az előírásoknak, és hogy megvizsgálja, hogy a
megközelítés jó design.
>> Más szóval, mennyire hatékony ez?
Például, nem beírt ismétlődő kód vonalak használata helyett egy hurkot?
Írás kód jobb tervezési fog jön a tapasztalat, amit elért
át a kurzus.
>> Ehhez a séta, megyek át Két módon lehet használni, hogy
teljes mohó.
Az első módszer egy olyan módszer segítségével hurkok és kivonás.
Korábban, amikor beszélgettünk a Greedy folyamat, folyamatosan
ellenőrizte, hogy mi jönne egy negyedévben, és használt negyede, míg a
érték fennmaradó kevesebb, mint $ 0.25.
>> Ez fordítja jól a while ciklus szerkezete.
Miközben továbbra is használhatja egy negyed, egy.
Ez a while ciklus kell végrehajtani, amíg a fennmaradó érték nagyobb, mint
vagy egyenlő egy negyed hüvelyk os értékét.
Ez azt jelenti, hogy akkor is szeretné nyomon követheti a fennmaradó készpénz
érték, és frissíti azt minden idő, hogy egy pénzérme.
>> Ne feledje, hogy a végén, a kimenet az érmék számának használni.
Így egy másik dolog, hogy nyomon követni az számát érmék, hogy használja.
Lehet nyomon követni ezeket a jól megnevezett változókra.
És a testület a loop lenne egy frissítést, hogy azokat a változókat.
Ha a hurok negyedévben befejeződött, használhat egy hasonlót a Dimes,
és így tovább és így tovább, amíg meg már vissza az összes pénzt.
>> Írtam néhány pszeudo-kódot itt segítenek elképzelni, hogy milyen a
folyamat beszéltünk is lefordítani, hogy C. Amint látod itt, én még mindig használja
Angol szavakat.
Ez nem a C még.
De én már elkezdtem francia dolgokat.
Tettem teremt a belső terekben a zárójelben.
Ez kezd nézni egy kicsit Kicsit olyan, mint programkód.
>> Pszeudo-kód egy nagyszerű módja belekezdenie.
Képzeld el a kódot, mielőtt felnézel szintaxis.
Mivel gyakran a legnehezebb az egészben a probléma valóban megértenék, hogy mit
Pontosan meg kell csinálni.
Ha írsz, hogy le, akkor ez egy sokkal könnyebb felnéz funkciók
és szintaxis jellemző a vonal a pszeudo-kód
>> Ne feledje, hogy ez nem lehet azonos a fajta csontváz
A kód, amit írsz.
Mindig vannak optimalizálás kell tenni.
És különösen az én pszeudo-kód Itt nézd meg, hogy a helyszínen is.
>> De alapvetően a folyamat és a gondolkodás
ugyanolyan megbeszéltük.
Az első sor azt mondja számunkra, hogy egy bizonyos összeget dollárban.
És a másik azt mondja, hogy átalakítani, hogy cent.
>> És aztán, míg a negyedek lehet használni, akkor szeretnénk növelni az érme szám és
csökkenti a készpénz mennyiségét.
Ugyanez vonatkozik Dimes, Nickels, és fillérekért.
És végül, mondd el a felhasználó hány érmét szoktunk.
>> Remek.
Így arra a következtetésre jutott, hogy a hurok módszer.
Most beszéljünk a moduláris módszer, ami több, mint a megosztottság.
>> Mindannyian ismerjük a plusz, mínusz, szaporodnak, és oszd üzemeltetők
elérhető számunkra.
Mind a négy C-e, hanem A modulo operátor által képviselt
százalék jel.
Modulo nagyon szép.
Ez adja a fennmaradó részt elosztjuk a két számot.
>> Ne feledje, a hosszú divízió üzenetet, amikor osztja, mondjuk, 74 három?
Kezdve a tízes helyen, akkor tudják, hogy a 3 megy hét
kétszer, hogy a hat és fennmaradó egy.
Az ember azt írni két a tetején, majd a kivonni 6 hét, melyen több mint
a fennmaradó 14 ismételje meg a folyamatot.
>> Three megy 14-négyszer hogy a 12, a maradék kettő.
És a kettő nem jár át többé.
Tehát két maradna a alsó, mint a többi.
>> És ez az, amit modulo ad, akkor ez a szám az alján.
Tehát 74 modulo három adna nektek.
És 10 modulo két, jól, hogy adná meg nulla.
Mivel nincs olyan maradék ha osztani 10-kettő.
>> Six modulo öt, illetve öt megy hat egyszerre.
És akkor azt egy maradt.
Tehát hat modulo öt egy.
>> Akkor, ha van hét modulo kilenc, azt, hogy a hét.
Mivel a kilenc nagyobb, mint hét.
Tehát ez nem osztja meg minden hét, így hét, mint a válasz.
>> Ha úgy gondolja, a modulo egy kicsit, ne feledjük, hogy ez adja az
fennmaradó miután osztani valamit.
Gondolja át, hogyan lehet, hogy tudja használni a mohó.
Tegyük fel, hogy a felhasználó kéri a 400,11 $.
Mi a módja annak, hogy kitaláljuk, hogy hány negyedévben kell, anélkül, hogy
számít mindegyik?
>> Ha kitaláljuk, hogy sok helyen tudod használni, hogy a 400,11 $, mennyit
addig marad?
Talán kombinációja között itt modulo és osztás jönne
praktikus, hogy kapsz egy hűvös, elegáns megközelíteni a Greedy problémát.
De ne feledjük, hogy az irányító a szabály továbbra is érvényes.
Mindig a legnagyobb érme lehetséges.
>> Miután végzett a számítás, hogy milyen sok érme használható, az utolsó lépés
hogy nyomtassa ki a számát érmék, hogy számítani.
Eddig már használja a printf funkció kizárólag a szálakat.
De ha azt szeretné, hogy nyomtassa ki az A, vagy a akármilyen típusú adat, hogy a tárolt
egy változó, van, hogy jelzi hogy egy helyőrző.
>> Itt már bele néhány tipp hogyan kell kinyomtatni értékeket.
Ha van egy egész szám, akkor lenne írja meg karakterlánc a% d, mint a
helyőrző.
Miután a záró idézet jelet, adjon meg egy vessző.
És aztán az egész, hogy majd helyettesítheti a% d kinyomtatáskor.
>> Tehát megjelenítése után a szám érmék használt, akkor
végzett mohó.
Ügyeljen arra, hogy ellenőrizze az összes sarokba esetben, rendet a stílus egy kicsit, és máris
minden beállítva, hogy nyújtson be.
Végén ez a probléma meg, akkor jobban ismerik a CS50
készüléket, a terminál, és a hurok struktúrák és változók C.
>> Te is az utat.
A tanulási görbe tűnhet kemény.
Tehát hogy lépésről lépésre.
Győződjön meg róla, írja meg pszeudo-kód merülés előtt túl mély
be ismeretlen szintaxis.
>> Készíts egy teendők, és szakítani a hozzárendelés kisebb, könnyebben
kezelhető feladatokat.
Fedezze fel az összes CS50 források.
Amellett, hogy előadás, rewatch ez a séta.
>> Fordítson figyelmet a részt.
Nézd meg a rövidnadrág.
Olvassa el osztálytársai kérdéseire A Beszéljétek meg, és tegye a saját.
>> Sok szerencsét a p-set.
És köszönet néz.
Ez volt mohó.
>> [MUSIC Playing]