[Powered by Google Translate] [Sezione 4] [meno confortevole] [Nate Hardison] [Harvard University] [Questo è CS50.] [CS50.TV] 

Va bene, bentornato alla sezione. Nella sezione di questa settimana andremo a fare un paio di cose. Stiamo per primo Set problema recap 2, che è il problema Cesare e Vigenère set. E poi andiamo a tuffarsi recensione Quiz 0 e trascorrere un po 'di tempo ricapitolando ciò di cui abbiamo parlato in ciascuna delle lezioni fino ad ora, e faremo anche fare qualche problema da quiz dell'anno precedente. In questo modo voi ragazzi avete un buon modo per prepararsi a questo. 

Per iniziare, ho avviato un paio di buone soluzioni per il set precedente problema, Problemi Set 2, in questo spazio. Se voi ragazzi ha colpito questo link, e se si fa clic su il mio nome e cliccate su il mio prima revisione vedrai caesar.c, che è esattamente quello che sto guardando. Parliamo di questo molto velocemente. Questo è solo una soluzione campione. Questo non è necessariamente la soluzione perfetta. Ci sono molti modi diversi per scrivere questo, ma ci sono un paio di cose che volevo mettere in evidenza che ho visto come mi è stato di classificazione, gli errori più comuni che penso questa soluzione fa un ottimo lavoro di manipolazione. 

La prima è avere una sorta di commento di intestazione in alto. Sulle linee da 1 a 7 si vedono i dettagli, che cosa è esattamente questo programma sta facendo. Una buona pratica standard quando si sta scrivendo codice C indipendentemente se il programma è contenuto all'interno di un singolo file o se è suddiviso su più file è quello di avere una sorta di orientando commento in cima. Questo è anche per le persone che escono e scrivere il codice nel mondo reale. Questo è dove metterò le informazioni sul copyright. Qui sotto trovi gli # include. Sulla linea 16 c'è questa # define, che torneremo a tra poco. E poi una volta che la funzione avvia, si avvia una volta i principali, perché questo programma è tutto contenuto in una singola funzione la prima cosa che accade, e questo è molto idiomatico e tipico di un programma C che accoglie gli argomenti della riga di comando, è che si verifica immediatamente 

per il numero di argomenti, argc. Proprio qui si vede che il programma si aspetta esattamente 2 argomenti. Ricordate che ci sono che il primo argomento che è la speciale che è sempre il nome del programma che è in esecuzione, il nome del file eseguibile. E così ciò che questo non fa altro che impedisce all'utente di eseguire il programma con argomenti più o meno. La ragione per cui si vuole verificare la presenza di questo subito è dovuto al fatto non si può effettivamente accedere a questo array argv qui affidabile fino a quando abbiamo controllato per vedere quanto è grande. 

Uno degli errori più comuni che ho visto è stata la gente subito andare in e afferrare argv [1]. Avevano afferrare l'argomento chiave dalla matrice e le differenze tra la a per controllare i su di esso, e poi che avrebbero fatto il test per argc e il prossimo test, se il primo argomento era effettivamente un intero al tempo stesso, e che non funziona perché nel caso in cui non ci sono argomenti forniti ti verrà afferrando un argomento che non c'è o il tentativo di afferrare quello che non c'è. 

L'altra cosa importante che si deve notare è che hai sempre voglia di stampare una sorta di messaggio di errore utile per l'utente di orientarli. Sono sicuro che hai tutti i programmi in esecuzione, dove tutto ad un tratto si blocca, e si ottiene questa finestra di dialogo po 'ridicolo che si apre e dice: qualcosa di terribilmente criptico e magari ti dà un codice di errore o qualcosa di simile che non ha senso. Questo è dove si vuole veramente offrire qualcosa di utile e mirate per l'utente in modo che quando si esegue vanno "Oh," faccia di palma. "So esattamente cosa fare. So come risolvere questo problema." 

Se non si stampa un messaggio, poi si finisce in realtà lasciando all'utente di andare a esaminare il codice sorgente per capire cosa è andato storto. Ci sono anche alcune volte che si usano diversi codici di errore. Qui abbiamo usato solo uno a dire che c'era un errore, c'è stato un errore, c'è stato un errore. Più grandi programmi, spesso i programmi che vengono richiamati da altri programmi, restituisce una sorta di codici di errore speciali in diversi scenari per comunicare di programmazione quello che sarebbe altrimenti basta usare un bel messaggio inglese per. Cool. Mentre lavoriamo in basso, si può vedere tiriamo fuori la chiave. Ci prova per vedere se la chiave adatta. Abbiamo un messaggio da parte dell'utente. Il motivo per cui lo facciamo in questa do while, e questo è qualcosa che ci occuperemo in un po ', ma si scopre che se si digita il controllo D quando si ottiene che GetString prompt del terminale quello che in realtà è esso invia un carattere speciale al programma. Si chiama ELF o il carattere di fine file. E in quel caso, la nostra stringa di messaggio sarà nullo, quindi questo non era qualcosa che abbiamo controllato per il problema posto stesso. 

Ma andiamo avanti, ora che abbiamo cominciato a parlare di puntatori e l'allocazione dinamica della memoria sul mucchio, controllo per nulla ogni volta che si dispone di una funzione che potrebbe ritorna null come valore è qualcosa che si vorrà prendere l'abitudine di fare. Questo è qui principalmente per illustrazione. Ma quando si fa vedere GetString in futuro, così da Problema Set 4 in poi, ti consigliamo di tenere questo in mente. Ancora una volta, questo non è un problema per problema Set 3 o dato che non l'aveva ancora coperto. Infine, si arriva a questa parte, dove si arriva al ciclo di crittografia principale, e ci sono un paio di cose che accadono qui. In primo luogo, scorrere la stringa intero messaggio stesso. Qui abbiamo mantenuto la strlen chiamata nella condizione, che molti di voi hanno sottolineato non è un ottimo modo per andare. Si scopre in questo caso non è anche un ottimo, in parte perché stiamo modificando il contenuto del messaggio stesso all'interno del ciclo for, quindi se abbiamo un messaggio che è 10 caratteri, la prima volta che si parte per il ciclo strlen tornerà cosa? 10. 

Ma se quindi modificare il messaggio, dire che modificare il suo carattere 5th, e ci buttiamo in un carattere \ 0 in 5 ° posizione, su una iterazione successiva strlen (messaggio) non restituirà quello che ha fatto la prima volta abbiamo iterato, ma sarà invece restituisce 5 perché abbiamo buttato in quel terminatore null, e la lunghezza della stringa è definita dalla posizione che \ 0. In questo caso, questo è un ottimo modo per andare, perché lo stiamo modificando in posizione. Ma si nota che questo è in realtà sorprendentemente semplice per crittografare se è possibile ottenere la matematica corretta. Tutto ciò che è richiesto è quello di verificare se la lettera che si sta guardando è maiuscolo o minuscolo. 

La ragione per cui non ci resta che verificare la presenza di questo e non si deve controllare da è il caso alfa è perché se un personaggio è maiuscola o se è minuscolo allora è sicuramente un carattere alfabetico, perché non abbiamo cifre maiuscole e minuscole. L'altra cosa che facciamo, e questo è un po 'difficile, è che abbiamo modificato la norma cifrario di Cesare formula che abbiamo dato nella specifica set problema. Cosa c'è di diverso è che abbiamo sottratto nella capitale caso A maiuscola, e poi abbiamo aggiunto maiuscola eseguire in alla fine. 

So che alcuni di voi hanno fatto questo nel codice. Forse qualcuno di voi fare questo nelle vostre osservazioni? Sei stato tu. Ci può spiegare cosa fa, SAHB? Sottraendo fuori, perché hai fatto un mod a destra dopo, si deve prendere fuori, in modo che modo si ottiene [tosse] posizione. E poi con l'aggiunta di nuovo in seguito si spostò su quello che si voleva. Sì, esattamente. Che SAHB detto è che quando vogliamo aggiungere il nostro messaggio e la nostra chiave insieme e poi mod che, mod tale da NUM_LETTERS, se non si scala il nostro messaggio negli appositi 0-25 primo intervallo, allora potremmo finire per ottenere un numero davvero strano perché i valori che stiamo guardando quando guardiamo messaggio [i], quando si guarda il carattere i-esimo del nostro testo normale messaggio, è un valore compreso in questo intervallo 65-122 in base ai valori ASCII per maiuscola attraverso z minuscola. E così quando la mod da 26 o da NUM_LETTERS, dato che era il nostro # define in alto a destra qui, che sta per darci un valore che è nel campo da 0 a 25, e abbiamo bisogno di un modo per ridimensionare allora che il backup e lo fanno nel range appropriato ASCII. Il modo più semplice per farlo è quello di scalare solo tutto giù nel campo da 0 a 25 per cominciare, e poi passare tutto torna alla fine. 

Un altro errore comune che ho visto la gente correre in è che se non effettivamente fare questo ridimensionamento subito e si aggiunge il messaggio e la chiave insieme e li aggiungi, ad esempio, in una variabile char, il problema con questo è dal messaggio [i] è un numero relativamente grande per cominciare- ricordatevi che è almeno il 65 se si tratta di un carattere maiuscolo- se si dispone di una grossa chiave, ad esempio, qualcosa come 100, e si aggiunge quei 2 insieme in un signed char che si vuole ottenere un overflow. Hai intenzione di ottenere un valore che è più grande di 127, che è il valore più grande che una variabile char può contenere. Anche in questo caso, è per questo che ci si vuole fare una cosa del genere per cominciare. Alcuni hanno intorno a quel caso per fare un if else e collaudo per vedere se sarebbe troppo pieno prima di farlo, ma in questo modo diventa intorno a quella. E poi in questa soluzione abbiamo stampato l'intera stringa alla fine. Altre persone stampato un carattere per volta. Entrambi sono impressionanti. A questo punto, voi ragazzi avete domande, commenti su questo? Cose che ti piacciono, le cose che non ti piacciono? 

Avevo una domanda. Forse ho perso durante la spiegazione, ma come fa questo programma saltare gli spazi per collegare la chiave per la lunghezza del testo? Questo è solo cifrario di Cesare. >> Oh, scusa, si '. Gia ', vedremo che. Nel cifrario di Cesare abbiamo ottenuto intorno che, a causa abbiamo solo girato caratteri. Abbiamo solo loro ruotate se fossero lettere maiuscole o minuscole. Voi ragazzi sentirsi abbastanza bene su questo? Sentitevi liberi di copiare questa casa, la prenda, confrontarlo con quello che voi scritto. Sicuramente non esitate a inviare domande su di esso troppo. E ancora, si rendono conto che l'obiettivo qui con il vostro problema imposta non è quello di ottenere voi per scrivere il codice perfetto per i vostri set di problemi. E 'una esperienza di apprendimento. Gia '. 

Torna alla do while, se è uguale a zero, quindi nullo significa proprio niente, hanno solo premere invio? Null è un valore speciale puntatore, e usiamo nullo quando vogliamo dire abbiamo una variabile puntatore che punta a nulla. E così di solito vuol dire che questa variabile, la variabile messaggio è vuota, e qui, perché stiamo usando il CS50 particolare tipo di stringa, qual è il tipo di stringa CS50? Hai visto quello che è quando David tirò indietro il cappuccio in conferenza? Si tratta di un funky-è un puntatore, giusto? Ok, si '. >> E' un char *. E così davvero si potrebbe sostituire questo proprio qui, con messaggio char *, e quindi la funzione GetString, se non correttamente ottenere una stringa dall'utente, non è possibile analizzare una stringa, e un caso in cui non si può analizzare una stringa è se l'utente digita il carattere di fine file, il controllo D, che non è qualcosa che di solito fare, ma se ciò accade allora la funzione restituisce il valore null come un modo di dire "Ehi, non ho avuto una stringa." Che cosa accadrebbe se non mettiamo messaggio = null, che è qualcosa che non abbiamo fatto ancora? Perchè dovrebbe essere un problema? Perché so che abbiamo parlato un po 'in conferenza sulle perdite di memoria. Si ', facciamolo, e vediamo cosa succede. 

Domanda Basilio era cosa succede se in realtà non hanno questo messaggio di prova = null? Facciamo scorrere fino alla cima. Voi ragazzi potete commentare questo fuori. A dire il vero, io lo salvo in una revisione. Questo sarà revisione 3. Quello che dovrete fare per eseguire questo programma è che dovrete fare clic su questa icona ingranaggio qui, e si dovrà aggiungere un argomento ad esso. Dovrete dare l'argomento chiave dal momento che desidera passare un argomento della riga di comando. Qui ho intenzione di dare il numero 3. Mi piace 3. Ora lo zoom indietro, l'esecuzione del programma. E 'in esecuzione, la compilazione, la costruzione. Ci siamo. E 'in attesa di essere richiesto. Se digito qualcosa come ciao, dove e 'andata? Oh, il mio programma ha impiegato troppo tempo per l'esecuzione. Ero jawing per troppo tempo. Qui si va. Ora digitare ciao. Vediamo che esegue la crittografia in modo appropriato. Ora, cosa succede se facciamo GetString richiesta di restituire null? Ricordate, ho detto che abbiamo fatto che premendo il controllo D, allo stesso tempo. Io scorrere verso l'alto qui. Ci funzionare ancora. Edificio. Ci va. Ora, quando ho colpito il controllo D Ho ottenuto questa linea che dice opt/sandbox50/bin/run.sh, Segmentation fault. Avete visto prima? 

[Studente] Perché non c'è nessuno >> Scusa? [Studente] Perché non c'è nessuna core dump in questo caso? Il core dump è la domanda è:-perché non c'è core dump qui? Il problema è che ci possono essere, ma il core dump è un file che viene memorizzato sul disco rigido. In questo caso abbiamo disattivato i core dump sul server di esecuzione in modo che non ci sono persone che ha provocato l'errore seg e costruire tonnellate di core dump. Ma si può ottenere uno. I core dump sono il genere di cose che spesso è possibile disabilitare, e qualche volta si fa. L'errore di segmentazione, per rispondere alla tua domanda, Basilico, sta dicendo che abbiamo cercato di accedere a un puntatore che non è stato impostato per puntare a qualcosa. Ricorda Binky nel video, quando cerca di Binky vai accedere a un puntatore che non sta puntando a qualcosa? In questo caso credo che tecnicamente il puntatore punta a qualcosa. Si punta a nulla, che è tecnicamente 0, ma che è definito per essere in un segmento che non è accessibile dal programma, in modo da ottenere un errore di segmentazione perché non stai accedendo alla memoria che è in un segmento valido come il segmento cumulo o segmento di stack o il segmento di dati. Cool. Altre domande su Cesare? 

Andiamo avanti. Diamo un'occhiata a revisione 2 molto velocemente. Questo è Vigenère. Qui in Vigenère faremo a piedi attraverso questo abbastanza in fretta perché, ancora una volta, Vigenère e Cesare sono molto simili. Commento Header è prima, # Define è prima di evitare l'uso di questi numeri magici. La cosa bella è dire che volevamo passare a un alfabeto diverso o qualcosa di simile. Anziché dover modificare manualmente tutti i 26 nel codice si potrebbe cambiare questo a 27 o cadere verso il basso se stessimo utilizzando alfabeti diversi, lingue diverse. Ancora una volta, abbiamo questo controllo del numero di argomenti, e davvero si può quasi prendere questo come un modello. Praticamente tutti i programmi che scrivi dovrebbe avere- se ci vogliono gli argomenti della riga di comando-una sequenza di linee che si legge come questo all'inizio. Questo è uno dei test di integrità prima che si desidera fare. 

Ecco quello che abbiamo fatto è stato che abbiamo fatto in modo che la parola chiave è valida, e che è stato il secondo controllo che abbiamo fatto. Si noti ancora una volta che ci siamo separati da questo argc e 2. Si noti che in questo caso una cosa che abbiamo dovuto fare è stato invece di utilizzare una per i abbiamo voluto convalidare l'intera stringa, e per fare che in realtà andare carattere per carattere sopra la corda. Non c'è buon modo per chiamare qualcosa su di esso perché anche, per esempio, da A a I restituirà 0 se non in grado di analizzare un numero intero, in modo che non funziona nemmeno. Anche in questo caso, bel messaggio che dice all'utente esattamente quello che è successo. Poi qui, ancora una volta, abbiamo anche gestire il caso in cui l'utente digita in un carattere di controllo D casuale. 

E poi Charlotte aveva una domanda in precedenza su come riusciamo a saltare gli spazi nella nostra stringa qui. Questo era un po 'simile a quello che abbiamo fatto con il programma di Myspace che abbiamo fatto in sezione, e il modo in cui questo ha funzionato è che abbiamo rintracciato il numero di lettere che avevamo visto. Mentre camminavamo sulla stringa del messaggio, come abbiamo attraversato carattere per carattere, abbiamo seguito l'indice come parte del nostro ciclo for, e poi abbiamo anche rintracciato il numero di lettere, in modo da non caratteri speciali, non-cifre, non bianco spazio che avevamo visto nella variabile separata. E poi questa soluzione modifica la chiave per ottenere un numero intero effettivo della chiave, e lo fa al volo, destra prima che vada poi per crittografare il carattere effettivo del messaggio. Ci sono alcune soluzioni che erano perfettamente troppo grande che modificare la chiave quando il test per la validità della chiave. Oltre a fare in modo che il carattere e la parola chiave è stato un carattere alfabetico che è anche trasformato in un numero intero nel campo da 0 a 25 a saltare poi dover fare avanti in questo ciclo for. Anche in questo caso, che vedete qui questo è davvero il codice esattamente lo stesso che abbiamo usato in Cesare, a questo punto. Stai facendo la stessa cosa, in modo che il vero trucco è capire come trasformare la parola chiave in un numero intero. 

Una cosa che abbiamo fatto qui che è un po 'denso è abbiamo ripetuto questa frase, penso che si potrebbe chiamare, 3 volte separate linee 58, 59, e 61. Qualcuno può spiegare che cosa è esattamente questa frase fa? E 'l'accesso a un personaggio, come hai detto tu. Si ', e' [incomprensibile] un personaggio la parola chiave, e quindi è il numero di lettere visto perché si sta solo muovendo la parola chiave una volta che hai visto la lettera, modo che sta per saltare in modo efficace gli spazi e cose del genere. Sì, esattamente. E poi una volta che hai visto la vuota parola chiave che avete appena mod in modo da tornare indietro in giro. Esattamente. Questa è una spiegazione perfetta. Che cosa ha detto Kevin è che vogliamo per indicizzare la parola chiave. Vogliamo ottenere il carattere num_letters_seen, se si vuole, ma se num_letters_seen supera la lunghezza della parola chiave, il nostro modo di tornare in campo appropriato è usiamo l'operatore mod per avvolgere in modo efficace in giro. Ad esempio, come nel breve, la nostra parola chiave è pancetta, ed è lunga 5 lettere. Ma abbiamo visto 6 lettere nel nostro testo in chiaro, a questo punto e criptato 6. Si finirà per l'accesso alla num_letters_seen, che è 6, mod la lunghezza della parola chiave, 5, e così avremo 1, e così quello che faremo è faremo accedere all'interno del primo carattere della nostra parola chiave in quel punto. 

Va bene, tutte le questioni sui Vigenère prima di andare avanti? Voi ragazzi sentirsi abbastanza bene su questo? Cool, grande. Voglio fare in modo che voi ragazzi sono sempre la possibilità di vedere il codice che noi pensiamo sembra buono e hanno la possibilità di imparare da esso. Questo sarà l'ultimo che useremo gli spazi per il momento, e abbiamo intenzione di transizione adesso, e ho intenzione di andare a cs50.net/lectures in modo che possiamo fare un po 'di revisione quiz. Il modo migliore penso di iniziare a fare quiz recensione è quello di venire in questa pagina Lectures, cs50.net/lectures, e sotto ciascuna delle rubriche settimana, quindi se guardo qui alla settimana 0, Vedo che abbiamo un elenco di argomenti che abbiamo trattato nella Settimana 0. 

Se uno qualsiasi di questi argomenti sembra sconosciuto a voi avrete sicuramente voglia di tornare indietro e setacciare gli appunti delle lezioni e, eventualmente, anche sfogliare le lezioni, li guarda ancora una volta, se si desidera per avere un'idea di quello che sta succedendo con ciascuno di questi argomenti. Devo dire inoltre questo un anno di risorse fresche che abbiamo ottenuto Sono questi i pantaloncini che abbiamo creato, e se si guarda alla settimana 0, non abbiamo tutti gli argomenti trattati, ma abbiamo un bel po 'di loro, alcuni di quelli più ingannevoli, così guardando questi pantaloncini nuovo è un buon modo per arrivare fino a velocità. In particolare, ho intenzione di mettere in una presa per il 3 sul fondo, da quando ho fatto quelle. Ma se siete alle prese con binario, bit, esagonali, quel genere di cose, binario è un ottimo punto di partenza. ASCII è un altro questo è un bene per vedere troppo. È anche possibile guardare me a velocità 1,5 x se sto andando troppo lento per voi. Dal momento che è recensione, non esitate a farlo. 

Tanto per iniziare molto velocemente, stiamo per passare attraverso un paio di questi problemi quiz solo per sfornare velocemente attraverso questi. Per esempio, diamo un'occhiata a un problema 16 che ho proprio qui sul tavolo. Abbiamo questa seguente calcolo in binario, e vogliamo mostrare qualsiasi lavoro. Va bene, ho intenzione di dare a questo un colpo. Voi ragazzi dovrebbero seguire con la carta, e lo faremo molto velocemente. Vogliamo eseguire il seguente calcolo in binario. Ho 00110010. E ho intenzione di aggiungere ad essa 00110010. Per la matematica geni segue lungo a casa, questo è effettivamente moltiplicare per 2. Cominciamo. Stiamo per seguire lo stesso algoritmo inoltre che facciamo quando aggiungiamo i numeri decimali insieme. In realtà l'unica differenza è che noi loop back intorno una volta che abbiamo 1 + 1 invece di una volta si arriva a 10. 

Se si parte da destra, molto rapidamente, qual è la prima cifra? [Studente] 0. >> [Nate H] 0. Grande, la seconda cifra? [Studente] 1. [Nate H] E 'un 1? 1 + 1 è? [Studente] 10. [Nate H.] Esattamente, quindi qual è la cifra che scrivo proprio sotto le 2 quelli aggiunti insieme? [Studente] 1, 0, o 0 e poi portare la 1. [Nate H] 0 e portare a 1, esattamente. Next up uno, Basil, tocca a te. Qual è il terzo? >> [Basilio] 1. [Nate H.] 1, perfetto. Kevin? [Kevin] 0. >> [Nate H] 0, Charlotte? [Charlotte] 0. >> [Nate H] Si ', e cosa devo fare? [Studente] Il 1. [Nate H] E cosa devo fare? E poi portare la 1. Perfetto, SAHB? >> [SAHB] Ora avete 1. [Nate H] E devo fare qualcosa qui? [SAHB] Allora per il prossimo si dispone di 1 perché riportati 1. [Nate H.] Grande, ecco che possiamo finire. Cool. [Studente] Fa 0 + 0 = 0? 0 + 0 = 0. 1 + 1, come hai detto tu, è di 10, o 1, 0, piuttosto. 10 è un termine improprio, perché per me 10 significa il numero 10, ed è il capriccio di come lo stiamo rappresentando quando stiamo scrivendo. Abbiamo rappresentano il numero 2 di 1, 0, e il numero 10 è leggermente diverso. 

Che tipo di bello di binario è che in realtà non sono che molti casi che dovete imparare. Ci sono 0 + 0 = 0, 0 + 1 = 1, 1 + 1 è 0, e poi portare a 1, e poi si può vedere qui sulla terza colonna da destra abbiamo avuto questa 1, 1, e 1. E 1 + 1 + 1 è un 1, e di portare un altro 1. Quando si sta facendo somma binaria, piuttosto semplice. Mi piacerebbe fare un altro paio di questi per voi stessi verificare sanità mentale prima di andare in, perché questo è probabilmente qualcosa che vedremo sul quiz. Ora facciamo questo anche il prossimo. Facciamo problema 17. Abbiamo intenzione di convertire il numero binario in decimale. Ho 10100111001. Ricordate nel video binario che ho fatto Ho camminato attraverso un paio di esempi, e mi ha fatto vedere come tutto funziona quando si sta facendo in decimale. Quando si lavora in rappresentazione decimale penso che siamo a questo punto della nostra vita in modo fluente in esso che è abbastanza facile a sorvolare il meccanismo di come funziona realmente. 

Ma per fare un breve riepilogo, se ho il numero 137 questo significa-e davvero di nuovo, questo è in rappresentazione decimale- il numero 137 in decimale significa che ho 1 x 100 + 3 x 10 + 7 x 1. Questo è tutto rimanendo sullo schermo. E poi se si guarda a questi numeri proprio qui, 100, 10 e 1, si vede che sono in realtà tutte le potenze di 10. Ho 10 ², 10 ¹, e 10 al punto zero. Abbiamo una sorta di cosa simile in binario, eccezione del fatto che la nostra base, come lo chiamiamo noi, è di 2 invece di 10. Questi 10s che ho scritto qui in basso, questo 10 ², 10 ¹, 10 allo zero, il 10 è la nostra base, e l'esponente, 0, 1, o 2, è implicito nella posizione della cifra del numero che scrivere. 1, se lo guardiamo, questo 1 è in 2 ° posizione. Il 3 è in posizione di prima, e il 7 è nella posizione di indice 0. È così che si ottengono i vari esponenti di seguito per le nostre basi. 

A seguito di tutto questo venite-in realtà, sai una cosa? Faremo, dove ha fatto il mio pulsante Annulla andare? Ci va. Amo questo annulla cosa. A seguito di questo credo che per me almeno il modo più semplice per avviare la conversione di un numero binario o un numero esadecimale in cui la base è 16 e non 10 o 2 è di andare avanti e scrivere le basi e gli esponenti di tutti i numeri nel mio numero binario in alto. Se si parte da sinistra a destra di nuovo, che è una specie di contro-intuitivo, Io tornare in nero qui, abbiamo il 2 alla posizione 0, e poi abbiamo 2 ¹, 2 ², e poi 2 alla 3, 2 alla 4, 2 alla 5, 6, 7, 8, 9, e 10. Questi numeri che ho scritto su tutti gli esponenti. Ho solo scritto le basi qui in primi 3 solo per lo spazio. 

A questo punto ho intenzione di andare avanti e sto andando a cancellare le cose che abbiamo fatto in decimale, se va bene. Hai capito tutto. Quelli di voi la visione di Sono sicuro che sarà in grado di riavvolgere me se vuoi. Ritornando alla penna. Ora, ciò che possiamo fare, se voi ragazzi non sono del tutto fino a velocità sulle potenze di 2, che è assolutamente cool. Succede. Capisco. Una volta ho avuto un colloquio di lavoro in cui mi è stato detto che dovrei conoscere tutte potenze di 2 fino a 2 per il 30. Non è stato un lavoro che ho ottenuto. Ad ogni modo, voi potete andare avanti e fare la matematica qui, ma con binario in realtà non ha senso, e non ha senso con decimale o esadecimale o, per fare i calcoli su cui si dispone zeri. Potete vedere che ho 0 per questo, qui a 0, 0 qui, 0 qui, 0 qui, 0 qui. Perché non potrebbe avere senso fare i calcoli reale per calcolare la potenza appropriata di 2 per quella posizione? Esattamente, come Charlotte ha detto, sarà 0. Tanto vale risparmiare il tempo se il calcolo potenze di 2 non è il tuo forte. In questo caso abbiamo solo bisogno di calcolarlo per 2 a 0 che è-? [Studente] 1. [Nate H.] 1, 2 alla 3 che è-? [Studente] 8. >> [Nate H] 8. 2 alla 4? [Studente] 2. Mi dispiace, 1. [Nate H] 2 ​​al 4 è 16, esattamente. 2 alla 5, Kevin? >> 32. [Nate H.] 32, 2 alla 8? [Studente] 32 x 8, 256. [Nate H] Perfetto. E 2 al 10? [Studente] 1024. [Nate H.] Si ', 1024. 

Una volta che abbiamo questi numeri si possono sintetizzare tutti in su. Ed è qui che è davvero importante per fare un paio di cose. Uno è andare piano e controllare il vostro lavoro. Si può dire che c'è un 1 alla fine di questo numero, quindi dovrei sicuramente ottenere un numero dispari come il mio risultato, perché tutti gli altri stanno per essere numeri pari dato che si tratta di un numero binario. L'altra cosa da fare è se si arriva a questo punto della prova e tu l'hai scritto fino a questo punto e sei a corto di tempo guardare il numero di punti che questo problema vale. Questo problema, come potete vedere, se mi capovolgere di nuovo al mio computer portatile molto velocemente- questo problema vale 2 punti, quindi questo non è il tipo di aggiunta si dovrebbe passare attraverso se siete veramente a corto di tempo. Ma noi tornare alla iPad, e andremo attraverso di essa molto velocemente. 

Mi piace fare i numeri prima i più piccoli perché trovo che facile. Mi piace 32 e 8, in quanto vanno insieme abbastanza facilmente, e si ottiene 50. 16 e 1 diventa 17. Ci si ottiene 57, e poi possiamo fare il resto di questo, in modo che possiamo fare 57, 156. Andiamo. L'uomo, beh, vediamo. Abbiamo avuto l '57, 256, e 1024. A questo punto, preferisco solo passare attraverso. Non ho nessuna idea. Ho chiaramente bisogno di leggere su questo. 7, 6, e 4, si ottiene 17. 1, 5, 5, 2, 13. Allora otteniamo 3, quindi si ottiene 1. 1337. Uovo di Pasqua, nessuno? Chiunque riconosce questo numero? Chris riconosce il numero. Che cosa significa, Chris? [Chris] Leet. Leet, quindi se si guarda a questo, sembra che leet. Hacker roba. Attenzione per questo genere di cose sul medio termine o il quiz, piuttosto. Se vedi che tipo di roba e ti stai chiedendo "Eh," che potrebbe effettivamente significare qualcosa. Non lo so. David ama mettendo trovi E 'un buon modo per verificarlo sanità mentale. Come va bene, riesco a vedere cosa sta succedendo. 

E 'Settimana 0/Week 1 roba. Se si passa di nuovo al nostro computer portatile ora, zoom out, e un paio di altre cose. Ci sono ASCII, che abbiamo fatto un sacco di problemi con il set. Questa nozione di capitale A. Che cosa è davvero? Sapendo che è il numero intero decimale. 65 è quello che è mappato nella tabella ASCII, ed è, quindi, come il computer scrive, ed è così che abbiamo ricevuto via nella scrittura la capitale carattere A e il carattere minuscolo una in alcune di queste soluzioni e set di problemi che hai fatto. Un paio di altre cose. Abbiamo istruzioni, le espressioni booleane, condizioni, cicli, variabili e fili. 

Quelli che tutti sembrano avere un senso per la maggior parte? Alcune di questa terminologia è un po 'funky, a volte. Mi piace pensare di una dichiarazione come per la maggior parte qualcosa che termina con un punto e virgola. Affermazioni come x = 7, che definisce una variabile, presumibilmente chiamato x = 7. Presumibilmente x è anche un tipo in grado di memorizzare il numero 7, quindi è un int o, eventualmente, di un galleggiante o di un breve o un char, qualcosa del genere. Un'espressione booleana utilizza questi doppio uguale e il bang uguale o non uguale, inferiore, superiore, inferiore o uguale a, tutto quel genere di cose. Condizioni quindi sono dichiarazioni if ​​else. Vorrei ricordare che non si può avere un altro senza un corrispondente se. Allo stesso modo, non si può avere un altro se senza un corrispondente se. Loops, ricordano i 3 tipi di loop siamo stati martellare dentro di te per l'ultimo paio di sezioni e set problema. Uso della funzione mentre quando stai ricevendo l'input dell'utente, Uso dei cicli while fino a quando una determinata condizione è vera, e quindi utilizzando i cicli for, se avete bisogno di sapere quale iterazione del ciclo Attualmente sei su è come ci penso. Oppure, se si sta facendo una per ogni carattere in una stringa che voglio fare qualcosa, per ogni elemento in una matrice che voglio fare qualcosa per tale elemento. 

Discussioni ed eventi. Questi non abbiamo trattato in modo così esplicito in C, ma ricordate che questo da zero. Questa è l'idea di avere diversi script. Questo è anche questa idea di trasmettere un evento. Alcune persone non si utilizza la trasmissione nei loro progetti inizialmente, che è assolutamente cool, ma questi sono 2 modi diversi di affrontare il problema più grande chiamato concorrenza, che è come si fa a ottenere i programmi da eseguire o apparentemente eseguire allo stesso tempo? Vari task in esecuzione, mentre altre attività sono in corso anche. Ecco come il sistema operativo sembra funzionare. Ecco perché, anche se, per esempio, Ho ottenuto il mio browser in esecuzione, posso anche attivare Spotify e suonare una canzone. Questo è più di una cosa concettuale da capire. Vorrei dare un'occhiata a dei fili corti se volete saperne di più su questo. 

Vediamo un po ', credo che ci sarebbe stato un problema su questo in uno di questi. Anche in questo caso, credo che le discussioni e gli eventi non sono qualcosa che tratteremo in C solo perché è molto più difficile che in Scratch. Non si deve preoccupare lì, ma sicuramente capire i concetti, capire cosa sta succedendo. Prima di andare avanti, di chiarimenti in merito Settimana 0 materiali? Ognuno sente abbastanza bene? Capire le variabili e ciò che è una variabile? 

Passando. Settimana 1. Un paio di cose qui che non erano particolarmente coperti nella revisione quiz necessariamente e sono anche cose più concettuali a cui pensare. La prima è questa nozione di ciò che del codice sorgente, compilatori e il codice oggetto sono. Nessuno? Basil. E 'di codice oggetto, voglio dire il codice sorgente è ciò che si mette in clang, e il codice oggetto è ciò che clang mette in modo che il computer in grado di leggere il programma. Esattamente. Il codice sorgente è il codice C che effettivamente digitare fino. Il codice oggetto è quello che si ottiene fuori clang. E 'il 0 e 1 in quel formato binario. Allora che cosa succede quando si ha un gruppo di file oggetto, dire che sta compilando un progetto o di un programma che utilizza più file di codice sorgente, che, per convenzione viene data la estensione di file. c. Questo è il motivo per cui abbiamo caesar.c, vigenère.c. Se state scrivendo programmi Java si dà loro l'estensione. Java. Programmi Python hanno l'estensione. Py spesso. 

Una volta che si dispone di più. File c, averli compilati. Clang sputa fuori tutta questa spazzatura binario. Allora perché si vuole solo 1 programma avete il link linker tutti questi oggetti file insieme in 1 file eseguibile. Questo è anche ciò che accade quando si utilizza la libreria CS50, per esempio. La biblioteca CS50 è sia quello. File di intestazione h di leggere, che # includecs50.h. E poi è anche uno speciale file di libreria binario che è stato compilato che è 0 e 1, e che-l, quindi se torniamo ai nostri spazi e non vediamo molto velocemente a quello che sta succedendo qui quando guardiamo al nostro comando clang, quello che abbiamo è questo è il nostro file di codice sorgente qui. Si tratta di un gruppo di flag di compilazione. E poi alla fine, questi-l collegamento bandiere i file binari effettivi per questi 2 biblioteche, la CS50 biblioteca e poi la libreria matematica. 

Comprendere ogni tipo di oggetto file ' nel processo di compilazione è qualcosa che si desidera essere in grado di dare almeno una panoramica di alto livello di. Il codice sorgente entra in codice oggetto viene fuori. File di codice oggetto collegare tra loro, e si ottiene una bella, file eseguibile. Cool. Questo è anche il luogo dove è possibile ottenere gli errori in più punti nel processo di compilazione. E 'qui che, ad esempio, se si prende questo flag di collegamento, il CS50 bandiera, e si omette in spazi o quando si esegue il codice, questo è dove si ottiene un errore in fase di collegamento, e il linker dirà: "Ehi, hai chiamato una funzione GetString che è nella libreria CS50. " "Mi hai detto che era nella biblioteca CS50, e non riesco a trovare il codice per questo." È lì che si deve collegare in, e questo è separato da un errore di compilazione, perché il compilatore sta guardando sintassi e questo genere di cose. E 'bene sapere cosa sta succedendo quando. 

Altre cose da sapere. Direi che è sicuramente desidera dare un'occhiata al corto di fusione di caratteri fatto da Jordan di capire quali interi sono sotto il cofano, quali caratteri sono sotto il cofano. Quando si parla di ASCII e in realtà abbiamo guardare la tabella ASCII, quello che sta facendo ci sta dando una sotto lo sguardo cofano il modo in cui il computer rappresenta in realtà maiuscola e la cifra 7 e una virgola e un punto interrogativo. Il computer ha anche modi speciali per rappresentare il numero 7 come numero intero. Ha un modo speciale per rappresentare il numero 7 come numero in virgola mobile, e questi sono molto diversi. Typecasting è il modo per dire al computer "Ehi, voglio di convertire da una rappresentazione ad un'altra rappresentazione. " Perché non dare un'occhiata a questo. 

Vorrei anche dare un'occhiata al breve sulle biblioteche e il corto di compilatori. Quelli parlare del processo di compilazione, ciò che una biblioteca è, e andare oltre alcune di queste domande che si potrebbe ottenere chiesto. Domande sulla Settimana 1 materiale? Ci sono argomenti di qui che sembrano scoraggiante vorresti coprire? Sto cercando di saltare attraverso la maggior parte di questi argomenti precedenti in modo che si possa arrivare a puntatori e fare un po 'di ricorsione. Pensieri? Qualcosa da coprire? Tempo per un po 'di cioccolata, magari? Voi ragazzi stanno lavorando attraverso di essa. Ho intenzione di continuare sorseggiando il mio caffè. Settimana 2. Buona idea, buona chiamata. In settimana 2 abbiamo parlato un po 'di più sulle funzioni. 

Nel primo set qualche problema non abbiamo davvero scrivere tutte le funzioni a tutti , anche se tale funzione? [Studente] principale. >> Principale, esattamente. E così abbiamo visto i diversi costumi che indossa principale. C'è quello in cui essa non accetta argomenti, e ci limitiamo a dire nulla tra le parentesi, e poi c'è l'altro dove si vuole prendere gli argomenti della riga di comando, e come abbiamo visto, è lì che avete int argc e argv array di stringhe o ora che abbiamo effettivamente esposti stringa di essere il char * che si tratta di stiamo per iniziare a scrivere come char * argv e poi staffe. In Set Problema 3, voi ragazzi ha visto un sacco di funzioni, e implementato una serie di funzioni, disegnare, guardare in alto, scramble. I prototipi sono stati tutti scritti lì per voi. 

Quello che volevo parlare qui con funzioni molto rapidamente è che ci sono 3 parti a loro ogni volta che si scrive una funzione. È necessario specificare il tipo di ritorno della funzione. È necessario specificare un nome per la funzione e quindi è necessario specificare l'elenco degli argomenti o la lista dei parametri. Per esempio, se dovessi scrivere una funzione per riassumere un po 'di numeri interi e poi tornare da me la somma ciò che sarebbe stato il mio tipo di ritorno se volessi riassumere interi e quindi restituire la somma? Quindi il nome della funzione. Se vado avanti e scrivere in verde, questa parte è il tipo restituito. Questa parte è il nome. E poi, tra parentesi è dove io do gli argomenti, spesso abbreviato in args, a volte chiamati params per i parametri. E se ne avete uno, è sufficiente specificare l'uno. Se si dispone di più di separare ognuno con una virgola. E per ogni argomento si dà 2 cose che sono, Kevin? [Kevin] Dovete dare il tipo e poi il nome. E poi il nome, e il nome è il nome che avete intenzione di usare per fare riferimento a tale argomento all'interno della funzione somma, all'interno della funzione che si sta scrivendo. 

Non è per-ad esempio, se ho intenzione di riassumere, diciamo, un array di interi-we'll do array di int, e io mi do alcune parentesi graffe vi- poi quando ho passare un array alla funzione somma Lo passo al primo posto della lista degli argomenti. Ma la matrice che mi passa in non avere il nome arr. Arr. sta per essere come mi riferisco a tale argomento all'interno del corpo della funzione. L'altra cosa che abbiamo bisogno di prendere in considerazione, e questo è leggermente diverso dalle funzioni, ma credo che sia un punto importante, è che in C, quando sto scrivendo una funzione come questa come faccio a sapere quanti elementi sono in questo array? Questo è un po 'di una domanda trabocchetto. Ne abbiamo parlato un po 'nella sezione della scorsa settimana. Come faccio a sapere il numero di elementi all'interno di un array in C? C'è un modo? 

Si scopre che non c'è modo di saperlo. Devi passare in parte. C'è un trucco che si può fare se siete nella stessa funzione in cui l'array è stato dichiarato, e si sta lavorando con una matrice di stack. Ma questo funziona solo se siete nella stessa funzione. Una volta che si passa una matrice a un'altra funzione o se si è dichiarato un array e si mette tale matrice sul mucchio, hai utilizzato malloc  e questo genere di cose, tutte le scommesse sono spenti. Poi effettivamente passare intorno un argomento speciale o un altro parametro che ti dice quanto è grande l'array è. In questo caso, vorrei usare una virgola-mi dispiace, sta andando fuori dallo schermo qui- e mi piacerebbe passare a un altro argomento  e lo chiamano int len ​​per la lunghezza. 

Una cosa che potrebbe venire sul quiz vi chiede di scrivere o implementare una particolare funzione chiamata qualcosa. Se non vi danno il prototipo, quindi tutta questa cosa qui, tutto questo casino si chiama dichiarazione di funzione o il prototipo di funzione, questa è una delle prime cose che si vorrà inchiodare se non è dato a voi subito sul quiz. L'altro trucco che ho imparato è che dire che concede il prototipo di una funzione, e diciamo: "Ehi, hai avuto modo di scriverlo." All'interno delle parentesi graffe che avete sul quiz se si nota che c'è un tipo di ritorno e si nota che il tipo di ritorno è qualcosa di diverso da void, il che significa che la funzione non restituisce nulla, poi una cosa che sicuramente voglio fare è scrivere una sorta di return alla fine della funzione. Ritorno, e in questo caso, ci metterò un vuoto perché vogliamo riempire il vuoto. Ma questo ti fa pensare nel modo giusto su come faccio a affrontare questo problema? E ti ricorda che stai andando ad avere per restituire un valore al chiamante della funzione. 

Si '. >> [Studente] Ha stile si applicano quando si sta scrivendo codice sul quiz? Come rientro e quel genere di cose? >> [Studente] Si '. No, non tanto. Penso che un sacco di-questo è qualcosa che ci chiariscono il quiz il giorno, ma in genere preoccuparsi include # e questo genere di cose, è una specie di fuori. [Studente] Avete bisogno di commentare il codice scritto a mano? Avete bisogno di commentare il codice scritto a mano? Commentando è sempre bene, se siete preoccupati per credito parziale o se si vuole comunicare la vostra intenzione allo livellatrice. Ma, ancora una volta, chiarirà 'in quiz e il giorno quiz, ma io non credo che ti verrà richiesto di scrivere commenti, no. In genere no, ma è sicuramente il genere di cose in cui è possibile comunicare la vostra intenzione, come "Hey, questo è dove sto andando con esso." E a volte che può aiutare con il credito parziale. Cool. 

Basil. [Basilio] Qual è la differenza tra la dichiarazione di, diciamo, int lang negli argomenti o parametri rispetto dichiara una variabile all'interno della funzione? Wow, il caffè è andato giù per la trachea. [Basilio] Ti piace che le cose che vogliamo mettere in argomenti. Sì, è una grande domanda. Come si fa a scegliere ciò che le cose che si desidera mettere in argomenti rispetto a ciò che le cose che si dovrebbero fare all'interno della funzione? In questo caso abbiamo incluso entrambi come argomenti perché sono qualcosa che chi sta per utilizzare la funzione somma ha bisogno di specificare quelle cose. 

La funzione somma, come abbiamo detto, non ha modo di sapere quanto è grande l'array è ottiene dal suo chiamante o di chi sta utilizzando la funzione di somma. Non ha modo di sapere quanto grande è quella matrice. La ragione per cui si passa in questa lunghezza qui come argomento è dovuto al fatto che è qualcosa che stiamo praticamente dicendo che il chiamante della funzione, chi sta per utilizzare la funzione somma, "Ehi, non solo dovete darci una matrice di int, si hanno anche per dirci quanto è grande l'array che ci hai dato è. " [Basilio] Coloro che saranno entrambi gli argomenti della riga di comando? No, questi sono argomenti reali che si dovrebbe passare alla funzione. 

Vorrei fare una nuova pagina qui. [Basilio] Come nome sarebbe pass- [Nate H] Se ho int main (void), e ho intenzione di mettere nel mio 0 return qui in basso, e dire che voglio chiamare la funzione somma. Voglio dire int x = sum (); Per utilizzare la funzione somma che devo passare sia la matrice che voglio riassumere e la lunghezza della matrice, quindi questo è dove assumendo Ho avuto un array di interi, dire che ho avuto numbaz int [] = 1, 2, 3, tipo di utilizzo che a pezzi sintassi proprio lì, allora quello che vorrei fare è insomma vorrei passare sia numbaz e il numero 3 a dire la funzione somma "Ok, ecco la matrice voglio che sommare." "Ecco le sue dimensioni." Ha senso? Ho risposto alla tua domanda? 

Per molti versi parallelo fa quello che stiamo facendo con il principale quando abbiamo gli argomenti della riga di comando. Un programma come Cesare cifra, per esempio, che aveva bisogno di argomenti della riga di comando non sarebbe in grado di fare qualsiasi cosa. Non saprei come crittografare se non indicare cosa chiave da utilizzare o se non lo dire cosa stringa che si vuole crittografare. La richiesta di input, questo è dove abbiamo ottenuto 2 diversi meccanismi per prendere in ingresso dall'utente, per prendere informazioni da parte dell'utente. Per Problema Set 1 abbiamo visto questa GetInt, GetString, modo getFloat di richiesta di input, e che si chiama con il flusso di input standard. E 'un po' diverso. E 'qualcosa che si può fare in una sola volta al contrario di quando si avvia il programma, quando si avvia il programma in esecuzione. Gli argomenti della riga di comando sono specificati tutti quando si avvia il funzionamento del programma. Abbiamo la miscelazione dei due di quelli. Quando si usano argomenti di una funzione, è molto simile a gli argomenti della riga di comando per principale. E 'quando si richiama la funzione è necessario indicare la che cosa ha bisogno per svolgere i propri compiti. Un'altra buona cosa da guardare, e ti farò vedere le cose nel tempo libero, ed è stato coperto nel quiz-era questa nozione di portata e variabili locali rispetto a variabili globali. Fare attenzione a questo. 

Ora che ci stiamo a queste altre cose, nella Settimana 3 abbiamo iniziato a parlare di ricerca e l'ordinamento. Ricerca e l'ordinamento, almeno in CS50, è molto un'introduzione ad alcune delle parti più teoriche di informatica. Il problema della ricerca, il problema di smistamento sono grandi, problemi canonici. Come si fa a trovare un determinato numero in un array di miliardi di numeri interi? Come si fa a trovare un particolare nome all'interno di una rubrica telefonica che è memorizzato su un computer portatile? E così si introduce la nozione di tempi di esecuzione asintotici per quantificare realmente quanto tempo, quanto sia difficile questo problema sono, quanto tempo impiegano a risolvere. In, credo, 2011 di quiz c'è un problema che penso meriti copertura molto rapidamente, che è questo, il problema 12. O no, è Omega. 

Qui stiamo parlando del tempo di esecuzione più veloce possibile per un particolare algoritmo e quindi il tempo di esecuzione più lento possibile. Questo Omega e O sono in realtà solo scorciatoie. Sono scorciatoie notazionali per dire la velocità nel caso migliore sarà il nostro algoritmo di esecuzione, e la lentezza nel caso peggiore sarà il nostro algoritmo di correre? Facciamo un paio di questi, e questi sono stati coperti a breve sulla notazione asintotica, che consiglio vivamente. Jackson ha fatto davvero un buon lavoro. Con la ricerca binaria, si parla di ricerca binaria come un algoritmo, e di solito parlarne in termini di grande O. Qual è la grande O? Qual è il tempo di esecuzione più lento possibile di ricerca binaria? [Studente] N ²? Chiudi, credo simile a quello. E 'molto più veloce di così. [Studente] binario? >> Si ', la ricerca binaria. [Studente] E 'log n. Log n, cosa fanno log n dire? E si dimezza ogni iterazione. Esattamente, quindi nel caso più lento possibile, dire se si dispone di un array ordinato di un milione di numeri interi e il numero che stai cercando o è il primo elemento nella matrice o l'elemento nella matrice. Ricordate, l'algoritmo di ricerca binaria funziona guardando l'elemento centrale, vedere se questa è la partita che si sta cercando. Se lo è, allora bene, l'hai trovato. 

Nel caso migliore, la velocità di esecuzione fa ricerca binaria? [Gli studenti] 1. 1, è la costante di tempo, grande O di 1. Gia '. [Studente] Ho una domanda. Quando si dice log di n, si intende rispetto alla base 2, giusto? Sì, in modo che l'altra cosa. Diciamo n log, e credo che quando ero al liceo Ho sempre pensato che il log era base 10. Gia ', quindi sì, log 2 base è in genere ciò che usiamo. Anche in questo caso, tornando alla ricerca binaria, se siete alla ricerca di uno dei due l'elemento alla fine o l'elemento all'inizio, perché si inizia a metà e poi scartare seconda metà non è conforme ai criteri che si sta cercando, e si va al prossimo mezzo e la prossima metà e la metà successiva. Se sto cercando per il più grande elemento dell'array milioni di interi Ho intenzione di dimezzare lo al più log di 1 milione di volte prima che finalmente provare e vedere che l'elemento che sto cercando è il più grande o nel più alto indice della matrice, e che avrà log n, log di 1 milione di volte. 

Bubble sort. Voi ragazzi ricordate l'algoritmo bubble sort? Kevin, mi puoi dare un breve riepilogo di quello che è successo con l'algoritmo bubble sort? [Kevin] In sostanza si passa attraverso tutto ciò che nella lista. Si guarda le prime due. Se il primo è più grande la seconda essa le swap. Poi si confronta secondo e terzo, la stessa cosa, swaps, terzo e quarto, fino in fondo. Più grandi i numeri seguirà fino alla fine. E dopo molti cicli tuttavia il gioco è fatto. Esattamente, quindi ciò che ha detto è che Kevin guarderemo più grandi numeri bolla fino alla fine della matrice. Ad esempio, ti dispiace camminare attraverso questo esempio, se questa è la nostra matrice? [Kevin] Ti prendo 2 e 3. 3 è più grande di 2, quindi li scambio. [Nate H.] Giusto, quindi ci scambiamo questi, e in modo da ottenere 2, 3, 6, 4, e 9. [Kevin] Allora si confronta il 3 e 6. 3 è inferiore a 6, in modo da lasciare loro, e 6 e 4, che li avresti scambiare perché 4 è inferiore a 6. [Nate H.] destro, in modo da ottenere 2, 3, 4, 6, 9. [Kevin] E 9 è superiore a 6, in modo da lasciare. E devi andare indietro attraverso di nuovo. 

[Nate H] Sto fare a questo punto? >> [Kevin] No. E perché io non ho fatto a questo punto? Perché sembra che il mio array è ordinato. Mi sto guardando. [Kevin] Vai attraverso di essa ancora e fare in modo che non ci sono gli swap non più prima di poter smettere completamente. Esattamente, quindi è necessario per andare avanti attraverso e fare in modo che non ci siano swap che si può fare a questo punto. E 'stato davvero solo fortuna, come hai detto tu, che abbiamo finito per solo dover fare 1 pass through e siamo ordinati. Ma per fare questo nel caso generale ci troveremo a fare questo più e più volte. E infatti, questo era un esempio del caso migliore, come abbiamo visto nel problema. Abbiamo visto che il caso migliore è stata n. Siamo andati con il tempo di matrice 1. Qual è il caso peggiore possibile per questo algoritmo? [Kevin] N ². E che cosa piace quello sguardo? Che cosa sarebbe un look matrice del genere sarebbe voluto del tempo ² n? [Kevin] [incomprensibile] ordinati. Esattamente, quindi se avessi la matrice 9, 7, 6, 5, 2, prima il 9 si bolla tutto il senso fino. Dopo 1 iterazione avremmo 7, 6, 5, 2, 9. Poi il 7 sarebbe bubble up, 6, 5, 2, 7, 9, e così via e così via. 

Dovremmo passare attraverso l'intero array n volte, e si può effettivamente ottenere un po 'più precisa di questa perché una volta che abbiamo spostato il 9 tutta la strada fino nella sua ultima posizione possibile sappiamo che non dobbiamo confrontare con tale elemento nuovo. Una volta che si comincia a gorgogliare il 7 sappiamo che siamo in grado di fermare una volta che il 7 è a destra prima del 9 dal momento che già il 9 rispetto ad esso. Se si esegue questa operazione in modo intelligente non è vero, credo, che molto tempo. Tu non stai andando a confrontare tutte le possibili combinazioni di [incomprensibile] ogni volta che si passa attraverso ogni iterazione. Ma ancora, quando si parla di questo limite superiore si dice che siete alla ricerca di n ² confronti fino in fondo. 

Torniamo indietro, e dato che stiamo iniziando a diventare un po 'a corto di tempo Direi che si dovrebbe andare per il resto di questa tabella, compilare tutto. Pensate di esempi. Pensate di esempi concreti. E 'davvero comodo e utile da fare. Disegna fuori. Questo è il tipo di tabella che come si passa attraverso in informatica si dovrebbe davvero iniziare a conoscere questi cuore da. Questi sono i tipi di domande che si ottiene nelle interviste. Questi sono i tipi di cose che è bene sapere, e pensare a questi casi limite, in realtà per capire come pensare sapendo che per bolla ordinare l'array peggiore possibile per ordinare con questo è uno che è in ordine inverso. 

Puntatori. Parliamo un po 'di puntatori. Negli ultimi minuti abbiamo qui So che questa è una cosa insieme a file di I / O che è piuttosto nuovo. Quando si parla di puntatori il motivo per cui vogliamo parlare di puntatori è perché, uno, quando stiamo lavorando in C siamo davvero ad un livello abbastanza basso rispetto ai linguaggi di programmazione più moderni. Siamo effettivamente in grado di manipolare le variabili in memoria, capire dove stanno in realtà si trova all'interno della nostra RAM. Una volta che hai continuato a prendere lezioni di sistema operativo che vedrete che questo è, ancora una volta, una specie di astrazione. Questo non è davvero il caso. Abbiamo la memoria virtuale che si nasconde questi dettagli da noi. 

Ma per ora si può supporre che quando si ha un programma, per esempio, quando si avvia l'esecuzione del programma-cifrario di Cesare Io tornare al mio iPad molto velocemente- che proprio all'inizio del programma, se si dispone di, diciamo, 4 gigabyte di RAM su un computer portatile, vieni messo da parte questo pezzo, e chiameremo questa RAM. E si avvia in un luogo che andremo a chiamare 0, e termina in un luogo che chiameremo 4 gigabyte. Io davvero non riesco a scrivere. L'uomo, che viene violato. Quando il programma viene eseguito il sistema operativo scolpisce la RAM, e specifica di segmenti diversi per le diverse parti del programma in cui vivere Quaggiù questa zona è una specie di terra di nessuno. Quando si sale un po 'più qui hai effettivamente il luogo in cui il codice per la vostra vita del programma. Questo codice binario vero e proprio, che in realtà file eseguibile viene caricato in memoria quando si esegue un programma, e vive nel segmento di codice. E come il programma esegue il processore in questo segmento di codice per capire che cosa è l'istruzione successiva? Qual è la prossima linea di codice che devo eseguire? 

C'è anche un segmento di dati, ed è qui che le costanti di stringa vengono memorizzati che hai usato. E poi, più in alto c'è questo posto chiamato l'heap. Abbiamo accedere alla memoria in esso, utilizzando malloc, e poi verso la cima del programma c'è la pila, ed è lì che abbiamo giocato per la maggior parte l'inizio. Questo non è in scala o altro. Molto di questo è molto dipendente dalla macchina, dipende dal sistema operativo, ma questo è piuttosto il modo le cose si Chunked up. Quando si esegue un programma e si dichiara una variabile chiamata x- Io vado a disegnare un'altra casella in basso, e questo sarà RAM pure. E sto andando a guardare. Ci disegnare linee frastagliate per indicare questo è solo una piccola parte di RAM e non tutti come attingiamo in alto. 

Se Dichiaro una variabile intera chiamata x, allora quello che è realmente ottenere una mappatura memorizzato nella tabella dei simboli del mio programma che collega la x nome a questa regione di memoria che ho disegnato proprio qui, tra le barre verticali. Se ho una riga di codice nel mio programma che dice che x = 7 il processore sa "Oh, va bene, lo so che la vita x in questa posizione in memoria." "Ho intenzione di andare avanti e scrivere un 7 lì". Come fa a sapere quale posizione questo è in memoria? Beh, questo è tutto fatto al momento della compilazione. Il compilatore si occupa di allocare in cui ciascuna delle variabili sta per andare e creando un mapping speciale o meglio i puntini tra un simbolo e dove sta andando, il nome di una variabile e dove sta andando a vivere nella memoria. Ma si scopre che si può effettivamente accedere ai nostri programmi pure. Questo diventa importante quando si comincia a parlare di alcune delle strutture di dati, che è un concetto che stiamo per introdurre in seguito. 

Ma per ora, quello che si può sapere è che posso creare un puntatore a questa posizione, x. Per esempio, è possibile creare una variabile puntatore. Quando creiamo una variabile puntatore si usa la notazione stella. In questo caso, questo dice che ho intenzione di creare un puntatore a un int. E 'un tipo come tutte le altre. Abbiamo dato una variabile come y, e poi impostarlo uguale all'indirizzo, ad un indirizzo. In questo caso, si può impostare y per puntare a x prendendo l'indirizzo di x, che fare con questo e commerciale, e poi abbiamo fissato y per puntare ad esso. Quello che in sostanza non è se guardiamo al nostro RAM questo crea una variabile separata. E 'intenzione di chiamarlo y, e quando questa riga di codice viene eseguito sta in realtà andando a creare un puntatore poco che abbiamo di solito disegnare come una freccia, e pone y per puntare a x. Sì. [Studente] Se x è già un puntatore, vuoi solo fare int * y = x al posto di avere la e commerciale? Sì. Se x è già un puntatore, allora è possibile impostare 2 puntatori uguali tra loro, nel qual caso y non indicavano un x, ma ricorda a tutto ciò che x sta puntando. Purtroppo, non siamo fuori dal tempo. 

Quello che vorrei dire a questo punto, possiamo parlare di questa linea, ma direi che iniziare a lavorare con questo problema, # 14. Si può vedere che c'è già un po 'compilato per voi qui. Si può vedere che, quando dichiariamo 2 puntatori, int * x e y *, e si noti che puntando il * accanto alla variabile è qualcosa che è stato fatto l'anno scorso. Si scopre che questo è simile a quello che stiamo facendo quest'anno. Non importa dove si scrive il * quando si dichiara il puntatore. Ma abbiamo scritto il * accanto al tipo di perché questo rende molto chiaro che si sta dichiarazione di una variabile puntatore. Si può vedere che dichiara i 2 puntatori ci dà 2 scatole. Qui quando abbiamo fissato x uguale a malloc cosa sta dicendo è mettere da parte la memoria nel mucchio. Questa piccola scatola proprio qui, questo cerchio, si trova sul mucchio. X è ad esso. Si noti che y non è ancora punta a nulla. Per memoria per memorizzare il numero 42 in x useremo la notazione che cosa? [Studente] * x = 42. Esattamente, * x = 42. Questo significa seguire la freccia e gettare 42 in là. Qui è dove si imposta y e x, abbiamo y punta a x. Ancora una volta, questo è proprio come quello che Kevin ha detto dove si imposta y = x. Y non punta a x. Piuttosto, sta puntando a ciò che x sta indicando pure. 

E poi, infine, in questa ultima finestra ci sono 2 possibili cose che potremmo fare. Uno è, potremmo dire * x = 13. L'altra cosa è che potrebbe dire-Alex, sai cosa potremmo fare qui? Si potrebbe dire che x * = 13 o- [Studente] Si potrebbe dire qualunque int. [Nate H] Se questo fosse indicato come una variabile int potremmo farlo. Potremmo anche dire * y = 13, perché sono entrambi puntando nello stesso posto, in modo da poter utilizzare sia variabile per arrivarci. Si '. >> [Studente] Che cosa sarebbe simile se ci limitiamo a dire x int è 13? Questo sarebbe dichiara una nuova variabile chiamata x, che non avrebbe funzionato. Avremmo una collisione perché abbiamo dichiarato x essere un puntatore qui. [Studente] Se abbiamo avuto solo questa affermazione di per sé ciò che potrebbe somigliare in termini di cerchio? Se avessimo x = 13 allora avremmo una scatola, e piuttosto che avere una freccia che esce dalla scatola l'avevamo disegnare come solo un 13. [Studente] Nella finestra. Va bene. 

Grazie per la visione, e buona fortuna per il Quiz 0. [CS50.TV]