>> DAVID J. MALAN: Questo è CS50 e questo è l'inizio della quarta settimana.
E, ragazzo, è Volkswagen difficoltà a tutto a causa di software.
Diamo uno sguardo.
[RIPRODUZIONE VIDEO]
Posti macchina, i personaggi più intelligenti nei film Fast and Furious.
Questa settimana automobilistica tedesca Volkswagen si è trovata
nel bel mezzo di uno scandalo di proporzioni potenzialmente criminali.
>> -Volkswagen Sta preparando per miliardi in multe, possibili accuse penali
per i suoi dirigenti, come l'azienda si scusa
per rigging 11 milioni di automobili a aiutarla a battere le prove di emissione.
>> Modelli diesel -Certain erano progettato con sofisticati software
che le informazioni utilizzati, compresa la posizione del volante e del veicolo
la velocità per determinare la macchina era in fase di test delle emissioni.
In base a tale circostanza, il motore ridurrebbe le emissioni tossiche.
Ma la macchina è stato truccato a bypass che quando veniva spinto.
Le emissioni sono aumentate da 10 a 40 volte superiori ai livelli di EPA accettabili.
>> [FINE RIPRODUZIONE]
>> DAVID J. MALAN: Quindi cerchiamo di guarda questo
e vedere esattamente come questo potrebbe essere attuato
e come questo potrebbe influenzare così tante vetture come questo.
Così in mano ecco il comunicato comunicato che è stato rilasciato dal EPA--
Ambientale Protection Agency che
è l'agenzia di regolamentazione degli Stati Uniti che gestisce le preoccupazioni ambientali,
e poi l'attuale note legali che era
inviare Volkswagen solo pochi giorni fa.
>> Così scrive l'EPA, e rivela ora pubblicamente, un sofisticato software
algoritmo su determinati Veicoli Volkswagen rileva
quando la macchina è in fase di le prove sulle emissioni ufficiali
e trasforma le emissioni pieni controlla soltanto durante la prova.
L'efficacia di Questi veicoli inquinamento
dispositivi di controllo delle emissioni è notevolmente ridotto durante tutto guida normale
situazioni.
Ciò si traduce in macchine che soddisfano la standard in laboratorio o test
ferroviaria, ma durante il normale funzionamento emettere oxides-- azoto o NOx--
fino a 40 volte la norma.
Il software prodotto da Volkswagen è un dispositivo tra virgolette, la sconfitta,
come definito dalla Clean Air Act negli Stati Uniti.
>> Continuano a dire che l'EPA e un'altra agenzia
scoperto il dispositivo sconfitta software dopo un'analisi indipendente
da ricercatori a West Virginia University.
Inquinamento NOx contribuisce il biossido di azoto, ozono troposferico,
e polveri sottili.
L'esposizione a questi inquinanti è stato collegato
con una vasta gamma di effetti gravi per la salute,
compresa una maggiore asma attacchi e altri respiratoria
malattie che possono essere abbastanza gravi per inviare le persone in ospedale.
L'esposizione all'ozono e particolato ha anche
stata associata con premature morte a causa di respiratorie correlate
o cardiovascolare effetti correlati.
I bambini, gli anziani, le persone con malattia respiratoria preesistente
sono particolarmente a rischio di effetti sulla salute di queste sostanze inquinanti.
>> Basti per dire, è abbastanza grave.
E andiamo avanti a leggere solo un altro stralcio
e poi daremo uno sguardo a le implicazioni sottostanti
di ciò nel contesto di una macchina.
In particolare, la Volkswagen prodotto e installato
software nel cosiddetto controllo elettronico
module-- o ECM-- di questi veicoli che intuivano
quando il veicolo è stato testato per la conformità alle norme sulle emissioni EPA.
Sulla base di diversi ingressi, tra cui il posizione del volante, veicolo
velocità, la durata del motore di operazione, e la pressione barometrica,
questi ingressi precisamente monitorati i parametri
della procedura di prova utilizzato per federale prove di emissione per la certificazione EPA
scopi.
>> Durante il test delle emissioni di EPA, il software veicoli ECM
corse software che ha prodotto Risultati delle emissioni conformi.
In tutti gli altri casi, la software ECM veicolo
correva una strada distinta taratura che ha ridotto
l'efficacia del sistema di controllo delle emissioni in generale,
specificamente il catalitica selettiva riduzione del NOx magra trap--
che vedremo su in un attimo.
Come risultato, le emissioni di NOx aumentato di un fattore di 10 a 40 volte
al di sopra dei livelli di conformità EPA a seconda del tipo di ciclo di guida.
>> Così che cosa questo significa veramente, e la codice sorgente per il software in esecuzione
sulle Volkswagen di non ha ancora rese pubbliche,
è che, effettivamente, questo equivalente c'è da qualche parte dentro
di codice di Volkswagen.
Se siete messi alla prova, e se l'auto rileva alcuni fattori ambientali
come il volante posizione o il movimento
o la mancanza della macchina o qualsiasi numero di altri fattori
che sono attualmente ipotizzarono di far parte di questa formula,
semplicemente accendere controllo delle emissioni completi.
In altre parole, cominciano emettono meno degli inquinanti.
>> Altrimenti, in ogni altra situazione quando non è rilevato come
in laboratorio, solo che non lo fanno.
E così si può semplificare questo in più pseudocodice calcestruzzo con qualcosa
Come questo.
Se le ruote stanno girando, ma la volante non è, suggestiva
che la vettura è in qualche tipo di cilindro rotante
ma in qualche tipo di magazzino in fase di test,
poi comportarsi come il EPA vorrebbe che.
In caso contrario, non lo fanno.
Quindi, diamo uno sguardo in un breve video che
prende in esame quali siano le implicazioni sono di questo in realtà meccanicamente.
>> [RIPRODUZIONE VIDEO]
>> -last Venerdì l'EPA ha annunciato che alcuni Auto Volkswagen Audi realizzati tra il 2009
e quest'anno usavano un cosiddetto impianto di manipolazione
per aggirare leggi di emissioni progettata per mantenere l'aria pulita.
Ma che cosa significa esattamente?
>> Beh, auto moderne hanno dozzine di computer al loro interno.
E alcuni di questi computer contribuire a coordinare le funzioni
del motore per ottimale prestazioni badando
non c'è troppo immondizia che esce dal tubo di scarico.
Hanno in realtà lavorato in questo modo da diversi decenni.
In sostanza, ogni parte di motore di una vettura moderna
dispone di un sensore o un controller su di esso, e questi computer
sono la lettura dei dati di migliaia di volte al secondo le regolazioni per la preparazione
come il rapporto tra carburante e aria che sta andando nei cilindri.
>> Questi barare Volkswagen e modelli di Audi sono diesel,
e diesel hanno un altro veramente importante del computer
parametri controllati, che è la quantità di carburante incombusto andare
nello scarico.
Ora che suona male.
Non sembra che si vorrebbe carburante incombusto andare nello scarico.
Ma nel caso di un diesel, hai qualcosa
chiamato una trappola di NOx, che è un dispositivo che assorbe e trappole per gli ossidi di azoto
che sono sostanze inquinanti che avrebbe altrimenti andare in atmosfera.
E l'effetto di quella trappola NOx si arricchisce di carburante incombusto.
Così un impianto di manipolazione è un programma speciale all'interno di questi computer che può rendere
apparire come la macchina incontra emissioni norme anche quando non è così.
Volkswagen ha avuto un problema sulle sue mani.
I suoi motori diesel erano noti per ottenere grande economia di carburante,
ma la trappola NOx funziona bene solo quando si utilizza più carburante.
Quindi la vettura sarebbe rilevare, utilizzo di questo impianto di manipolazione,
quando si stava facendo un emissioni Test, sarebbe utilizzare più combustibile,
fare bene il lavoro trappola NOx, emissioni andrebbe bene.
Ma poi si arriva sulla strada, il dispositivo si spegne, si sta bruciando meno combustibile
ma avete deciso di mettere fino a 40 volte più inquinanti in atmosfera.
Ma come cavolo ha fatto la macchina sapere che era
in fase di test per la conformità delle emissioni?
L'EPA dice che era un sofisticato sistema che controllò le cose
come posizione del volante, velocità, quanto tempo il motore era acceso,
e anche la pressione atmosferica.
In altre parole, non vi era nessun modo questo è stato accidentale
perché il software è stato progettata con molta attenzione per rilevare
un test ufficiale delle emissioni.
Ecco alcuni piuttosto gravi inganno e che è
perché Volkswagen è in tale guaio serio.
Infatti, la loro CEO, Martin Winterkorn, appena dimesso.
>> Allora, cosa succede dopo?
Beh, se sei uno dei mezzo milione Jettas diesel, Beatles, Golfs, Passat,
o Audi A3s effettuata, La buona notizia è è
che l'auto è ancora sicuro da guidare.
Non dovete mettere via fino a quando la Volkswagen emette un richiamo.
Ma a un certo punto sono probabilmente andando ad avere
per aggiornare il software all'interno della vostra auto.
Quando ciò accade si potrebbe ottenere un minor numero di miglia per serbatoio.
Gli avvocati sono già attrezzando per cause class action
così i proprietari potrebbero ottenere compensata ad un certo punto in futuro.
Ma questo non sta andando accadere in qualunque momento presto.
>> [FINE RIPRODUZIONE]
DAVID J. MALAN: Quindi questo in realtà solleva un interessante maggiore domanda immagine
da fiducia.
Destra?
Tutti noi avere iPhone o androidi o qualcosa nelle nostre tasche più probabile
in questi giorni, o computer portatili sui nostri giri che sono
il software in esecuzione fatta da Apple e Microsoft
e grappoli di altre società.
Ma come facciamo a sapere che ciò che questi prodotti software stanno facendo
è in realtà ciò che questi aziende dicono che stanno facendo?
>> Per esempio, chi può dire che ogni volta che si
fare una telefonata sul tuo iPhone o telefono Android o simili,
che quel numero di telefono non è anche essere caricato sul server alcune società di
a causa di qualche programma che avete scritto, se è il funzionamento
stesso sistema come iOS o Android, o perché hai scaricato
una terza parte app che in qualche modo è in ascolto
per tutto quello che stai digitando o tutto ciò che si sta effettivamente dicendo.
Come fai a sapere che, quando voi ragazzi sono in esecuzione Clang
o Crea per compilare il proprio software in CS50, come
Sei il proprietario di personale che di CS50, a titolo di biblioteca CS50,
Non è stata la registrazione ogni stringa che sia mai capitata
o tutto e per tutto che tu abbia mai ottenuto?
Beh, si potrebbe certamente guardare il codice sorgente per qualcosa
come la biblioteca CS50, si poteva guardare il codice sorgente
per il sistema operativo Linux in esecuzione su CS50 IDE.
Ma una sorprendente presentazione è stato dato nel 1984
in ricezione del Turing Award da un molto famoso scienziato computer noto
as-- di nome Ken Thompson, che ha ricevuto il Premio Turing che
è una sorta di informatica di Premio Nobel, se si vuole,
per il suo lavoro su un sistema operativo chiamato
Unix, che è molto simile a spirito a quello che usiamo, che è Linux.
E la domanda ha chiesto nella sua discorso di accettazione, essenzialmente
che stabilisce il quadro per anni e anni di discussione
di fiducia e sicurezza, è stata questa.
Fino a che punto si dovrebbe fiducia un affermazione che un program-- un pezzo
di software-- è libero di cavalli di Troia?
Forse è più importante avere fiducia chi ha scritto il software.
>> E infatti, abbiamo legati per il discorso che lui
dato che l'accettazione di questo premio negli anni '80 sul sito web del CS50
sotto la pagina di lezioni per oggi.
Perché quello che vedrete è che in realtà dà
abbastanza semplice esempio di come anche un compilatore Clang come o qualsiasi altra cosa
compilatori altri hanno utilizzato in passato, cosa se incorporato nel compilatore noi
noi stanno usando è un po 'se condizione che dice in sostanza,
se si nota che questo codice utilizza la funzione GetString o GetInt
la funzione, andare avanti e inserire una porta sul retro o un cavallo di Troia
tale che tale programma ora ha degli zeri
e quelli che fanno qualcosa di dannoso.
Registrazione tutti i tuoi battiture, caricamento che i dati
ad un server, o realmente nulla.
>> E che Ken Thompson continua a fare nel suo discorso
è quello di dimostrare che anche se si ha accesso alla fonte
codice di un compilatore che maliziosamente potrebbe fare questo,
non importa perché c'è questo uovo e la gallina
realtà del passato molti anni in base alle quali i compilatori
sono utilizzati per compilare stessi.
In altre parole, quando qualcuno ritorno doveva aver scritto il primo compilatore.
E da allora in poi, ogni volta che ho aggiornato un compilatore cambiando il suo codice sorgente,
l'aggiunta di funzionalità e ricompilata per chi come noi da usare, bene,
che stanno utilizzando il vecchio versione del compilatore
per compilare la nuova versione del compilatore.
E se si dà un'occhiata al discorso che ha dato,
vedrai che a causa di quella circolarità,
si può effettivamente avere bug o Cavalli di Troia incorporati nel software
stiamo usando.
E anche se si guarda al codice sorgente per questi programmi,
potrebbe anche non essere evidente perché l'inganno è in realtà
in qualche versione precedente di un compilatore che da allora è stato
iniettare la minaccia nel nostro software.
>> Che è solo per dire, abbiamo davvero non può e non deve
software fiducia in esecuzione sul nostro computer portatili o telefoni o qualsiasi numero di posti.
E infatti, più avanti in questo semestre, quando cominciamo a parlare di programmazione web
ed effettivamente iniziare a costruire applicazioni web noi stessi,
parleremo di questi minacce e altri.
Ora, si potrebbe essere chiesto e ho notato che c'era un piccolo piccolo Darth
Vader nei clip che The Verge mostrava lì
su Volkswagen. Se non hai mai visto, io
pensato che dovrebbe alleggerire lo stato d'animo perché questo è tutto
molto deprimente e spaventoso.
Io vado a guardare indietro al Super Bowl 2011
quando uno spot da Volkswagen-- e questo
quasi li rende simpatici again-- trasmesso per la prima volta in TV.
E 'la seconda clip 60 Penso che godrete.
[RIPRODUZIONE VIDEO]
[MUSICA - TEMA "STAR WARS"]
[Cane abbaia]
[Automobile si avvia]
[FINE RIPRODUZIONE]
DAVID J. MALAN: Sì.
Stavo solo controllando.
Quella macchina è sulla lista delle violazioni.
Tutto ok.
Quindi guardiamo un po ' pseudocodice un momento fa.
Ed ecco un grande frammento di codice pseudocodice
che abbiamo visto un paio di volte finora.
E usiamo questa è un'opportunità ora per introdurre una nuova programmazione
tecnica che abbiamo fatto vedi algoritmicamente
la settimana scorsa quando abbiamo guardato merge sort.
Ma andiamo formalizzare e vediamo come potremmo usarlo in codice vero e proprio,
e poi abbiamo intenzione di utilizzare questo tecnica lungo la strada più
in grado di risolvere alcuni altri problemi.
>> Quindi questo è stato uno dei primi programmi che mai scritto, anche se in codice pseudocodice.
E quello che questo programma ci ha permesso di fare rotta
era quello di trovare Mike Smith in una rubrica telefonica.
E notare in particolare le linee otto e 11 che ha avuto questa affermazione Vai a.
Ed infatti, alcuni lingue, C tra loro,
in realtà hanno un dichiarazione che è letteralmente
andare che permette di passare a una linea specifica.
E 'generalmente malvista perché può essere facilmente abusato
e si può iniziare a saltare la vostra programma di tutto il luogo in contrapposizione
per utilizzare il tipo di logica e il flusso di controllo
che abbiamo usato finora solo con loop e le condizioni e simili.
>> Ma possiamo semplificare questo algoritmo in pseudocodice codice come segue.
Invece di questo iterativo o approccio looping
dove continuiamo a tornare e indietro e torna alla linea a tre,
perché non solo tipo di Punt e più generalmente dire in linea di sette e 10,
basta sostituire quei due coppie di linee con,
altrimenti se Smith è anteriore nel libro faremo
cercare Mike nel la metà sinistra del libro.
Altrimenti se Smith è più avanti nel libro, cercare Mike nella giusta
metà del libro.
E notare già la circolarità.
Destra?
Sto cercando Mike in la rubrica telefonica e poi
Alla fine ho colpito forse Linea sette o forse la linea 10
e la mia istruzione a me stesso è la ricerca per Mike a metà della rubrica.
Beh, come faccio a cercare Mike?
Sono nel bel mezzo di la ricerca di Mike, perché
stai sorta di mandarmi in un cerchio?
Ma va bene, perché ciò che è accade alle dimensioni del problema,
come scritto in linea 7 e 10?
Non stiamo solo dicendo di ricerca per Mike, la ricerca di Mike.
Stiamo specificamente dicendo che cosa?
Cerca per lui nella metà sinistra di la metà destra che è effettivamente
metà delle dimensioni del problema.
Quindi è bene che siamo tipo di impegnarsi in questa circolarità,
questo argomento circolare, perché almeno siamo
rendendo il problema più piccolo.
E alla fine abbiamo intenzione di raggiungere che cosiddetto caso base dove
abbiamo solo una pagina a sinistra- come il nostro volontario la settimana scorsa
did-- abbiamo avuto una sola pagina a sinistra e poi non lo facciamo
devono continuare a cercare Mike Smith perché è sia su quella pagina
o non lo è.
>> Quindi, come possiamo implementare questa idea, questo sorta di circolarità in codice vero e proprio?
Beh, siamo in grado di sfruttare una tecnica che è generalmente conosciuto come la ricorsione.
E abbiamo visto questo in pseudocodice per merge sort la settimana scorsa.
Ricordiamo che questo è stato il pseudocodice per merge sort.
E 'forse ancora più semplice di bolla o selezione o insertion sort
solo in termini di semplicità con cui è possibile esprimere.
>> Ma questo è perché noi siamo una sorta di circolare
dicendo, cercare qualcosa la ricerca di nuovo.
Ma stiamo cercando sia su la metà sinistra o quella destra
e poi alla fine siamo fondendo in questo caso.
Ma anche qui, con quelle due righe di ordinamento,
abbiamo ancora una volta abbiamo questo idea di ricorsione.
E concretamente cosa significa, nel contesto di un algoritmo,
è che un algoritmo è ricorsiva se usa o si chiama.
>> Oppure in termini di C, una funzione è recursive-- una funzione chiamata
pippo è ricorsiva se foo, da qualche parte nel suo codice sorgente,
chiama la funzione foo sé.
E questo è male se tutto foo fa mai è chiamarsi ancora e ancora.
Va bene se foo finalmente si arresta, come fa merge sort, dicendo, aspetta un minuto,
se questo problema è super piccolo, per esempio,
o l'ho trovato chi mi cercando, appena di ritorno.
Non in modo ricorsivo, non lo fanno chiamare ciclicamente di nuovo me stesso.
>> E così diamo un'occhiata a come questo potrebbe effettivamente funzionare.
Quindi ho intenzione di andare avanti e aperto due esempi di codice sorgente qui.
Uno dei quali è chiamato sigma 0.
E questo non è affatto ricorsiva, ma prendiamo
uno sguardo a ciò che questo programma fa.
Ho spogliato fuori tutto commenti da essa, ma tutto
del codice sorgente sul CS50 di sito ha commenti se
consiglia di leggere attraverso di essa più tardi.
E facciamo un paio di sanità mentale controlla qui.
>> Così nella parte superiore di questo codice, abbiamo includere CS50.h.
Cosa fa questo?
Perché è qui?
In termini ragionevoli del laico.
Che cosa fa?
Già.
>> PUBBLICO: In modo che la funzione GetInt funziona.
>> DAVID J. MALAN: In modo che la funzione GetInt funziona.
Poiché all'interno di questo file CS50.h, che
vedremo tra non molto in termini di codice sorgente,
ha un sacco di funzioni declared-- GetInt, GetString,
e un po 'di meno e others-- in realtà abbiamo che includono la linea,
il compilatore Clang non è andando a sapere che esiste.
E vale per la linea stessa due dove è definita int
printf, che è una funzione continuiamo con un bel po '.
Ora, la linea a quattro sembra un po 'funky perché è solo un uno di linea.
E 'ottenuto un punto e virgola, non riccio bretelle, nessun codice all'interno di esso.
Ma quello che facevamo noi chiamiamo questa cosa in settimane passato?
Già.
Quindi un prototipo.
E perché abbiamo un prototipo che sembra
per essere un po 'ridondante in genere perché noi di solito
rivedere la funzione più avanti nel file, giusto?
Quindi perché abbiamo have-- sei solo grattarsi la testa, ma la prendo.
Già.
>> PUBBLICO: [incomprensibile] la funzione dopo la principale.
DAVID J. MALAN: Esattamente.
In modo che il compilatore ti conosce finirà per definire o attuare
tale funzione dopo principale, presumibilmente.
Così Clang e più compilatori sono una specie di muto
e sapranno solo che cosa dite loro.
E se si desidera utilizzare una funzione chiamata sigma,
è meglio insegnare il compilatore che esiste in anticipo.
>> Ora, si principale, anche se si tratta di una serie di linee,
è abbastanza familiare si spera ormai.
Ha un do while il cui scopo nella vita
qui a quanto pare è quello di ottenere un intero positivo da parte dell'utente.
E proprio tenerlo pestering o lei fino a che non collaborano.
Poi, in linea 16 ho una chiamata interessante.
IntAnswer.
Quale sulla mano sinistra lato mi dà un Int
che può store-- chiamato Answer-- che sta per archiviare, a quanto pare,
il valore di ritorno di sigma.
Quindi sigma è solo un nome arbitrario ma significativo
che ho dato ad una funzione il cui scopo nella vita
è quello di prendere un argument-- che chiameremo N in questa case--
e solo per prendere la somma di quel numero più ogni numero positivo che è
più piccolo di esso.
>> Quindi, se mi passate il numero 2 a Sigma, voglio aggiungere 2 più 1
più 0-- non 0-- in modo che dà me 3.
Se mi passa a 3 a sigma, voglio hanno 3 più 2 più 1, che mi dà 6.
E così via.
Quindi aggiunge solo su tutto il numeri inferiori o uguali ad esso.
>> Ora, qui sto solo andando per stampare la risposta.
Così come un controllo di integrità rapido, diamo fare sigma 0-- puntino barra sigma 0--
e fammi scriv dentro 2.
E ho davvero ottenere 3.
Lasciatemi scriv dentro 3.
Io davvero ottenere 6.
E se qualcuno può fare la matematica in fretta, se faccio 50 cosa devo arrivare?
>> PUBBLICO: [incomprensibile].
DAVID J. MALAN: Beh, no.
Ma 1.275 che è abbastanza vicino.
Quindi questo è il risultato di fare 50 più 49, più 48, più 47, più 46
tutta la strada fino a 1.
Quindi questo è tutto sigma fa.
Ma vediamo come siamo attuato ora.
Così qui è la funzione stessa.
E questo non sembra avere nulla a che fare con la ricorsione ancora.
In realtà, stiamo usando un vecchia tecnica della scuola.
Sto inizializzazione di una variabile chiamata sum a zero, poi ho un foreloop qui,
e sto dichiarando un Int chiamato Io, l'impostazione uguale a 1--
anche se ho potuto impostare uguale a zero, ma dal momento che sto facendo, inoltre,
chi se ne frega se è zero o uno.
Sta andando ad avere alcun effetto.
>> Così sto iterazione fino a quando mi è minore o uguale a m, che
è l'argomento che è stato passato in.
E poi ho appena mantenere incrementando I. E insight
del ciclo tutto sto facendo sta facendo somma più uguale I. E questo è intenzionale.
Io non voglio fare, in questo caso, come somma plus plus.
Voglio aggiungere realmente il valore corrente di I
che mantiene sempre più grande e più grande per il conteggio in esecuzione.
>> E poi torno somma.
E così risposta ottiene la somma del valore.
E poi ho stamparlo.
Quindi c'è la possibilità qui, però, di tipo di semplificare
questo codice concettualmente e il tipo di colpo uno è
mente in termini di semplicità anche se
vuole un po 'di ordinare di capire perché questo
è potente in questi piccoli esempi.
Ecco quindi il sigma-tra-- seconda versione di questo codice.
Tutto sulla cima è identica così che stessa storia vale come prima.
Ma ora diamo un'occhiata al implementazione di Sigma che
Ho ridotto a solo questi lines-- quattro righe di codice, in realtà,
più alcune parentesi graffe e lo spazio bianco.
>> Ma cosa sto facendo?
Se m è inferiore o uguale a pari a zero, ho bisogno di gestire tipo di
che super semplice caso.
E se mano mi zero o niente negativo che è proprio strano,
Sto solo andando a arbitrariamente ma costantemente restituire zero.
Non voglio che questa cosa a entrare in alcuni infinito strano
ciclo a causa di un valore negativo.
Così sto solo dicendo, se mi dai zero o meno, sto tornando a zero.
>> Ma questo è un bene perché è quella singola pagina della rubrica
ciò che è rimasto.
Sto morde fuori un problema molto specifico e non chiamare qualcosa in modo ricorsivo.
Ma in linea di 31, cosa Non mi sembra di fare?
Le parentesi sono solo mantenendo le cose, si spera, un po 'più chiaro.
Ma tutto quello che sto facendo è che sono ritorno M-- qualunque
di consegnare me-- più il valore della M-- dispiace,
più il valore di sigma di meno 1 m.
Che cosa significa questo?
Se mi dai il numero 3 come input, la risposta che voglio ottenere in ultima analisi,
è 6 perché 3 più 2 più 1 mi dà 6.
Ma come faccio a pensare come questo codice viene eseguito?
La prima volta che io chiamo sigma e passo nel valore 3,
che è come dire su un pezzo di carta, ecco il valore 3
e sono stato superato questo come sigma.
3 è ovviamente non inferiore a 0 così la condizione IF non si applica.
L'altro fa.
Quindi cosa devo fare?
Voglio tornare m, che è 3, più sigma di m meno 1.
Così mi permetta di tenere traccia di questo.
Ho intenzione di mettere questo pezzo di carta giù.
E che valore, per essere chiaro, sto andando a passare
in sigma a questo punto della storia?
Che numero?
2, giusto?
3 meno 1 è 2.
Così ho solo bisogno di un po ' pezzo di carta qui.
Così ora Sigma si sta chiamato di nuovo.
E ho volutamente messo questo in giù perché è
un po 'come mettere in pausa che versione della storia
perché ora sono concentrato al segnale di meno 1 m.
Così era m 3, m è meno 1 2.
Così qui è 2 che ho passato.
2 è ovviamente non inferiore 0 in modo che caso non si applica.
Altrimenti torno m, che è questo cosa, più sigma di quale valore?
Quindi, se sigma di 1-- perché m è in questo momento così 2 2 meno 1 è 1.
Così ora ho solo il valore 1.
Sto passando solo il numero 1 alla funzione sigma--
o me qui-- così 1 non è ovviamente meno di zero, ancora non si applica.
>> Ritorno Else 1 più sigma di che cosa?
0.
Quindi lasciatemi solo ricordo.
Tornerò più avanti.
Ora ho intenzione di andare avanti e jot giù il numero 0 perché è
il mio argomento o parametro.
Sto superato il numero 0 e infine questo processo
di appena ripetermi annuncio fino alla nausea cessa perché ciò che
devo subito fare una volta che vedo questo 0?
Torno a zero.
Così ora si deve riavvolgere la storia.
>> Se ora vado a ritroso nel tempo, qual è stata la cosa più recente
Ho fatto se si fosse letteralmente riavvolgere un video?
Io vado a prendere il più recente 1 e che mi dà più 1 0 è 1.
Se tengo il riavvolgimento del storia, che sta per darmi
2 più questo valore in esecuzione, che è 1.
Ecco, questo è 3.
E poi ho intenzione di continuare a riavvolgimento.
Quando ho messo giù il numero 3-- così 3 più 3 mi dà 6.
>> E ora, se hai riavvolto il video fino a questo punto,
questo era il molto prima domanda ho chiesto.
Quando viene passato 3, qual è sigma di 3?
È infatti 6, la somma di tutti questi pezzi di carta.
Quindi, se questo richiede un po 'di tempo per avvolgere la mente intorno, va bene.
Ma si consideri che era un little-- esso era molto intenzionale che impilati
questi numeri sopra l'altro.
E 'un po' come avere un memory-- un record nel tempo,
come uno scrubber in un video, che io possa davvero tornare indietro in.
E abbiamo intenzione di tornare a che la metafora in appena un po '.
>> Ma prima, si scopre che non c'è un sacco di geek e persone divertenti,
Credo che, a Google.
Sarebbe qualcuno che è molto bravo a mente Googling
fino a venire per un momento e aiutami ricerca di qualcosa?
Molto chiave, molto basso.
Qualcuno che non è mai venire prima, forse.
OK.
Sì?
Avanti.
Vieni giù.
Come ti chiami?
>> SAM: Sam.
>> DAVID J. MALAN: Sam, vieni giù.
Questo è lo stesso.
Felice di conoscerti.
Ciao.
Vieni su.
Quindi tutto quello che devi fare, se si potrebbe, Sam, ecco Google.
Si può cercare il termine ricorsione?
Non rovinare.
>> E ora let's-- sì.
OK Fare clic su questo.
Meglio fare clic su tale.
Ahh, ottenerlo.
No?
OK.
Allora, facciamo un paio di altri.
Non tanto correlate accademicamente qui, ma hai
mai cercato di Google per anagramma?
>> SAM: No.
>> DAVID J. MALAN: OK.
Cerca anagramma invece di ricorsione.
Che ne dite di traverso.
Hai mai cercato di traverso?
Ora, questo è un po 'difficile da vedere, ma si spera everything's-- OK.
E 'solo io e te godere di questo.
OK.
>> Così alla fine, questo one's-- è un po 'di traverso.
Ora fare un barrel roll.
Meraviglioso.
Tutto ok.
Grazie di cuore a Sam.
Ecco qui.
Grazie.
>> Allora, cosa sta succedendo in tutta la di questi esempi stupidi?
Quindi, in realtà, sotto il cofano della Milioni di Google di righe di codice
a quanto pare è un qualche sciocco IF condizioni che sono essenzialmente
controllare se l'utente ha digitato in questa frase,
fare qualcosa che probabilmente ha preso una quantità non banale di tempo
di implementare solo a essere divertente in questo modo.
Ma questo è tutto si riduce fino a sotto la cappa.
Ma, naturalmente, la ricorsione è più del geekier
esempio tra quei trucchi speciali.
E sicuramente ci sono altri là fuori così che noi forse abbiamo nemmeno
scoperto ancora.
>> Quindi uno sguardo, o prendere in considerazione ora il seguente programma,
e certamente afferrare qualsiasi di questi sulla vostra uscita.
Ho intenzione di andare avanti e aprire un programma che è
andando a provare a sostituire due valori.
Ma prima di andare lì, facciamo questo.
Potremmo ottenere un altro volontario, penso?
Vuoi fare volontariato?
No?
Vieni su.
Tutto ok.
Così il vostro nome è quello che?
>> LAUREN: Lauren.
>> DAVID J. MALAN: Lauren.
Vieni su, Lauren.
Così Lauren è essere sfidato qui di seguito.
Felice di conoscerti.
Così Lauren qui ha di fronte dei suoi due tazze vuote.
E abbiamo un po 'di colore arancione succhi di frutta e latte
e abbiamo intenzione di andare avanti e fare quanto segue.
Stiamo solo andando a riempire questo.
A poche once di latte qui e cerchiamo di riempire un po 'di succo d'arancia qui.
>> E davanti tutti questi membri del pubblico,
scambiare i due valori di queste tazze.
Mettete il succo d'arancia in tazza di latte e il latte nella tazza succo d'arancia.
Come si esegue questa operazione se foste a casa e aveva accesso ad altre forniture?
LAUREN: Mettere in un'altra tazza.
DAVID J. MALAN: OK.
Quindi cerchiamo di avere una temporanea variabile, se ci sarà.
E andare avanti ora e realizzare la stessa procedura swapping.
Così buono.
Abbiamo messo GU in temporanea variabili, il latte nella variabile GU,
e ora la variabile temporanea nella variabile latte.
OK.
Quindi molto ben fatto finora.
Così si scopre fuori-- ritenere che pensato per un momento.
Qui, a geek solo su un po ', questo sarebbe il corrispondente codice C
che abbiamo appena implementato.
Avevamo due ingressi, a e b, entrambi che ci limiteremo a dire che per semplicità sono
int di.
E notare qui, se voglio scambiare i valori di due variabili, a e b,
abbiamo davvero bisogno di un intermediario, un variabile temporanea, una tazza temporanea,
in cui il getto uno dei valori in modo da avere un segnaposto per esso.
Ma allora il codice è esattamente come Lauren qui attuata.
>> Ora, solo per ottenere un poco più pazzo, si rivela
che si può fare questo senza una variabile temporanea.
Per farlo correttamente, però, stiamo andando avere a barare con un po 'di chimica.
Abbiamo alcune coppe in più qui.
Quindi la cosa più vicina che sembra come latte e acqua perhaps--
o latte e OJ-- è che abbiamo un po ' acqua, quindi dovremo riempire questo uno
con poche once di acqua limpida.
Questo è probabilmente troppo.
Già.
Questo è decisamente troppo.
Aspetta un secondo.
>> E ora abbiamo il petrolio, che, se ben ricordo da metà classe chimica della scuola,
speriamo che non si mescola con l'acqua.
Ma che tipo di tipo di si presenta come il latte e succo d'arancia.
Così ora, senza l'utilizzo di una variabile temporanea,
potete scambiare questi due valori?
Così oli va nella tazza d'acqua, l'acqua entra nella tazza di olio.
LAUREN: No altre coppe?
DAVID J. MALAN: No altre coppe.
E io non ho in realtà testato questo prima di quest'anno
quindi non so se questo sarà effettivamente lavorare chimicamente.
Questo non doveva succedere.
Funziona?
Tutto ok.
Così la separazione?
Bene.
Ora siamo arrivati ​​a ottenere il acqua nella tazza altra.
Smarter concentratori chimica potrebbe probabilmente fare meglio di me.
>> LAUREN: L'acqua è sul fondo.
>> DAVID J. MALAN: Il water-- che era qual è fondamentale l'ultima volta che abbiamo fatto questo.
Devi farlo nel giusto ordine.
Già.
Va bene.
Così ora abbiamo due tazze di olio.
OK.
Va bene.
Ma chimicamente se questo ha funzionato di I--
>> LAUREN: Questa è l'acqua.
>> DAVID J. MALAN: Questo è per lo più di acqua.
Tutto ok.
Ma è ancora la stessa tazza di prima.
Quindi versare it-- provare laggiù.
OK.
Questo è un buon uso del tempo classe oggi.
OK.
Così ora we-- bello.
Una specie di.
Tutto ok.
Quindi molto buono.
Grazie a Lauren.
Molto ben fatto.
>> Quindi, solo a soffiare le vostre menti, e questo è forse qualcosa
giocare con se ti piace in ID CS50, è possibile, infatti, scambiare due variabili
senza utilizzare un numero intero temporanea.
E questo è il corrispondente codice C.
E se vi ricordate da ultimo Mercoledì, abbiamo introdotto, se per breve tempo,
alcuni nuovi operatori C. E lo fa chiunque ricordare ciò che la piccola carota
simbolo, quel piccolo triangolare simbolo dalla tastiera rappresenta?
Cosa bit per bit operatore?
>> PUBBLICO: EXOR.
>> DAVID J. MALAN: EXOR.
OR esclusivo.
Quindi, se volete, solo per divertimento a a casa, per dare a e b due arbitrario
valori come qualsiasi eight-- e io avrebbe scelto un valore di otto bit.
Se si esegue questa operazione con 32 bit, avrai molto rapidamente annoiarsi.
Ma basta dare un po 'di otto una valore che è indipendentemente, uno o due,
e dare un valore simile b.
E poi utilizzando la definizione di XOR dal Mercoledì scorso,
applicare tale a poco a poco, ciascuno dei questi otto bit in ciascuna di ae b,
e poi fare esattamente per questo codice.
E non è quello errato vedete qui sullo schermo.
Esso infatti si riduce a tre operazioni XOR
e in qualche modo magicamente un e b scambieranno le posizioni
senza perdere alcuna informazione.
>> Quindi il trucco olio e l'acqua è la vicino incarnazione mondo reale
Potrei pensare di imitare quello.
Ma è sicuramente più facile utilizzare una variabile temporanea,
come in questo caso qui.
E anche questo è un'opportunità dire, Anche questo tipo di micro ottimizzazione,
come un informatico direbbe, mentre una specie di divertimento
di cui vantarsi come hai fatto questo senza come scambiare con una variabile in più,
non è tutto ciò che convincente.
Poiché per salvare 32 bit, come nel caso di un int reale,
non è poi così avvincente su un sistema in cui
si potrebbero utilizzare decine di megabyte o ancora di più tale memoria in questi giorni.
Ed infatti, quando otteniamo a un set problema più tardi
e implementare ortografico correttore e avrete
essere sfidato a farlo con questo il meno RAM e poco
tempo possibile sulla computer-- ancora
una settimana per attuare it-- ti have-- sarete
sfidato per ridurre al minimo tali risorse.
E questo è davvero l'unico occasion questo semestre
dove sarete incoraggiati a radersi fuori anche le migliori prestazioni
costa altrimenti.
>> Quindi, come possiamo Cosa-- vedere questo in codice vero e proprio?
Lasciami andare avanti ora e di aprire un esempio
che deliberatamente si chiama No Swap perché non lo fa
infatti scambiare le variabili mentre in realtà si potrebbe aspettare.
Quindi, diamo uno sguardo.
Ecco un programma che non ha CS50 biblioteca in corso, I / O solo standard.
Ora abbiamo un prototipo per lo swap sulla parte superiore che ha appena
significa che è ottenuto da definire in seguito.
Ed ecco principale.
>> I arbitrariamente assegnato xey, rispettivamente, i valori uno e due
solo perché sono piccoli e facile da pensare.
E allora non mi resta che un mucchio di printfs dove ho un controllo di integrità. x è 1
ey 2 è presumibilmente che cosa quelle printfs diranno.
Quindi nessuna magia finora.
>> Poi ho intenzione di rivendicare con stampare def, scambiando dot dot dot.
Io vado a chiamare lo swap funzione, passando x ed y.
E supponiamo per ora che swap è implementato esattamente
come è stato un momento fa con una variabile temporanea.
E così io sostengo arditamente, scambiato.
x è ora presente ed y è ora che.
Ma il file, ovviamente, si chiama No Swap.
Quindi cerchiamo di realtà vediamo cosa succede.
Se compilo non swap e poi do ./noswap, x è 1, y è 2.
Scambiare scambiati.
x è 1, y è 2.
Così sembra in realtà essere viziato anche anche se swap-- facciamo scorrere verso il basso now--
è implementato esattamente per la codice che ho proposto un momento fa.
Quindi non stiamo andando per ottenere l'immaginazione con la roba XOR per ora.
Anche questo dovrebbe funzionare come con il latte e succo d'arancia,
ma non sembra funzionare.
>> Quindi cerchiamo di farlo di nuovo.
Forse sono io che non correvo nel modo giusto.
Così corriamo di nuovo No Swap.
Forse I-- no.
Quindi è solo non funziona.
Allora, facciamo un po 'di controllo di integrità.
Lasciami andare avanti qui in Swap e basta aggiungere, aspetta un minuto,
una è% i / n e facciamo plug-in del valore di una.
Perché voglio davvero per vedere cosa sta succedendo.
E in effetti, questo è una tecnica di debug
che si potrebbero utilizzare in orari d'ufficio o in casa, già
simile al primo semestre del Dan Il video di Armendariz in PSET3
in cui abbiamo introdotto stampa def come una tecnica raccomandata, almeno
per i casi semplici.
Lasciami andare avanti e correre fare ancora una volta non di swap, ./noswap.
>> Interessante.
Quindi notare ciò che sembra essere vero. X è 1, y è 2, ma a è 2 quando b è 1.
Così quei due in qualche modo preso scambiati ma xey non sono sempre scambiate.
Quindi, per essere chiari, quello che sta succedendo è, qui ho xey
e questi sono variabili locali nel campo di applicazione principale, sto passando in X e Y
scambiare.
Ora, scambio, come una funzione separata, è libero di chiamare i suoi argomenti
o la sua parametri tutto ciò che vuole.
Foo o bar o X o Y o ao b.
Giusto per chiarire che sono non identico xey per sé,
Ho detto a e b.
Ma potremmo chiamarli tutto ciò che vogliamo.
>> E così sembra di swap viene passato
x-- AKA a-- ed è essere passato y-- AKA b.
In qualche modo queste tre linee sono scambiando esattamente quei valori
come ha fatto Lauren con il latte e succo d'arancia.
Ma quando stampiamo i valori, e un b
sono infatti scambiare ma xe y hanno nessun cambiamento ad essi.
Ricordiamo che xey sono quassù.
>> Così possiamo vedere questo via un'altra tecnica pure.
E anche questa è una tecnica incorporato nel problema impostare tre.
Andiamo avanti e fare questo a CS50 ID se non l'hai già.
Sulla mano destra lato noi avere questa scheda Debugger.
E se si apre questo in su, ci sono alcune informazioni arcane
che è gettato a voi inizialmente.
Ma cerchiamo di prendere in giro questo pezzi molto velocemente.
>> Quindi uno, si vede variabili locali.
Risulta che costruire in CS50 IDE, e un sacco di ambienti di programmazione più
in generale, è un debugger.
Uno strumento che consente di vedere visivamente cosa sta succedendo all'interno del vostro programma
senza dover ricorrere all'aggiunta printfs e compilazione e l'esecuzione
e l'aggiunta di printf e la compilazione e in esecuzione, che già, in orario di ufficio
o la casa, è probabilmente sempre piuttosto noioso.
>> Così qui, in un momento, siamo andando a vedere in tempo reale
i valori delle nostre variabili locali.
Stiamo anche andando a essere in grado di impostare quelli che vengono chiamati i punti di interruzione che
sono opportunità nel mio programma per mettere in pausa esecuzione ad una specifica linea di codice
che mi incuriosisce.
Destra?
Questi programmi eseguiti in una frazione di secondo.
È un po 'bello per noi esseri umani più lenti per essere in grado di mettere in pausa, prendere un momento, vedere
quello che sta succedendo intorno a una certa linea di codice
senza il programma aratura attraverso di essa e la finitura del tutto.
Così un punti di interruzione intenzione di permettere a noi rompere e pausa a un certo punto.
>> Chiamata stack è un modo elegante per dire quali funzioni sono attualmente
essere chiamati in questo momento.
Principale è sempre chiamato prima.
Ma se chiama principale a funzione chiamata Swap,
realmente stiamo andando a vedere questo torre di funzioni che sono stati
chiamato in ordine cronologico inverso.
Quindi cerchiamo di vedere quello.
>> Ho intenzione di ridurre.
Ho intenzione di tornare al mio codice.
E proprio perché voglio essere pedanti qui,
Ho intenzione di andare avanti e fare clic appena a sinistra della linea di cinque.
E che crea un punto rosso.
E notare sul lato destro della strada che il debugger sa, hey,
Ho appena detto un punto di interruzione noswap.c linea a cinque, in particolare
in questa linea di codice.
Così il debugger sa che io hanno chiesto che la prossima volta
Ho eseguito il mio programma è di pausa esecuzione lì piuttosto che solo
l'esecuzione del tutto super veloce.
>> Così ora ho intenzione di fare clic sul debug pulsante nella parte superiore della IDE
e che sta andando a fare quanto segue.
E 'intenzione di aprire un po' inizialmente spaventoso secondo terminale cercando window--
debug remoto da ospitare tale e such--
e torneremo a quello che tutto questo significa che tra non molto.
Ma ciò che è importante per la società è che quel puntino rosso è stato colpito,
il debugger ha deliberatamente pausa execution--
non su quella linea per sé, ma sulla prima linea di codice effettivo in tale funzione.
Ed è per questo che la linea sette è ora evidenziato in giallo.
>> E ora diamo un'occhiata sul lato destro.
Sembra che, per impostazione predefinita, abbastanza bene, x ha quale valore?
0.
E y ha che valore?
Zero.
E questo è da aspettarselo in senso che x e y-- che line-- gialla ha
non ancora eseguita.
Quindi x non dovrebbero avere il valore 1.
Si può avere qualsiasi altro valore, un cosiddetto valore spazzatura.
E siamo stati fortunati in quanto è zero in questo punto, essenzialmente.
>> Così ora c'è solo pochi pulsanti abbiamo bisogno di cure
circa durante il debug in questo modo.
Notate qui, abbiamo un pulsante Play.
E se giochiamo o colpire riprendere, questo è solo
andando a correre attraverso il resto del programma
o fino a quando non colpisce un altro punto di interruzione.
Ma io non ho impostato nessun altro punti di interruzione quindi è solo
andare a correre fino alla fine.
Questo tipo di sconfitte le scopo di rovistando.
>> Così, invece, mi interessa queste icone a destra.
E se mi passa il mouse sopra loro, come si dovrebbe troppo,
vedrete piccoli consigli strumento tips--.
Questo è un passo sopra.
Ora questo non significa saltare la seguente riga di codice.
Ciò significa che solo eseguirlo e passare alla successiva, passare al successivo,
passare alla successiva.
In altre parole, tramite quel tasto, posso camminare
attraverso il mio codice di un passo alla volta.
Riga per riga, letteralmente.
Ora, il diritto di che, ce n'è un altro
che vedremo in un attimo.
Questo è il cosiddetto Step Into icona che è
andando a me consentire immersioni in un'altra funzione.
Ma vediamo questo in un attimo.
Quindi ho intenzione di fare clic su scavalcare.
Ed ora notare, come clicco questo tasto in alto a destra,
tenere gli occhi più o meno sotto locale Variabili e vedere cosa succede a x.
x è ora 1 perché la linea gialla è ora eseguito
e ci siamo spostati alla linea 8.
E in un attimo y dovrebbe speriamo che diventi 2.
>> Ora, nulla che interessante avviene per un po '.
Tutto questo è è printf.
E notare, a mio terminale secondario finestra, vedo l'output di stampa def.
E ora devo fare una decisione come il programmatore.
Posso scavalcare questa linea di codice, eseguendolo ma non
ottenere curioso di sapere cosa c'è dentro.
O posso davvero un passo in esso e andare dentro di sé Swap.
Allora, facciamo il secondo.
>> Lasciami andare avanti e fare clic Non Step Over ma Step Into.
Avviso, tutto ad un tratto finestra cambia
per evidenziare la prima riga di codice nel Swap.
Questa è la linea 21.
E ora, che una specie di funky è che, se si guarda qui, come previsto,
una virgola b è 1 e 2, rispettivamente.
Perché temperatura 32.767?
Ricordando che temperatura, molto simile la tazza vuota un momento fa,
è dichiarato qui sulla linea 21.
Perché 32,000- Voglio dire, perché è solo qualche valore strano?
Sì?
>> PUBBLICO: Non è inizializzato.
>> DAVID J. MALAN: E ' non è stato inizializzato.
Così il nostro computer sempre ha memoria fisica.
Ha sempre RAM fisica.
E c'è sempre Zero e uno è in là, giusto?
Perché stiamo usando il nostro computer di tutto il giorno,
si sta utilizzando il CS50 IDE oi server per tutto il giorno.
In modo che la RAM o ha alcuni zeri o qualcuno di alcuni o di zero e uno.
Non importa se o non si sta usando loro.
Non si può semplicemente avere in bianco spazi in cui si desidera bit.
Sono sia zero e uno.
>> Così si scopre che temperatura, perché non abbiamo ancora inizializzato esso,
abbiamo quelle a 32 bit, ma non ho stato inizializzato per i valori noti.
Quindi, qualsiasi fossero più recentemente utilizzato for-- quelle 32 bits--
stiamo solo vedendo i manufatti di alcune precedente uso di quei particolari 32
bits.
Appena clicco Step Over, però, uff, temperatura sta per ottenere il valore 1.
E se lo faccio di nuovo, una è sta per essere dato il valore 2
e poi b sta per essere dato il valore 1.
>> E così ciò che è bello ora questo punto della storia
è che il debugger è mostrandomi, super lentamente
al mio ritmo, cosa lo stato di Swap è.
Ma bando ai vertici qui, avviso che lo stack di chiamate in realtà
ha due strati ad esso.
Ora quello che è evidenziata come Swap, se clicco su Main invece,
notate come le variabili locali cambiano perché lo sviluppatore può solo salire
intorno e andare in qualsiasi ambito diverso.
Così, anche se stiamo facendo tutto questo lavorare e scambiando correttamente a e b,
se vado avanti e indietro tra Swap dove a è 2 e b è 1 e principale,
è principale stato colpito a tutti?
No.
Allora qual è il takeaway qui?
Beh, si scopre che in qualsiasi momento si chiama una funzione come swap,
e si passa argomenti, cosa si sta passando alla funzione Swap
in questo caso è una copia di tali argomenti.
Quindi, se X e Y sono ciascuno rispettivamente 32 bit, ciò che sta ottenendo Swap
è due nuovi locali variabili, o argomenti,
chiamato e b-- ma questi sono arbitrari names-- ma il modello di zeri
e quelli all'interno di A e B sono fila per essere identico a x e y
ma non sono la stessa cosa xe y.
>> È come se ha principale sul suo pezzo di carta il numero 1 e 2 per x ed y,
e poi quando mani pezzo di carta per Swap,
Swap diventa molto rapidamente la propria penna, scrive
1 e 2 sul proprio foglio di carta, mani indietro il xy originale principale
e poi fa il suo cosa con ae b.
E questo è importante perché ora super- questo ha implicazioni non banali
per in realtà la scrittura di codice corretto perché sembrerebbe non possiamo scambiare
due variabili.
>> Ho scritto una funzione Swap corretto.
Abbiamo implementato con Lauren come una funzione swap corretta in realtà,
ma a quanto pare niente di tutto ciò cose se non si può effettivamente
scambiare due valori in modo permanente.
Quindi abbiamo bisogno di un altro modo per arrivare realmente a questo,
e dobbiamo essere in grado di effettivamente risolvere questo problema.
E si scopre fuori-- e verremo di nuovo a questo particolare immagine
prima long-- questo è un modo che si potrebbe richiamare la memoria del computer.
E 'solo un rettangolo.
Si potrebbe disegnare qualsiasi numero di modi, ma è
conveniente per disegnare come rettangolo per il seguente motivo.
>> Stiamo per iniziare oggi e oltre parlando del cosiddetto stack.
E la pila è solo un pezzo di RAM-- un pezzo di memory--
che le funzioni hanno accesso quando si chiamano.
E così si scopre che a il fondo di questo stack
è dove tutte le variabili locali di principali org e C e org V e tutta quella roba
stanno per andare in default. E se Principale chiama qualche altra funzione come Swap,
bene, Swap sta per ottenere un altro strato di memoria fino sopra di esso.
>> E così, proprio per darvi un rapido superficiale foto di questo, se vado su qui--
e lasciami rispecchio questo sul overhead well-- quello che realmente ho,
se ci preoccupiamo soltanto del fondo dell'immagine, per ora,
è che quando ho eseguito un programma e principale viene chiamato,
Principale è dato un pezzo di RAM nel mio computer che è
in fondo a questo cosiddetto stack.
E ho intenzione di disegnarlo deliberatamente come un quadrato.
Quindi è come 32 bit o quattro byte.
E se questa funzione principale ha un variabile chiamata x per un valore di 1
e ha una variabile denominata y con il valore di 2, che è
come prendere questo frammento di memoria che Principale è stata proposta dal operativa
Sistema e dividendolo in modo che la prima variabile locale va qui,
il secondo va qui, e questo è tutto.
>> Quando chiama principale Swap, Swap ottiene la propria fetta di memoria
che noi disegniamo come questo dal sistema operativo,
e sta andando ad avere la sua proprie variabili locali basato
sulla nostra implementazione precedente con variabili locali un
e b che inizialmente ottenere i valori 1 e 2.
Ma poi, non appena il codice viene eseguito Swap,
e Lauren scambia in realtà il OJ e latte, che cosa sta succedendo?
Ebbene, questo 2 sta diventando un 1, questo 1 sta diventando un 2, e, tra l'altro,
vi è una variabile temporanea che viene usato che per tutto il tempo che alla fine
Va via.
Ma non ha importanza la quantità di lavoro che fate
in questa linea di-- in questo spazio di memoria, xey sono completamente intatta.
>> Quindi abbiamo bisogno di un modo per dare Swap e funziona come esso
accesso segreto, se si vuole, a funzioni like-- di memoria come x ed y.
Quindi, diamo uno sguardo a un esempio che aiuta
di vedere esattamente ciò che è stato succede tutto questo tempo.
Ho intenzione di andare avanti e di aprire Confronta Zero.
E ho intenzione di chiudere il nostro debugger, vado
per chiudere questo messaggio paura cercando il solo dice, aspetta un minuto,
sei nel mezzo di debug.
Io vado a nascondere questa scheda qui solo per tornare alla semplicità.
Quindi non preoccupatevi se GDB viene ucciso.
Questo significa solo che il programma ha stato smettere, deliberatamente in questo caso,
da me.
>> E ora Confronta Zero fa questo.
Sto utilizzando il CS50 libreria in I / O standard.
Ho una funzione principale che prima dice, dire qualcosa, e ottiene una stringa.
Poi dice ancora e ottiene un'altra stringa.
E notare che queste due stringhe sono chiamati s e t rispettivamente.
E ora questo programma, Confronta Zero, il suo scopo nella vita,
si suppone a dirmi, ho digitare la stessa cosa?
E così ho intenzione di nuovo in settimana uno.
Sto utilizzando il mio operatore uguale uguale che è l'operatore qualità.
Non l'operatore di assegnazione, l'operatore di uguaglianza.
Sto solo paragonando s e t.
>> Quindi cerchiamo di realmente andare avanti e fare questo.
E ho intenzione di andare avanti e fare Confronta Zero.
Ho intenzione di fare ./comparezero.
E ho intenzione di andare avanti e dire qualcosa
come, facciamo mamma in minuscolo E per quanto riguarda la mamma in maiuscolo.
E, naturalmente, si digita cose diverse.
Tutto ok.
Questo è da aspettarselo.
>> Corriamo ancora.
Entrambe le volte fanno in minuscolo, minuscolo.
Che sembra eccellente identico a me.
Invio.
OK.
Forse è solo strano perché non è gradire la mia grammatica.
Allora, facciamo un MOM del capitale, capitale MOM, identici.
Cose differenti.
>> Allora perché?
Ebbene, che cosa sta realmente succedendo in sotto la cappa qui?
Quindi cerchiamo di andare indietro sopra qui solo per un attimo
e considerare ciò che GetString è in realtà facendo.
Quando si chiama GetString, questa è una funzione che abbiamo
noi scritto e in qualche modo ottiene un sequenza di caratteri da parte dell'utente.
E supponiamo che il primo volta che chiamo GetString, che mi dà
un pezzo di memoria che assomiglia a questo.
E se ho digitato tutto minuscolo m-o-M-- e cosa succede dopo?
Solo un controllo di integrità rapido.
>> Pari a zero backslash.
Lo sappiamo.
E ricordiamo che abbiamo giocato in giro con il nome di Zamila
e un sacco di altri nomi quando Rob è stato qui in cerca
a quello che sta succedendo all'interno della memoria.
In modo che la storia è esattamente la stessa.
Questo è ciò che GetString sta tornando a me.
Ora, il mio codice un attimo fa memorizzata il valore di ritorno di GetString
in una variabile denominata s.
E poi la seconda volta che la chiamava, è conservato in una variabile chiamata t.
>> Quindi, se vado qui, ho bisogno per disegnare questo variable-- locale
e sto in generale andando a disegnare una stringa come solo-- faremo
chiamare S-- come una piazzetta qui.
E ora, come fa la mamma somehow-- andare all'interno di questo s variabile?
Beh, abbiamo bisogno di tornare indietro per primi principi qui.
Che cosa è realmente GetString tornando?
>> Così si scopre che M-O-M backslash zero e un numero qualsiasi
di altre stringhe in memoria come Zamila e Rob o Andy e tutti gli altri,
sono naturalmente nel nostro RAM del computer o della memoria.
E la RAM ha like-- avete un giga di RAM, due concerti di RAM,
o un miliardo o due miliardi di byte, o forse anche di più in questi giorni.
Quindi supponiamo, per finalità di oggi, che non importa il modo in cui annoveriamo
loro, ma siamo in grado di numerare ogni di quelli miliardo o due miliardi
o quattro miliardi di byte.
>> E diciamo solo arbitrariamente dire che questo è il primo morso, secondo morso,
terzo, quarto.
Non sto usando deliberatamente zero oggi, ma ci torneremo a questo.
Quindi, in altre parole, se questo è il molto prima volta che sto utilizzando il programma,
Sto solo avere fortuna e il primo morso è in posizione uno poi due
poi tre a quattro.
E se ho continuato a disegnare, numero di casella due miliardi sarebbero fin qui.
>> Allora, cosa ne pensi, poi, GetString ritorna in realtà?
Non è il ritorno M-O-M backslash nulla di per sé, perché questo chiaramente
non si adatta nella casella che ho disegnato.
Quindi, che cosa potrebbe realmente GetString Ritorneremo tutte queste settimane?
La risposta è sul bordo qui da qualche parte.
Non si può andare bene M-O-M backslash a zero, così quello che potrebbe avere un senso, invece?
Se dovessi essere super intelligente, mettendo il cosiddetto cappello engineering,
quello che si potrebbe tornare?
Qual è la quantità minima di informazioni si potrebbe tornare che sarebbe ancora
consentono di trovare M-O-M in memoria?
Sì?
>> PUBBLICO: Uno.
>> DAVID J. MALAN: One.
E perché uno?
PUBBLICO: Perché avrebbe detto dove andare [incomprensibile].
DAVID J. MALAN: Esattamente.
Sto solo andando a restituire l'indirizzo della stringa che ho ottenuto.
L'indirizzo in questo caso è la posizione uno.
Quindi, ciò che realmente viene memorizzato in S-- e ogni variabile stringa così far--
è appena stato indirizzo di tale stringa.
>> Nel frattempo, se io chiamo GetString una seconda volta e mi
digitare letteralmente la stessa cosa-- M-O-M con lowercase-- M-O-M
e un altro backslash pari a zero, e ora forse il mio programma di
stato in esecuzione per qualche tempo così forse questo è 10, questa è la posizione 11, questo è 12,
questo è 13.
I computer che utilizzano un altro memoria per qualsiasi motivo.
Ciò che ora va nel mio secondo variabile nel mio programma t?
10.
Esattamente.
>> E così quando guardiamo la il codice sorgente di questo programma
dove sto semplicemente cercando per confrontare i due valori,
è s uguale uguale a t, ciò che è la risposta umana ovvia?
Proprio no, perché uno non è uguale a 10.
E così qui sta un opportunità per noi davvero
di andare solo indietro per, ancora una volta, prima principi e pensare, beh,
cosa sta succedendo sotto il cofano?
Abbiamo parlato bit e byte e la memoria,
ma in realtà è utile per capire perché quando si chiama GetString,
anche se pensiamo che è tornando M-O-M o stringa di mamma
o Andy o Zamila o simili, tecnicamente
è solo restituendo l'indirizzo di quel pezzo di memoria.
>> Ma va bene.
Perché come faccio a sapere dove la stringa finisce?
Se mi sono dato solo l'inizio?
Beh, il backslash a zero, giusto?
Appena in tempo lineare che posso stampare con la stampa def M-O-M.
E non appena vedo backslash pari a zero, non mi importa dove ho iniziato,
So già implicitamente dove ho bisogno di finire.
>> E così oggi ricorre il beginning-- e mi permetta di fare questo in modo drammatico perché noi
ha attraversato un sacco di problemi a ottenere questi qui formazione wheels--
così oggi le ruote di formazione iniziano per venire fuori e ci rivelano almeno:
>> [Applausi]
>> Questo è stato ben vale il viaggio a Target questa mattina, sì?
Così now-- c'è, si trasforma fuori, una cosa come stringa.
Stringa non esiste.
E 'un sinonimo che abbiamo avuto all'interno della biblioteca CS50.
D'ora in poi, stiamo per iniziare a chiamare s e t non stringhe ma char stelle.
E la stella char faremo prendere in giro a parte in breve tempo.
Ma questo per dire, che, anche se continuiamo
utilizzando GetString per ora, tecnicamente dovrei
essere dicendo char e char stella stella.
>> E si scopre che cosa stella sta per denotare qualcosa
chiamato un puntatore o un indirizzo.
E infatti, un teaser per quello che ci aspetta
è questa seconda clip 20 dal nostro amico Nick Parlante a Stanford
che, qualche tempo fa, spendere una quantità ridicola di tempo,
come meglio posso dire a suo cucina o la sua cantina,
rendendo claymation conoscere il mondo
un personaggio di nome Binky con i quali ci sarà
introdurre la prossima volta a puntatori.
Così qui è un'anteprima di quello che verrà.
>> [RIPRODUZIONE VIDEO]
>> Ehi, Binky.
Svegliare.
E 'il momento per l'indicatore del divertimento.
>> -Che cos'è?
Ulteriori informazioni su puntatori?
Oh, Goody.
>> [FINE RIPRODUZIONE]
DAVID J. MALAN: E su questa nota, ci vediamo il Mercoledì.
Tutto ok.
Chi è la danza?
Avanti.
Chi è la danza?
Vuoi che farla partire?
Prendo ha cominciato.
Woooo!
>> LAUREN: fantasia dolce Mosè.