[Redare a muzicii] 

ZAMYLA CHAN: Acum, haideți să abordeze Greedy. Spune că ești un casier, și tu nevoie pentru a da dvs. de client un anumită cantitate de schimbare. Ei bine, dacă ați fost un casier lacomi, ai vrea să păstreze toate monedele pentru tine. Deci ai oferi clientului schimbarea lor folosind cât mai puține monede posibil. 

Sarcina ta pentru acest p-set este de a pune în aplicare Lacom, un program care calculează numărul minim de monede utilizate pentru a face orice având în vedere cantitatea de schimbare. Înainte de scufundare în programarea concepte și C sintaxa pentru Greedy, Să vorbim mai întâi prin Greedy programul, și să vedem dacă ne-am poate identifica un algoritm. Amintiți-vă că un algoritm este doar un set de instrucțiuni pentru rezolvarea problemelor. Un algoritm de lacomi ar fi doar o set de reguli logice și pașii pe care putem urmări. Și ei vor da întotdeauna minim număr de monede necesare. 

Primul lucru pe care ar trebui să știu este cât de mult schimbarea este datorată de client. Pentru acest exemplu, să spunem 0.32 dolari. Există mai multe modalități de a obține înapoi 0.32 dolari. Ai putea folosi, de exemplu, 32 mărunțiș. Sau dacă ai fost un pic lacom în alegerea monede tale, ai putea folosi cinci monede în loc de 32, oferindu- clientului de trei parale - 0.10 dolari fiecare - și doi bani - 0.01 dolari fiecare. 

Dar putem face mai bine decât cinci monede? Putem fi chiar lacomi? Destul de posibil. 

Să continua mersul pe jos prin programul Greedy, și a se vedea. În cazul în care obiectivul dvs. final este de a folosi câteva monede posibil, atunci ar fi cel mai prudent pentru a utiliza cea mai mare posibile monede. V-ar da mai degrabă un sfert spate - 0.25 dolari fiecare - mult de cinci monezi - 0.05 dolari fiecare. Deci, poate că regula noastră de conducere pentru Greedy poate fi de a utiliza întotdeauna cea mai mare monedă posibil. Din trimestre, Dimes, Nickels, și bani, nostru cea mai mare monedă este trimestru. Deci, vom încerca să le folosească în primul rând. 

Înapoi la nostru 0.32 dolari. Putem folosi un sfert pentru a da Clientul 0.32 dolari? Da. Care ne-ar lăsa cu 0.07 dolari la stânga. 

Putem folosi un alt sfert? Nu, pentru că 25 este mai mare de șapte. Noi nu vrem să dea clientului mai mult decât le datorăm. 

Bine. Acum, că ne-am epuizat sferturi noastre, Să trecem la cea mai mare următoare monedă, ban. Putem folosi un ban pentru a da clientul lor 0.07 dolari înapoi? Nu, deoarece 10 este mai mare de șapte. 

Deci, atunci cea mai mare următor moneda accesibil pentru noi este nichel. Putem folosi un nichel? Da. Și atunci vom avea 0.02 dolari la stânga peste. 

Nu putem folosi un nichel pentru a reveni 0.02 dolari. Deci, ne-am mutat ultima moneda la dispoziția noastră - penny. Și după utilizarea doi bani, am fi a plecat cu zero, de cenți, ceea ce înseamnă că ne-am achitat cu succes înapoi utilizatorul schimbare lor datorate folosind doar patru monede - sfert, unul nichel, și doi bani. 

Puteți rula soluția de personal pentru a vedea dacă regula nostru de guvernare și procesul de dat ne răspunsul corect. Pentru cele mai multe seturi de probleme, vei putea pentru a rula soluția de personal pentru a vedea cum propriul program ar trebui să funcționeze. Și instrucțiuni specifice vor fi în problema seturi specificatii. 

Odată ce vom rula soluția de personal, ea ne solicită cât de mult se datorează schimbare rețineți că aceasta cere Suma în dolari. Noi intrare 0.32 dolari, 0.32. Ea ne spune că patru monede sunt datorate, în concordanță cu răspunsul nostru. Fantastic. 

Deci, acum, să începem căutarea la punerea în aplicare algoritmului Greedy. Noi știm câteva lucruri. Unul, că vom avea nevoie pentru a solicita de utilizator pentru o sumă de schimbare. 

Două, că vom dori să urmeze nostru reglementează regulă să utilizați întotdeauna cea mai mare monedă posibil. Și trei, de care avem nevoie pentru a ține evidența de cât de multe monede le folosim. Pentru că în cele din urmă, avem nevoie pentru a imprima numărul de monede pe care le. 

În primul rând, fapt care ia determinat utilizatorul pentru o sumă de schimbare. Ori de câte ori te descurci cu datele introduse de utilizator, asigurați- sigur că te gândești la toate a Cerințe de intrare, și doar accepta de intrare care îndeplinește aceste cerințe. În acest caz, ne-am vrea să se ocupe cu o valoare monetară în dolari. 

Funcțiile GetFloat și getint asigura că intrarea este numeric. Dar utilizatorul este capabil să intrare Valorile numerice negativ. Deci, amintiți-vă să utilizați numai non-negativ intrări, care include toate negativ numere și de zero. 

În acest caz, intrarea ar trebui să fie un float. Cu alte cuvinte, un număr zecimal. Deoarece spec. set problemă necesită te pentru a cere intrarea în dolari. 

Dar în C, valori în virgulă mobilă nu se poate fi reprezentat cu precizie. Deoarece există un număr finit de biți cu care să reprezintă valori infinite. Ia numărul 0.1. Dacă ar fi să vă întreb pentru a scrie de 0,1 mână pentru a zecimală suta, v-ar scrie un 1, urmat de 99 de zerouri. Ne-am aștepta ca calculatorul nostru ar fi imprima exact același lucru dacă l-am cerut. 

Deci, haideți să vedem ce face. O să revizuiască valorile de imprimare față la sfârșitul acestei plimbare prin. Pentru moment, a se vedea aici că f% este o substituent pentru un virgulă mobilă. Dar am specifica dinainte că ne-o dorim 100 zecimale afișate, și apoi o nouă linie de formatare mai frumos. 

După șirul, alegem 0.1 ca float pe care dorim să imprimați. Iar rezultatul, unul, urmat prin niște zerouri, dar apoi o grămadă de numere. Desigur, nu cum era de așteptat. 

Virgulă mobilă imprecizie poate introduce rotunjire erori în dvs. calculele pe care le va cu siguranță doresc să evite. Dacă doriți să vedeți mai multe exemple, vă Puteți descărca imprecision.ce From plimbare prin cod, care este un simplu program care cere plutesc și se imprimă înapoi la zecimală suta. Desigur, dacă doriți să arate mai mult sau mai puțin zecimale vă puteți schimba. 

După cum veți vedea, deși diferența între cele două este mic, atunci când vei ajunge la multiplicarea și adăugarea de flotoare, care discrepanță poate adăuga în cele din urmă. Înapoi la Greedy. Vom dori, pentru a evita erorile de rotunjire de-a face cu numere întregi. Deci, după ce ne-am lua de intrare valabil de la utilizatorului, să transforme acest valoare dolar la cenți. 

Mental, vom face acest lucru prin înmulțirea valoarea de dolar de 100. Dar tine minte, din cauza virgulă mobilă imprecizie, dorim să facem sigur că suntem folosind dreptul de valoare. Înmulțind cu 100 se va deplasa, în esență, zecimală două spații pentru a dreapta, taind sau trunchierea nimic după aceea. 

Dacă joci în jurul cu unele mai mult exemple, veți vedea că nu veți Trebuie întotdeauna numărul corect, dacă utilizați această metodă de trunchiere. De exemplu, 12,59 imprimate la 100 zecimale, care vă oferă 12.5899, et cetera. Veți primi 12.58 dacă trunchiat, Nu 12,59, ca ai nevoie. 

În schimb, este mai bine pentru a rotunji numărul de primul. Din fericire, C vine cu functie numita Round. Este în biblioteca matematica. 

Dacă vrei să știi cum să folosească Round, atunci puteți aduce manualul sau pagina de manual pentru această funcție. Puteți face acest lucru prin tastarea om, pe termen scurt pentru manual, iar apoi funcția pe care o Vreau să te uiți în sus. Astfel tastarea în jurul omului în terminalul linie de comandă va aduce manual. 

Acesta ar putea fi un pic mai greu de descifrat, dar în cele din urmă veți te obișnuiești cu ea. Pagini man show vă ce funcția nu, și apoi unele posibile utilizări ale acestuia. Te las să exploreze pagina de manual pentru Runda. Dar știu că îl puteți folosi pentru a rotunji valoarea în timpul de conversie de la de dolari pentru a cenți. 

Runda va da înapoi un număr de tip de date dublă. Și puteți converti sau turnat l la un int ulterior. Mare. Până acum ne-am determinat utilizatorul pentru o sumă de bani, și convertit în cenți. Acum putem implementa un algoritm care utilizează întotdeauna mai mari de monede disponibile. 

Țineți minte că există multiple modalități de a pune în aplicare Greedy, la fel ca există mai multe modalități de abordare fiecare problemă de informatică. Găsirea modul cel mai elegant, asta e partea distractivă. De-a lungul aceste p-seturi, în cazul în care programul tău nu se potrivește exact mea explicație în walkthroughs, asta e OK. Dar asigurați-vă doar că trece verificați 50, satisface toate Cerințe forma caietul de sarcini, și care să ia în considerare dacă dumneavoastră abordare are un design bun. 

Cu alte cuvinte, cât de eficient este? De exemplu, ai de tip repetitiv linii de cod, în loc de a folosi o buclă? Scrierea de cod cu un design mai bine va fi vin experiență pe măsură ce progresezi prin curs. 

Pentru aceasta plimbare prin, voi trece peste două metode care pot fi utilizate pentru a finaliza Greedy. Prima metodă este o metodă care utilizează bucle și scădere. Mai devreme, când am vorbit prin Proces lacomi, ne continuu verificat dacă am putea folosi un sfert, și folosit un sfert până valoare rămasă a fost de mai puțin de 0.25 dolari. 

Acest lucru se traduce bine la o în timp ce structura de buclă. În timp ce noi putem folosi în continuare un sfert, utilizați una. Care buclă în timp ce ar trebui să execute cât timp ca valoarea rămasă este mai mare decât sau egal cu valoarea de un sfert de cent. Asta înseamnă că veți dori, de asemenea, să urmări de bani rămasă valoare, și o actualizează în fiecare timpul pe care îl utilizați o monedă. 

De asemenea, amintiți-vă că la sfârșitul anului, dvs. de ieșire este numărul de monede utilizate. Deci, un alt lucru pentru a urmări este numărul de monede pe care le utilizați. Puteți urmări aceste folosind bine numit-variabile. Și în corpul buclei dumneavoastră ar fi o actualizare a acestor variabile. Odată ce bucla de trimestru se termină, te se poate utiliza unul similar pentru Dimes, și așa mai departe și așa mai departe, până când le-ați întors toate de numerar. 

Am scris niște pseudo-cod aici pentru a vă ajuta să vizualizați cât de proces am discutat s-ar putea traduce în C. După cum vedeți aici, eu sunt încă utilizați Cuvinte în limba engleză. Nu este C încă. Dar am început să lucruri liniuță. Am pus condiții în interiorul paranteze mele. Este începe să arate un pic pic ca cod de programare. 

Pseudo-cod este o modalitate foarte bună pentru a te început. Vizualizați codul înainte te uiți în sus sintaxă. Deoarece de multe ori cea mai grea parte despre o problemă este înțelegerea cu adevărat ceea ce exact ce trebuie să faceți. Odată ce ați scrie asta, atunci este o mult mai ușor să se uite în sus funcțiile și sintaxa specifice pentru dvs. linie de pseudo-cod 

Țineți minte că acest lucru nu ar putea fi identic cu tipul de schelet de codul pe care îl scrie. Există întotdeauna optimizări să se facă. Și mai ales în mea pseudo-cod aici, vezi dacă poți să-l fața locului. 

Dar în esență, procesul și modul de gândire este la fel cum am discutat. Prima linie ne spune pentru a obține o anumită sumă în dolari. Iar al doilea ne spune să converti de cenți. 

Apoi, în timp sferturi pot fi folosite, vom doresc să crească numărul de monede și reduce cantitatea de numerar. Același lucru este valabil pentru Dimes, monezi, și mărunțiș. Și, în sfârșit, ne spune utilizatorului cât de multe monede am folosit. 

Mare. Astfel că încheie metoda de buclă. Acum hai sa vorbim despre metoda modular, care este mai mult ca divizie. 

Suntem familiarizați cu toate plus, minus, înmulțesc și împart operatorii disponibile pentru noi. C are toate cele patru cele, dar are operatorul modulo, reprezentat printr-un la sută semn. Modulo este foarte elegant. Acesta vă oferă restul de la împărțind două numere. 

Amintiți-vă mesajul divizie lung, atunci când împărțiți, să zicem, 74 de trei? Începând cu locul zeci, te-ar Știu că 3 intră în șapte de două ori pentru a face un șase cu rest unul. Te-ai scrie două în partea de sus, și apoi scade 6 din șapte, care transportă peste restul de 14 la repeta procesul. 

Trei merge în 14 de patru ori la face 12, cu rest doi. Și doi nu mai reporta. Deci, doi s-ar fi lăsat la de jos ca restul. 

Și asta e ceea ce dă modulo, te ca număr în partea de jos. Deci, 74 modulo trei s-ar da doi. Și 10 modulo doi, bine că s-ar da la zero. Deoarece nu există nici un rest atunci când vă împărțiți 10 de două. 

Șase modulo cinci, bine cinci merge în șase dată. Și apoi a lăsat-o peste. Deci, șase modulo cinci este unul. 

Apoi, dacă aveți șapte modulo nouă, veți primi șapte. Pentru că nouă este mai mare decât șapte. Deci, nu toate împărți în șapte, lăsând șapte ca răspunsul dumneavoastră. 

Dacă te gândești la modulo un pic mai mult, amintiți-vă că vă dă restul după ce împărți ceva. Gândiți-vă cum s-ar putea fi capabil să-l folosească în Greedy. Să presupunem că utilizatorul cere pentru 400.11 dolari. Ce este o modalitate de a da seama cât de multe sferturi de care aveți nevoie, fără a fi nevoie să conta fiecare unul? 

Odată ce îți dai seama cât de multe trimestre puteți folosi pentru a face 400.11 dolari, cât de mult schimba rămâne? Poate că o combinație între aici modulo și divizare ar veni în la îndemână pentru a vă oferi o rece, elegant abordare a problemei Greedy. Dar amintiți-vă că guvernarea regulă se aplică în continuare. Folosiți întotdeauna cea mai mare moneda posibil. 

Odată ce ați făcut calculul de modul în care multe monede de a utiliza, ultimul pas este de a imprima numărul de monede pe care le calculate. Până în prezent, am fost folosind printf funcționeze exclusiv pentru siruri de caractere. Dar, atunci când doriți să imprimați o în, sau orice fel de tip de date care este stocat într-o variabilă, trebuie să indice că folosind un substituent. 

Aici am inclus doar câteva sfaturi cu privire la modul de a imprima valori. Dacă aveți un întreg, v-ar scrie șir folosind% d ca o înlocuitor. După ce cotația de închidere marca, introduceți o virgulă. Și a pus apoi în întreg care va să ia locul de% d, atunci când tipărite. 

Deci, după afișarea numărului de monede utilizate, esti a terminat cu Greedy. Asigurați-vă că pentru a verifica toate cazurile de colt, curețe stilul tau un pic, și tu ești gata să-și prezinte. La sfârșitul acestui set de probleme, veți fi mult mai familiarizați cu CS50 aparat, terminalul, și bucla structuri și variabile în C. 

Ești pe drumul cel bun. Curba de învățare poate părea greu. Deci, ia-o pas cu pas. Asigurați-vă că scrie în pseudo-cod înainte de scufundare prea adânc în sintaxa necunoscut. 

Face-o pentru a face lista, și te desparți de cesiune în mai mici, mai sarcini de gestionat. Explorați toate resursele CS50. În plus față de curs, rewatch această plimbare prin. 

Să acorde o atenție aproape de secțiune. A verifica afară de pantaloni scurți. Citiți întrebările colegii dumneavoastră " pe Discutați, și posta ta. 

Cel mai bun de noroc cu p-set. Și mulțumiri pentru vizionarea. Acest lucru a fost Greedy. 

[Redare a muzicii]