>> JASON HIRSCHHORN: Benvenuto per tre settimane, tutti.
Abbiamo un occupato, ma entusiasmante parte davanti a noi.
Quindi, in primo luogo, perché abbiamo fatto qualche progressi con il corso, ma dobbiamo ancora
hanno un sacco di apprendimento resta da fare, io sono intenzione di mostrare voi ragazzi alcune risorse
che dovrebbe rivelarsi incredibilmente utile come ci si avvicina non solo il vostro
problema di imposta, ma anche digerire tutto il materiale che vi diamo ragazzi
lezioni e pantaloncini e la sezione.
>> Poi andremo a spendere i primi 20 a 25 minuti di sezione andare oltre
GDB, che si può o non può avere usato a questo punto, ma è un
incredibilmente utile strumento che eseguire il debug del programma.
Molti di voi potrebbe aver utilizzato printf nel metà del programma per capire
ciò che una variabile pari.
GDB è anche meglio di printf e non rovinare il vostro codice, perché si
eseguirlo su un file eseguibile.
Così andremo oltre il 10 più disponibile comandi necessari per GDB, e siamo
intenzione di andare in un esercizio insieme in modo in problema di impostare tre e oltre, si
possono utilizzare GDB per aiutare il debug i vostri programmi.
E, infine, abbiamo intenzione di andare oltre alcune ordinamento e ricerca di algoritmi
che avete visto in conferenza, e siamo andando in realtà il codice, e non solo
pseudocodice, ma il codice binario di ricerca, bubble sort e selection sort.
>> Quindi in primo luogo, io voglio andare sulle risorse.
Questa è una lunga lista, ed è carattere più piccolo, perché ho avuto un sacco di
stare su qui.
Ma questi non solo vi aiuterà, ancora una volta, con i set problematiche e
digerire le informazioni che hai imparato, ma sicuramente, venuto il tempo quiz, questi saranno
essere incredibilmente utile.
Quindi in primo luogo, la conferenza rileva.
Se andate a cs50.net/lectures e scorrere fino alla settimana e giorno specifico,
vedrete che ci sono note per ogni lezione, che non è semplicemente un
trascrizione, ma una versione modificata di ciò che è stato coperto in conferenza con il codice
frammenti e altre delizie voti.
Consiglio vivamente di andare su quelle.
E poi così, c'è il codice sorgente disponibile da ogni lezione.
E ancora, queste diapositive saranno anche disponibile online all'indirizzo cs50.net/sections
questa sera.
>> Quindi secondo sono i pantaloncini ogni settimana che Argomenti di copertura, di solito 5-15
minuti di lunghezza.
E quelli si spera vi darà un grande fondo su diversi argomenti.
Terzo -
e questo è nuovo di zecca questo anno - è study.cs50.net.
Se non hai controllato fuori, mi consigliamo di farlo.
Si arriva a scegliere un argomento.
Abbiamo decine di argomenti in là.
Così, per esempio, si sceglie funzioni.
Ti dà alcune diapositive e note sulle funzioni.
Coloro che sono in realtà le diapositive che TF sono incoraggiati ad utilizzare durante la nostra
presentazioni in sezione.
Ci sono anche consigli e suggerimenti per affrontare con funzioni, e c'è
problemi pratici che aiutano si lavora con le funzioni.
Vi diamo anche collegamenti a breve su funzioni e le volte che funzioni
sono venuti a lezione.
Così study.cs50.net, nuovo questa anno, una risorsa fantastica.
>> Poi, ho l'uomo, che è il manuale comando che è possibile eseguire al
riga di comando.
Quindi, se avete domande su un comando, per esempio, rand, che abbiamo
incontrato la scorsa settimana durante la sezione e probabilmente avete incontrato in
il problema impostato quando passa attraverso il generare il codice, ma se si digita l'uomo
rand, si otterrà la pagina tutto racconta rand.
Ti dà quello che ci vuole, l' parametri che prende, nonché di restituzione
tipo e una breve descrizione di tale funzione.
>> Allora date un'occhiata rand.
Può essere un po 'prolisso e confuso, così a volte trovo che
semplicemente Googling quello che voglio sapere è il modo migliore per trovare la risposta.
Quindi praticare con Google.
Get bravo a Google.
Esso diventerà il vostro migliore amico.
>> Così come Google, se non è possibile trovare su Google, cs50.net/discuss, è
il forum di discussione.
Le probabilità sono se avete una domanda, una dei tuoi 700 + coetanei ha anche che
domanda e può essere chiesto già nel discutere
forum e lo hanno risposto.
Quindi, se avete una domanda comune o avete una domanda che si pensa
magari altre persone avrebbero potuto incorrere in, check out cs50.net/discuss.
>> Infine, gli ultimi due, se si vuole parlare con un vero e proprio essere umano, ufficio
ore Lunedi al Venerdì.
C'è anche l'orario di ufficio on-line per gli studenti di estensione.
E per ultimo ma certamente non meno importante, me, punto esclamativo.
Tutti voi avete le mie informazioni di contatto.
Se avete bisogno di qualcosa, per favore non esitate a contattarmi.
Sento sempre libero di farlo.
Pochissimi di voi mi hanno aggiunto Gchat, tanto che è stata deludente,
ma spero che ti cambia tra questo e il prossimo capitolo.
Tutte le domande finora sulle risorse?
Grande.
>> Infine, un'altra spina per feedback, sayat.me/cs50.
Mi puoi dare un feedback anonimi su come sto facendo.
Questo è stato davvero utile la scorsa settimana.
Ho un paio di commenti da voi ragazzi subito dopo la sezione, più da
altri studenti che hanno guardato lo durante la settimana, e
era incredibilmente disponibile.
Ho intenzione di cercare di limitare il mio uso di la parola "dolce", ma io ti mostrerò il mio
entusiasmo ed eccitazione in altri modi.
Ma c'erano altre aggiuntivo Giudizi di merito,
entrambe vantaggi e delta.
Quindi, per favore, io do voi ragazzi le risposte il vostro set di problemi.
Sentitevi liberi di darmi le risposte il mio insegnamento.
Sono qui per voi ragazzi.
>> Grande.
Questo è tutto quello che ho per la prima sezione.
Qualcuno ha domande finora?
E ho una nota per il centro di controllo.
Studenti di estensione mi hanno messaged dicendo che non stanno ricevendo alcun audio,
ma che è fuori del mio potere di fissare.
Così si spera, che ottiene risolto a breve.
Se stai guardando on-line, hi, ma tu non mi puoi sentire.
>> Quindi in primo luogo, stiamo andando passare attraverso GDB.
GDB, come ho accennato in precedenza, è uno strumento di debug
molto meglio di printf.
Quindi, per iniziare con GDB, voi ragazzi, se si vuole aprire il vostro apparecchio
e prendere il file che ho mandato a te prima - questo file sarà anche
disponibile on-line in un po '-
ed eseguire GDB. / il nome del file.
In primo luogo, naturalmente, è necessario compilare file perché GDB funziona solo su
file eseguibili.
>> Ma se si volesse iniziare GDB, la prima cosa che fai,
si esegue GDB. / Cesare.
Ecco, questo è il nome del programma che siamo intenzione di andare con lui in questo momento.
Quindi ho intenzione di scrivere rendere Cesare, che mi darà un file eseguibile
qui evidenziata in verde.
E poi io vado a correre GDB. / Cesar.
>> E ci si va.
Si vede che abbiamo un testo che mi dice sulla versione di GDB, dandomi
alcune informazioni di garanzia, e poi ci avere il prompt PIL, che sembra sort
di come il nostro prompt dei comandi, ma si vede che è aperto
paren, GDB, vicino parentesi.
Prima di continuare ed eseguire il debug questo file che ho inviato a tutti voi, diamo un'occhiata a
alcuni comandi utili in modo da avere un senso di quello che stiamo andando a coprire.
>> Questi comandi sono qui elencati nella ordine in cui io generalmente li uso.
Così comincio il mio programma eseguendo GBD. / Nome del programma,
in questo caso, Cesare.
E poi la prima cosa che faccio al 99,9% del tempo è tipo di interruzione media.
Che imposta un punto di interruzione al principale.
In sostanza, quello che stai facendo lì è il programma sta per fermarsi a
principale, in modo da poter iniziare a esaminarlo linea per linea, piuttosto che correre tutto
il modo attraverso.
È possibile interrompere in diversi punti il codice, ma principale è generalmente un
buon punto di partenza.
>> Il comando successivo corro è a conduzione.
Che avvia il programma in esecuzione, e se è necessario immettere riga di comando
argomenti, si esegue quel comando.
Eseguire con gli argomenti.
Quindi, dal momento stiamo andando su una versione di C, che è il programma di voi ragazzi
ha scritto per pset due -
questo, naturalmente, ha alcuni bachi in essa che si spera troveremo -
stiamo andando a correre corsa con qualche comando gli argomenti della riga perché Cesare,
come voi sapete per il problema set spec, richiede un po '
argomenti della riga di comando.
>> La prossima coppia di comandi, il prossimo uno è effettivamente chiamato successivo.
Quello ti porta riga per riga tramite il programma.
Quindi colpire n, quindi Invio porta alla riga successiva, eseguendo
la riga precedente.
Passo che richiede non solo di la riga successiva, ma
ti porta funzioni all'interno.
Quindi, se avete scritto una funzione in il codice o se si vuole esplorare un
a Io, per esempio, si può colpire s, e piuttosto che andare alla riga successiva di
il file che si sta passando a destra ora, ci troveremo a passo in
questa funzione e vedere il suo codice.
>> Elenco mostra, molto facile da usare formato, i 10 o giù di lì linee intorno
dove siete attualmente nel codice in modo da poter effettivamente vedere il file
piuttosto che dover scambiare indietro e indietro tra diversi punti di vista.
La stampa è come printf, come suggerisce il nome.
Che si mostra ciò che una variabile è uguale.
>> Info gente del posto è veramente utile.
Questa è una versione speciale di stampa.
Info gente del posto ti mostra tutti i locali variabili, li tutte le stampe per voi
che sono attualmente disponibili.
Quindi io in genere, piuttosto che dover stampare le quattro variabili che sto
curioso di sapere se sono in un ciclo for, per esempio, ho appena scrivo informazioni locali,
e mi qual è il mio contatore ti faccio vedere uguali, così come la matrice che sono
lavoro sul pari.
>> Infine, continuare.
Digitando pausa si ferma al punto di rottura.
Si può camminare attraverso la linea da linea con successiva e passo.
Continuare esegue il programma per il vostro prossimo punto di rottura o fino al completamento se
non ci sono più punti di rottura.
Disable rimuove punti di rottura, se si ha deciso la pausa principale era
appropriato, si vuole impostare da qualche altra parte.
E infine q, uscire, esce di GDB.
>> Quindi questo programma. / Cesare, stiamo andando di guardare attraverso in questo momento e abbiamo
stanno andando a utilizzare GDB per trovare i bug in questo programma.
Ho eseguito questo programma precedente con Controllare 50, e ho avuto un cipiglio.
Tutto ciò che è esistito, è compilato, superato molte prove, ma per
qualche ragione, non ha superato il quinto prova, girando barfoo, tutte le protezioni, in
E-D-U-I-R-R, tutte le protezioni, usando tre come chiave.
Ho avuto abbastanza vicino.
Scesi da una lettera.
Quindi c'è qualche piccolo errore qui.
Ho guardato attraverso il mio codice.
Non riuscivo a capire.
Speriamo, voi potete aiutarmi capire ciò che questo bug è.
>> Ecco, questo è l'errore che siamo cercando.
Muoviamoci in GDB.
Ancora una volta, ho eseguito GDB. / Cesare, così ora siamo in GDB.
E qual è il primo cosa devo fare?
Ho appena entrato GDB.
Qualcuno mi dia un buon comando per entrare.
>> STUDENTE: Rompere principale.
>> JASON HIRSCHHORN: Rompere principale.
Fantastico.
Proviamo quindi a digitare che trovi
Voi potete guardare qui o seguire lungo sui computer.
Rompe principale, e vedrete un punto di rottura è stato fissato a -
mi dà qualche indirizzo di memoria strano, e mi dà anche il numero della linea.
Se dovessi guardare indietro a questo file, Vorrei capire che principale
successo on line 21.
Cosa devo correre il prossimo?
È il mio programma in esecuzione?
No.
Allora cosa devo correre il prossimo?
>> STUDENTE: Run.
>> JASON HIRSCHHORN: Run.
Devo solo correre correre, o dovrebbe Aggiungo alcune altre cose?
>> STUDENTE: Eseguire con l'argomento.
>> JASON HIRSCHHORN: esecuzione con gli argomenti del comando.
E dato che sto debug di un ben preciso caso, devo entrare in quella
argomento della riga di comando.
Quindi io non corro tre, che è, ancora una volta, l'output che ho ricevuto da partner di 50.
L'avvio del programma.
Attraversiamo un paio di righe.
Vedrai che siamo sulla linea 21.
Come faccio a sapere che siamo sulla linea 21?
Perché se si guarda a sinistra della mia finestra di terminale, vi
dice la linea 21.
E questo mi dà, in realtà, l' codice che è alla riga 21.
Così ho misspoke in precedenza.
Principale non è in realtà in linea 21.
Principale è un paio di righe sopra 21.
Ma alla riga 21, che è dove stiamo rompendo.
Questa riga di codice è non ancora eseguita.
Questo è importante.
La linea che vedete non ha stata ancora eseguita.
Questa è la riga di codice successiva si sta per eseguire.
>> Così la linea successiva, come voi siete probabilmente familiarità con, questo
condizione di controllo per vedere se ho entrato in un argomento della riga di comando.
E una di i, qual è il secondo parte di quel fare?
Che è una di i?
>> STUDENTE: modifica in un numero intero.
>> JASON HIRSCHHORN: Sorry?
>> STUDENTE: Sta cambiando l' argomento di un numero intero.
>> JASON HIRSCHHORN: Quindi una per i cambiamenti arg v1 da una stringa in un intero.
E poi che cosa è il controllo?
>> STUDENTE: Se c'è un secondo argomento della riga di comando, da parte
l'esecuzione del programma.
>> JASON HIRSCHHORN: E che cosa è la seconda metà di questo
Espressione booleana controllo?
Questa parte qui, una per i?
>> STUDENTE: Se è negativo.
>> JASON HIRSCHHORN: Fare in modo che cosa?
>> STUDENTE: Fare in modo che è, infatti, positivo.
>> JASON HIRSCHHORN: Esattamente.
Questo è il controllo per vedere se è negativo, e se è negativo, io
avere una sensazione riga successiva potenza essere me urlando presso l'utente.
Quindi cerchiamo di colpire fine di eseguire questa riga.
Noi non vediamo che la linea che voi ragazzi forse si aspettavano di vedere urlare al
utente e poi tornare, perché questa linea non è stato eseguito.
Entrai 3.
Così ho fatto, infatti, entro due comando gli argomenti della riga, e 3 è
maggiore di zero.
Così abbiamo visto che la linea, abbiamo eseguito, ma non abbiamo fatto un passo
all'interno della condizione if.
>> Così ora, dopo, vedo che sto impostando chiave int equivale a per i ARG v1.
Così che è mi creazione di una chiave variabile.
Quindi, se mi stampare chiave in questo momento, perché che permette di vedere il
valore all'interno della variabile, chiave è uguale a 47.
Questo è strano, ma, naturalmente, è perché non ho
eseguito ancora quella linea.
Così ora se ho colpito n, eseguire quella linea, e fare tasto di stampa, la chiave sarà uguale a 3,
che è quello che ci aspettiamo di uguale.
>> Quindi, di nuovo, nel GDB, la linea si vedete non avete ancora eseguito.
Devi colpire n o s o un numero di altri comandi per effettivamente
eseguire quella linea.
Tasto di stampa.
Di chiave a 3.
Fin qui, tutto bene.
String è testo normale.
Facciamo execute quella linea.
Ricevo una stringa da utente.
>> Vediamo nel mio partner di 50, ho Inserisci barfoo tutti i tappi, così
questo è quello che farò entrare.
Se ora stampare testo normale.
Vedrete che equivale a una stringa.
Mi dà qualche altra strana esadecimale numero, ma lo fa in
Infatti dire che la mia stringa è barfoo.
Se volevo vedere cosa chiave è pari a questo punto, come ho potuto verificare chiave?
>> STUDENTE: tasto Stampa.
>> JASON HIRSCHHORN: tasto Stampa, esattamente.
E in realtà, c'è una scorciatoia.
Se siete stanchi di digitare stampa, si può semplicemente digitare p.
Così chiave p fa la stessa cosa esatta.
E ancora, lo vedo uguale a 3.
>> Se volevo scoprire cosa sia il tasto e barfoo eguagliato allo stesso tempo
ma ero stanco di digitare ogni individualmente fuori,
potrebbe digitare informazioni locali.
Questo mi dà eguali chiave 3.
Testo normale uguale barfoo.
Mi dà anche queste due cose strane nella parte superiore, la variabile i e
questa variabile n.
>> Coloro che sono in realtà già esistenti nel mio programma principale.
Noi non li abbiamo ancora incontrato, ma come anteprima, quelli
esiste nel mio ciclo for.
Così adesso, sono uguali un po 'strano numeri perché non sono stati
ancora inizializzate, ma loro esistono ancora in memoria, quindi sono appena impostati
ad un certo valore immondizia.
Ma noi vediamo chiave in pianura testo proprio lì.
>> Quindi ho intenzione di eseguire questa linea, linea 34, il ciclo for.
Stiamo andando a saltare in per il ciclo colpendo n.
E noi siamo dentro il ciclo for.
Siamo al nostro primo controllo.
E ancora, questi dovrebbero sorta di guardare familiare a voi, perché questo è stato un
Programma di Cesare che è stato scritto, ma ancora una volta, ha una sorta di bug.
>> E ora se faccio informazioni locali, perché sono all'interno di tale ciclo for, vedrai
che ho è uguale a zero, come ci aspettiamo.
Questo è quello che abbiamo impostato per e inizializzato It To nel ciclo for.
n è uguale a 6.
Questo rende anche senso perché noi mettemmo al strlen di testo normale.
Così mi piace fare informazioni residenti o stampa alla variabile spesso per assicurarsi che
tutto è sempre quello Mi aspetto che uguale.
In questo caso, tutto è quello che mi aspetto che uguale.
>> Quindi cominciamo muove attraverso questo per ciclo.
La linea Sono on è la linea 36, ​​se pianura testo i è maggiore di una semplice e
testo i è minore o uguale a z.
So che il mio problema non è con il mio primo lettera, è con la seconda lettera.
Se guardiamo indietro al check 50, B va a E bene.
Sto prendendo la A e lasciando come una A, non cambiarlo a D. Quindi
qualcosa non va con la seconda lettera.
Quindi ho intenzione di muoversi lì in un secondo.
>> Ma se volevo controllare ciò pianura testo che ho eguagliato in questo particolare
caso, penso che dovrebbe essere quello?
Cosa dovrei testo normale ho eguagliare in questo primo turno attraverso il ciclo?
>> STUDENTE: Zero?
>> JASON HIRSCHHORN: Testo normale di I?
Quindi dovrebbe essere capitale B. I, naturalmente, è uguale a zero, ma solo testo
Staffa di zero parentesi chiusa è uguale a B perché le stringhe, come abbiamo visto la scorsa settimana,
siamo array, quindi stiamo ricevendo il primo carattere da quello.
Quindi, di nuovo, se ho stampato in testo normale Io, io, infatti, ottenere il carattere
B. E questo è pulito, giusto?
Io in realtà non ho testo normale I. Che non è una delle variabili ho impostato
o inizializzato, ma è possibile stampare su tutta una serie di cose
se vuoi.
>> Ma passiamo attraverso.
Se solo testo I è maggiore di A e testo normale I è minore o uguale a
Z, che è chiaramente vero perché abbiamo la B maiuscola vado a correre
qualche comando su di esso.
Abbiamo visto che la matematica la settimana scorsa, quindi dovremo dare per scontato che funziona
destra secondo Partenza 50.
>> Queste parentesi graffe, il primo mostrato che stavo uscendo dal se
condizione, il secondo mostrava che sto uscendo dal ciclo for.
E così ora, quando ho colpito successivo, vedremo siamo tornati al ciclo for nuovamente.
Stiamo passando attraverso la per il nuovo ciclo.
Facciamo in realtà un passo nel secondo iterazione del ciclo for e tipo
Informazioni locali.
>> Quindi siamo nella seconda iterazione del nostro ciclo per.
I è uguale a 1, che ci aspettiamo.
N è uguale a 6, che ci aspettiamo.
Key è uguale a 3, che ci aspettiamo.
E solo testo, vedrete, Equals EARFOO ora, non barfoo più perché
nel nostro iterazione precedente, il B era cambiato in un capitale E. Quindi stiamo
incontrare il problema, quindi questo è dove stiamo andando a
tuffarsi nel debugging.
Ma qualcuno ha delle domande in merito a quello che abbiamo fatto finora?
Fantastico.
>> Quindi stiamo per eseguire questo se condizione normale staffa di testo ho chiuso
staffa superiore A e testo normale io minore o uguale a Z. Ma prima
Vado in quella, perché è qui So che il mio errore è, voglio sottolineare
fuori testo in chiaro di I. Quindi mettiamola stampa.
Fa uguale al carattere A, in modo che sembra finora, tutto bene e buono.
>> Quindi mi aspetto che questa linea per la mia logica, questa linea dovrebbe essere vero.
E 'una lettera maiuscola.
Ma se ho colpito n, ci rendiamo conto che questo linea, infatti, non è stata eseguita.
Saltai giù al else if.
Perché è successo?
>> STUDENTE: Perché avete la vostra condizione di testo normale è maggiore
di A, sia pari o superiore.
>> JASON HIRSCHHORN: Così ho avuto il mio testo normale I è maggiore di A, non superiore
o uguale a.
Quindi, chiaramente, la A maiuscola non ha attivare questa se la condizione, e lo abbiamo fatto
non passo in esso, e lo abbiamo fatto non fare il cambiamento necessario.
Allora è così, in realtà.
Ho capito il mio errore.
Potrei tornare nel mio file di origine, modificarlo e aggiornarlo e
eseguire Verifica 50 nuovamente.
>> Ma vedremo, solo per la pedagogia del bene, se continuo ad andarci.
L'altro, se non esegue neanche, ma ciò che invece è uguale è il comando
che non cambia.
Quindi non è cambiato affatto, e se io stampare il testo normale qui, vedremo andando
attraverso quel ciclo for non ha, infatti, cambiamento che secondo personaggio a tutti.
E 'ancora un capitale A.
>> Così ancora una volta, abbiamo debug nostro errore.
Ci siamo resi conto che c'era una logica mancante.
E noi debug prima del tempo, prima espletare effettivamente quella linea,
ma si sarebbe accorto se avessimo appena premere Avanti e passare a quella else if,
ciò significa che se tale condizione non era vero.
Non abbiamo, infatti, otteniamo il risultato che ci aspettavamo.
Allora avremmo potuto essere richiesto, avevamo Non siamo stati così astuti, a guardare
che se la condizione e verificare se, in effetti, la nostra condizione dovrebbe valutare a
vero nel contesto attuale.
>> Questo è tutto per il debug di questo programma.
Qualcuno ha delle domande?
Quale comando potevo colpire smettere di GDB?
D. E poi mi verrà chiesto, esce comunque?
Sì o no.
Mi ha colpito di sì, e avrò smettere di GDB.
>> Così che era un primer veloce di GDB.
In realtà, in uno scenario reale, Ho fatto questo in orario di ufficio.
Ho GDBed questo programma esatto a Orario di ricevimento con uno studente.
E se torniamo ai comandi che abbiamo visto prima, abbiamo utilizzato pausa principale, prima
cosa che abbiamo fatto.
Abbiamo usato corsa con gli argomenti della riga di comando, seconda cosa che abbiamo fatto.
Abbiamo usato accanto un sacco di muoversi noi attraverso le linee.
E ancora, la versione corta del prossimo è n.
Ecco le parentesi in grigio sulla diapositiva.
>> Non abbiamo usato passo, ma non abbiamo necessariamente per questo caso.
Ma potremmo usarlo in un po 'più tardi oggi se siamo debug, per
esempio, la ricerca binaria quando binaria ricerca viene chiamato in un separato
funzione, ma c'è certo errore con esso.
Stiamo andando a voler entrare in la chiamata alla ricerca binaria e
in realtà il debug.
Lista non abbiamo usare o perché abbiamo avuto un buon senso del nostro codice, ma se mi
voleva ottenere un senso di codice di quello che ho era intorno, ho potuto solo usare la lista.
>> Stampiamo abbiamo usato, informazioni locali che abbiamo usato.
Continua non abbiamo bisogno di usare in questo caso, non avevamo bisogno di usare
disattiviamo, ma abbiamo fatto uso smettere.
Di nuovo, questi comandi 10, praticarle.
Se si capisce questi comandi 10, si dovrebbe essere impostato per il debug di qualsiasi
emettere con GDB.
>> Quindi siamo in procinto di andare avanti, di nuovo, per la nodo della sezione di oggi, andando oltre
Questi ordinamento e ricerca algoritmi.
Prima lo facciamo, ancora una volta, tutte le domande, commenti, preoccupazioni per GDB?
Così è ognuno userà GDB piuttosto che printf?
Così tutti, per il bene di perpetuità, tutti annuisce il loro diritto di testa
ora, così ti vedrò in orari di ufficio e tutti i TF ti vedranno e
diranno, mi mostra come utilizzare GDB, e sarete in grado
per mostrare loro, giusto?
Tipo di?
Forse si spera.
Freddo.
>> Quindi stiamo andando a muoversi in ordinamento e ricerca.
Vedrete Ho una lista già ordinata per noi, ma che non sta
essere il caso sempre.
Così nel problema posto disciplinare problema impostare tre, avete corti
che si può guardare, e in realtà si chiede di guardare quei pantaloncini.
Anche in conferenza la scorsa settimana, siamo andati oltre molti di questi algoritmi, quindi sono
non andare a trascorrere del tempo in classe in corso più volte questi algoritmi o disegni
le foto di come questi algoritmi funzionano.
Anche in questo caso, che le informazioni si può ri-guardare lezione, oppure che le informazioni
viene catturato eccezionale sui pantaloncini per queste ricerche, tutti
che sono disponibili a cs50.net.
>> Così, invece, quello che stiamo andando a fare è scrivere questi programmi.
Abbiamo un certo senso, un modello mentale, di come lavorano, e quindi quello che sta succedendo
da fare è codificare per davvero.
Stiamo andando a trasformare quel modello mentale, quella foto, se si vuole, nel
codice effettivo.
E se tu fossi un po 'confuso o nebuloso sul modello mentale, sono totalmente
capire.
>> Non stiamo effettivamente andando a salta al codice subito.
Così, mentre questo messaggio in questa diapositiva chiede di codificare ricerca binaria, e
in realtà, una versione iterativa di ricerca binaria, la prima cosa che ho
vuole veramente di fare è scrivere qualche pseudocodice.
Così avete questo modello mentale di come binario lavori di ricerca.
Prendete un foglio di carta se si dispone di uno prontamente disponibile, o aprire un
editor di testo, e mi piacerebbe tutti a scrivere.
Prendere quattro minuti per scrivere il pseudocodice per la ricerca binaria.
>> Ancora una volta, pensare a quel modello mentale.
Io venire intorno se avete domande e siamo in grado di disegnare l'immagine fuori.
Ma prima, prima di iniziare la programmazione, Mi piacerebbe scrivere l'
pseudocodice per la ricerca binaria così quando siamo tuffarsi in, abbiamo qualche direzione
a dove dovremmo andare.
>> STUDENTE: Possiamo ipotizzare la matrice di I valori che otteniamo è già ordinato?
>> JASON HIRSCHHORN: Così, per la ricerca binaria di lavorare - domanda eccellente - si
prendere in un ordinato matrice di valori.
Così scontato che funzionerà.
Torneremo a questa diapositiva.
Vedrete in viola funzione dichiarazione bool binary_search int
valore, valori int, int n.
Questo dovrebbe essere familiare se avete già affrontato o ottenuto il tuo
mani sporche con il problema proposto.
>> Ma questa è la vostra dichiarazione di funzione.
Anche in questo caso, non dovrebbe avere bisogno di preoccuparsi che tanto in questo momento.
Quello che voglio davvero fare è prendere quattro minuti a binario pseudocode
Cerca e quindi andiamo oltre che come gruppo.
E io verrò in giro.
Se avete domande, si sentono liberi di alzare la mano.
>> Perché non prende più di due minuti per finire lo pseudocodice?
So che questo può sembrare ridicolo che stiamo spendendo così tanto tempo su
qualcosa che non è nemmeno realmente in C, ma soprattutto per questi più
Algoritmi impegnative e problemi set che dobbiamo capire,
a partire dal pseudocodice non preoccuparsi sulla sintassi, basta preoccuparsi
la logica, è incredibilmente disponibile.
E in questo modo, non è risolvere i due problemi incredibilmente difficili in una volta.
Stai concentrarsi solo sulla logica, e poi si sposta nella sintassi.
>> OK.
Cominciamo passando lo pseudocodice.
Ho scritto qui, binario ricerca pseudocodice.
Ti scriviamo questo sul salire a bordo insieme.
O ti scrivo e ti darò me le istruzioni di cui ho bisogno.
Così qualcuno può darmi la prima linea della pseudocodice voi
ha scritto per la ricerca binaria?
Sì, Annie?
>> STUDENTE: Mentre la lunghezza del elenco è maggiore di zero.
>> JASON HIRSCHHORN: Mentre lunghezza di elencare maggiore di zero.
E ancora, vediamo alcuni C-looking cose sintattiche qui.
Ma la maggior parte di questo è in inglese.
Qualcuno ha avuto alcuna linea hanno messo prima di questo nella loro pseudo-codice?
>> STUDENTE: Ottenere un array di numeri ordinati.
>> JASON HIRSCHHORN: Hai scritto "ottiene un matrice di numeri ordinati. "Per l'
dichiarazione di funzione, saremo di passaggio una matrice di numeri ordinati.
>> STUDENTE: [incomprensibile].
>> JASON HIRSCHHORN: So avremo che.
Ma sì, se non abbiamo avuto questo, abbiamo avrebbe bisogno di ordinare la nostra gamma di
numeri, perché la ricerca binaria funziona solo su array ordinati.
Così, mentre la lunghezza della lista è uguale a zero, io sono andando a mettere in alcune parentesi graffe
per farlo sembrare un po 'più simile C. Ma mentre, sembra mappare su un
ciclo while, quindi all'interno di questo mentre ciclo di cosa abbiamo bisogno di
fare per la ricerca binaria?
>> Qualcun altro che non mi ha dato un risponde ancora, ma chi ha scritto questo?
>> STUDENTE: Vai alla metà della lista.
>> JASON HIRSCHHORN: Tom.
Vai alla metà della lista.
E la domanda di follow-up, cosa facciamo una volta siamo al
metà della lista?
>> STUDENTE: Fare un controllo se questo è il numero che stai cercando.
>> JASON HIRSCHHORN: Excellent.
Vai alla metà della lista e controllare se il nostro valore è lì -
fantastico.
Qualcuno ha avuto niente altro che era diverso da questo?
Questo è esattamente vero.
>> La prima cosa che facciamo nella ricerca binaria è andare al centro della lista e
controllare per vedere se il nostro valore è lì.
Quindi presumo se il nostro valore è lì, che cosa facciamo?
>> STUDENTE: Torniamo a zero [incomprensibile].
>> JASON HIRSCHHORN: Sì, se il nostro valore è lì, abbiamo trovato.
Così possiamo dire in qualche modo, ma questo funzione è definita, diciamo l'utilizzatore
abbiamo trovato.
Se non c'è, però, che è dove questo diventa difficile.
Quindi, se non c'è, qualcun altro che stava lavorando sulla ricerca binaria o
ha un'idea adesso, cosa dobbiamo fare?
>> STUDENTE: Domanda.
>> JASON HIRSCHHORN: Sì?
>> STUDENTE: è l'array già ordinati?
>> JASON HIRSCHHORN: Sì, stiamo assumendo l'array è già ordinato.
>> STUDENTE: Allora devi controllare se il valore che si vede è più grande di
il valore che si desidera, è possibile spostare per mezzo dell'altra metà.
>> JASON HIRSCHHORN: Quindi, se la metà del la lista è più grande di ciò che siamo
cercando, allora facciamo che cosa?
Ci spostiamo dove?
>> STUDENTE: Si desidera spostare la metà della lista con
numeri più bassi di quello.
>> JASON HIRSCHHORN: Così faremo chiamare che la sinistra.
Quindi, se di mezzo è maggiore, possiamo cercare la metà sinistra della lista.
E poi la ricerca, cosa cosa intendo per ricerca?
>> STUDENTE: [incomprensibile].
>> JASON HIRSCHHORN: Andiamo verso il centro.
Abbiamo effettivamente ripetiamo questa cosa.
Torniamo attraverso il nostro ciclo while.
Ti darò l'ultimo -
altrimenti, se, medio è inferiore a quello facciamo, cosa facciamo qui?
>> STUDENTE: Andate a destra.
>> JASON HIRSCHHORN: Cerca destra.
Questo sembra buono, ma qualcuno ha tutto ciò che ci può essere che manchi o
qualsiasi altra cosa che si mette nel pseudo-codice?
Quindi questo è ciò che abbiamo finora.
Mentre la lunghezza della lista è maggiore di zero, stiamo per andare
a metà della lista e controllare se il nostro valore è lì.
>> Se il centro è più grande, stiamo andando a cercare di sinistra, altrimenti se il mezzo è
meno, stiamo andando a cercare il giusto.
Così abbiamo avuto tutti una certa familiarità con i termini che usiamo in informatica
e gli strumenti che abbiamo.
Ma avrete già notato che eravamo parlando in inglese, ma abbiamo trovato un
sacco di cose che sembravano mappare a strumenti che abbiamo nel nostro kit di strumenti di codifica.
Così destra fuori del blocco, non siamo andando ancora da codificare in realtà.
>> Che cosa vediamo qui in inglese che le mappe a cose possiamo scrivere in C?
>> STUDENTE: While.
>> JASON HIRSCHHORN: While.
Quindi questo mentre qui mappe su a che cosa?
>> STUDENTE: un ciclo while.
>> JASON HIRSCHHORN: un ciclo while?
O probabilmente, più in generale, un ciclo.
Vogliamo fare qualcosa di più e più volte.
Quindi stiamo andando a codificare un ciclo.
E già sappiamo, perché abbiamo fatto questo un paio di volte e abbiamo
hanno un sacco di esempi là fuori, come effettivamente scrivere
questo indice per un loop.
Così che dovrebbe essere abbastanza facile.
Dovremmo essere in grado di ottenere che iniziato abbastanza rapidamente.
>> Che cosa vediamo qui?
Quali altre strutture di sintassi, cose che siamo a conoscenza di C, facciamo
già hanno un senso di Based al largo delle parole che abbiamo usato?
Sì, Anna?
[Incomprensibile]
solo scherzando.
Anna, andare avanti.
>> STUDENTE: Se e altro.
>> JASON HIRSCHHORN: se e altro - proprio qui.
Così che cosa fanno quelli assomigliano?
>> STUDENTE: Un caso else.
>> JASON HIRSCHHORN: Sì, condizioni, giusto?
Così avremo probabilmente bisogno di scrivere alcune condizioni.
E ancora, anche se forse di confusione all'inizio in primo luogo, abbiamo generalmente un senso ora
di come scrivere condizioni e la sintassi per le condizioni.
E se non lo facciamo, ci limitiamo a guardare la sintassi per le condizioni, taglia e incolla
che, perché sappiamo bisogno di una condizione di qui.
Tutte le altre cose che vediamo che mappa sul cose che potremmo bisogno di fare in C?
Sì, Aleha?
>> STUDENTE: Questo potrebbe essere ovvio, semplicemente controllando se un
valore è uguale a qualcosa.
>> JASON HIRSCHHORN: Così come controlliamo e - in modo da andare al centro della lista
e verificare se il nostro valore è lì?
Come facciamo che in C?
Qual è la sintassi per questo?
>> STUDENTE: Uguale, uguale.
>> JASON HIRSCHHORN: Uguale, uguale.
Quindi, questo controllo è destinata probabilmente di essere un pari, uguale.
Così sapremo abbiamo bisogno che da qualche parte.
E in realtà, solo in scrittura, vediamo quelle altre cose.
Stiamo andando a fare un po ' operatori di confronto in là -
fantastico.
Così in realtà sembra, da e un grande, non abbiamo scritto
parola di codice C ancora.
Ma abbiamo ottenuto il modello mentale verso il basso tramite lezioni e quei pantaloncini.
>> Abbiamo scritto pseudo-codice come gruppo.
E già, abbiamo l'80% se non 90% di quello che dobbiamo fare.
Ora, abbiamo solo bisogno di codificare essa, che ancora una volta, è un
problema non banale da risolvere.
Ma almeno siamo bloccati sulla logica.
Almeno ora quando andiamo a orari di ufficio, Posso dire, so quello che mi serve
da fare, ma si può ricordare me della sintassi?
O anche se le ore d'ufficio sono affollate, si può google per la sintassi, piuttosto
che essere bloccato sulla logica.
>> E ancora, piuttosto che cercare di risolvere la logica ed i problemi di sintassi tutti
contemporaneamente, spesso è molto meglio rompere questi due problemi principali off in
due quelli più gestibili e fare il pseudo-codice e poi codice in C.
Quindi cerchiamo di vedere quello che ho fatto per l' pseudo-codice prima del tempo.
>> Mentre la lunghezza della lista è maggiore di zero, guardare al centro
dell'elenco.
Se il numero trovato restituito true, altrimenti se il numero più alto, la ricerca di sinistra.
Altrimenti se il numero più basso, ricerca a destra, restituire false.
In modo che sembra quasi identico, se non quasi identico a quello che abbiamo scritto.
In realtà, Tom, quello che hai detto prima, rompendo il centro dell'elenco e se
numero trovato in due prospetti è in realtà quello che ho fatto.
>> Li ho combinato lì.
Avrei ascoltato la prima volta.
Così che è la pseudo-codice che abbiamo.
Se si vuole ora, mi dispiace, andare tornare al nostro problema iniziale.
Facciamo codice binary.c.
Quindi implementare una versione iterativa di ricerca binaria usando la seguente
dichiarazione di funzione.
>> E non è necessario copiare giù ancora.
In realtà sto andando ad aprire proprio qui binary.c.
Quindi non vi è la dichiarazione di funzione al centro dello schermo.
E vedrete ho preso la pseudo-codice da sui miei fianchi, ma quasi identici
a quello che abbiamo scritto, e che mettere in per voi.
Così ora, diamo cinque minuti codificare questa funzione.
>> E ancora, se avete domande, alzare la mano, fammi sapere, io
venire intorno.
>> STUDENTE: [incomprensibile].
>> JASON HIRSCHHORN: Così ho preso il binario definizione di ricerca presso l'
In alto, sulla linea 12.
Questo è quello che ho ottenuto per la mia presentazione.
E allora tutto questo pseudo-codice che ho appena copia e incollato dalla diapositiva,
pseudo-codice diapositiva.
Non ho ancora sentito [incomprensibile].
>> Quindi, se avete finito il vostro attuazione, voglio controllare.
Ti ho mandato il file Helpers.h in precedenza in questa classe.
E sarà disponibile online e per il download per osservare la gente
questa volta parte in ritardo.
E ho appena usato la distribuzione generica codice da pset3.
Così ho preso find.C, usare il mio file Helpers.h anziché il file Helpers.h
che è dato nel codice distribuzione.
>> E ho dovuto fare un altro cambiamento in find.C piuttosto che chiamare semplicemente
ricerca, chiamare binary_search.
Quindi, se volete testare il vostro codice, sanno che questo è come farlo.
Infatti, quando saremo in esecuzione di questo codice in questo momento, ho solo fatto una copia di
mia directory pset3, ancora una volta, scambiato i file aiutanti e poi ha fatto che
cambiare in find.C chiamare binary_search piuttosto che semplicemente cercare.
>> JASON HIRSCHHORN: sì.
Hai una domanda?
>> STUDENTE: Nevermind.
>> JASON HIRSCHHORN: Non preoccuparti.
Bene, cominciamo.
Vi codificare questo come un gruppo.
Un'altra nota.
Di nuovo, questo è, può essere facilmente scambiato a Problem Set Three.
Ho il mio file Helpers.h che, piuttosto rispetto alla Helpers.h ci è dato,
dichiara ricerca binaria, bolla ordinamento e la selezione di ordinamento.
E in find.c noterete on line, ciò è che, la linea 68, che noi chiamiamo binario
cerca piuttosto che di ricerca.
Quindi, di nuovo, il codice che è disponibile online o il codice che si sta
creando in questo momento può essere facilmente scambiato a p set 3 per verificarlo.
>> Ma prima, diamo codice binario di ricerca.
La nostra dichiarazione di funzione, torniamo un bool.
Prendiamo un intero chiamato valore.
Prendiamo un array di interi chiamato valori, e prendiamo n essere
la dimensione della matrice.
Sulla linea 10, proprio qui, ho sharp includono stdbool.h.
Qualcuno sa il motivo che è lì?
Così che cosa fa quella riga di codice?
>> STUDENTE: Esso consente di utilizzare un tipo restituito bool.
>> JASON HIRSCHHORN: Esattamente.
>> STUDENTE: O è una libreria che permette utilizzare un tipo restituito bool.
>> JASON HIRSCHHORN: Così il forte comprendono linea stdbool.h mi dà un po '
definizioni e dichiarazioni per le cose che mi è permesso di utilizzare in
questa biblioteca.
Così tra quelle sta dicendo che non c'è questo tipo chiamato bool, e può essere
vero o falso.
Quindi questo è quello che fa la linea.
E se non ho avuto questa linea, vorrei finire nei guai per la scrittura di questo
parola giusta qui, bool, proprio lì.
Esattamente.
Quindi ho bisogno che in questo codice.
OK.
Quindi questo, di nuovo, è un iterativo versione, non un ricorsiva.
Cerchiamo quindi di iniziare.
>> Partiamo con questa prima linea di pseudo codice.
E si spera, ci sarà - o non si spera.
Stiamo per andare in giro per la stanza.
Andremo riga per riga, e io lo aiuteremo a capire la linea che abbiamo bisogno di
a scrivere prima.
Così, mentre la lunghezza della lista è maggiore di zero.
Cominciamo nella parte anteriore.
Che linea devo scrivere qui, in codice?
>> STUDENTE: Mentre parentesi n è maggiore di 0.
>> JASON HIRSCHHORN: mentre n è grande di 0.
Quindi n è la dimensione di un elenco, e stiamo verificando se -
>> [VOCI interponendo]
>> JASON HIRSCHHORN: - scusate?
>> STUDENTE: Come facciamo a sapere che n è la dimensione della lista?
>> JASON HIRSCHHORN: Mi dispiace.
Per la specifica pset, la ricerca e liste funzioni è necessario scrivere,
n è la dimensione della lista.
Ho dimenticato di spiegare che qui.
Ma sì. n è la dimensione l'elenco, in questo caso.
Così, mentre n è maggiore di 0.
OK.
Questo può risultare un po 'problematico però, se le cose vanno avanti.
Perché noi continueremo a conoscere il dimensione della lista in questo
funzione, ma dire iniziamo con un array di 5 interi.
E passiamo attraverso e abbiamo ora ristretto la scelta a
un array di 2 numeri interi.
Che 2 numeri interi è?
La dimensione è di 2 ora che vogliamo guardare, ma che 2 è che?
Questo fa senso, tale questione?
>> OK.
Te lo chiedo di nuovo.
Quindi cominciamo con questa serie di 5 interi, e n è uguale a 5, giusto?
Faremo di qui.
probabilmente cambieremo il formato, destra, come le cose vanno avanti.
Che è quello che diciamo che vogliamo fare.
Non vogliamo per la ricerca la cosa di nuovo piena.
Quindi diciamo che cambiamo a 2.
Prendiamo la metà della lista che è strano.
Quindi basta scegliere 2.
Così ora n è uguale a 2.
Mi scuso per i poveri pennarelli a secco.
Giusto?
E noi stiamo cercando l'elenco nuovamente con una lista di dimensione 2.
Beh, la nostra gamma è ancora di dimensioni 5.
Noi diciamo che vogliamo solo ricerca 2 punti in esso.
Così che due punti sono quelli?
>> Ritiene che senso?
Sono i due punti lasciati?
Sono il giusto due punti?
Sono le centrali 2 spot?
Abbiamo rotto il problema, ma noi in realtà non si sa quale parte di
il problema che stiamo ancora guardando, solo avendo queste due variabili.
Quindi abbiamo bisogno di un po 'di più, allora, mentre n è maggiore di 0.
Abbiamo bisogno di sapere se tale n è nel nostro matrice reale.
>> Così qualcuno ha un cambiare questa linea?
La maggior parte di questa linea è perfettamente corretta.
C'è un'altra aggiunta?
Possiamo scambiare qualcosa per n a fare questa linea un po 'meglio?
Mm-hm?
>> STUDENTE: Si può inizializzare una variabile come la lunghezza di n che sarà poi utilizzato
successivamente nella funzione?
>> JASON HIRSCHHORN: Così inizializzare una lunghezza variabile n,
e usiamo che più tardi?
Ma poi abbiamo appena aggiorniamo lunghezza e noi correre ancora in questo problema dove noi
ridurre la lunghezza del nostro problema, ma sappiamo mai dove, in realtà,
che la lunghezza mappe su.
>> STUDENTE: Non è che succederà più tardi, quando stai dicendo, cercare di sinistra,
verificare giusto?
Hai intenzione di andare in un diverso area della tua -
>> JASON HIRSCHHORN: Stiamo per andare ad una zona, ma come facciamo a sapere
che sono per andare a?
Se abbiamo solo l'array e questo n, come facciamo a sapere dove
andare nella matrice.
Nella parte posteriore, sì?
>> STUDENTE: Avete, come, una minore legato e una variabile limite superiore o
qualcosa di simile?
>> JASON HIRSCHHORN: OK.
Quindi questa è un'altra idea.
Piuttosto che tenere traccia del dimensioni, teniamo traccia del minore e
variabile limite superiore.
Quindi, come si fa a calcolare il formato da un limite inferiore e limite superiore?
>> [VOCI interponendo]
>> JASON HIRSCHHORN: Sottrazione.
E anche tenere traccia del minore legato e limite superiore a farcelo sapere,
stiamo cercando questi due?
Stiamo cercando questi due qui?
Stiamo cercando il due centrali?
Probabilmente non è il mezzo a due, perché questa, infatti, è la ricerca binaria.
Ma ora saremo in grado di ottenere le dimensioni, ma anche i limiti della matrice.
In sostanza, se abbiamo il nostro gigante rubrica telefonica, ci strappiamo a metà.
Ora sappiamo se tale minore rubrica è.
Ma non stiamo in realtà lo strappo la rubrica a metà.
Abbiamo ancora bisogno di sapere dove l' nuovi confini del nostro problema.
Qualcuno ha domande a tale proposito?
Sì?
>> STUDENTE: Sarebbe lavorare creando un variabile, i, che poi appena sposto
la posizione di i rispetto al suo posizione attuale, e la lunghezza, n?
>> JASON HIRSCHHORN: E che cosa è i?
>> STUDENTE: Come ho essere come una sorta di -
Come si dovrebbe inizializzare i per essere il posizione intermedia della matrice.
E poi, se il valore nella posizione i in il centro della matrice in risultata
essere inferiore al valore di cui avete bisogno, io adesso diventa la lunghezza della matrice, più
il valore di i diviso per 2.
Come vedi, si passa i -
>> JASON HIRSCHHORN: Giusto.
>> STUDENTE: - fino al -
>> JASON HIRSCHHORN: Quindi io sono quasi positivo che funzionerà.
Ma il punto è, avete bisogno di due pezzi di informazione qui.
Potete farlo con inizio e fine, o si può fare con la dimensione, e quindi
qualche marcatore.
Ma si ha bisogno di due pezzi delle informazioni qui.
Non è possibile cavarsela con uno solo.
Ritiene che ha un senso?
>> Quindi stiamo andando a passare attraverso, e stiamo andando a fare [incomprensibile]
e creare alcuni marcatori.
Quindi cosa hai scritto nel codice?
>> STUDENTE: Ho appena detto int limite uno è uguale a 0.
>> JASON HIRSCHHORN: Chiamiamo che int inizio.
>> STUDENTE: OK.
>> JASON HIRSCHHORN: Che fa più senso per me.
E?
>> STUDENTE: Ho detto, credo, int fine.
>> JASON HIRSCHHORN: int finale.
>> STUDENTE: Credo, n meno 1, o qualcosa di simile.
Come, l'ultimo elemento.
>> JASON HIRSCHHORN: Quindi hai scritto, int inizio uguale a 0, punto e virgola, e int
finale è uguale a n meno 1, punto e virgola.
Quindi, in sostanza, quello che stiamo facendo qui, la prima posizione 0.
E come sappiamo in array, non vanno fino a n, salgono a n meno 1.
Così abbiamo alcuni limiti della nostra matrice.
E questi limiti iniziali capita di essere i limiti iniziali del nostro problema.
OK.
Così che suona bene.
Poi, se torniamo a questa linea, mentre lunghezza della lista è maggiore di 0,
ciò, invece di n, dovrebbe mettiamo qui?
>> STUDENTE: Scrivere finale meno all'inizio.
>> JASON HIRSCHHORN: Mentre termina meno inizio è maggiore di 0?
OK.
E potremmo, se volessimo fanno si che un po 'più bello, quello che
altro potremmo fare?
Se volessimo pulire questo codice un po '?
Come possiamo sbarazzarci di 0?
Questa è solo una questione di stile.
E 'corretto in questo momento.
>> STUDENTE: Ending non parità di principio?
>> JASON HIRSCHHORN: Possiamo fare che cosa?
>> [VOCI interponendo]
>> STUDENTE: Fine è maggiore?
>> JASON HIRSCHHORN: Già.
Possiamo solo fare durante la finale è maggiore di inizio.
Giusto.
Abbiamo aggiunto cominciando a l'altro lato di questo, e ci siamo liberati del 0.
Quindi questo sembra proprio un po 'più pulito.
OK.
Così, mentre la lunghezza della lista è 0, abbiamo scritto che, pur finendo è maggiore
di inizio.
Stiamo andando a mettere nel nostro necessaria parentesi graffe, e quindi la prima cosa
che vogliamo fare è guardare li in una piccola lista.
Lei?
Potete darmi il -
>> STUDENTE: Se parentesi valore parentesi quadra -
>> JASON HIRSCHHORN: Se parentesi valore parentesi quadra.
>> STUDENTE: Ending diviso per 2.
>> JASON HIRSCHHORN: Fine?
>> STUDENTE: Vedo un problema con il vostro -
>> JASON HIRSCHHORN: OK.
Beh, guarda al centro.
Come facciamo a sapere quello che il mezzo è?
Già.
Così mi permetta di cancellare quel codice.
Come facciamo a sapere quello che il mezzo è?
In qualsiasi cosa, quando si ha l'inizio e alla fine, come si fa a trovare
mezzo?
>> STUDENTE: Si calcola la media.
>> STUDENTE: Li voglio insieme e poi -
>> JASON HIRSCHHORN: essi Aggiungi insieme e poi?
>> STUDENTE: E si calcola la media.
Dividerlo per 2.
>> JASON HIRSCHHORN: essi Aggiungi insieme e dividere per 2.
Così metà int uguale?
Tom, si può dare a me?
>> STUDENTE: Inizio più desinenza -
>> JASON HIRSCHHORN: Beginning più fine.
>> STUDENTE: Tutto, staffa, diviso 2.
>> JASON HIRSCHHORN: Tutto, in parentesi, diviso per 2.
In modo che mi dà la metà di nulla, giusto?
>> STUDENTE: È inoltre necessario arrotondare in su.
>> JASON HIRSCHHORN: Quello che fai dire, ho bisogno di arrotondare in su?
>> [VOCI interponendo]
>> STUDENTE: Perché se 'una strana numero, quindi è come -
>> JASON HIRSCHHORN: Beh, OK.
Così ho potuto arrotondare in su.
Ma se è un numero dispari, un 5, posso 1 tenendo lontano dal centro.
Oppure, se si tratta di un numero pari, piuttosto, questo è un caso meglio.
Se è 4, abbiamo solo 4, posso prendere il primo "mezzo", citazione, unquote o
il secondo "medio".
O potrebbe funzionare per una ricerca binaria, quindi non ho davvero bisogno di arrotondare.
Ma c'è un'altra cosa che mi bisogno di guardare a questa linea.
Potremmo non rendersene conto ancora, ma ci torneremo ad esso.
Perché questa linea in realtà ancora ha bisogno di un'altra cosa.
>> Ma finora, abbiamo scritto quattro righe di codice.
Abbiamo il nostro inizio due indicatori.
Abbiamo il nostro ciclo while, che mappa sulla direttamente al nostro pseudocodice.
Stiamo guardando il mezzo che mappa direttamente sul nostro pseudocodice.
Direi che questo va a metà della lista, questa riga di codice.
E poi, una volta che andiamo a metà la lista, la prossima cosa che dobbiamo fare
è controllare se il nostro valore è lì per pseudocodice abbiamo scritto in precedenza.
>> Quindi, come possiamo controlliamo se il nostro valore è al centro dell'elenco?
Tu.
Perché non fare questo?
>> STUDENTE: Se il nostro valore è di al centro è uguale a
tutto ciò abbiamo impostato il -
Voglio dire pari pari a -
>> JASON HIRSCHHORN: E -
OK.
>> STUDENTE: Non sono sicuro di quello che il variabile che stiamo cercando
perché anche se, è perché -
>> [VOCI interponendo]
>> STUDENTE: [incomprensibile].
>> JASON HIRSCHHORN: Esattamente.
Per la dichiarazione di funzione, stiamo cercando un valore.
Quindi stiamo cercando un valore in una matrice di valori.
Così siete esattamente a destra.
Potrai fare, se la staffa valore parentesi aperta centro chiuso eguali staffa
uguale valore, e dentro c'è che cosa dobbiamo fare?
Se il nostro valore di lì, che cosa cosa dobbiamo fare?
>> [VOCI interponendo]
>> STUDENTE: ritorno a zero.
>> JASON HIRSCHHORN: Restituisce vero.
>> STUDENTE: Restituisce vero.
>> JASON HIRSCHHORN: Michael, cosa fa questo effetto?
>> STUDENTE: [incomprensibile] il programma ha funzionato traiettoria e che è finita, e
hai quello che devi fare?
>> JASON HIRSCHHORN: il programma o cosa?
In questo caso?
>> STUDENTE: La funzione.
>> JASON HIRSCHHORN: la funzione.
E così, per tornare a qualsiasi chiamata e dare il valore true.
Esattamente.
Principale.
Qual è il tipo di ritorno di principale, Michael?
>> STUDENTE: int, intero?
>> JASON HIRSCHHORN: int, esattamente.
Un numero intero.
Quella era solo una questione di assicurarsi voi siete stati su di esso.
Che cosa fa di solito di ritorno, se tutte le cose stanno funzionando bene?
>> STUDENTE: Zero.
>> JASON HIRSCHHORN: Zero.
Esattamente.
>> STUDENTE: Se questo restituisce semplicemente true, non c'è informazione fornita
su ciò che il -
Oh, questo è solo dicendo che tale valore è all'interno della matrice.
>> JASON HIRSCHHORN: Esattamente.
Questo programma non sta dando informazioni di dove esattamente il valore è.
E 'solo dire, sì, abbiamo trovato , o no, noi non lo abbiamo trovato.
Quindi, se il numero trovato, restituisce true.
Beh, in realtà abbiamo appena fatto davvero rapidamente con quella riga di codice.
Quindi mi sposterò quella linea di pseudocodice.
>> STUDENTE: Non abbiamo bisogno modificare la matrice?
Dovrebbe essere valori, non di valore, giusto?
>> JASON HIRSCHHORN: Mi dispiace.
Grazie.
>> STUDENTE: Già.
>> JASON HIRSCHHORN: Questa linea dovrebbero essere valori.
Esattamente.
OK.
Così abbiamo guardato la lista centrale.
Se il numero trovato return true.
Continuando con il nostro pseudocodice, se centrale è più grande, la ricerca lasciato.
Così ho avuto qui, se il numero superiore, ricerca a sinistra.
Costantino, si può dare me questa riga di codice?
>> STUDENTE: Se il valore medio -
>> JASON HIRSCHHORN: Quindi, se il valore -
se parentesi aperta valori staffa centrale vicino Staffa -
>> STUDENTE: è più piccolo di valore?
>> JASON HIRSCHHORN: è minore di.
>> STUDENTE: Meno di valore.
>> JASON HIRSCHHORN: Value.
Beh, in realtà, si vuole controllare se il numero -
Scusi.
Questo è un po 'di confusione.
Ma altrimenti se il numero in mezzo della lista è maggiore.
>> STUDENTE: Oh, OK.
>> JASON HIRSCHHORN: cambierò quella.
Altrimenti se centrale è più alta, noi vuole cercare di sinistra, OK?
E che cosa facciamo all'interno questa se la condizione?
>> STUDENTE: Posso fare una piccola modifica al la condizione, cambiate a else if?
>> JASON HIRSCHHORN: Else if?
OK.
Quindi, questo codice verrà eseguito circa lo stesso.
Ma la cosa bella di usare if, else if, else if o if, else if, else
significa che solo uno di quelli che sta per da verificare, non tutti e tre,
potenzialmente.
E che lo rende un po ' bello sul computer che è
l'esecuzione del programma.
>> Così [? Costantino,?]
siamo dentro questa linea, altrimenti se i valori, staffa centrale vicino staffa
è maggiore del valore.
Che cosa dobbiamo fare?
Dobbiamo cercare sinistra.
Come lo facciamo?
Sto per darvi un inizio.
>> Abbiamo queste due cose chiamate inizio e fine.
Quindi, ciò che deve accadere all'inizio?
Se si desidera cercare sinistra del lista, otteniamo il nostro inizio attuale.
Che cosa dobbiamo fare?
>> STUDENTE: Abbiamo impostato l'inizio a metà più 1.
>> JASON HIRSCHHORN: Quindi, se siamo ricerca a sinistra?
>> STUDENTE: Siamo spiacenti, meno centrale -
così il finale sarebbe mezzo meno 1 e l'inizio -
>> JASON HIRSCHHORN: E che cosa accade all'inizio?
>> STUDENTE: Si rimane lo stesso.
>> JASON HIRSCHHORN: Così l' significato rimane lo stesso.
Se stiamo cercando di sinistra, noi siamo utilizzando lo stesso principio -
esattamente a destra.
E il finale?
Siamo spiacenti, cosa fa l' finendo di nuovo uguali?
>> STUDENTE: meno Middle 1.
>> JASON HIRSCHHORN: meno Middle 1.
Ora, perché meno 1, e non solo di mezzo?
>> STUDENTE: La metà è fuori immaginare già, perché abbiamo avuto
verificato che è fuori?
>> JASON HIRSCHHORN: Ecco esattamente a destra.
La metà è fuori dal quadro.
Abbiamo già controllato il mezzo.
Quindi noi non vogliamo "mezzo", citazione unquote, continuare ad essere nella
array che stiamo cercando.
Quindi questo è fantastico.
>> Else if staffa valori medio è maggiore di valore finale pari
meno centrale 1.
Jeff, che dire di questa ultima riga?
>> STUDENTE: Else.
Valori medio è inferiore al valore?
>> JASON HIRSCHHORN: Ci mi stai dando altro.
Quindi, se non mi dai -
>> STUDENTE: Allora inizio sarebbe più centrale 1.
>> JASON Hirschhorn: equals Inizio più centrale 1, nuovamente, per lo stesso
ragione che Costantino ci ha dato in precedenza.
E alla fine, che non ha dato me una riga di codice ancora?
Return false, Aleha, cosa scriviamo qui?
>> STUDENTE: Ritorno false.
>> JASON HIRSCHHORN: Ritorno false.
E dobbiamo farlo, perché se noi non trovarlo, dobbiamo dire noi
non trovarlo.
E abbiamo detto che andremo a restituire un bool, quindi abbiamo sicuramente tornare
un qualche bool.
>> Quindi cerchiamo di eseguire questo codice.
In realtà sto andando -
quindi siamo nel terminale.
Ti eliminiamo la nostra finestra.
Facciamo tutto.
Abbiamo trovato c'è un errore.
C'è un errore sulla linea 15, previsto virgola alla fine della
dichiarazione.
Così che cosa ho dimenticato?
>> STUDENTE: virgola.
>> JASON HIRSCHHORN: Punto e virgola proprio qui.
Credo che sia stato il codice di Tom.
Così Tom, [incomprensibile].
Sto scherzando.
Facciamolo fare tutti di nuovo.
>> STUDENTE: Cosa directory Dropbox dovremmo essere in questo?
>> JASON HIRSCHHORN: Così si può solo guardare per questo bit.
Ma ancora una volta, se si voleva spostare questo codificare nella directory pset3 per provare
fuori, questo è quello che ho fatto.
Se si noterà qui - mi dispiace, buona domanda.
>> [? LS,?]
Ho qui il codice find.c dal codice distro di questa settimana.
Ho Helpers.h.
Ho un file Marca che ho effettivamente modificato un po 'per includere questi nuovi
i file che stiamo scrivendo.
Tutto il codice sarà disponibile, non il codice di distribuzione, ma la nuova
Rendere il file, il nuovo file Helpers.h verrà essere disponibile online per il download.
Ancora una volta, quindi queste sono le Codici supplementari abbiamo.
>> Così fanno tutti, a questa linea, fa trovare, binario, selezione bubble - marche
tutti e tre e compila in questo codice ritrovamento eseguibile.
Quindi in generale, non vogliamo a diritto a check50.
Vogliamo eseguire alcuni test per conto nostro.
Ma solo così possiamo accelerare questo un po ', check50 2013 pset3.find passerà
in helpers.c-- il mio male.
>> Non ho adesso.
Quindi stiamo effettivamente andando a eseguire il codice per davvero.
Usage.find /, sapete cosa significa?
>> STUDENTE: Avete bisogno di un secondo riga di comando su di esso.
>> JASON HIRSCHHORN: Ho bisogno di una seconda linea di comando.
E per la specifica, ho bisogno per entrare in quello che stiamo cercando.
Allora diamo un'occhiata per 42.
Ci terremo in ordinata, perché noi non hanno ancora scritto una funzione di ordinamento -
42, 43, 44.
>> E Controllo D non ha trovato il ago nel pagliaio.
Questo è male.
E 'sicuramente lì.
Proviamo qualcos'altro.
Forse è perché ho messo esso all'inizio.
>> Facciamo 41, 42, 43.
Ci andiamo.
Si trovò.
Mettiamola alla fine ora, solo così possiamo essere approfondita -
40, 41, 42.
Non hai trovato l'ago.
Così ho parlato di questo in precedenza.
Purtroppo, sapevo che questo che stava per accadere.
>> Ma per scopi pedagogici, è bene esplorare.
Non funziona.
Per qualche motivo, non è possibile trovarlo.
Noi sappiamo cosa c'è dentro, ma non stiamo trovando esso.
Così una cosa che potremmo fare è passare attraverso GDB per trovarlo, ma lo fa nessuno,
senza passare attraverso GDB, hanno un senso di cui abbiamo avvitato su?
[? Madu? ?]
>> STUDENTE: Penso che potrebbe essere quando finisce è uguale all'inizio, ed è
solo un elenco unico elemento.
Poi ignora semplicemente invece effettivamente controllarlo.
>> JASON HIRSCHHORN: Ecco esattamente a destra.
Quando fine è uguale all'inizio, facciamo hanno ancora un elemento nella nostra lista?
>> STUDENTE: Sì.
>> JASON HIRSCHHORN: Sì, infatti, abbiamo avere uno ed un solo elemento.
E che molto probabilmente accadrà quando, per il codice che abbiamo provato, siamo al
davanti pagliaio oa la fine del pagliaio.
Ecco dove inizio e finale sta per pari
uno, con ricerca binaria.
Così in questi due casi non ha funzionato, perché finendo è stato pari a all'inizio.
>> Ma se il fine è uguale all'inizio, fa questo ciclo while esegue?
Non è così.
E avremmo potuto controllare che ancora una volta attraverso la GDB.
Quindi, come possiamo risolvere questo codice, perché mentre quando termina è uguale a
inizio, vogliamo anche questo ciclo while per l'esecuzione.
>> Quindi cosa fix possiamo fare per la linea 18?
>> STUDENTE: [incomprensibile] è maggiore o uguale a.
>> JASON HIRSCHHORN: Esattamente.
Mentre desinenza è maggiore o uguale all'inizio.
Così ora, facciamo in modo di ottenere che caso angolo alla fine.
E vediamo.
Corriamo questo ancora una volta.
>> Facciamo tutti.
Anche in questo caso, dovrete solo seguire qui.
Trova 41 questa volta.
Basta tenerlo coerente.
>> Trova 42.
Mettiamola all'inizio -
42, 43, 44.
Abbiamo trovato.
Così che era davvero il cambiamento abbiamo bisogno di fare.
>> Che era un sacco di codifica che appena fatto, la ricerca binaria.
Qualcuno ha domande prima Mi sposto su in linee che abbiamo scritto in
ricerca binaria o come abbiamo capito che cosa abbiamo fatto capire?
Prima di andare avanti, voglio anche sottolineare che, in linea di massima, abbiamo mappato
nostra pseudo-codice tra uno sul nostro codice.
>> Abbiamo avuto quella cosa difficile di capire con l'
inizio e fine.
Ma avevi tu non capito che fuori, avrebbe scritto più o meno la
codice identico, salvo per queste prime due righe.
E poi si sarebbe reso conto quando hai fatto in controlli e casi
avete bisogno di qualcosa d'altro.
Quindi, anche se si fosse seguito il nostro linea pseudo-codice per linea, avresti
ottenuto tutti ma due linee di codificare avevi bisogno di scrivere.
>> E sarei pronto a scommettere che voi ragazzi avrebbe tutti capito che fuori
abbastanza rapidamente, che avevi bisogno di mettere una sorta di marcatore in là per capire
dove eravate.
Di nuovo, è il potere di fare pseudo-codice prima del tempo.
Così possiamo fare la logica, e poi siamo in grado di preoccuparsi della sintassi.
>> Se fossimo stati confusi circa la logica durante il tentativo di scrivere questo codice in C,
avremmo ottenuto tutto incasinato.
E poi saremmo domande su la logica e la sintassi e meshing
tutti insieme.
E avremmo persa in quello che può diventare rapidamente un
problema molto difficile.
Quindi passiamo ora di ordinamento per selezione.
>> Abbiamo 20 minuti dalla fine.
Così ho la sensazione che non saremo in grado di ottenere attraverso tutti selection sort
e bubble sort.
Ma fateci almeno tentare per finire selection sort.
Così attuare ordinamento per selezione utilizzando il seguente dichiarazione di funzione.
>> Ancora una volta, questo è preso dal problema impostare specifiche.
I valori INT è tra parentesi, è un array di interi.
E int.n è la dimensione di tale matrice.
Selezione ordinamento sta andando per ordinare questo array.
>> Quindi per il nostro modello mentale di selezione ordinamento, tiriamo il -
in primo luogo, passiamo attraverso la lista del primo tempo, trovare il numero più piccolo,
messo all'inizio, trovare il secondo minor numero, metterlo in
seconda posizione se vogliamo ordinamento in ordine crescente.
Non sto forzando di scrivere pseudo-codice al momento.
>> Ma prima facciamo il codice come una classe in cinque minuti, ci accingiamo a scrivere
pseudo-codice in modo che abbiamo un senso di dove stiamo andando.
Quindi, tentare di scrivere pseudo-codice per conto proprio.
E poi tentare di trasformare quel pseudo-codice in codice.
Lo faremo come gruppo in cinque minuti.
>> E, naturalmente, fatemi sapere se avete tutte le domande.
>> STUDENTE: Che?
>> JASON HIRSCHHORN: vedere quanto si può ottenere in altri due minuti.
Capisco che non sarà essere in grado di finire.
Ma andremo oltre questo come un gruppo.
>> Siete tutti codifica in modo [incomprensibile], quindi sono mi dispiace per mettere in pausa quello che stai facendo.
Ma andiamo con questo come un gruppo.
E ancora, la ricerca binaria, tutti danno me uno se non più righe di codice.
Grazie per questo.
Stiamo andando a fare la stessa cosa qui, codice insieme come gruppo.
>> Così ordinamento per selezione - scriviamo qualche rapido pseudo-codice.
Per modello mentale, qualcuno può darmi la prima linea di pseudo-codice, per favore?
Cosa voglio fare?
>> STUDENTE: Mentre la lista è fuori uso.
>> JASON HIRSCHHORN: OK, mentre l'elenco è in ordine.
E che cosa vuol dire "out of order?"
>> STUDENTE: Mentre [incomprensibile]
non è stato risolto.
>> JASON HIRSCHHORN: Mentre la lista è fuori ordine, cosa facciamo?
Dammi la seconda linea, per favore, Marcus.
>> STUDENTE: Quindi, trovare il prossimo numero più piccolo.
Questo sarà rientrata.
>> JASON HIRSCHHORN: Così trovare il prossimo numero più piccolo.
E poi qualcun altro?
Una volta che troviamo il prossimo più piccolo numero, cosa facciamo?
Sto per dire trovare il numero più piccolo.
Questo è quello che vogliamo fare.
>> Così trovare il più piccolo numero.
Allora cosa facciamo?
>> STUDENTE: [incomprensibile] all'inizio.
>> JASON HIRSCHHORN: Sorry?
>> STUDENTE: posiziona nel inizio della lista.
>> JASON HIRSCHHORN: Quindi metterlo in all'inizio della lista.
E cosa facciamo alla cosa che era in principio
della lista, giusto?
Stiamo sovrascrittura qualcosa.
Allora, dove mettiamo che?
Sì, Anna?
>> STUDENTE: Se il più piccolo numero era?
>> JASON Hirshhorn: Così si può mettere l'inizio della lista in cui la
piccolo numero era.
Così, mentre l'elenco è in ordine, trovare il più piccolo numero, posizionarlo in
all'inizio della lista, mettere la inizio della lista in cui la
piccolo numero era.
Marcus, si può riformulare questa linea mentre l'elenco è in ordine?
>> STUDENTE: Mentre i numeri Non sono stati ordinati?
>> JASON Hirshhorn: OK, quindi per sanno che i numeri non sono stati
ordinato, cosa dobbiamo fare?
Quanto abbiamo bisogno di passare attraverso questo elenco?
>> STUDENTE: Quindi credo che un ciclo for, o mentre, mentre i numeri controllati è inferiore
rispetto alla lunghezza della lista?
>> JASON Hirshhorn: OK, questo è un bene.
Penso misphrased la mia domanda poco.
Stavo solo cercando di arrivare stiamo andando ad avere per andare
attraverso l'intera lista.
Così, mentre l'elenco è in ordine, per me, è difficile da mappare su.
Ma in fondo, è così che Penso a questo.
Passare attraverso l'intera lista, trovare il minor numero, posizionarlo nella
inizio - in realtà, hai ragione.
Facciamo entrambi messi.
>> Così, mentre l'elenco è in ordine, abbiamo bisogno di passare attraverso l'intera lista
una volta, trovare il numero più piccolo, posto esso all'inizio della lista, mettere
all'inizio della lista in cui la minor numero era, e poi se l'
elenco è ancora fuori uso, abbiamo avuto modo di passare attraverso questo
processo di nuovo, giusto?
Ecco perché selection sort, runtime Big-O di ordinamento per selezione, chiunque?
>> STUDENTE: n quadrato.
>> JASON Hirshhorn: n quadrato.
Perché come Marcus e ho appena realizzato Qui, stiamo andando ad avere per
passare attraverso la lista lista numero di volte.
Quindi passare attraverso una sorta di lunghezza n n numero di volte
è in realtà n quadrato.
>> Quindi questo è il nostro pseudocodice.
Questo sembra molto buona.
Qualcuno ha domande sulla pseudocodice?
Perché in realtà ordinamento per selezione deve probabilmente venire un a uno, codice
pseudocodice.
Quindi tutte le domande circa l' logica del pseudocodice?
Si prega di chiedere adesso.
>> Selection sort - mentre la lista è fuori dell'ordine, stiamo per passare attraverso di essa
e trovare il più piccolo ogni volta e metterlo nella parte anteriore.
Così, mentre l'elenco è in ordine, può qualcuno mi dia quella riga di codice che
Non mi ha dato una linea di codice ancora, per favore?
Sembra una cosa?
>> STUDENTE: Questo è un ciclo for.
>> JASON Hirshhorn: Suona scrivere un ciclo for.
OK, potete darmi il ciclo for?
Per -
>> Studente: è uguale a 0.
>> JASON Hirshhorn: i o -
cosa ci manca?
Quello che viene qui?
>> STUDENTE: Int.
>> JASON Hirshhorn: Esattamente.
(Int i = 0; -
>> STUDENTE: i <n, i + +).
>> JASON Hirshhorn: Inchiodato esso, Jeff.
Stiamo attraverso la lista, giusto?
Abbiamo visto che il codice prima.
Perfetto.
Quindi cerchiamo di mettere i nostri parentesi graffe qui.
Ho intenzione di mettere un po ' parentesi graffe qui.
>> Così, mentre è 0, abbiamo bisogno di andare attraverso l'intera lista.
Così ogni volta che passare attraverso la lista, cosa vogliamo tenere traccia di?
>> STUDENTE: Se si apportano swap.
>> JASON Hirshhorn: Trova il numero più piccolo.
Quindi probabilmente dovremmo tenere traccia di il più piccolo numero ogni volta.
Così la linea che posso fare per tenere traccia il numero più piccolo?
Aleha, come posso mantenere traccia di qualcosa?
>> STUDENTE: Avviare una nuova variabile.
>> JASON Hirshhorn: Avviare una nuova variabile.
Quindi cerchiamo di creare una variabile.
Che tipo?
>> STUDENTE: Int.
>> JASON Hirshhorn: Int.
Chiamiamolo il più piccolo.
E che cosa fa uguali quando siamo solo agli inizi?
Non abbiamo ancora passati attraverso la lista.
Siamo alla prima parte della inserisci la nostra prima volta attraverso.
Cosa lo fa uguale, la numero più piccolo?
>> STUDENTE: valori che ho.
>> JASON Hirshhorn: valori che ho.
Che suona esattamente a destra, giusto?
Il numero più piccolo all'inizio è dove siamo.
Così ora abbiamo il nostro piccolo, e abbiamo bisogno di di passare attraverso l'intera lista e
confrontare questo piccolo a tutto il resto.
Quindi andiamo attraverso la lista di nuovo?
Michael?
>> STUDENTE: Hai bisogno di fare un altro ciclo for.
>> JASON Hirshhorn: Un altro ciclo for.
Facciamolo.
Dammi un po 'di codice.
>> STUDENTE: Per il ciclo -
per i più piccoli -
solo int j, potreste dire?
= 0, tali che -
>> JASON Hirshhorn: Beh, se vogliamo di passare attraverso l'intera lista -
>> STUDENTE: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Stiamo per passare attraverso il ciclo for, ancora una volta.
E come facciamo a trovare l' numero più piccolo?
Tom?
Abbiamo l'attuale numero più piccolo, così come facciamo a trovare il nuovo più piccolo?
>> STUDENTE: Possiamo controllare se il più piccolo numero abbiamo è maggiore
valori staffa j.
>> JASON Hirshhorn: Quindi, se più piccolo è maggiore di valori staffa j.
Quindi, se il nostro attuale più piccolo è maggiore di -
Ho intenzione di spostare queste due righe di codice fuori per un secondo.
Perché prima di fare qualsiasi scambio, abbiamo bisogno di passare attraverso l'intera lista.
Quindi questo pseudocodice dovrebbe effettivamente sia esterno che interno ciclo for.
Quindi, passare attraverso l'intera lista.
Se più piccolo è maggiore I valori j allora che cosa?
>> STUDENTE: Quindi più piccolo uguale valori j.
>> JASON Hirshhorn: Fantastic.
Una domanda veloce -
la prima volta che andiamo attraverso questo ciclo, mi sta andando a uguale a 0, j sta andando
ad eguagliare 0 volta che otteniamo qui.
Quindi stiamo andando a confronto un numero a se stesso.
Che è efficiente?
No, non è davvero efficiente.
Così fa il nostro j bisogno di andare da 0 a n ogni volta?
Abbiamo sempre bisogno di controllare attraverso l'intera lista?
[Incomprensibile]?
>> STUDENTE: Inizia con i invece.
>> JASON Hirshhorn: j can iniziare con quello?
>> STUDENTE: i.
>> JASON Hirshhorn: j può iniziare con i.
Così ora confrontiamo partire con quello che siamo su.
Ma anche allora, è che, come efficiente possibile?
>> STUDENTE: i + 1.
>> JASON Hirshhorn: i + 1 sembra essere la più efficiente, perché
già ho.
Stiamo affermando che l' più piccolo in linea 15.
Stiamo per iniziare con il successiva automaticamente.
Quindi passiamo attraverso il ciclo for.
Andremo attraverso ogni volta.
Andremo attraverso un certo numero di volte.
Ora abbiamo ottenuto attraverso questo ciclo for interno.
Noi abbiamo il valore più piccolo salva.
Dobbiamo metterlo al inizio della lista.
Allora, come faccio a metterlo al inizio della lista?
Qual è la variabile che si riferisce all'inizio della lista?
Siamo in questo al di fuori ciclo for, così quello che si riferisce alla
inizio della lista?
>> STUDENTE: valori che ho.
>> JASON Hirshhorn: Esattamente.
Valori i è l'inizio del -
o mi dispiace, non l'inizio.
Quello era confusa.
E 'dove siamo all'inizio del la porzione indifferenziati della lista.
Così valori che ho.
E che cosa fa che la parità?
>> STUDENTE: più piccolo.
>> JASON Hirshhorn: valori che è uguale a cosa?
>> STUDENTE: più piccolo.
>> JASON Hirshhorn: più piccolo.
Esattamente.
Quindi stiamo posizionarlo all'inizio della lista, e ora abbiamo bisogno di mettere
l'inizio della lista in cui il numero più piccolo era.
Allora, come faccio a scrivere dove l' piccolo numero era?
Valori di che cosa?
>> STUDENTE: 0.
>> JASON Hirshhorn: Il piccolo il numero è a 0?
>> STUDENTE: Già.
>> JASON Hirshhorn: Cosa succede se il più piccolo numero era alla fine del
questa lista non ordinata?
>> STUDENTE: Siamo spiacenti, qual era la domanda?
>> JASON Hirshhorn: Dove si trova il più piccolo numero?
Abbiamo preso il più piccolo e messo al inizio, con questa linea qui.
>> STUDENTE: Esso dovrebbe avere immagazzinate in alcuni -
>> STUDENTE: Valori j.
>> JASON Hirshhorn: Beh, è Valori non necessariamente j.
Non esiste nemmeno a questo punto.
>> STUDENTE: Devi dichiarare una variabile prima e
poi assegnarla a -
quando si trova il più piccolo numero, assegnare l'indice di quel numero di
qualche variabile o qualcosa del genere.
>> JASON Hirshhorn: Così può dici che ancora una volta?
>> STUDENTE: Allora, dove avete dichiarato int più piccolo, si dovrebbe anche dichiarare int
piccolo index = i, o qualcosa di simile.
>> JASON Hirshhorn: Allora, dove mi int piccola, non dovrei solo tenere traccia
del valore ma la posizione.
int smallest_location = in questo caso, ci limiteremo a fare i.
Abbiamo bisogno di sapere dove si trova.
Siamo arrivati ​​alla fine del codice, e noi realizzato non avevamo idea di dove fosse.
E così ancora una volta, siamo di mappatura questo su uno a uno.
Voi ragazzi di codifica da soli volontà probabilmente ottenere allo stesso problema.
Come diavolo faccio a trovarlo?
E poi ti rendi conto, aspetta, io bisogno di tenere traccia di quello.
>> Quindi, se più piccolo è maggiore rispetto ai valori j.
Abbiamo impostato più piccolo uguale ai valori j.
Che altro abbiamo bisogno di cambiare?
Constantin, che altro fare abbiamo bisogno di cambiare?
>> STUDENTE: La posizione.
>> JASON Hirshhorn: Esattamente.
Quindi, mi dia quella riga nel codice.
>> STUDENTE: smallest_location = j.
>> JASON Hirshhorn: Esattamente.
E poi giù alla fine, se vogliamo mettere all'inizio della lista in cui
il numero più piccolo era, come Non ci riferiamo al punto in cui il
piccolo numero era?
Marcus?
>> STUDENTE: Il numero più piccolo era situato in posizione più piccolo.
>> JASON Hirshhorn: Quindi a valori smallest_location.
E cosa ci mettiamo lì?
L'inizio della elenco, che cos'è?
>> STUDENTE: Beh, noi non sappiamo veramente più perché abbiamo sovrascritto.
Quindi è una località scambiati di queste due linee?
Se si passa a quelle due righe in giro.
>> JASON Hirshhorn: OK, così noi non lo facciamo più, perché abbiamo reimpostare la linea
prima i valori ai più piccoli.
Così abbiamo perso quel valore iniziale.
Quindi lei ha detto di swap queste due linee.
Così ora mettere l'inizio della lista dove il numero più piccolo era.
Così smallest_location uguale valori i.
Che si muove l'inizio di questo parte indifferenziati della lista per il
posizione più piccolo.
E poi in valori mi ci stiamo muovendo che più piccolo numero.
>> Ha senso perché noi ha dovuto fare quel swap?
Avremmo sovrascritto quel valore - un'altra cosa che probabilmente avrebbe
capito e si trovano in PIL.
Così ci siamo presi cura di tutto il pseudocodice.
C'è qualcos'altro che bisogno di scrivere qui?
Qualcuno può pensare a qualcosa?
>> STUDENTE: Come lo sai quando hai finito?
>> JASON Hirshhorn: Come facciamo a sapere quando abbiamo finito?
Ottima domanda.
Quindi, come facciamo a sapere quando abbiamo finito.
>> STUDENTE: Creare una variabile per tenere il conto di se c'è un contratto di swap effettuate o non
e passare attraverso un passaggio.
>> JASON Hirshhorn: OK.
Che avrebbe funzionato in bubble sort.
Ma per ordinamento per selezione, se non lo facciamo fare uno scambio, che potrebbe essere solo
perché il valore più piccolo è in esso la sua posizione di destra.
Potremmo avere una lista 1, 2, 4, 3.
La seconda volta con noi non farà alcuna swap.
Saremo al numero 2, ma staremo a ancora bisogno di andare avanti.
Quindi abbiamo bisogno di tenere traccia di quando abbiamo finito, o vogliamo solo andare
fino a quando questo è finito?
>> STUDENTE: Possiamo solo andare finché non è finito.
>> JASON Hirshhorn: possiamo solo andare fino a quando questo è finito.
In bubble sort, hai proprio ragione, Jeff e Aleha, con la soluzione -
è ottimo per tenere traccia di quanti swap che hai fatto, perché in bolla
ordinamento, se si fa, infatti, non fare swap, il gioco è fatto e si può forse tagliare il
problema un po '.
Ma per ordinamento per selezione, hai davvero avuto modo di passare attraverso alla fine del
elencare ogni volta.
>> Quindi questo è quello.
Abbiamo due minuti dalla fine.
Facciamo tutti.
Vorrei solo aprire trovare qui e fare sicuro che sto infatti richiamare -
Non sto chiamando bubble sort.
Cambiamo questo ordinamento per selezione.
fare tutti. / trovare.
Scopriamolo 42.
Questa volta andiamo a passare un elenco indifferenziati, perché dovrebbe ordinare
in primo luogo, per il codice find - dovrebbe ordinare prima utilizzando la nostra funzione di ordinamento e quindi
cercare qualcosa.
Incrociamo le dita tutti.
>> Oh mio Dio.
Wow, il mio cuore batteva.
In modo che sia corretta.
Infatti, se abbiamo corso questo più estesamente, il codice, per quanto posso
dire, è perfettamente corretta.
Ci sono alcuni suggerimenti Vorrei avere per voi.
Per esempio, 15 e 16 sembrano un po 'ridondante.
Sembra che non necessariamente necessario salvare sia quelli.
Se avete la località più piccola, è può facilmente trovare il valore più piccolo da
semplicemente digitando valori di i.
>> Quindi, se dovessi essere classificazione codice, che io in realtà essere, vorrei
probabilmente decollare un punto, se si incluso entrambi, perché si
non hanno bisogno di entrambi.
Se avete la posizione, è possibile molto facilmente ottenere il valore.
E sembra un po 'strano memorizzare entrambi.
Forse nemmeno prendere un punto, ma certamente commentare che questo è forse
Non una scelta stilistica è necessario fare.
Naturalmente, il codice ancora funziona perfettamente.
>> Così purtroppo non abbiamo fatto arrivare a bubble sort.
Mi dispiace per questo.
Abbiamo fatto finitura selection sort.
Qualcuno ha domande finali sulla selezione tipo?
>> OK, prima di testa fuori, ti voglio di aprire il vostro browser Chrome.
Ci dispiace che era solo una spina palese per un tipo di browser internet.
È possibile aprire qualsiasi tipo di browser, ma probabilmente sarà Chrome.
E andare a questa seguente sito Web -
sayat.me/cs50.
Se non stai digitando nel vostro computer in questo momento, siete chiaramente
non farlo, Tom.
>> E vi prego di farlo sia a destra ora o nella prossima ora -
darmi qualche feedback.
Questo è solo capitolo due.
Abbiamo molti di più insieme, così ho hanno un sacco di spazio per migliorare.
Ho magari anche fatto bene alcune cose.
Così si può farmi sentire tutto male, ma se anche voi volete darmi uno smiley
faccia, mi apprezzerebbe che pure.
Fill che dentro
>> E con un solo minuto dalla fine, che è stato tre settimane.
Io starò fuori per un po ' se avete domande.
Vedrò voi ragazzi in lezione di domani.