ROB BOWDEN: Ciao, io sono Rob Bowden, e parliamo di quiz0. Quindi, prima domanda. Questa è la domanda cui avevi bisogno di codificare il numero 127 dei bulbi binari. Se si voleva, si potrebbe fare la conversione regolare da bi-- o, da decimale a binario. Ma questo è probabilmente andando di prendere un sacco di tempo. Voglio dire, si può capire che, OK, 1 è in là, 2 è in là, 4 è lì, 8 è in là. Modo più semplice, è di 128 127 meno uno. Quella lampadina più a sinistra è il 128-bit. Quindi 127 è in realtà solo tutto delle altre lampadine, dato che è il più a sinistra lampadina meno 1. Questo è tutto per questa domanda. 

Prima domanda. Quindi, con 3 bit è possibile rappresentano 8 valori distinti. Perché, allora, è il più grande 7 non negativo numero intero decimale si può rappresentare? Beh, se si può solo rappresentano 8 valori distinti, allora quello che stiamo andando a essere che rappresenta è da 0 a 7. 0 occupa uno dei valori. 

Domanda due. Con n bit, il numero di distinte I valori si possono rappresentare? Così, con n bit, si dispone di 2 valori possibili per ogni bit. Quindi abbiamo 2 valori possibili per il primo bit, 2 valori possibili per il secondo, 2 possibile per il terzo. E così che è 2 volte 2 volte 2, e in ultima analisi, la risposta è 2 al n. 

Domanda tre. Cosa c'è di 0x50 in binario? Quindi ricorda che esadecimale è molto conversione semplice binario. Così qui, abbiamo solo bisogno di guardare il 5 e 0 indipendentemente. Così che cosa è 5 in binario? 0101, questo è il 1 bit e il bit 4. Cosa c'è 0 in binario? Non difficile. 0000. Quindi, solo metterli insieme, e questo è il numero intero in binario. 01.010.000. E se si voleva si poteva togliere quella più a sinistra a zero. E 'irrilevante. 

E allora, in alternativa, ciò che è 0x50 in decimale? Se si voleva, si could-- se siete più a suo agio con il binario, si potrebbe prendere quella risposta binaria e convertire in decimale. Oppure potremmo ricordare che esadecimale. Affinché 0 nel 0-esimo posto, e il 5 è in 16 alla prima. Ecco, noi abbiamo 5 volte 16 per il prima, più 0 volte 16 allo zero, è 80. E se hai guardato il titolo alla domanda, era CS 80, che era una specie di suggerimento per la risposta a questo problema. 

Domanda cinque. Abbiamo questo script Scratch, che è ripetere 4 volte il burro di arachidi gelatina. Quindi, come facciamo noi ora codice in C? Bene, abbiamo qui-- la parte in grassetto è l'unica parte si doveva attuare. Quindi abbiamo un 4 ciclo che sta loop 4 volte-ing printf burro di arachidi gelatina, con la nuova linea come il problema chiede. 

Domanda di sei, un altro problema Scratch. Si vede che siamo in un eterno ciclo. Stiamo dicendo che la variabile i e poi incrementando i di 1. Ora vogliamo farlo in C. Ci sono molteplici modi in cui avrebbe potuto farlo. Qui ci è capitato di codificare il sempre ciclo come while (true). Così si dichiara la variabile i, appena come abbiamo avuto i variabili in Scratch. Dichiarare la variabile i, e per sempre while (true), diciamo che la variabile i. Così printf% I-- o avresti potuto usato% d. Diciamo che variabili, e poi incrementarlo, i ++. 

Domanda sette. Ora vogliamo fare qualcosa di molto simile di Mario dot c dal problema impostare uno. Vogliamo stampare questi hashtags, vogliamo stampare un cinque per tre rettangolo di questi hash. Quindi, come facciamo a fare questo? Beh, vi diamo un intero mucchio di codice, e basta devono compilare la funzione di griglia di stampa. 

Così che cosa PrintGrid assomiglia? Beh, tu sei oltre il larghezza e l'altezza. Quindi abbiamo un esterno 4 ciclo, che è looping su tutte le righe di questo griglia che vogliamo stampare. Poi abbiamo l'inter-nested 4 loop, questa è la stampa su ogni colonna. Quindi, per ogni riga, il risultato della stampa per ogni colonna, un unico hash. Poi alla fine della riga della stampa una singola nuova linea per passare alla riga successiva. E questo è tutto per l'intera griglia. 

Domanda di otto. Una funzione come PrintGrid si dice avere un effetto collaterale, ma non un ritorno valore. Spiegare la distinzione. Quindi questo si basa su di voi ricordare ciò è un effetto collaterale. Beh, un ritorno value-- sappiamo PrintGrid non lo fa avere un valore di ritorno, dal momento che proprio qui si dice nulla. Quindi tutto ciò che restituisce void in realtà non restituire nulla. Allora, qual è l'effetto collaterale? Ebbene, un effetto collaterale è tutto ciò che tipo di persiste dopo la fine della funzione che non era appena tornato, e non era solo dagli ingressi. 

Così, per esempio, potremmo modificare una variabile globale. Sarebbe un effetto collaterale. In questo caso particolare, molto importante effetto collaterale è la stampa su schermo. Così che è un effetto collaterale che PrintGrid ha. Stampiamo queste cose sullo schermo. E si può pensare di che come effetto collaterale, dato che è una cosa che persiste dopo questa funzione si conclude. Questo è qualcosa al di fuori del campo di applicazione di questa funzione che infine viene modificato, il contenuto dello schermo. 

Domanda nove. Si consideri il seguente programma, a cui i numeri di riga sono stati aggiunti per il bene della discussione. Quindi, in questo programma ci sono solo chiamando GetString, riporlo In questa variabile s, e poi stampa la variabile s. Ok. Quindi spiegare perché la linea uno è presente. #include CS50 dot h. Perché abbiamo bisogno di #include CS50 dot h? Bene, noi stiamo chiamando il Funzione GetString, e GetString è definito in biblioteca CS50. Quindi, se non avessimo #include CS50 dot h, otterremmo tale dichiarazione implicita dell'errore funzione GetString dal compilatore. Quindi abbiamo bisogno di includere il library-- abbiamo bisogno di includere il file di intestazione, altrimenti il ​​compilatore non riconoscere che GetString esiste. 

Spiegare perché la linea due è presente. Così standard io punto h. E 'esattamente lo stesso come il problema precedente, tranne che invece di trattare con GetString, stiamo parlando di printf. Quindi, se non abbiamo detto che abbiamo bisogno di per includere norma io dot h, allora non saremmo in grado Per utilizzare la funzione printf, perché il compilatore non sarebbe sapere. 

Why-- qual è il significato di diritto nella linea a quattro? Quindi qui abbiamo int main (void). Questo è solo dicendo che noi non si ottiene alcuna riga di comando argomenti di principale. Ricordate che potremmo dire int principali int argc parentesi stringa argv. Così qui ci limitiamo a dire nulla a dire che stanno ignorando gli argomenti della riga di comando. 

Spiegare, riferendosi alla memoria, esattamente cosa GetString in linea sei rendimenti. GetString restituisce un blocco di memoria, un array di caratteri. E 'davvero un ritorno puntatore al primo carattere. Ricordate che una stringa è una stella char. Quindi s è un puntatore alla prima carattere qualunque sia la stringa è che l'utente immessi tramite tastiera. E che la memoria sembra essere malloced, in modo che la memoria è in mucchio. 

Domanda 13. Si consideri il seguente programma. Quindi tutto questo programma sta facendo è printf-ing 1 diviso per 10. Così, quando compilato e eseguito, questo programma uscite 0.0, anche se 1 diviso per 10 è 0,1. Allora perché è 0.0? Beh, questo è dovuto al fatto della divisione intera. Quindi 1 è un numero intero, 10 è un numero intero. Così 1 diviso 10, tutto è trattato come numeri interi, e in C, quando facciamo divisione intera, abbiamo troncare qualsiasi punto decimale. Quindi 1 diviso per 10 è 0, e quindi stiamo cercando stampare che come un galleggiante, così lo zero stampato come un galleggiante è 0.0. Ed è per questo che otteniamo 0.0. 

Si consideri il seguente programma. Ora stiamo stampa 0.1. Quindi no divisione intera, stiamo solo la stampa 0.1, ma stiamo stamparlo a 28 cifre decimali. E riusciamo ad ottenere questo 0.1000, un intero gruppo di zeri, 5 5 5, bla bla bla. Quindi la domanda qui è il motivo per cui lo fa stampare che, invece di esattamente 0,1? 

Quindi la ragione qui è ora virgola mobile imprecisioni. Ricordate che un galleggiante si trova a soli 32 bit. Così possiamo rappresentare solo un numero finito di valori in virgola mobile con quelle 32 bit. Beh c'è infine infinitamente molti valori in virgola mobile, e ci sono infiniti galleggiante valori in punti in tra 0 e 1, e siamo ovviamente in grado di rappresentano ancora di più i valori di quello. Quindi dobbiamo fare sacrifici per essere in grado di rappresentare la maggior parte dei valori. 

Quindi un valore come 0.1, a quanto pare non possiamo garantirne la precisione. Così, invece di rappresentare 0.1 facciamo il meglio che possiamo rappresentare questa 0.100000 5 5 5. E questo è abbastanza vicino, ma per molte applicazioni si deve preoccupare di virgola mobile imprecisioni, perché noi non possiamo rappresentare tutte galleggiante punti esattamente. 

Domanda 15. Si consideri il codice di seguito. Stiamo solo la stampa di 1 più 1. Quindi non c'è nessun trucco. 1 più 1 restituisce a 2, e allora siamo di stampare tale. Questo stampa solo 2. 

Domanda 16. Ora stiamo stampando il carattere 1 più il carattere 1. Allora perché questo non stampare la stessa cosa? Beh, il carattere 1 più il carattere 1, il carattere 1 ha valore ASCII 49. Quindi questo è davvero dire 49 più 49, e in ultima analisi, si tratta di andare per la stampa 98. Quindi questo non stampa 2. 

Domanda 17. Completare l'attuazione dispari di seguito in modo che la funzione restituisce true se n è dispari e falso se n è pari. Questo è un grande scopo per l'operatore mod. Quindi prendiamo il nostro argomento n, se n mod 2 è uguale a 1, e ciò significa che n divide da 2 aveva un resto. Se n diviso 2 aveva un residuo, che significa che n è dispari, quindi torniamo vero. Altrimenti si ritorna falso. Si potrebbe anche aver fatto n MOD 2 uguali pari a zero, restituire false, altrimenti restituisce true. 

Si consideri la funzione ricorsiva di seguito. Quindi, se n è minore o uguale a 1, ritorno 1, else return n volte f di n meno 1. Così che cosa è questa funzione? Beh, questo è solo il funzione fattoriale. Questo è ben rappresentato come n fattoriale. 

Quindi, mettere in discussione 19 ora, vogliamo prendere questa funzione ricorsiva. Noi vogliamo rendere iterativo. Quindi, come possiamo farlo? Bene per il personale soluzione, e ancora una volta non c'è diversi modi che avresti potuto fare che, iniziamo con questo int prodotto è uguale a 1. E per tutto questo ciclo for, stiamo andando da moltiplicare prodotto in ultima analisi, finire con la piena fattoriale. Così, per int i uguale a 2, i è minore o uguale an, i ++. 

Ci si potrebbe chiedere il motivo per cui i uguale a 2. Beh, ricordate che qui dobbiamo assicurarsi che il nostro scenario di base è corretta. Quindi, se n è minore o uguale a 1, stiamo solo tornando 1. Così qui, iniziamo a i uguale a 2. Beh, se fossi 1, allora the-- o se n fosse 1, quindi il ciclo for Non avrebbe eseguito affatto. E così ci sarebbe solo prodotto di ritorno, che è 1. Allo stesso modo, se n fosse niente di meno che 1-- se fosse 0, 1 negativa, whatever-- saremmo ancora torneremo 1, che è esattamente ciò che il versione ricorsiva sta facendo. 

Ora, se n è maggiore di 1, allora stiamo andando fare almeno un iterazione di questo ciclo. Quindi diciamo che n è 5, allora siamo intenzione di fare i tempi di prodotto è uguale a 2. Così ora prodotto è 2. Ora stiamo andando a fare volte di prodotto è uguale a 3. Ora è 6. Volte del prodotto è uguale a 4, ora è 24. Prodotto è uguale a 5 volte, ora è 120. Allora in definitiva, siamo di ritorno 120, che è corretto e 5 fattoriale. 

Domanda 20. Questo è quello in cui è necessario compilare in questa tabella con qualsiasi dato algoritmo, tutto ciò che abbiamo visto, che si adatta questi run algoritmico volte questi tempi di esecuzione asintotici. Così che cosa è un algoritmo che è omega di 1, ma grande O di n? Quindi ci potrebbe essere infinitamente molte risposte qui. Quello che abbiamo visto probabilmente più spesso è solo ricerca lineare. 

Quindi, nel migliore dei casi scenario, la voce siamo cercando al all'inizio della lista e così in omega di passi di 1, la prima cosa che controlliamo, abbiamo appena torniamo subito che abbiamo trovato il prodotto. Nel peggiore dei casi, l'elemento è alla fine, o l'articolo non è nell'elenco affatto. Quindi dobbiamo cercare l'intera lista, tutti gli n elementi, ed è per questo che è o di n. 

Così ora è qualcosa che è sia omega di log n n, e grande O di log n n. Beh, la cosa più rilevante che abbiamo visto qui è merge sort. Così merge sort, ricordare, Theta è in ultima analisi, di n log n, dove è definito theta se entrambi omega e grande O sono uguali. Sia n log n. 

Che cosa è qualcosa che è omega di n, e O di n al quadrato? Beh, ancora non c'è più risposte possibili. Qui ci capita di dire bubble sort. Insertion sort sarebbe anche lavorare qui. Ricordate che bubble sort ha che l'ottimizzazione in cui, se si è in grado di ottenere attraverso l'intera lista senza bisogno di fare eventuali swap, poi, beh, possiamo tornare subito che l'elenco è stato ordinato per cominciare. Quindi, nel migliore dei casi, è solo omega di n. Se non è solo un bene ordinati lista per cominciare, allora abbiamo O di n al quadrato swap. E, infine, abbiamo ordinamento per selezione per n al quadrato, sia omega e grande O. 

Domanda 21. Cosa c'è di integer overflow? Ebbene nuovo, simile al precedente, abbiamo solo un numero finito di bit per rappresentare un numero intero, così forse 32 bit. Diciamo che abbiamo un intero con segno. Quindi in ultima analisi, il più alto numero positivo possiamo rappresentare è 2 alla 31 meno 1. Che cosa succede se proviamo a quindi incrementare tale numero intero? Beh, stiamo andando a passare dal 2 al 31 meno 1, tutta la strada fino a negativo 2 al 31. Quindi questo Integer Overflow è quando si mantiene l'incremento, e in ultima analisi, non si può ottenere solo più in alto e avvolge tutto il viaggio di ritorno intorno ad un valore negativo. 

Che dire di un buffer overflow? Così un buffer overflow-- ricordare ciò che un buffer è. E 'solo un pezzo di memoria. Qualcosa di simile a un array è un buffer. Così un buffer overflow è quando si tenta di accedere alla memoria oltre la fine di tale matrice. Quindi, se si dispone di un array di dimensione 5 e tentare di accedere staffa matrice 5 o 6 o staffa staffa 7, o qualcosa al di là del fine, o addirittura nulla staffa di serie below-- negativo 1-- tutti questi sono buffer overflow. Stai toccando la memoria in cattiva strada. 

Domanda 23. Quindi, in questo è necessario per implementare strlen. E vi diciamo che è possibile assumere s non sarà nullo, in modo da non dover fare tutti i controlli per nulla. E ci sono diversi modi avresti potuto fare questo. Qui dobbiamo solo prendere il semplice. Si comincia con un contatore, n. n è contare quanti caratteri ci sono. Così iniziamo a 0, e poi ci iterare l'intero elenco. 

È s staffa 0 pari al carattere terminatore null? Ricordate che stiamo cercando il carattere terminatore null per determinare quanto tempo la nostra stringa è. Che sta per terminare qualsiasi stringa in questione. Così è s staffa 0 uguale per il terminatore nullo? Se non lo è, allora stiamo andando a guardare staffa s 1, s 2 staffa. Continuiamo fino a quando non trovare il terminatore null. Una volta che abbiamo trovato, allora n contiene la lunghezza totale della stringa, e possiamo solo tornare quella. 

Domanda 24. Quindi questo è quello in cui si devono fare il compromesso. Quindi una cosa è buona in un modo, ma in che modo è brutto? Quindi, ecco, merge sort tende a essere più veloce di bubble sort. Detto che-- bene, ci di risposte qui. Ma la principale è che bubble sort è omega di n per un elenco ordinato. 

Ricordate quel tavolo che abbiamo appena visto in precedenza. Così bolla ordina omega di n, la migliore delle ipotesi è che è in grado di andare poco più di la lista una volta, determinano ehi questa cosa è già ordinati, e ritorno. Merge sort, non importa quale che fai, è l'omega di log n n. Così per la lista ordinata, bolla tipo sta per essere più veloce. 

Ora, per quanto riguarda le liste collegate? Quindi, una lista concatenata può crescere e ridursi per adattarsi tanti elementi come necessario. Detto così che-- di solito il confronto diretto sta per essere collegato elenco di una serie. Così, anche se gli array possono facilmente crescere e ridursi per soddisfare il maggior numero di elementi se necessario, un elenco collegato rispetto ad un un array-- matrice ha accesso casuale. Siamo in grado di indicizzare in qualsiasi particolare elemento della matrice. 

Così, per una lista collegata, non possiamo basta andare al quinto elemento, dobbiamo attraversare dall'inizio fino ad arrivare al quinto elemento. E che sta per impedirci di fare qualcosa come la ricerca binaria. Parlando di ricerca binaria, ricerca binaria tende ad essere più veloce di ricerca lineare. Detto che-- così, una cosa possibile è che non si può fare binario cercare liste concatenate, si può fare solo su array. Ma probabilmente ancora più importante, non si può fare ricerca binaria su una matrice che non è ordinato. Upfront potrebbe essere necessario ordinare l'array, e solo allora può fate la ricerca binaria. Quindi, se la vostra passione non è ordinato per cominciare, poi ricerca lineare potrebbe essere più veloce. 

Domanda 27. Quindi prendere in considerazione il programma qui di seguito, che sarà nella diapositiva successiva. E questo è quello dove siamo andando a voler dichiarare esplicitamente i valori per le diverse variabili. Quindi diamo un'occhiata a questo. 

Così la linea uno. Abbiamo int x è uguale a 1. Questa è l'unica cosa che è successo. Quindi in linea uno, vediamo nel nostro tavolo, che y, a, b, e TMP sono tutti oscurati. Così che cosa è x? Beh, abbiamo appena impostato è pari a 1. E poi la linea due, beh, vediamo che y è impostato su 2, e la tabella è già compilato per noi. Quindi x è 1 e y è 2. 

Ora, la linea a tre, ora siamo all'interno della funzione di scambio. Cosa abbiamo passiamo a scambiare? Passammo commerciale x per una e commerciale y per b. Nei casi in cui il problema precedente affermato che l'indirizzo di x è 0x10, e l'indirizzo di y è 0x14. Quindi a e b sono pari a 0x10 e 0x14, rispettivamente. 

Ora in linea tre, quali sono x e y? Beh, non è cambiato nulla merito xey a questo punto. Anche se sono all'interno di una stack frame principale, hanno ancora la stessa I valori hanno fatto prima. Non abbiamo modificato la memoria. Quindi x è 1, y 2. Bene. Così ora abbiamo detto int tmp pari ad una stella. Così alla linea a quattro, tutto è la stessa tranne tmp. Non abbiamo cambiato i valori di qualsiasi cosa tranne che per tmp. Stiamo allestendo tmp pari ad una stella. Che cosa è una stella? Beh, un punti di x, così una stella sta per la parità di x, che è 1. Quindi tutto è copiato verso il basso, e tmp è impostato su 1. 

Ora la riga successiva. Stella è uguale a una stella b. Quindi, linea five-- di nuovo bene, tutto è lo stesso, tranne qualunque stella a è. Che cosa è una stella? Beh, abbiamo appena detto una stella è x. Quindi stiamo cambiando x alla parità di stelle b. Che cos'è stelle b? y. b indica y. Quindi stelle b è y. Quindi stiamo impostando x uguale ay, e tutto il resto è lo stesso. Così vediamo nella riga successiva che x ora è 2, e il resto sono appena copiato verso il basso. 

Ora, nella riga successiva, stella b è uguale tmp. Beh, abbiamo appena detto stella b è y, quindi stiamo impostando y pari a tmp. Tutto il resto è lo stesso, quindi tutto viene copiato verso il basso. Stiamo impostando y pari a tmp, che è uno, e tutto il resto è lo stesso. 

Ora finalmente, linea sette. Siamo di nuovo nella funzione principale. Siamo dopo di swap è finito. Abbiamo perso a, b, e tmp, ma alla fine siamo Non cambiano i valori niente a questo punto, dobbiamo solo copiare x e y verso il basso. E vediamo che x e y sono ora 2 e 1 invece di 1 e 2. Lo swap è stato eseguito con successo. 

Domanda 28. Supponiamo che si incontrano i messaggi di errore di seguito durante l'orario di ufficio l'anno prossimo come CA o TF. Consiglia come risolvere ciascuno di questi errori. Così undefined reference to GetString. Perché si potrebbe vedere questo? Beh, se uno studente sta usando GetString nel loro codice, hanno correttamente hash incluso CS50 dot h per includere la libreria CS50. 

Ebbene, che cosa bisogno di correggere questo errore? Hanno bisogno di fare un lcs50 trattino al riga di comando quando sono la compilazione. Quindi, se non passano clang trattino lcs50, sono non andando ad avere l'attuale codice che implementa GetString. 

Domanda 29. Implicitamente dichiara funzione di libreria strlen. Bene adesso, che non ha fatto la corretta hash includere. In questo caso particolare, il file di intestazione hanno bisogno di includere è stringa dot h, e compresa una stringa punto h, ora il student-- ora il compilatore ha accesso al dichiarazioni di strlen, e si sa che il codice sta usando correttamente strlen. 

Domanda 30. Più conversioni per cento di argomenti di dati. Così che cosa è questo? Bene ricordare che queste cento signs-- come sono rilevanti per printf. Quindi, in printf potremmo percent-- potremmo stampare qualcosa come cento i backslash n. Oppure potremmo stampare come i cento, spazio, cento i, spazio, cento i. Quindi, per ciascuno di detti segni di percentuale, abbiamo bisogno di per passare una variabile alla fine del printf. 

Quindi se diciamo paren printf per cento i backslash n stretti paren, beh, diciamo che siamo andare in stampa un numero intero, ma poi noi non passiamo printf un numero intero da stampare in realtà. Quindi, qui più per cento conversioni di argomenti di dati? Che sta dicendo che abbiamo un sacco di percentuali, e noi non abbiamo abbastanza variabili di compilare in realtà in quelle percentuali. 

E poi sicuramente, per la domanda 31, definitivamente perso 40 byte in una blocchi. Quindi questo è un errore Valgrind. Questo sta dicendo che da qualche parte nel codice, si dispone di una dotazione che è di 40 byte di grandi dimensioni in modo da malloced 40 byte, e non avete mai liberato esso. Molto probabilmente è sufficiente di trovare qualche perdita di memoria, e scoprire dove è necessario liberare il blocco di memoria. 

E mettere in discussione 32, scrittura non valido di dimensioni 4. Anche in questo caso si tratta di un errore di Valgrind. Ciò non deve fare con perdite di memoria ora. Questo è, più likely-- voglio dire, è una sorta di diritti di memoria non validi. E molto probabilmente questo è un po ' sorta di buffer overflow. Nei casi in cui si dispone di una matrice, forse un array di interi, e cerchiamo di dicono che è di dimensione 5, e si provate a toccare la staffa serie 5. Quindi, se si tenta di scrivere in quella valore, che non è un pezzo di memoria che in realtà ha accesso a, e così si sta andando ad ottenere questo errore, dicendo di scrittura non valido di dimensioni 4. Valgrind sta andando a riconoscere che sei cercando di toccare la memoria in modo inappropriato. 

E questo è tutto per quiz0. Sono Rob Bowden, e questo è CS50.