ROB BOWDEN: Hola, sóc Rob Bowden, i parlarem de quiz0. Per tant, la primera pregunta. Aquesta és la pregunta on que necessitaves per codificar el nombre 127 en els bulbs binaris. Si volguessis, podries fer la conversió normal des bi-- o, de decimal a binari. Però això probablement va de prendre un munt de temps. Vull dir, vostè podria adonar-se que, Acceptar, 1 és d'allà, 2 és allà, 4 és aquí, 8 és en allà. Manera més fàcil, 127 és 128 menys un. Aquesta bombeta més a l'esquerra és la de 128 bits. Així que 127 és realment tot de les altres bombetes, ja que és el més a l'esquerra bombeta almenys 1. Això és tot per aquesta pregunta. 

Pregunta un. Així que amb 3 bits que pugui representar 8 valors diferents. Per què, llavors, és la més gran de 7 no negatiu sencer decimal es pot representar? Bé, si només podem representar 8 valors diferents, llavors el que serem que representa és de 0 a 7. 0 ocupa un dels valors. 

Pregunta 2. Amb n bits, quants diferent valors poden representar? Així, amb n bits, té 2 els valors possibles per a cada bit. Així que tenim dos valors possibles per el primer bit, 2 valors possibles per al segon, 2 possible per a la tercera. I pel que és 2 vegades 2 cops 2, i en última instància, la resposta és 2 a la n. 

Pregunta 3. Què és 0x50 en binari? Així que recordi que té una molt hexadecimal conversió directa a binari. Així que aquí, només hem de mirar el 5 i el 0 independent. Així que el que és 5 en binari? 0101, que és el bit 1 i el 4 bits. El que és 0 en binari? No és complicat. 0000. Així que només cal posar junts, i aquest és el número complet en binari. 01.010.000. I si volguessis podries enlairament que més a l'esquerra de zero. És irrellevant. 

Així que, alternativament, el que és 0x50 en decimal? Si vostè volgués, vostè could-- si estàs més còmode amb el binari, vostè podria prendre aquesta resposta binària i convertir això en decimal. O podríem recordar que hexadecimal. Així que 0 està en el lloc 0º, i el 5 és al 16 al primer lloc. Així que aquí, tenim 5 vegades 16 a la primer, més 0 vegades 16 a la zero, és 80. I si un mira a la el títol de la pregunta, era CS 80, que era una mena de al·lusió a la resposta a aquest problema. 

Pregunta 5. Tenim aquest script Scratch, que és repetir 4 vegades la mantega de cacauet gelea. Llavors, ¿com ara el codi que en C? Bé, tenim aquí-- la part en negreta és l'única part que calia posar en pràctica. Així que tenim un bucle de 4 que està en bucle 4 vegades, la mantega de cacauet gelea ing-printf, amb la nova línia que el problema demana. 

Pregunta 6, un altre problema d'Scratch. Veiem que estem en un bucle per sempre. Estem dient que la variable i i després incrementar i en 1. Ara volem fer que a C. Hi ha múltiples formes en les que podríem haver fet això. Aquí passem a codificar el per sempre com un bucle while (true). Així que declarem la variable i, només com teníem i variable en scratch. Declari la variable i, i per sempre while (true), diem que la variable i. Així printf% jo-- o que podria haver utilitzat% d. Nosaltres diem que la variable, i després incrementar-lo, i ++. 

Pregunta 7. Ara volem fer alguna cosa molt similar Mario punt c del problema plantejat un. Volem imprimir aquests hashtags, volem imprimir un cinc per tres rectangle d'aquests hashes. Llavors, ¿com anem a fer això? Bé, et donem un tot paquet de programes, i que acaba de ha d'omplir en la funció d'impressió de quadrícula. 

Així que el que es veu com PrintGrid? Doncs estàs més enllà de la amplada i l'alçada. Així que tenim un exterior 4 llaç, això és un bucle sobretot de les files d'aquest quadrícula que volem imprimir. Després tenim el bucle niat entre 4, aquesta és la impressió sobre cada columna. Així que per a cada fila, imprimim per cada columna, un sol hash. Després, al final de la fila és la impressió d'un línia de nou senzill per anar a la següent fila. I això és tot per tota la xarxa. 

Pregunta 8. Una funció com PrintGrid es diu que tenir un efecte secundari, però no un retorn valor. Explicar la distinció. Així que això es basa en recordar el que és un efecte secundari és. Bé, un retorn value-- sabem PrintGrid no ho fa tenen valor de retorn, ja que aquí es diu sense efecte. Així que qualsevol cosa que retorna void en realitat no tornar res. Llavors, quin és l'efecte secundari? Bé, un efecte secundari és res aquest tipus de persisteix després dels extrems de la funció que no era acabem de tornar, i que no era només de les entrades. 

Així, per exemple, podríem canviar una variable global. Això seria un efecte secundari. En aquest cas particular, un efecte secundari molt important s'imprimeix a la pantalla. Així que és un efecte secundari que té PrintGrid. Imprimim aquestes coses a la pantalla. I vostè pot pensar en que com un efecte secundari, ja que això és una cosa que persisteix després que acabi aquesta funció. Això és una cosa que està fora de l'abast d'aquesta funció que en última instància està sent canviat, la contingut de la pantalla. 

Pregunta nou. Considereu el programa, a la qual els números de línia s'han afegit per En nom de la discussió. Així que en aquest programa només som trucant GetString, emmagatzemant- en aquesta variable s, i després la impressió que la variable s. Okay. Així d'explicar per què la línia un està present. #include punt CS50 h. Per què necessitem #include CS50 punt h? Bé estem cridant a la Funció GetString, i GetString es defineix a la biblioteca CS50. Així que si no teníem #include punt CS50 h, que anava a aconseguir que la declaració implícita de la funció d'error GetString del compilador. Així que hem d'incloure la library-- hem d'incloure l'arxiu de capçalera, o en cas contrari el compilador no ho farà reconeixen que hi ha GetString. 

Expliqueu per què la línia dos està present. Així estàndard punt h io. És exactament la mateixa com el problema anterior, excepte que en lloc de tractar amb GetString, estem parlant de printf. Així que si no diem el que necessitem per incloure estàndard de punt io h, llavors nosaltres no podríem utilitzar la funció printf, perquè el compilador no saber-ho. 

Què-- quin és el significat de ple dret en la línia de quatre? Així que aquí tenim int main (void). Això és just dir que no estan rebent cap línia d'ordres arguments a principal. Recordeu que nosaltres podríem dir int principals suports de cadena argv argc int. Així que aquí ens limitem a dir nul·la dir que no tenen en compte dels arguments de línia de comandes. 

Explicar, pel que fa a la memòria, exactament el GetString en línia de sis voltes. GetString està tornant un bloc de memòria, una gran varietat de personatges. És realment un retorn punter al primer caràcter. Recordeu que una cadena és una estrella de carbó. Així que s és un punter a la primera personatge en qualsevol que sigui la cadena és que l'usuari va entrar en el teclat. I que la memòria passa a ser malloced, de manera que la memòria està en el munt. 

Pregunta 13. Considereu el programa. Així que tot aquest programa està fent es printf-ing 1 dividit per 10. Així que quan es compila i executat, aquest programa sortides 0.0, tot i que 1 dividit per 10 és 0,1. Així que per què és 0.0? Bé, això es deu a de la divisió entera. Així que és un nombre enter 1, 10 és un nombre enter. Així que 1 dividit per 10, tot es tracta com nombres enters, i en C, quan fem la divisió entera, trunquem qualsevol punt decimal. Així que 1 dividit per 10 es 0, i llavors estem tractant per imprimir que com un flotador, per la qual zero impresa com un flotador és 0.0. I és per això que obtenim 0.0. 

Considereu el programa. Ara estem imprimint 0.1. Així que no hi ha divisió entera, només estem imprimint 0,1, però estem imprimir a 28 xifres decimals. I obtenim aquest 0,1000, un munt de zeros, 5 5 5, bla, bla, bla. Així que la pregunta aquí és per què ho fa imprimir que, en lloc d'exactament 0,1? 

Així que la raó aquí és ara punt imprecisió flotant. Recordeu que un flotador és a 32 bits. Així que només podem representar un nombre finit de valors de punt flotant amb els 32 Bits. Bé, hi ha, en última instància infinitament molts dels valors de punt flotant, i hi ha infinitament molts flotant els valors de punt d'entre 0 i 1, i estem òbviament capaç de representar fins i tot més valors que això. Així que hem de fer sacrificis per ser capaç de representar la majoria dels valors. 

Així com un valor de 0,1, pel que sembla, no podem representar això exactament. Així que en lloc de representar el 0,1 fem la El millor que podem representar aquest 0.100000 maig 5 5. I això és bastant estreta, però per a una gran quantitat d'aplicacions vostè ha de preocupar sobre punt imprecisió flotant, perquè simplement no podem representar tots flotant punts exactament. 

Pregunta 15. Penseu en el codi de sota. Estem imprimint 1 més 1. Així que no hi ha truc aquí. 1 més 1 avalua a 2, i llavors estem imprimint això. Això només imprimeix 2. 

Pregunta 16. Ara estem imprimint el caràcter 1 més el caràcter gener. Així que per què això no imprimir la mateixa cosa? Bé, el personatge 1 més el caràcter 1, el personatge té un valor ASCII 49. Així que això realment està dient 49, més 49, i en última instància, això va a imprimir 98. Així que això no imprimeix 2. 

Pregunta 17. Completar l'aplicació de imparell a continuació de tal manera que la funció retorna vertader si n és imparell i false si n és parell. Aquest és un gran propòsit per a l'operador mod. Així que ens prenem el nostre argument n, si n mod 2 és igual a 1, així això vol dir que n divideix per 2 tenia una resta. Si n dividit per 2 tenia una resta, que vol dir que n és imparell, de manera que tornar realitat. Altres vendes tornem falsa. També podria haver fet n mod 2 iguals zero, return false, en cas contrari retorna true. 

Penseu en la funció recursiva a continuació. Així que si n és menor que o igual a 1, retorna 1, o torni n vegades f de n menys 1. Llavors, què és aquesta funció? Bé, això és només el funció factorial. Això està molt ben representat com n factorial. 

Així que ara la pregunta 19, volem aprofitar aquesta funció recursiva. Volem que sigui iteratiu. Llavors, com fem això? Bo per al personal solució, i de nou no és múltiples formes en les que podria haver fet que, vam començar amb aquest producte int és igual a 1. I en tot aquest bucle for, anem multiplicar producte a última instància acabar amb el factorial complet. Així que per int i és igual a 2, i és menys d'o igual a n, i ++. 

Potser es pregunti per què i és igual a 2. Bé, recordeu que aquí hem de assegurar-se que el nostre cas base és correcta. Així que si n és menor o igual a 1, només estem tornant gener. Així que aquí, vam començar a i és igual a 2. Bé, si jo fos 1, llavors ell-- o si n era 1, llavors el bucle for no executar en absolut. I així ho faríem només producte de tornada, que és 1. De la mateixa manera, si n eren ni més ni menys que 1-- si fos 0, 1 negatiu, whatever-- encara estaríem tornant 1, que és exactament el que el versió recursiva està fent. 

Ara, si n és més gran que 1, llavors anem fer com a mínim un iteració d'aquest bucle. Així que diguem que n és 5, llavors estem farà vegades de productes és igual a 2. Així que ara el producte és de 2. Ara anem a fer vegades de productes és igual a 3. Ara és el 6. Temps de producte és igual a 4, ara és el 24. Temps de producte és igual a 5, ara és el 120. Així que, en última instància, estem tornant 120, que és correctament maig factorial. 

Pregunta 20. Això és en la que vostè ha de omplir en aquesta taula amb qualsevol algoritme donat, res del que hem vist, que encaixa aquests algorísmica termini vegades aquests temps d'execució asimptòtica. Llavors, què és un algoritme que és l'omega d'1, però gran O de n? Així que podria ser infinitament moltes respostes aquí. La que hem vist probablement més sovint és només recerca lineal. 

Així, en el millor dels casos escenari, el tema que estem buscant està en el principi de la llista i així en omega de passos d'1, el primer que vam comprovar, acabem de tornar immediatament que trobem l'article. En el pitjor dels casos, l'article està a l'extrem, o l'article no està en la llista en absolut. Així que hem de buscar tota la llista, tots els n elements, i és per això que és o de n. 

Així que ara és una cosa que alhora omega de n log n, i gran O de n log n. Bé, la cosa més rellevant que hem vist aquí és fusionar espècie. Així fusionar espècie, recordar, és en última instància, Theta de n log n, on es defineix theta si tots dos omega i gran O són ​​els mateixos. Tant n log n. 

Què és una cosa que és omega de N, i O del quadrat n? Bé, de nou hi ha múltiples respostes possibles. Aquí ens toca dir bombolla espècie. Inserció espècie també treballaria aquí. Recordeu que la bombolla de tipus ha de l'optimització on, si vostè és capaç d'obtenir a través de tota la llista sense necessitat de fer qualsevol swaps, llavors, bé, podem tornar immediatament que la llista es va solucionar per començar. Així que en el millor dels casos, és només l'omega de n. Si no es tracta només d'un bé perquè el procés de ordenats, llavors tenim O de n al quadrat swaps. I finalment, tenim la selecció espècie per n al quadrat, tant omega i gran O. 

Pregunta 21. Què hi ha desbordament de sencer? Bé de nou, similar a l'anterior, només tenim un nombre finit de bits de per representar un nombre enter, per la qual cosa potser 32 bits. Diguem que tenim un enter amb signe. A continuació, en última instància, el més alt nombre positiu podem representar és 2 a l'31 almenys 1. Llavors, què passa si intentem a continuació, incrementar aquest sencer? Bé, anem a anar de 2 a l'31 menys 1, tot el camí fins negatiu 2 a la 31. Així que aquest desbordament de sencers és quan segueixes incrementant, i en última instància, no es pot aconseguir més amunt i que només envolta tot el camí de tornada al voltant d'un valor negatiu. 

Què passa amb un desbordament de memòria intermèdia? Així un tampó overflow-- recorda el que un buffer és. És només una part de la memòria. Una cosa així com una matriu és un tampó. Així que un desbordament de memòria intermèdia és quan intenta accedir a memòria més enllà del final de la matriu. Així que si vostè té una matriu de mida 5 i vostè tractar d'accedir a suport de matriu 5 o 6 el suport o el suport 7, o qualsevol cosa més enllà de la extrem, o fins i tot gens suport de sèrie aquí a continuació, negatiu 1-- tots aquests són desbordaments de memòria intermèdia. Estàs tocant de memòria en mals camins. 

Pregunta 23. Així que en aquest el que necessita per implementar strlen. I els diem que es pot assumeixen s no és nul, pel que no ha de fer qualsevol xec per nul. I hi ha diverses maneres que podria haver fet això. Aquí només prenem el senzill. Comencem amb un comptador, n. n és comptant el nombre de caràcters que hi ha. Així que vam començar a 0, i després iterar sobre la llista completa. 

És s igual a 0 a suport de la caràcter terminador nul? Recordin que estem buscant el caràcter terminador nul per determinar quant de temps la nostra cadena és. Això va a acabar qualsevol cadena corresponent. Així que és suport de s 0 igual per al terminador nul? Si no és així, llavors anem a mirar s suport 1, s 2 suport. Seguim camí fins que trobar el terminador nul. Un cop hem trobat, llavors n conté la longitud total de la cadena, i només podem tornar aquest. 

Pregunta 24. Així que aquest és l'un en el qual haver de fer la compensació. Així que una cosa és bona en un manera, però de quina manera és dolent? Així que aquí, fusionar espècie tendeix a ser més ràpid que la bombolla espècie. Dit que-- així, hi ha són múltiples respostes aquí. Però la principal és que la bombolla espècie és omega de n per a una llista ordenada. 

Recordeu que la taula que acabem de veure abans. Així bombolla ordena omega de n, el millor dels casos és que és capaç d'anar més la llista una vegada, determinar bé això ja és ordenats, i retorn. Ordenament per barreja, sense importar el que vostè ho fa, és l'omega de n log n. Així que per a la llista ordenada, bombolla espècie que serà més ràpid. 

Ara què passa vinculada llistes? Així que una llista enllaçada pot créixer i encongir per adaptar-se a tants elements com sigui necessari. Dit així que-- en general la comparació directa serà un vinculat una llista amb una matriu. Així que tot i que les matrius poden augmentar i reduir fàcilment per adaptar-se a tants elements segons sigui necessari, una llista enllaçada en comparació amb un una array-- matriu té accés aleatori. Ens pot indexar en qualsevol en particular element de la matriu. 

Així que per a una llista enllaçada, no podem només ha d'anar al cinquè element, hem de recórrer des del principi fins arribar al cinquè element. I això va a impedir- fer alguna cosa com a recerca binària. Parlant de recerca binària, recerca binària tendeix a ser més ràpida que la recerca lineal. Dit que-- així, una cosa possible és que no es pot fer binari buscar en llistes enllaçades, només pot fer-ho en matrius. Però, probablement, el més important, no es pot fer la cerca binària en una matriu que no està ordenada. Allà davant pot ser que hagi d'ordenar la matriu, i només llavors pot que fas de recerca binària. Així que si el teu no és ordenada, per començar, llavors la recerca lineal podria ser més ràpid. 

Pregunta 27. Així que consideri el programa a continuació, que estaran a la següent diapositiva. I això és en la que estem voldrà declarar explícitament els valors per a diferents variables. Així que donem una ullada a això. 

Així que la línia un. Tenim int x és igual a 1. Aquesta és l'única cosa que ha passat. Així que en la línia 1, que veiem en la nostra taula, i que, a, b, i tmp són tots ratllat. Llavors, ¿què és x? Bé tot just fixem que igual a 1. I a continuació, la línia dos, bé, veiem que i s'estableix en 2, i la taula ja està emplenat per a nosaltres. Així que x és 1 iy és 2. 

Ara, la línia de tres, ara estem dins de la funció d'intercanvi. ¿Què vam fer passar a intercanviar? Passem signe x per 1, i símbol d'unió i de b. Quan el problema anterior va declarar que la direcció de x és 0x10, i la direcció d'i és 0x14. Així que a i b són iguals a 0x10 i 0x14, respectivament. 

Ara en línia de tres, ¿quins són x i y? Bé, res ha canviat sobre de x i y en aquest punt. Tot i que són dins d'un marc principal de pila, encara tenen la mateixa els valors que tenien abans. No hem modificat cap memòria. Així que x és 1, i és 2. Bé. Així que ara hem dit int tmp igual a protagonitzar un. Així que en la línia de quatre, tot és el mateix excepte per tmp. No hem canviat cap valor de res, excepte per tmp. Estem establint tmp igual a protagonitzar un. Què és una estrella? Bé, uns punts a X, per la qual protagonitzen un va a igualtat de x, que és 1. Així que tot es copia baix, i tmp s'estableix en 1. 

Ara la següent línia. Estrella és igual a un estel b. Així per línia five-- bé de nou, tot que és el mateix, llevat que sigui una estrella és. Què és una estrella? Bé, acabem de dir una estrella és x. Així que estem canviant x a la igualtat d'estrelles b. Quina és l'estrella b? i. b punts a i. Així estrella b és i. Així que estem establint x igual a i, i tota la resta és igual. Així que ens veiem en la següent fila que x és ara 2, i la resta són simplement copiar. 

Ara, en la següent línia, estrella b és igual a tmp. Bé, acabem de dir estrella b és i, pel que estem establint i igual a tmp. Tota la resta és el mateix, així que tot es copia a baix. Estem establint i igual a TMP, que és un, i tota la resta és igual. 

Ara, per fi, la línia 7. Estem de tornada a la funció principal. Estem després d'intercanvi es va acabar. Hem perdut a, b, i tmp, però en última instància, ens no es canvia cap valor de res en aquest moment, que acabem de copiar x i i cap avall. I veiem que x i y són ara 2 i 1 en lloc d'1 i 2. El canvi s'ha executat amb èxit. 

Pregunta 28. Suposem que et trobes els missatges d'error a continuació en horari d'oficina l'any que ve com una CA o TF. Assessorar com solucionar cadascun d'aquests errors. Així referència indefinida a GetString. Per què pot vostè veure això? Bé, si un estudiant està utilitzant GetString en el seu codi, s'han inclòs correctament hash CS50 punt h per incloure la biblioteca CS50. 

Bé, ¿què és el que que hagi de corregir aquest error? Han de fer un guió al lcs50 línia d'ordres quan s'està compilant. Així que si no passen lcs50 guió so metàl·lic, que són no tindrà la real codi que implementa GetString. 

Pregunta 29. Implícitament declarar funció de biblioteca strlen. Bé això ara, que no té fet el hash apropiat incloure. En aquest cas particular, l'arxiu de capçalera que necessiten per incloure és la cadena de punts h, i incloent cadena dot h, ara la student-- ara el compilador té accés a la declaracions de strlen, i se sap que el seu codi Esteu strlen correctament. 

Pregunta 30. Més per cent de les conversions que els arguments de dades. Llavors, ¿què és això? Bo recordar que aquests cent signs-- com són rellevants per printf. Així que en printf podríem cent- podríem imprimir alguna cosa com cent i barra invertida n. O podem imprimir com cent i, espai, i per cent, l'espai, i per cent. Així que per a cada un dels signes de percentatge, que necessiten passar una variable al final de printf. 

Així que si diem que parin printf cent i barra invertida n prop parin, així, diem que estem va a imprimir un nombre enter, però llavors no passem printf un enter per imprimir en realitat. Així que aquí més per cent conversions que els arguments de dades? Això és molt dir que tenim un munt de percentatges, i no tenim prou variables per omplir realment en aquests percentatges. 

I llavors, sens dubte, per a la pregunta 31, definitivament perdut 40 bytes en un blocs. Així que això és un error de Valgrind. Això és a dir que en algun lloc del seu codi, vostè té una assignació que és 40 bytes gran, així que malloced 40 bytes, i mai es va alliberar. El més probable és que vostè només ha trobar alguna pèrdua de memòria, i trobar on vostè necessita alliberar aquest bloc de memòria. 

I la pregunta 32, escriptura no vàlida de mida 4. Una vegada més es tracta d'un error de Valgrind. Això no té a veure amb pèrdues de memòria ara. És a dir, més likely-- Vull dir, és algun tipus de drets de memòria no vàlida. I el més probable és que això és cert tipus de desbordament de memòria intermèdia. Quan vostè té una matriu, potser una matriu d'enters, i anem a diuen que és de mida 5, i vostè tractar de tocar matriu suport maig. Així que si s'intenta escriure en aquesta valor, això no és un tros de la memòria que en realitat es té accés a, i per la qual cosa anem a aconseguir aquest error, dient escriptura no vàlida de mida 4. Valgrind va a reconèixer que ets tractant de tocar la memòria de forma inadequada. 

I això és tot per quiz0. Estic Rob Bowden, i això és CS50.