>> [MUSIC PLAYBACK]
>> ZAMYLA CHAN: Teraz poďme riešiť Greedy.
Povedzme, že ste pokladničné, a Potrebujete, aby vaše zákazníkovi
určité množstvo zmien.
No, ak ste boli chamtiví pokladničné, by ste chceli, aby všetky
mince pre seba.
Takže by ste dať zákazníkovi ich zmeny za použitia niekoľkých mincí, ako je to možné.
>> Vašou úlohou v tomto p-set je realizovať Greedy, program, ktorý
vypočíta minimálny počet mincí použitých k akejkoľvek
vzhľadom na množstvo zmien.
Než sa ponoríme do programovania koncepty a C syntaxe pre Greedy,
Poďme hovoriť cez Greedy programu, a uvidíme, či nám
môže identifikovať algoritmus.
Pamätajte si, že algoritmus je len sada
pokyny pre riešenie problémov.
Algoritmus pre Greedy by byť len súbor logických pravidiel, a kroky, ktoré
môžeme sledovať.
A vždy získa minimálne počet mincí potrebných.
>> Prvá vec, ktorú si musíte vedieť, ako veľa zmien
je voči zákazníkovi.
V tomto príklade, povedzme 0,32 dolár.
Existuje mnoho spôsobov, ako sa dostať späť 0,32 doláre.
Dalo by sa použiť, napríklad, 32 halierov.
Alebo, ak ste boli trochu greedier v výber mincí, môžete použiť
päť mincí namiesto 32 tým, že zákazníkov tri desaťhalierniky -
0,10 dolár každý - a dva haliere - 0,01 dolár každý.
>> Ale môžeme robiť lepšie než päť mincí?
Môžeme byť aj greedier?
Dosť možno.
>> Poďme pokračovať v prechádzke Greedy programu, a uvidíte.
Ak je váš konečný cieľ je použiť niekoľko mincí ako je to možné, potom by bolo najviac
rozumné použiť najväčšie Možné mince.
Radšej dať štvrtiny back - 0,25 dolár každý -
ako päť Nickels -
0,05 dolár každý.
Tak snáď naše riadiace pravidlo pre Greedy môže byť vždy
najväčší mince je to možné.
Z štvrťroku, desetníky, Nickels, a haliere, naše
najväčší mince je štvrťrok.
Takže sa budeme snažiť, aby im najprv použiť.
>> Späť k nášmu 0,32 doláre.
Môžeme použiť štvrtinu, aby zákazník 0,32 dolár?
Áno.
To by nás nechať s 0,07 dolárov odišiel.
>> Môžeme použiť iný štvrtinu?
Nie, pretože 25 je väčší ako sedem.
Nechceme, aby zákazníkovi nič viac, než sme im dlhujeme.
>> Dobrá.
Teraz, keď sme vyčerpali naše ubikácie, poďme sa presunúť na ďalšie najväčšie
mince, desetník.
Môžeme použiť desetník, aby zákazník ich 0,07 dolár späť?
Nie, pretože 10 je väčší ako sedem.
>> Takže budúci najväčší mince prístupné pre nás je nikel.
Môžeme použiť nikel?
Áno.
A potom by sme museli 0,02 dolárov zostane.
>> Nemôžeme použiť nikel na return $ 0,02.
Tak sme sa presťahovali poslednú mincu na ktoré máme k dispozícii - penny.
A potom, čo pomocou dvoch haliere, boli by sme odišiel s nulovými centov, čo znamená, že
sme úspešne splatená užívateľ ich zmeny dlžný
s použitím iba štyri mince -
jedna štvrtina, jedna nikel, a dva haliere.
>> Môžete spustiť riešenie zamestnanca, či naše riadiace pravidlo a proces dal
nám správnu odpoveď.
Pre väčšinu problémových sád, budete môcť spustiť riešenie zamestnanca, ako
svoj vlastný program by mal fungovať.
A zvláštne pokyny budú byť problém zavádza špecifikácie.
>> Potom, čo sme sa spustiť riešenie zamestnancov, je vyzve nás, koľko zmena dlhuje
na vedomie, že sa spýta na Čiastka v dolároch.
Sme vstup 0,32 dolár, 0.32.
To nám hovorí, že štyri mince dlhuje, v súlade s našou odpoveďou.
Fantastic.
>> Takže teraz poďme začať hľadať pri vykonávaní
z Greedy algoritmus.
Vieme, že pár vecí.
Jeden, že budeme musieť vyzvať užívateľ vo výške zmeny.
>> Dva, že budeme chcieť, aby sa riadili upravujúce pravidlá pre vždy
najväčší mince je to možné.
A za tretie, že musíme sledovať na to, koľko mincí sa použiť.
Pretože nakoniec, musíme vytlačiť počet mincí, ktoré nám.
>> Po prvé, pobádať užívateľa vo výške zmeny.
Kedykoľvek budete riešiť vstup užívateľa, aby Uistite sa, že si myslíte, že všetky
požiadavky na vstup a iba prijímať vstup, ktorý spĺňa tie
požiadavky.
V tomto prípade, chceme zaoberať peňažnú hodnotu v dolároch.
>> Funkcie GetFloat a vezmi_int zabezpečiť že vstup je číselná.
Avšak užívateľ môže zadať záporné číselné hodnoty.
Takže nezabudnite používať iba nezáporné vstupy, ktoré zahŕňa všetky negatívne
čísla a nula.
>> V tomto prípade, je vstupné by mala byť float.
Inými slovami, desatinné číslo.
Pretože problém sada spec vyžaduje môžete požiadať o vstup v dolároch.
>> Ale v C, možno hodnoty desatinných nie byť zastúpené presne.
Pretože existuje konečný počet bitov, s ktorým
predstavujú nekonečné hodnoty.
Vezmite číslo 0,1.
Keby som sa vás spýtal, písať o 0,1 ruka sté desatinné miesto,
by ste napísať 1, nasledoval od 99 nulami.
Mali by sme očakávať, že náš počítač by vytlačiť presne to isté
ak sme požiadali ho.
>> Takže poďme sa pozrieť, čo to robí.
Budem preskúmanie tlač hodnôt na Koniec to prejsť.
Pre túto chvíľu, vidieť, že f% je zástupný symbol pre plávajúcou desatinnou čiarkou.
Ale určiť vopred, že chceme Zobrazené 100 desatinné miesta, a potom nový
linka pre krajší formátovania.
>> Po reťazca, volíme 0,1 as vznášať sa, že chceme vytlačiť.
A výsledok, jeden, nasledoval niektorými nulami, ale potom
Celá banda čísel.
Určite nie, ako sa očakávalo.
>> Plávajúce bod nepresnosť môže zaviesť chyby zaokrúhlenia do svojej
výpočty, ktoré budete určite chcieť, aby sa zabránilo.
Ak chcete vidieť viac príkladov, vám si môžete stiahnuť imprecision.ce od
prejsť kód, ktorý je jednoduchý program, ktorý sa spýta plávať a vytlačí ho
späť na sté desatinné miesto.
Samozrejme, ak chcete zobraziť viac či menej desatinných miest
si sami môžete meniť.
>> Ako uvidíte, aj keď rozdiel medzi nimi je malá, keď sa dostanete
násobenie a pridanie plaváky, ktoré Nesúlad môže nakoniec pridať až.
Zálohovanie na Greedy.
Budeme chcieť, aby sa zabránilo chybám zaokrúhľovania o nakladaní s celými číslami.
Takže potom, čo sme si platný vstup z užívateľ, poďme zmeniť toto
dolár hodnotu centov.
>> Mentálne, robíme to vynásobením hodnota dolára o 100.
Ale pamätajte si, pretože s plávajúcou desatinnou čiarkou nepresnosť, chceme, aby
Uistite sa, že budeme používať správnu hodnotu.
Vynásobením 100 sa v podstate pohybovať desatinné miesto dve medzery na
právo, sekanie preč, alebo skrátenie niečo neskôr.
>> Ak budete hrať si s niektorými viac príklady, uvidíte, že nebudete
ak ste vždy správne číslo použiť tento spôsob skrátenia.
Napríklad, 12,59 vytlačená na 100 desatinných miest, ktoré vám umožnia
12,5899, et cetera.
Vy by ste sa 12,58, ak skrátený, nie 12.59, ako budete potrebovať.
>> Namiesto toho, to je najlepšie na bicykli číslo prvý.
Našťastie, C je dodávaný s funkcia tzv Round.
Je to v matematickej knižnici.
>> Ak chcete vedieť, ako používať bicykel, potom si môžete priniesť až naávod alebo
man stránka pre túto funkciu.
Môžete to urobiť tým, písanie človeka, krátky pre manuál, a potom funkciu, ktorú
chcete vyhľadať.
Takže písanie muž koleso do terminálu Príkazový riadok bude vychovávať manuál.
>> To by mohlo byť trochu ťažké rozlúštiť, ale nakoniec budete
dostať na kĺb.
Manuálové stránky ukázať, čo funkciu áno, a ešte niečo navyše
Možné využitie toho.
Nechám vás, aby preskúmala muž stránka pre bicykle.
Ale viete, že môžete použiť na zaokrúhlenie hodnota pri svojom obrátení od
dolárov centov.
>> Kolo vám späť číslo dátového typu double.
A môžete previesť alebo obsadenia to int potom.
Skvelé.
Do teraz sme vyzvaní užívateľa pre peňažná suma, a
prevedie do centov.
Teraz môžeme implementovať algoritmus že vždy používa
Najväčší mince k dispozícii.
>> Majte na pamäti, že existuje viac spôsoby, ako implementovať Greedy, rovnako ako
existuje niekoľko spôsobov, ako pristupovať každý problém počítačová veda.
Nájdenie najelegantnejší spôsob, To je tá zábavná časť.
V priebehu týchto p-sád, ak váš program presne nezodpovedá my
vysvetlenie v návodoch, to je v poriadku.
Ale len uistiť, že to prejde skontrolovať 50, spĺňa všetky
požiadavky sú špecifikácie, a že zváži, či vaše
prístup má dobrý dizajn.
>> Inými slovami, ako efektívne je to?
Napríklad, ste typ opakujúce sa riadky kódu, namiesto použitia slučky?
Písania kódu s lepším dizajnom bude príde skúsenosti, ako budete postupovať
prostredníctvom kurzu.
>> Za týmto prejsť, pôjdem cez Dve metódy, ktoré môžu byť použité pre
kompletné Greedy.
Prvá metóda je metóda využívajúca slučky a odčítanie.
Predtým, keď sme spolu hovorili cez Greedy proces, neustále
Kontroluje sa, či by sme mohli použiť štvrtinu, a používa štvrtina až
zostávajúca hodnota bola menšia ako 0,25 $.
>> To sa premieta aj do zatiaľ čo štruktúra slučky.
Aj keď stále ešte môžeme použiť štvrť, použite jednu.
Že kým slučka by mala vykonávať tak dlho, ako zostávajúca hodnota je vyššia ako
alebo rovná cent hodnoty štvrtina je.
To znamená, že budete tiež chcieť, aby sledovať zostávajúce hotovosť
hodnotu, a aktualizovať každý čas, ktorý môžete použiť mincu.
>> Tiež si pamätám, že na konci svojho Výstupom je počet použitých mincí.
Takže ďalšia vec, sledovať je počet mincí, ktoré používate.
Môžete sledovať z nich pomocou dobre-menovaný premenné.
A v tele vašej slučky by bude aktualizácia týchto premenných.
Akonáhle sa slučka pre štvrťrok skončí, vás Môžete použiť nejaký podobný pre desaťhalierniky,
a tak ďalej a tak ďalej, kým ste vrátila všetky peniaze.
>> Napísal som nejaký pseudo-kód tu vám pomôže predstaviť, ako
Proces sme diskutovali môže prekladať C. Ako vidíte tu, som stále používate
Anglické slová.
Nie je C doteraz.
Ale ja som začal odsadenie veci.
Ja som dal podmienky vo vnútri moje zátvorky.
Už to začína vyzerať trochu Trochu ako programový kód.
>> Pseudo-kód je skvelý spôsob, aby si sami začali.
Vizualizácia kódu pred sa pozriete do syntaxe.
Pretože často najťažšie časť o Problém je skutočne porozumieť tomu, čo
presne, čo musíte urobiť.
Akonáhle si to zapísať, potom je to oveľa ľahšie vyhľadať funkcií
a syntax sú špecifické pre vašu rad pseudo-kódu
>> Majte na pamäti, že to nemusí byť totožný s druhom kostry
Váš kód, ktorý napíšete.
Tam sú vždy optimalizácia ktoré majú byť vykonané.
A to najmä v mojom pseudo-kódu tu, uvidíme, či si môžete na mieste ju.
>> Ale v podstate proces a spôsob myslenia
je, rovnako ako sme sa bavili.
Prvý riadok nám hovorí, aby sme získali určitá čiastka v dolároch.
A druhá hovorí, aby previesť na centy.
>> A potom, zatiaľ čo štvrtiny môžu byť použité, sa Chcete zvýšiť počet mincí a
znížiť sumu hotovosti.
To isté platí aj pre desaťhalierniky, Nickels, a haliere.
A konečne, povieme užívateľovi koľko mincí sa použiť.
>> Skvelé.
Tak, že dospel k záveru metódu slučky.
Teraz poďme hovoriť o stavebnicové metódy, čo je viac ako divízia.
>> My všetci sme oboznámení s plus, mínus, násobenie a delenie operátormi
ktoré máme k dispozícii.
C má všetky štyri tie, ale aj operátor modulo, zastúpená
znak percenta.
Modulo je naozaj čistý.
To vám dáva zvyšok z delenie dvoch čísel.
>> Spomeňte si na dlhú divízie správu pri rozdeliť, povedzme, 74 o tri?
Počnúc mieste desiatok, mali by ste viem, že 3 ide do siedmich
dvakrát, aby sa šesť s Zostávajúce jedna.
By ste napísať dva hore, a potom odpočítať 6 zo siedmich, nosenie cez
Zvyšok dňa 14. pre proces opakovať.
>> Tri ide do 14 štyrikrát do aby 12 sa zostávajúce dva.
A dva nenesie nad už.
Takže dva by byť ponechané na dno ako zvyšok.
>> A to je to, čo modulo dáva, si toto číslo v dolnej časti.
Takže 74 modulo tri by vám dve.
A 10 modulo dva, dobre, že by vám nulu.
Vzhľadom k tomu, že nie je žiadny zvyšok keď delíte 10 dva.
>> Šesť modulo päť, a päť ide do šiestich raz.
A potom to jeden zostane.
Takže šesť modulo päť je jeden.
>> Potom, ak máte sedem modulo deväť, mali by ste mať sedem.
Vzhľadom k tomu, deväť je väčšia ako sedem.
Takže to nie je rozdeliť to všetko do siedmich, takže sedem ako odpoveď.
>> Ak si myslíte, že o modulo trochu viac, nezabudnite, že vám dáva
zvyšok po delení niečo.
Premýšľajte o tom, ako by mohli byť ho používať v Greedy.
Povedzme, že užívateľ požiada o 400,11 dolárov.
Čo je to spôsob, ako zistiť, koľko štvrťroku, ktoré potrebujete, bez toho aby ste museli
počítať každý z nich?
>> Potom, čo ste zistili, koľko štvrtiny môžete použiť, aby 400,11 dolárov, koľko
zmeniť ostatky?
Možná kombinácia tu medzi modulo a rozdelenie by sa v
užitočné, aby vám v pohode, elegantný prístup k Greedy problému.
Ale pamätajte, že riadiaci pravidlo stále platí.
Vždy používajte najväčšiu mincu je to možné.
>> Potom, čo ste urobil pre výpočet, ako najviac mincí použiť, posledný krok
je vytlačiť počtu mince, ktoré ste vypočítané.
Zatiaľ sme sa pomocou printf fungovať iba pre reťazca.
Ale keď chcete vytlačiť in, alebo proste akýkoľvek typ dát, ktorý je uložený
do premennej, musíte uviesť že pomocou zástupného symbolu.
>> Tu som zahrnuté iba niektoré tipy o tom, ako vytlačiť hodnoty.
Ak máte celé číslo, by ste napíšte reťazec pomocou% d ako
zástupný symbol.
Po záverečnej kotácie značka, zadajte čiarku.
A potom sa dal do celé číslo, ktoré bude sa namiesto% d pri tlači von.
>> Takže po zobrazení čísla použitých mince, ty si
skončil s Greedy.
Uistite sa, že kontrolu všetkých rohových prípady, upratať váš štýl trochu, a vy ste
všetko nastavené, aby predložila.
Na konci tohto problému nastavenie, budete si musieť vybrať byť oboznámení s CS50
zariadenie, terminál, a slučka štruktúry a premenné v C
>> Ste na dobrej ceste.
Krivka učenia môže zdať ťažké.
Takže to brať krok za krokom.
Uistite sa, že píšete z pseudo-kódu Pred potápanie príliš hlboko
do neznámej syntaxe.
>> Urobiť zoznam úloh, a rozbiť priradenie do menšej,
zvládnuteľné úlohy.
Preskúmajte všetky CS50 zdrojov.
Okrem prednášky, rewatch to prejsť.
>> Venujte pozornosť kapitole.
Pozrite sa na šortky.
Prečítajte si otázky svojimi spolužiakmi " na Diskutujte a zverejňovať vlastné.
>> Veľa šťastia s p-set.
A vďaka za sledovanie.
To bolo Greedy.
>> [MUSIC PLAYBACK]