>> [REPRODUCCIÓ DE MÚSICA]
>> ZAMYLA CHAN: Ara abordarem cobdiciós.
Diguem que vostè és un caixer, i vostè necessitar donar al seu client un
certa quantitat de canvis.
Bé, si vostè fos un caixer cobdiciós, t'agradaria mantenir tots
les monedes a tu mateix.
Així que li donaria al client el seu canvi utilitzant el mínim de monedes com sigui possible.
>> La seva tasca en aquest joc de p-és implementar Greedy, un programa que
calcula el nombre mínim de les monedes que s'utilitzen per realitzar qualsevol
determinada quantitat de canvi.
Abans de capbussar-se en la programació conceptes i la sintaxi de C per Greedy,
Primer parlem a través de la Greedy programa, i veure si podem
pot identificar un algorisme.
Recordeu que un algorisme és només un conjunt de
instruccions per a la solució de problemes.
Un algorisme per Greedy no seria més que una un conjunt de regles i passos lògics que
podem seguir.
I ells sempre van a donar el mínim nombre de monedes necessàries.
>> El primer que havia necessitat de saber és quant canvi
es deu al client.
Per a aquest exemple, diguem que 0,32 $.
Hi ha moltes maneres d'obtenir una còpia de $ 0,32.
Vostè podria utilitzar, per exemple, 32 centaus.
O si, estaves una mica cobdiciós en l'elecció de les seves monedes, es pot utilitzar
05:00 monedes en lloc de 32 per donant client 3 monedes de deu centaus -
Cadascun $ 0,10 - i dues monedes d'un cèntim - 0,01 $ cada un.
>> Però, podem fer alguna cosa millor que 5 monedes?
Podem ser encara més cobdiciosos?
És molt possible.
>> Seguim caminant per el programa cobdiciós, i veure.
Si el seu objectiu final és utilitzar unes monedes com sigui possible, llavors seria més
prudent utilitzar la més gran possibles monedes.
Prefereix donar una quarta còpia - $ 0,25 cada un -
de cinc centaus -
0,05 $ cada un.
Així que potser la nostra regla de govern per Greedy pot haver d'utilitzar sempre el
moneda més gran possible.
Fora de quarts, monedes de deu centaus, cinc centaus, i monedes d'un cèntim, el nostre
la moneda més gran és el trimestre.
Així que anem a tractar d'usar ells primer.
>> De tornada al nostre $ 0,32.
Podem utilitzar una cambra per donar el client $ 0,32?
Sí
Això ens deixa amb 0,07 $ a l'esquerra.
>> Podem utilitzar un altre quart?
No, perquè 25 és més gran que 7.
No volem donar al client més del que els devem.
>> Està bé.
Ara que hem esgotat els nostres barris, anem a passar a la següent més gran
moneda, la moneda de deu centaus.
Podem utilitzar una moneda de deu centaus per donar la client el seu 0,07 $ de tornada?
No, ja que 10 és més gran que 7.
>> Així que la moneda més gran següent accessible per a nosaltres és el níquel.
Podem utilitzar una moneda?
Sí
I llavors hauríem $ 0,02 sobra.
>> No podem fer servir una moneda per tornar 0,02 $.
Així que ens vam canviar l'última moneda a nostra disposició - el darrer cèntim.
I després d'usar dues monedes d'un cèntim, estaríem esquerra amb zero centaus, el que significa que
hem pagat amb èxit de nou l'usuari el seu canvi havia
utilitzant només quatre monedes -
quart, un níquel, i dues monedes d'un cèntim.
>> Podeu executar la solució personal per veure si nostra regla de govern i el procés van donar
nosaltres la resposta correcta.
Per a la majoria dels butlletins de problemes, vostè serà capaç de per executar la solució personal per veure com
el seu propi programa funcionarà.
I les instruccions específiques es estar al problema estableix especificacions.
>> Quan es corre la solució personal, és ens impulsa a què es deu tant canvi
tingui en compte que sol · licita la Suma en dòlars.
Nosaltres d'entrada $ 0,32, 0.32.
Ens diu que 4 monedes se'ls deu, coherent amb la nostra resposta.
Fantàstic.
>> Així que ara anem a començar mirant en la implementació
l'algorisme cobdiciós.
Sabem que un parell de coses.
Un, que necessitarem per sol · licitar al usuari per a una quantitat de canvi.
>> Dos, que anem a voler seguir el nostre que regeix la regla d'utilitzar sempre el
moneda més gran possible.
I tres, que necessitem per realitzar un seguiment de quantes monedes que fem servir.
Com que, finalment, hem de imprimir el nombre de monedes que tenim.
>> En primer lloc, preguntar a l'usuari per un import de canvi.
Cada vegada que s'ocupa de la entrada de l'usuari, assegureu-vos Segur que vostè pensa en tota la
requisits de l'entrada, i només acceptar l'entrada que compleix amb els
requisits.
En aquest cas, volem fer front a un valor monetari en dòlars.
>> Les funcions getFloat i getInt asseguren que l'entrada és numèric.
Però l'usuari és capaç d'introduir els valors numèrics negatius.
Així que recordi utilitzar només no negatiu entrades, el que inclou tots negatius
números i el zero.
>> En aquest cas, l'entrada ha de ser un flotador.
En altres paraules, un nombre decimal.
Com que el conjunt d'especificacions problema requereix que demani per a l'entrada en dòlars.
>> Però en C, els valors de punt flotant no pot són representats amb precisió.
Com que hi ha un nombre finit de bits amb el qual
representar valors infinits.
Prengui el nombre 0.1.
Si hagués de demanar-li que escrigui 0,1 per mà a la posició decimal centèsima,
que anava a escriure un 1, seguit per 99 zeros.
És d'esperar que el nostre equip ho faria imprimir exactament el mateix
si demanem que ho faci.
>> Així que anem a veure el que fa.
Vaig a revisar els paràmetres d'impressió cap Al final d'aquest passeig per.
Per ara, veiem aquí que f% és una marcador de posició per a un punt flotant.
Però s'especifica per endavant que volem 100 decimals que apareixen, i després una nova
línia per al format més agradable.
>> Després de la cadena, triem 0,1 com surem que volem imprimir.
I el resultat, un u, seguit per alguns zeros, però llavors un
Tot munt de nombres.
Per descomptat, no com s'esperava.
>> Punt flotant imprecisió pot introduir errors d'arrodoniment en la seva
càlculs que es vol definitivament vol evitar.
Si vols veure més exemples, pot descarregar des del imprecision.ce
caminar a través de codi, que és un simple programa que demani surar i l'imprimeix
de nou a la posició decimal centèsima.
Per descomptat, si vostè vol mostrar més o menys decimals
pot canviar-se a si mateix.
>> Com veuràs, tot i que la diferència entre els dos és petit, quan arribi
per a la multiplicació i l'addició de flotadors, que discrepància amb el temps es van acumulant.
Retorn a la cobdiciosa.
Anem a voler evitar errors d'arrodoniment en tractar amb nombres enters.
Així que després de rebre una entrada vàlida de l'usuari, convertirem aquest
Valor en dòlars a centaus.
>> Mentalment, ho fem multiplicant el valor en dòlars per 100.
Però recordeu, a causa de coma flotant imprecisió, volem fer
assegurar-nos que estem utilitzant el valor correcte.
Multiplicar per 100 serà essencialment moure del punt decimal dos espais a
la dreta, tallant o truncant res després.
>> Si jugues una mica amb una mica més de exemples, veurà que no podrà
Sempre tenim el nombre correcte si utilitzar aquest mètode de truncar.
Per exemple, 12,59 imprès a 100 decimals, que li dóna
12.5899, etcètera.
Obtindria 12,58 si truncat, no 12.59, igual que vostè necessita.
>> En lloc d'això, el millor és per arrodonir el nombre primer.
Afortunadament, C ve amb el funció anomenada Ronda.
Està a la biblioteca matemàtica.
>> Si vostè vol saber com utilitzar Ronda, a continuació, pot obrir el manual o
pàgina de manual per a aquesta funció.
Això es fa escrivint man, curtcircuit per manual, i la funció que
vulgueu cercar.
Així que escriure tot l'home a la terminal línia d'ordres s'obrirà el manual.
>> Pot ser que sigui una mica difícil de desxifrar, però el temps et
aconseguir la caiguda d'ella.
Les pàgines de manual li mostren el que la funció fa, i una mica més
possibles usos de la mateixa.
Els deixo per explorar la pàgina del manual per a la Ronda.
Però saps que pots usar-lo per arrodonir el valor durant la seva conversió de
dòlars a centaus.
>> Ronda li va a tornar un nombre del tipus de dades doble.
I es pot convertir o fos a un int després.
Gran.
Per ara hem sol · licita a l'usuari per una quantia monetària, i
el va convertir en centaus.
Ara podem implementar un algorisme que utilitza sempre el
majors monedes disponibles.
>> Tingueu en compte que hi ha múltiples formes d'implementar cobdiciós, igual que
hi ha diverses maneres d'apropar-se tots els problemes de la informàtica.
Trobar la forma més elegant, aquesta és la part divertida.
Al llarg d'aquests p-sèries, si el seu programa no coincideix exactament el meu
explicació en els tutorials, això està bé.
Però només assegureu-vos que el seu pas comprovar 50, respon a tots els
prescripcions constitueixen les especificacions, i que té en compte si el
enfocament té un bon disseny.
>> En altres paraules, què tan eficient és?
Per exemple, sabia vostè mecanografia repetitiva línies de codi, en lloc d'utilitzar un bucle?
Escriure codi amb un millor disseny serà vingui a experimentar a mesura que avança
a través del curs.
>> Per a aquest passeig a través, vaig a anar més dos mètodes que es poden utilitzar per
completar cobdiciós.
El primer mètode és un mètode que utilitza bucles i la resta.
Abans, quan parlem a través de la Procés Greedy, contínuament
comprovem si podríem utilitzar un trimestre, i utilitzat quart fins que el
valor restant era menys de $ 0,25.
>> Això es tradueix bé a una mentre que l'estructura de bucle.
Tot i que encara podem utilitzar quart, utilitzeu un.
Aquest bucle while ha d'executar sempre com el valor restant és més gran que
o igual al valor cent vint centaus.
Això significa que vostè també voldrà no perdre de vista els diners restant
valor, i actualitzar cada vegada que utilitzi una moneda.
>> Així mateix, recorda que, al final, la seva la sortida és el nombre de monedes utilitzades.
Així que una altra cosa per no perdre de vista és el nombre de monedes que s'utilitzen.
Pot fer un seguiment d'ells utilitzant ben anomenada variables.
I dins del cos del seu llaç faria ser una actualització d'aquestes variables.
Una vegada que el bucle de trimestre acabi, pot utilitzar una similar per dimes,
i així successivament i així successivament, fins que hagi retornat tots els diners en efectiu.
>> He escrit alguns pseudo-codi per ajudar a visualitzar com el
procés ja vam comentar es podria traduir en C. Com es veu aquí, encara estic fent servir
Les paraules en anglès.
Encara no és C.
Però he començat a coses de sangria.
He posat dins de les condicions meus parèntesi.
Està començant a veure una mica cosa així com el codi de programació.
>> Pseudocodi és una gran manera per aconseguir començat.
Visualitza el teu codi abans de vostè mira cap amunt de sintaxi.
Perquè sovint la part més difícil d'un problema és realment la comprensió del
exactament el que heu de fer.
Una vegada que vostè escriu que cap avall, llavors és una molt més fàcil per buscar les funcions
i la sintaxi específica del seu línia de pseudo-codi
>> Tingueu en compte que això podria no ser idèntica a la classe d'esquelet de
el codi que s'escriu.
Sempre hi ha optimitzacions a realitzar.
I sobretot al meu pseudo-codi aquí, a veure si ho pot veure.
>> Però essencialment el procés i la manera de pensar
és just com ho discutim.
La primera línia ens diu que hem d'obtenir una certa quantitat en dòlars.
I el segon ens diu que convertir-lo en centaus.
>> I llavors, mentre quartes parts es poden utilitzar, ens que desitgi augmentar el recompte de monedes i
disminuir la quantitat d'efectiu.
El mateix va per a deu, cinc, i monedes d'un cèntim.
I, finalment, li diem a l'usuari quantes monedes que fem servir.
>> Gran.
Així que amb això conclou el mètode de bucle.
Ara anem a parlar sobre el mètode modular, que s'assembla més a la divisió.
>> Tots estem familiaritzats amb el signe més, menys, multiplicar i dividir els operadors
disponible per a nosaltres.
C té tots els quatre dels, però també té l'operador de mòdul, representat per una
signe de percentatge.
Mòdul està molt ben cuidat.
Li dóna la resta de dividir dos nombres.
>> Recorda el missatge de la divisió llarga quan es divideix, per exemple, 74 per tres?
A partir de la posició de les desenes, hauria saben que 3 entrarà en set
dues vegades per fer un 6 amb resta un.
Vostè escriuria dos a la part superior, i després restar 6 de set, portant sobre
la resta de 14 a repetir el procés.
>> Tres entra en 14 quatre vegades a fer 12, amb la resta dos.
I dos no es trasllada més.
Així que dos quedarien en la inferior que la resta.
>> I això és el que li dóna mòdul, vostè aquest número a la part inferior.
Així que el 74 de mòdul de tres li donaria 2.
I 10 mòdul dos, així que donaria a posar a zero.
Perquè no hi ha cap resta quan es divideix 10 per dos.
>> Sis mòdul cinc, així 5:00 entra en sis una vegada.
I llavors, s'ha un sobres.
Així que sis de mòdul és un de cinc.
>> Llavors, si tens 7 mòdul 09:00, s'obtindria 07:00.
Com que el nou és més gran que 7.
Per tant, no es divideix tot en set, deixant set com a la seva resposta.
>> Si ho penses mòdul una mica més, recordi que vostè la dóna
resta després de dividir una cosa.
Penseu en com és possible que capaç d'utilitzar en Greedy.
Diguem que l'usuari demana $ 400,11.
Quin és una manera d'esbrinar quantes quarts que vostè necessita sense haver de
comptar cada un?
>> Un cop d'esbrinar quants trimestres vostè pot utilitzar per fer $ 400,11, quant
canviar restes?
Potser una combinació entre aquí mòdul i divisió entrarien
a mà per donar-li un lloc fresc, elegant acostar-se al problema cobdiciós.
Però recorda que el Consell de regla segueix sent vàlida.
Utilitzeu sempre la moneda més gran possible.
>> Un cop fet el càlcul de com moltes monedes a utilitzar, l'últim pas
és imprimir el nombre de monedes que va calcular.
Fins ara, hem estat utilitzant el printf funcionar únicament amb cordes.
Però quan es vol imprimir una a, o qualsevol tipus de dades que s'emmagatzema
en una variable, cal indicar que l'ús d'un marcador de posició.
>> Aquí he inclòs només alguns consells sobre com imprimir valors.
Si vostè té un nombre enter, ho faria escriure la seva cadena usant% d com
marcador de posició.
Després de la cotització de tancament marca, afegiu una coma.
I a continuació, posar en el sencer que es prendre el lloc de% d quan s'imprimeix.
>> Així que després de mostrar el nombre de les monedes utilitzades, ets
acabat amb Greedy.
Assegureu-vos de revisar tots els casos de cantonada, posar en ordre el seu estil una mica, i ja està
tot a punt per presentar.
Al final d'aquest conjunt de problemes, se li estar més familiaritzat amb el CS50
aparell, el terminal, i el bucle estructures i variables en C.
>> Vostè està bé en el seu camí.
La corba d'aprenentatge pot semblar difícil.
Així que anar pas a pas.
Assegureu-vos d'escriure fora de pseudo-codi abans de bussejar massa profund
en la sintaxi desconeguda.
>> Feu una llista de tasques, i trencar el assignació en més petits i més
tasques manejables.
Explora tots els recursos CS50.
A més de la conferència, rewatch aquest passeig a través.
>> Presti molta atenció a la secció.
Fes una ullada als pantalons curts.
Llegiu les preguntes dels seus companys de classe en Discutiu i publicar el seu propi compte.
>> Bona sort amb el p-set.
I gràcies per mirar.
Això era cobdiciós.
>> [REPRODUCCIÓ DE MÚSICA]