[Powered by Google Translate] [Sezione 3] [meno confortevole] [Nate Hardison] [Harvard University] [Questo è CS50.] [CS50.TV] Bene, cominciamo. Benvenuti alla Settimana 4 di CS50. Se voi ragazzi aprire un browser Web e aprire pset 3, Scramble con CS50, stiamo per cominciare ad andare attraverso la sezione di domande. Proprio come la scorsa settimana, lavoreremo in CS50 spazi, se ti anche tirare su pure che, e se si va avanti e visitare questo link che ho qui in alto. E 'ora di iniziare. Abbiamo ottenuto il nostro piccolo programma hi qui. Niente di pazzesco. Una delle prime cose che voglio fare con voi oggi è andare oltre alcune soluzioni Set di Problema 1, tipo di soluzioni di esempio, solo così si può avere un'idea di che tipo di personale è la scrittura del codice, che tipo di studenti di altri codici di scrittura, e hanno si dà un'occhiata a esso, perché so che è strano quando si invia una soluzione ad un problema proposto e ricevere commenti sulla vostra versione, ma a volte è utile per vedere come altre persone lo ha fatto, in particolare quelli che sono carina. Per la maggior parte, sono rimasto veramente colpito con le soluzioni che voi ragazzi prodotte. Non ho ancora iniziato a guardare 2s problemi il set, ma se siete come la prima, vuol dire solo cose positive. Se guardate le mie revisioni, cominciamo tutta la strada fino a Revisione 1, e stiamo andando a prendere una rapida occhiata a una soluzione Mario. Se si tira questo in su, questi programmi che andremo a presentare sono corretti. Non ci sono stati problemi di correttezza con questi problemi, ma piuttosto, vogliamo parlare un po 'di problemi di progettazione diverse , che vengono utilizzate qui. Una delle cose interessanti che era circa la soluzione è che ha usato questo costrutto nuovo, chiamato libra definire, talvolta indicato anche come un hash definire. Vorrei ingrandire qui. A # define consente di assegnare un nome a questi numeri nel programma. In questo caso, l'altezza massima di una piramide in Mario è stato 23 e piuttosto che mettere 23 in mio codice- ci riferiamo a quella più forte codifica 23 - invece questo dà il nome MAX_HEIGHT a quel numero, in modo che qui nella mia do-while si può effettivamente fare riferimento a MAX_HEIGHT invece di mettere il numero 23 pollici [Studente] Qual è il vantaggio di fare questo? Questa è una grande domanda. Uno è la leggibilità. Un vantaggio di utilizzare questo # define è la leggibilità. Quando sto leggendo questo codice, posso vedere quello che sta succedendo. Vedo in questa condizione qui che stiamo testando per l'altezza essere <0, che potremmo anche definire essere una altezza minima o un'altezza min. L'altro vantaggio è che posso leggere il resto della linea per vedere che stiamo anche il controllo per assicurarsi che l'altezza non è superiore all'altezza massima, perché abbiamo intenzione di continuare mentre l'altezza è maggiore dell'altezza max. L'altro vantaggio è che, se diminuire un po 'qui- se corro questo programma e l'ho eseguito, ad esempio, con 23 in questo momento, verrà stampata su tutte le 23 righe, proprio come questo. Ma dire che ho deciso di cambiare l'altezza massima, e ora voglio limitare l'altezza massima delle piramidi essere solo dire-l'uomo, che era originale. # Include, # define MAX_HEIGHT, e diciamo che abbiamo voluto impostare uguale a 10. Ora, a questo punto, tutto quello che dovevo fare era cambiare in questa posizione uno. Posso ricompilare il codice, e ora se cerco di digitare 12, che mi chiederà di nuovo. In questo caso, stiamo solo usando MAX_HEIGHT volta. Non è quello grande di una seccatura per andare in e cambiare nel ciclo while se è necessario. Ma nei programmi dove si sta fanno riferimento lo stesso numero magico più e più volte, questo meccanismo di # define è davvero a portata di mano perché basta cambiare una sola volta nella parte superiore del file, è in genere dove li metti- e la variazione percola attraverso il resto del file. Altre cose che volevo sottolineare in questo compito che ho pensato che sembrava davvero bello, una era la denominazione delle variabili. Si vede qui che abbiamo variabili intere chiamate altezza di riga e di chiamata. Spazi, hash, aiuta a rendere il codice un po 'più leggibile, rende un po 'più comprensibile quello che sta realmente succedendo. Questo è in contrasto con l'utilizzo, per esempio, lettere casuali o semplicemente incomprensibile del tutto. Un'ultima cosa farò notare è che in cicli for, spesso queste variabili iteratore, questi contatori che è possibile utilizzare nel vostro cicli for, è standard e convenzionali per iniziare con i due e poi e poi j k e andare da lì, se avete bisogno di più variabili, e questo è solo una convenzione. Ci sono un sacco di convenzioni. Dipende dal linguaggio di programmazione che si sta utilizzando. Ma in C, di solito inizia con i. Non ha senso utilizzare, ad esempio, a o b a seconda della situazione. Questo è tutto per questo. Se ora tirare su Revisione 2, vedrete un altro Mario, e questo è simile a un altro che abbiamo visto, ma fa specie qualcosa di fresco. Se guardiamo a questa sezione proprio qui all'interno del ciclo for interno, si sta utilizzando un po 'di sintassi pazzo cercando qui proprio in questa linea. Questo è chiamato un operatore ternario. Si tratta di un'istruzione if else condensato in una sola riga. La condizione è questa parte tra parentesi. E 'equivalente a dire se j > Sam. Sam. Come Sam ha detto, che il processo di ricerca lineare sarà molto lento, e invece con la ricerca binaria, il modo in cui funziona è questo ogni volta che passare attraverso una iterazione del nostro algoritmo di ricerca, stiamo andando a dividere la lista in due, in sostanza, in due liste più piccole. E poi sulla prossima iterazione del ciclo, ci si divide di nuovo in altri elenchi più piccoli. Come si può vedere, il problema continua a sempre più piccolo perché osserviamo mezzo scarto della lista ogni volta. Come funziona questo scarto? Proprio come un promemoria, quello che stiamo andando a fare se ci fosse un computer e siamo stati, per esempio, alla ricerca del numero 5 in questa lista è che ci sarebbe scegliere un numero al centro. Nel mezzo di questa lista, perché ci sono 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 numeri, ci piacerebbe scegliere il numero sia presso il 4 ° o al 5 ° posto, e noi chiameremmo che il centro della nostra lista. Selezionare il numero in mezzo. Poi, proprio come Sam ha detto, faremo un test per vedere se questo numero è uguale al numero che si vuole ottenere o il nostro numero desiderato. Se è uguale, poi l'abbiamo trovato. Abbiamo vinto. Se non è uguale, poi ci sono un paio di casi. I due casi sono o il numero deve essere maggiore del numero che stiamo cercando, o è inferiore. Se è più grande, ci si sposta a destra. E se è di meno, ci si sposta a sinistra. E poi ripetere l'intero processo di nuovo sia sulla metà destra o la metà sinistra della lista. Il primo problema nella sezione di oggi è di capire come si può effettivamente iniziare a esprimere questo concetto in codice C. Abbiamo lo pseudocodice qui. Quello che inizieremo a fare io è tirare su un nuovo spazio, salvare questa revisione in modo da avere queste note per la successiva, dovremo eliminare tutto questo, e quindi copiare e incollare dal set problema queste informazioni nei nostri spazi, e spero che questo non si rompe. Perfetto. Se voi ragazzi tutto fare, copiare e incollare questo codice nel tuo nuovo spazio, in uno vuoto. Proviamo Daniel. Se si compilare ed eseguire il programma, funziona? >> No. Cosa sta dicendo? Dice il controllo raggiunge il termine della funzione non void. Si ', per cui vorrei provare a eseguirlo. Avete visto prima? Sapete cosa significa questo? Okay, sezionare questo un po '. Sta dicendo a file.c sulla linea 9, colonna 1 si ha un errore, proprio come hai detto, e si dice che è derivante da l'avviso di errore e l'avviso tipo restituito. Sembra che qualcosa sta succedendo con il tipo di ritorno, che ha un senso. Abbiamo un non-vuoto funzione, il che significa che abbiamo una funzione che non restituisce nulla. Una funzione vuoto è uno che assomiglia a questo: void foo (), ed è nullo in quanto il tipo di ritorno è nullo, il che significa che se avessimo qualcosa qui come il ritorno 1, otterremmo un errore di compilazione per questo. Tuttavia, abbiamo un non-vuoto funzione. Il nostro non void funzione, in questo caso è la nostra funzione di ricerca perché ha un tipo di ritorno di bool. Quando è dire che il controllo raggiunge la fine di una funzione non void, è perché la ricerca non ha un'istruzione return. Non è niente di ritorno di tipo bool. Siamo in grado di risolvere questo, e che cosa ne pensate voi ragazzi ricerca dovrebbe restituire per impostazione predefinita? Quale dovrebbe essere il valore di ritorno di ricerca? Perché questo è quello che può mettere alla fine. Charlotte, hai qualche-? Vero o falso? >> Vero o falso. Quale? False. Non lo so. Falso? Proviamo. Perché dici return false? E 'una grande intuizione. [Charlotte] Non lo so. Stiamo per tornare false in questo caso, perché questo sarà il nostro difetto se per qualche motivo l'elenco è vuoto o l'ago che stiamo cercando non esiste. Poi, alla fine, se non restituire true in precedenza in questa funzione, noi sappiamo sempre che questa funzione dirà no, non è nella matrice. Non è nel pagliaio. Ora, se compilare ed eseguire-fatemi salvare questo modo che possiamo tirare su. Ora, se compilare ed eseguire il nostro programma, si costruisce. Otteniamo la nostra richiesta poco. Se mi ha colpito 4-uh-oh. Non ha stampare nulla. Sembra che tutto è finito bene. Dobbiamo riempire questo trovi Abbiamo parlato l'algoritmo in pseudocodice un po 'di tempo fa. Fammi vedere, salvare questo, e io tirerò tale algoritmo su nuovamente. Che ha colpito questo ragazzo. Nope. Eccolo. Come possiamo fare questo? Quale potrebbe essere una buona strategia per la partenza di questo codice? È necessario scegliere un numero in mezzo. Come si fa a scegliere un numero nel corso di un array? Qualche suggerimento? [Studente] strlen diviso per 2. Strlen diviso 2. Questo è un grande. Strlen funziona con particolari tipi di matrici. Che tipo di array? Array di stringhe, array di caratteri. E 'quello stesso tipo di concetto che vogliamo applicare, ma non possiamo usare strlen, perché non abbiamo un array di caratteri. Abbiamo un array di int. Ma che cosa strlen ottenere per noi? Sai cosa si fa per noi? [Studente] strlen ci ottiene la lunghezza. Esattamente, ci ottiene la lunghezza. Strlen ottiene la lunghezza della matrice per noi. Come possiamo ottenere che il nostro programma di ricerca binaria? Come si ottiene la lunghezza di un array? [Studente] strlen? È possibile ottenere la lunghezza di una formattata correttamente matrice di stringhe C con strlen. Il problema, però, è che non abbiamo una matrice di stringhe. Se guardiamo a questo codice, abbiamo questa matrice intera. Come facciamo a sapere quanto è lungo? [Studente] C'è una equivalente per endpoint, come l int o qualcosa del genere? Si scopre in realtà non vi è, e così in un certo senso, questo è una di quelle cose che è solo buono da sapere su C, che non vi è alcun modo per ottenere la lunghezza di un array se tutto ti do è la matrice. Il motivo per cui con le stringhe, la ragione strlen opere, perché se una stringa sia formattato correttamente, avrà quel particolare carattere \ 0 alla fine. Si può anche immaginare se si dispone di una stringa formattato in modo errato e non c'è alcun carattere \ 0 lì, allora la cosa non funziona. [Studente] Si può aggiungere il \ 0? Potremmo in questo caso. Si potrebbe aggiungere una sorta di \ 0 o una sorta di significante carattere e quindi utilizzare tale. Ma questo non è proprio andare a lavorare perché il 0 \ è per un tipo char, e qui abbiamo int. L'altra cosa è che se dovessimo usare un valore speciale come -1 per indicare la fine di un array allora non abbiamo mai potuto conservare un -1 nei nostri array interi. Ci piacerebbe essere bloccato. Si scopre che l'unico modo per ottenere la lunghezza di un array in C è in realtà lo ricordo quando lo si imposta e poi passare con il contenuto dell'array in modo che ogni volta che ho una funzione che sta per fare un certo lavoro su una serie di numeri interi o in virgola mobile o doppie o quello che hai, Ho anche bisogno di dare la funzione di lunghezza della matrice, e questo è esattamente quello che abbiamo fatto qui in funzione di ricerca. Se si guarda, quello che abbiamo fatto quando si passa nella nostra matrice qui, Passiamo anche nella lunghezza, la dimensione. Accade solo che abbiamo chiamato questa variabile qui, questo parametro o argomento. Questo si chiama lista degli argomenti di una funzione o di un elenco dei parametri, e questi sono anche chiamati argomenti o parametri. Le persone usano termini diversi in momenti diversi. A volte li scambiare me stesso. Si dà il caso che questa variabile qui si chiama allo stesso modo a questo # define qui. Ma non sono la stessa cosa. La capitalizzazione è importante. Se si guarda a ciò che accade qui, si dichiara il nostro array di int, che abbiamo chiamato i numeri. Abbiamo dato la nostra dimensione, che corrisponde alla nostra # define in cima. E 'intenzione di essere 8. E poi, quando abbiamo poi chiama la nostra funzione di ricerca in basso, passiamo il numero che si vuole cercare, che abbiamo richiesto, ottenuto dall'utente. Passiamo nella matrice, questi numeri, e poi abbiamo anche passare nella dimensione della matrice, e quindi il valore di dimensione 8 viene memorizzato o passato a questo intero dimensione variabile chiamata. Abbiamo la dimensione della matrice. Ora, se torniamo a quello che stavamo parlando prima, Penso che Missy cresciuto al punto che quello che abbiamo bisogno di fare è ottenere la lunghezza della matrice e dividere per 2, e che ci darà il punto medio. Vediamo un po '. Posso avere qualcuno scrivere questo e salvarlo nel loro spazio? Che ne dici di Leila? Posso scrivere questo? Scrivi la prima linea dove si prende la lunghezza della matrice e ottenere il punto medio e conservarla in una nuova variabile. Ti do un paio di secondi. Sei pronto? [Studente incomprensibile] Certo, avrei potuto di calcolare il punto medio della matrice pagliaio all'interno della funzione di ricerca utilizzando la lunghezza della matrice pagliaio, che è la dimensione variabile? Niente di difficile qui. [Leila] Appena dimensioni / 2 e just- E salvare, e premere il pulsante Salva qui in alto, e noi lo tira su. Perfetto. Ecco fatto. Awesome. Come è, sarà questo compilare? [Leila] No, ha bisogno di essere più alto. [Nate] Sì, così che cosa dobbiamo fare? [Leila] Come punto medio int o qualcosa del genere. Awesome. Si ', facciamolo, int = punto medio formato. Sarà questo compilare? Facciamo eliminare questo commento e farlo uscire di strada. Che cosa non si compila su questo? Non stiamo facendo nulla con numero intero, quindi abbiamo bisogno di stamparlo o qualcosa di simile. Sì, esattamente. Avremo una variabile non utilizzata. Che altro non è andare a lavorare su questo? Penso che hai detto una cosa, Sam. Punto e virgola. Si ', mi manca quei punti e virgola. E sarà una cosa costante durante tutto il corso del termine. L'ultima cosa che farò è metto un po 'di spazio bianco su entrambi i lati di questo operatore qui, dato che è in genere come lo facciamo secondo la nostra guida di stile. Abbiamo il punto centrale della nostra matrice. Ora, se ci ricordiamo di nuovo al nostro algoritmo, quello che era il secondo passo che abbiamo dovuto fare una volta che abbiamo il punto medio? [Studente] Se si tratta di una maggiore [incomprensibile]. Gia ', quindi dobbiamo fare una sorta di confronto, e che cosa stiamo confrontando qui? Hai detto che se è superiore. Che cosa è in questa frase riferisce? Il numero che esce, se questo è superiore al punto centrale, poi salite alla matrice? Esattamente, quindi il numero che si apre quando si- L'ago, quindi stiamo confrontando l'ago, e cosa stiamo confrontando contro l'ago? Poiché l'ago è quello che stiamo cercando. Ci stiamo confrontando per arrivare al punto medio. Ma ha senso per verificare se metà ago =? Ha senso? Qualcuno d'accordo? Facciamo fare un tentativo, se (ago punto medio ==). [Studente] Non printf l'hai trovato. [Nate] printf ("L'abbiamo trovato \ n"); In caso contrario, sto per iniziare a fare qualcosa di diverso qui. Ho intenzione di iniziare a mettere le parentesi attorno if tutto il tempo solo perché se si aggiungono più roba, poi non otteniamo i compilatori. Si ', Sam. Tu hai un punto. Il problema è che il punto medio rappresenta una posizione nella matrice, ma si può arrivare a rappresentare il valore in quella posizione dell'array. Questo è un ottimo punto. Tutti hanno sentito quello che ha detto Sam? Ha detto che è il punto centrale rappresenta solo una posizione nella matrice, ma non è l'effettivo elemento nella matrice. Se ci pensate il codice come scritto in questo momento, se guardiamo a questo array qui, che ha 8 elementi in esso, qual è il valore del punto medio sarà in questa funzione? [Studente] 4. [Nate] 4. Se guardiamo il numero 4 - e possiamo solo eseguire questo codice e mettere un faccino triste qui perché noi non lo abbiamo trovato, se si esegue questo codice come è in questo momento, caricarlo, costruzione, fammi scorrere verso il basso, e se cerchiamo il numero 4, abbiamo trovato, ma non siamo riusciti ad printf sì. Una ragione è che non abbiamo fatto ritorno vero, ma abbiamo davvero trovare il numero 4? E Sam è dire di no. Che cosa abbiamo trovato? Abbiamo trovato il punto medio, che se guardiamo la matrice qui, che sta per essere l'elemento di indice 4 che stiamo guardando, che è 23. Come possiamo realmente ottenere tale elemento a metà e non solo lo stesso punto medio? [Studente] Ci sarebbe entrato char o qualcosa del genere? Cosa che lo fanno, solo per curiosità? Si può elaborare un po 'di più? È necessario trasformare la posizione nel numero, quindi hai avuto modo di fare un po 'di connessione penso che sia char, ma non potrebbe essere. Sì, questo è un buon punto. Abbiamo fatto un sacco di queste posizioni conversione in caratteri, questi personaggi, nei primi due insiemi di problemi. Risulta che qui, questo è quasi simile a l'accesso il carattere i-esimo all'interno di una stringa, se questo ha un senso. Qui si vuole accedere all'elemento punto medio. Come lo facciamo? Kevin, hai qualche suggerimento su come possiamo farlo? Si potrebbe fare pagliaio, parentesi aperta, metà, chiusa parentesi. Si può scrivere che per noi? Salva in qua, e noi provvederemo a tirare che fino. Stiamo guardando questa linea 9, e stiamo rendendo conto che non vogliamo confrontare l'ago al punto medio, ma invece, vogliamo confrontare l'ago per l'elemento in posizione punto centrale all'interno della nostra matrice pagliaio. Cool. Ecco fatto. Si ', sembra piuttosto buono, se (== ago pagliaio [punto medio]). L'abbiamo trovata. Ora, se si esegue il codice-we'll il backup di un po '- si compila, corre, e ora se guardiamo per 4, noi non lo abbiamo trovato, perché ora stiamo in realtà sempre il numero 23. Stiamo ottenendo il valore di 23, ed è quello che stiamo confrontando per il nostro ago. Ma questo è un bene. Questo è un passo nella giusta direzione. E 'quello che stiamo cercando di fare. Non stiamo cercando di confrontare l'ago contro le posizioni della matrice ma piuttosto contro gli elementi effettivi della matrice. Se guardiamo indietro ora il prossimo passo nel nostro algoritmo, qual è il prossimo passo? Leila già accennato brevemente. [Studente] Controllare per vedere se è maggiore o minore e poi decidere da che parte andare. [Nate] Sì, così come dovremmo farlo? Puoi mettere in qualche-I'Ll salvare questa revisione, e poi se si mette in alcune linee che farà questo. Si ', Charlotte. >> Ho una domanda. Non dovrebbe essere punto medio - 1 perché la prima cosa è 0 è indicizzato, quindi se mettiamo 4, che non è in realtà il personaggio che stiamo cercando? Sì, e l'altro problema che è- questo è un grande pesca, perché quello che sta per finire accadendo forse se continuare a muoversi e non abbiamo mai regolare inizialmente? Credo che quello che potrebbe finire per fare sta tentando di accedere l'elemento alla posizione 8 della matrice, che in questo caso non esiste. Noi vogliamo fare una sorta di contabilità per il fatto che abbiamo un po 'di indicizzazione pari a zero. [Charlotte] Scusa, volevo dire punto medio - 1 tra le parentesi quadre. Siamo in grado di farlo. Torneremo su questo punto in appena un po '. Una volta che si inizia a raggiungere il ciclo vero e proprio, che quando ci sarà davvero vedere questo entrano in gioco. Per il momento, siamo in grado di fare questo, ma hai completamente ragione. Tale indicizzazione zero, avrà un effetto che abbiamo bisogno di spiegare. Vediamo un po '. Come è il maggiore e minore di-? [Studente] ho come fare il superiore e inferiore a parte. Non ero sicuro di quello che la stampa se si scopre che è inferiore al punto medio pagliaio o superiore. Qui posso salvare ciò che I've- [Nate] Sì, se si salva quello che hai, e noi lo tira su. Ecco fatto. [Studente] E ho messo i punti interrogativi per quello che non sapevo. [Nate] che sembra grande. Qui abbiamo dei punti interrogativi, perché ancora non si sa quello che stiamo andando a fare molto ancora. Che cosa vogliamo fare-ops, abbiamo alcune coppie tutti funky su di noi. Ci correggere queste parentesi graffe. Ecco fatto. E allora cosa vogliamo fare, secondo il nostro algoritmo, se non troviamo l'ago? Dire nel caso in cui l'ago è meno di quello che stiamo guardando. Kevin. Solo guardare la metà sinistra. Giusto, quindi metteremo un commento qui dentro che dice "guarda metà sinistra." E se l'ago è superiore al pagliaio a metà, che cosa vogliamo fare? [Studente] Poi si guarda la metà destra. Guardate la metà destra, "guarda a metà a destra." Non c'è male. Ok, a questo punto, le cose sembrano abbastanza buono. Il problema con il codice come scritto è che cosa? [Studente] Non hai punti finali per le due metà. Giusto, non abbiamo punti finali per le due metà. Abbiamo anche solo per andare in una volta. Stiamo solo andando a guardare un punto medio. In entrambi i casi l'elemento c'è, o non lo è. Per completare questo, abbiamo bisogno di fare una sorta di ripetizione. Abbiamo bisogno di continuare a ripetere fino a quando si scopre che sia l'elemento è in là, perché abbiamo ristretto il campo e finalmente trovato, o non è lì perché abbiamo guardato attraverso tutte le cose nelle metà appropriate della matrice e trovato che nulla è lì. Ogni volta che abbiamo ottenuto questa ripetizione in corso, quello che abbiamo intenzione di usare? [Studente] Un ciclo. Una specie di loop. Sì. [Studente] Possiamo fare un ciclo do-while e farlo fare e poi mentre l'ago non è uguale a non-sono sicuro dove stavo andando con questo. Ma un po 'come fare questo fino a quando non è uguale al valore che l'input dell'utente. Sì, così vediamo, come potrebbe questo stesso scrivere? Hai detto che usiamo un ciclo do-while. Da dove viene il do di partenza? [Studente] Subito dopo la dimensione / 2. [Nate] Ok, e cosa dobbiamo fare? Ci riempire il tempo dopo. Che cosa abbiamo intenzione di fare? [Studente] Non vogliamo fare tutte le cose che abbiamo in se parte? [Nate] fare tutta questa roba, grande. Copia e incolla. Oh, cavolo. Vediamo se questo funziona, se possiamo scheda questo oltre. Bella. Ok, e salvare questo modo voi ragazzi ce l'hanno. Va bene, e ci accingiamo a fare questo mentre- qual è stata la condizione mentre eri dopo? [Studente] Mentre l'ago non è uguale, così come il punto esclamativo. Ma io non so esattamente di cosa si tratta ancora. [Nate] Sì, questo è un modo per farlo. Sam, hai un commento? [Sam] mi sono ricordato quando ho guardato i video, Ho preso uno screenshot di uno dei-come quando abbiamo fatto lo pseudocodice per esso, ci fosse qualche relazione tra max e min. Penso che sia stato qualcosa di simile, se max è mai inferiore a min. Capito. [Sam] O come se max non è inferiore a quello minimo o qualcosa del genere, perché vorrebbe dire che hai cercato tutto. Sì, così che cosa suona come max e min sono state riferendo? [Sam] Vero che i-numeri interi che stanno per cambiare rispetto al punto in cui abbiamo messo il punto medio. Esattamente. [Sam] A questo punto, sta andando a [incomprensibile] calcolare il max e min. Punto centrale è il max e min idea. Questo ha un senso per la gente? Se dovessimo iniziare a guardare come stiamo andando a fare questa iterazione, hai perfettamente ragione che vogliamo utilizzare una sorta di do-while. Ma credo che se ci ricordiamo quello che sta succedendo nel punto di questa matrice e quello che succede-sto per scrivere qui- alla prima iterazione della ricerca binaria, abbiamo- Ho intenzione di usare b ed e per indicare l'inizio. E poi la fine del nostro array. Sappiamo che l'inizio è alle 4 del proprio qui, e sappiamo che la fine è a 108. Dire che stiamo cercando per il numero 15. La prima volta che lo facciamo, come abbiamo visto in precedenza, il punto centrale è o sta per essere 16 o 23 a seconda di come si calcolano le cose. Dal momento che in modo uniforme dividendo in mezzo ci avrebbe dato questo spazio tra il 16 e il 23, non si può dividerlo in modo uniforme o dividere e arrivare a un punto medio vero. Vedremo 16. Ci rendiamo conto "Ehi, 16> 15 che stiamo cercando." Per vedere poi la metà sinistra della matrice quello che finirà per fare è scartare Questa intera porzione superiore e dicendo: "Okay, ora il nostro punto finale sta per essere qui." La prossima iterazione del nostro ciclo, stiamo ora guardando questa matrice, efficacemente aver scartato questa porzione perché ora se stiamo prendendo il punto medio di essere la differenza tra l'inizio e la fine, troviamo il nostro punto centrale per essere 8, che possiamo quindi verificare 8 per vedere dove è in relazione al numero che stiamo cercando, 15, trova che 15 è maggiore, quindi dobbiamo passare alla parte destra della lista, che sappiamo perché siamo esseri umani, e possiamo vedere. Sappiamo che la parte destra sarà dove la troviamo, ma il computer non sa che, per ciò che faremo è che troveremo a hanno questo salire, e ora l'inizio e la fine sono nello stesso punto, in modo che il punto centrale diventa il numero nell'elenco solo a quel punto, che è il 15, e l'abbiamo trovato. Vuol far luce su dove questo max intero e la notazione min sta andando, tenere traccia dei punti finali della matrice, al fine di capire come limitare le cose? Che cosa accadrebbe se questo non fosse pari al 15 adesso? Che cosa succede se stavamo cercando per il 15 e, invece, questo numero erano anche 16? Ci piacerebbe dire: "Oh, è maggiore. Vogliamo tornare a sinistra. " E ci piacerebbe spostare la nostra e verso destra, a questo punto abbiamo un endpoint che sarebbe in conflitto. Non sarebbe in grado di cercare elementi più perché ora abbiamo il nostro punto finale e il nostro punto di partenza, la nostra massima e la nostra min, ora sono capovolte. Cerchiamo attraverso l'intero array. Non riusciamo a trovare nulla. Questo è il punto in cui si vorrebbe dire: "Va bene, andiamo a fermare questo algoritmo. Non abbiamo trovato nulla. Sappiamo che non e 'qui. " Come è questo? [Studente] Come fa esattamente il computer passa alla fine? In che modo la fine finisce prima dell'inizio? L'estremità finisce prima dell'inizio a causa della matematica che stiamo andando a fare ogni volta che lo facciamo. Il nostro modo di scambiare è se si guarda la prima volta che facciamo questo swap dove abbiamo l'inizio a 4 e fine tutta la strada fino a 108 e il nostro punto di mezzo, diciamo, a 16 - Ho intenzione di ripristinare questo ritorno a 15, se stiamo cercando il 15, sapevamo che quello che abbiamo fatto quando ci siamo registrati il ​​16 e vide che era più grande e voleva eliminare tutta la parte destra della lista, abbiamo visto che quello che volevamo fare è spostare questo e proprio qui. In effetti, l'e hanno spostati in uno prima il punto medio. Allo stesso modo, quando abbiamo fatto questa iterazione dell'algoritmo e il punto medio era a 8, abbiamo scoperto che 8 <15, quindi abbiamo deciso di spostare il b un passato il punto medio. Ora, l'inizio e la fine sono entrambi insieme a questo 15. Se avessimo sta accadendo a cercare qualche altro valore, non 15, o se questa era stata invece 15 a 16, avremmo trovato che l'indirizzo che vogliamo spostare uno prima il punto medio. Ora l'indirizzo e ci sarebbe capovolto inferiore alla b. Esaminiamo il modo in cui in realtà finiscono per questo algoritmo di codifica. Sappiamo che vogliamo avere questo calcolo punto medio. Sappiamo anche che si vuole monitorare l'inizio e la fine della matrice della nostra matrice corrente in modo da poter capire dove questa metà sinistra della lista e dove la metà destra della lista è. Lo facciamo sia con inizio e fine, o possiamo chiamarli min e max. Userò iniziare e finire questa volta. Quando iniziamo, se guardiamo indietro al nostro esempio qui, il nostro inizio è stato impostato fin dall'inizio della matrice, come naturale. Che indice è stato questo? Quale dovrebbe essere il nostro inizio? Daniel. [Daniel] Haystack [0]. [Nate] Sì, così potremmo posto uguale a pagliaio [0]. Il problema, tuttavia, è che questo non ci dà la posizione del primo elemento. Ci dà l'indice del primo elemento o il valore reale che prima posizione. [Studente] che converte a 0,20? [Nate] Quello che voglio fare è, be ', non farà alcuna conversione. Quello che farà è che memorizza un 4 a iniziare, e poi sarà difficile fare paragoni contro iniziare perché begin terrà il valore di 4, che è l'inizio del nostro array, ma vogliamo tenere traccia gli indici della matrice a differenza dei valori. Ci effettivamente utilizzare uno 0, come quella. Per il fine della matrice-Charlotte portato questo poco prima. E 'qui che prenderemo in considerazione l'indicizzazione zero. Charlotte, qual è il fine della matrice? Qual è l'indice della fine? [Charlotte] Size - 1. Gia ', e che dimensioni dovremmo usare? Dovremmo usare la dimensione di capitale o di dimensioni minuscole? Capitale dimensioni. In questo caso, si potrebbe usare la dimensione di capitale. Se volessimo questa funzione per essere portatile e usare questa funzione in altri programmi, si può effettivamente utilizzare dimensioni minuscole. Va bene anche. Ma Charlotte è del tutto giusto che vogliamo avere dimensioni - 1. A questo punto- [Studente] Come è possibile che è possibile utilizzare size maiuscolo? Come è possibile che potremmo usare dimensioni maiuscolo? Si scopre che questi definisce # sono veramente, sotto il cofano, un testo come trovare e sostituire, se questo ha un senso. Quando si compila il codice, la pre-elaborazione di fase del compilatore passa attraverso il file, e cerca in tutto il mondo che hai scritto dimensione del capitale, e sostituisce il testo letteralmente con un 8, proprio così. In questo senso, questo è molto diverso da una variabile. Non occupa spazio in memoria. E 'un trucco semplice sostituzione di testo. In questo caso, abbiamo intenzione di usare la dimensione. Da qui ci si vuole fare una sorta di ripetizione, e siamo sulla strada giusta con il nostro do-while. Vogliamo fare qualcosa fino a quando una condizione non regge più, e, come abbiamo visto in precedenza, abbiamo visto che tale condizione era, infatti, che non vogliamo la fine essere inferiore inizia. Questa è la nostra condizione di arresto. In questo caso, si vuole fermare e dichiarare del tipo: "Ehi, non abbiamo trovato nulla." Per esprimere questo, noi vogliamo utilizzare una sorta di loop. In questo caso, sarebbe un ciclo do-while, un ciclo for, un ciclo while? Abbiamo un ciclo do-while qui. Avete tipi come questo approccio? Pensi che dovremmo tentare un approccio diverso? Kevin, qualche idea? Si potrebbe avere un ciclo while perché sappiamo massimo sarebbe maggiore di min a centrael inizio. Gia ', quindi non c'è di inizializzazione che deve accadere. Questi do-while sono grandi quando si ha qualcosa di inizializzare prima di effettuare i test, mentre qui sappiamo che non stiamo andando a tenere reinizializzazione sia iniziare e terminare ogni giro del ciclo. Sappiamo che vogliamo inizializzare loro, quindi controllare la nostra condizione. In questo caso, io in realtà andare con un semplice ciclo while. Si scopre che do-while vengono utilizzati abbastanza di rado. Un sacco di posti non hanno nemmeno lo insegnano i cicli while. Vanno bene per la gestione di input dell'utente, quindi abbiamo visto un sacco di loro finora. Ma normali cicli for e while sono molto più comune. Si scopre che questa condizione come scritto che in realtà non ci fare molto bene, e perché? Mi dispiace, io non conosco il tuo nome. Sono Jerry. >> Scusa? E 'B-O-R-U-I. Oh, va bene. Io non ti vedo nella mia lista. Oh, è perché-oh, questo ha un senso. Avete un idea del perché questo ciclo while potrebbe non funzionare come previsto, come scritto con la condizione? [Jerry] Vuoi dire come si desidera che tutte le cose dopo che al-? Si ', e questo è uno. Potremmo mettere tutte queste cose nel ciclo while, che è del tutto vero. L'altra cosa che è un po 'più problematico, però, è che questa condizione non funziona. [Studente] Hai bisogno di capovolgerla. Giusto, quindi questa condizione non sarà mai vero inizialmente il modo in cui ne abbiamo parlato. Vogliamo fare qualcosa fino > Inoltre cominciare? [Studente] Alla fine. Perché è calcolato solo la metà della lunghezza. È necessario aggiungere l'inizio. [Nate] Che cosa sarebbe questo il calcolo per noi? Se pensiamo a finire su questa prima iterazione del ciclo, fine sta per essere in posizione di indice 7. Iniziare è in posizione 0. Ricordate, stiamo cercando sia posizione 3 o posizione 4. Se guardiamo a questa matematica, solo per fare un po 'più tangibile, mettere un po 'i numeri qui, abbiamo 7, 0, così 7-0, e poi / 2 è 3 a divisione intera, che è. Poi abbiamo bisogno di aggiungere poi di nuovo il nostro inizio? Non fare in questo caso. Nella prima iterazione, sarà bene perché Begin è 0. Ma, come abbiamo progressi, facciamo davvero tutto solo bisogno di fine - inizio / 2. C'è un altro trucco qui, e questo è precisamente uno di precedenza. [Studente] Abbiamo bisogno di parentesi? [Nate] Esattamente, e questo perché, se non mettiamo queste parentesi, allora questa linea sarà interpretata invece come (fine) - (inizio / 2), che sicuramente non si desidera. Attenzione per le regole di precedenza. [Studente] Perché non è fine + inizio? Perché non è fine + inizio? [Studente] Perché non è così? Perché sarebbe +? Penso che tu abbia ragione. [Studente] Perche 'e' media? [Nate] + Fine iniziare, hai assolutamente ragione. Wow, ho preso una cantonata del tutto. Hai ragione. Se stavamo facendo il segno meno, vorremmo aggiungere l'inizio interattiva In questo caso, sei molto giusto che si vuole prendere la media dei due, così noi vogliamo aggiungerli, al contrario di sottrarre loro. [Studente] Sarebbe anche funzionare se fatto alla fine - inizio / 2 + iniziare. Sarebbe se lo facciamo-Credo di sì. Per esempio, se stavamo guardando iniziare, e lo abbiamo spostato qui alla 15. Ora iniziare è in posizione 2. End è in posizione 7. Se li sottraiamo, si ottiene 5. Dividere che per 2, otteniamo 2. E poi aggiungere 2 indietro, e che ci porta al 4 ° posto, che è proprio qui, che è il punto medio. [Studente] Abbiamo bisogno di prendersi cura di avvolgimento? In che senso abbiamo bisogno di prendersi cura di avvolgimento? Se la somma o la differenza tra a seconda di come lo facciamo non è un numero pari. Poi il computer si confonde se quando è 2,5; ci si sposta verso sinistra o verso destra per determinare quale è il punto medio? Capito. Si scopre che con la divisione intera, non abbiamo mai ottenere questi numeri in virgola mobile. Non abbiamo mai ottenere il decimale. E 'del tutto scartata. Se si dispone di un computer dividere due variabili int, e uno è 7, e l'altro è 2, non sarà possibile ottenere come risultato 3,5. Si otterrà 3. Il resto verrà scartato, quindi è efficace arrotondamento Non un giro, ma piuttosto un piano, se voi ragazzi sono a conoscenza che in matematica, dove è completamente scartare il decimale, e così si sta essenzialmente troncare fino al più vicino intera posizione, al numero intero più vicino. [Studente] Ma allora questo è un problema perché se si dispone di una serie di 7 elementi allora che prende automaticamente l'elemento 3a dal punto medio anziché il quarto. Come abbiamo a che fare con questo? E 'un problema, perché se avessimo una serie di 7, che prendeva il 3 al posto del 4. Potresti spiegare un po 'di più? [Studente] Perché se si dispone di 7 elementi quindi il 4 ° elemento sarebbe il punto centrale, giusto? Ricordate che il vostro commento di essere indicizzati a zero, però. [Studente] Si ', quindi in posizione 3. Questo sarebbe il punto medio. Gia '. Oh, va bene. Capisco quello che vuoi dire. E 'un po' strano, come ci abituiamo a questa intera nozione di sbarazzarsi di decimali. Questo è un ottimo punto. Finiamo questo. Abbiamo calcolato il nostro punto medio. Stiamo testando per vedere se il nostro ago è uguale al valore medio. Siamo la stampa che abbiamo trovato, ma in realtà, che cosa vogliamo fare in questa situazione? Lo abbiamo trovato, quindi vogliamo lasciare che il chiamante sa che abbiamo trovato. Abbiamo una funzione che è una funzione booleana tipizzato. Il nostro modo di segnalare al chiamante della nostra funzione che siamo pronti a partire è diciamo: "Ehi, questo è vero." Come lo facciamo, Kevin? Stai annuire con la testa. >> [Kevin] Aggiungi un return true. [Nate] Esattamente, restituisce true. Ora, se non è uguale, come possiamo vedere nella metà di sinistra? Tutte le idee? Stella, qualche idea? È necessario impostare una nuova posizione per la fine. Gia '. Quindi dobbiamo fare la posizione del punto medio - fine. Grande. Abbiamo bisogno di impostare una nuova posizione per la fine a guardare la metà sinistra. Questo era ciò che abbiamo parlato prima, dove Continuo a tornare in questo esempio. Ho l'inizio qui, e poi ho la fine fin qui. Anche in questo caso, se siete alla ricerca di 15, e il nostro punto centrale è a 16, e ci rendiamo conto, "Oops, 16 è più grande. Vogliamo passare alla metà di sinistra. " Vorremmo quindi spostare il termine al 15, e lo facciamo prendendo una distanza dal punto centrale e l'impostazione che, come la nostra fine nuova. Allo stesso modo, se si vuole guardare la metà destra, come potremmo farlo? Avete un idea? [Studente] Devi solo iniziare a impostare punto medio + 1. [Nate] Grande. E ora nel caso in cui non troviamo nulla, vuol avere curato per noi? Daniel, non che vengono curati per noi? [Daniel] No. [Nate] Se lo facciamo attraverso l'intero array e non troviamo nulla, dove sarebbe che essere curato, o dovremmo prendersi cura di essa? [Daniel] La condizione di tempo. [Nate] Sì, la condizione mentre, esattamente. Esso si occuperà di passare attraverso l'intero array, se non troviamo nulla. Questo ciclo while termina. Ci sarà mai incontrato questa condizione, e siamo in grado di restituire false. Possiamo anche lasciare questo qui come se in questo perché se questa affermazione è vera se, e la nostra funzione ritornerà, e così faremo essenzialmente annullare questa funzione, a questo punto quando torneremo vero. Ma cosa succede con questa struttura qui? Sarà questo lavoro del tutto, o c'è qualche difetto logico in là? C'è qualche difetto logico in là, con il modo in cui è impostato l'alto. Che cosa potrebbe essere? [Studente] Perché avete bisogno di - e + 1s? Questo imposta la nostra matrice fino a essere la nostra nuova metà sinistra e metà a destra. [Studente] Ma perché non hai potuto fare a meno - e 1s + 1s? [Nate] Potremmo impostato uguale al punto medio? Ciò che potrebbe essere problematico di questo? [Studente] Credo che sia inefficiente perché si sta verificando un valore che è già stato controllato. [Nate] Esattamente, quindi Sam è totalmente ragione. Se si imposta la fine e l'inizio pari alla metà invece di - 1 e + 1 riflessivo, ad un certo punto in futuro finiremo per il controllo del punto medio di nuovo. [Studente] ho iniziato il pset, e poi ho avuto qualcosa di simile dove ho dimenticato il + 1, ed è rimasto bloccato in un ciclo infinito. Già, perché a un certo punto non si è mai intenzione di iniziare a ottenere e terminare sovrapporre realtà. Cool. C'è un difetto più logico, e che è che questo deve assolutamente essere un else if. Perché potrebbe essere? La ragione è che se non è un altro se-hai visto che, Kevin? [Kevin] Sì, perché si sta cambiando il punto finale. [Nate] Esattamente. Stiamo cambiando il punto finale, e se è scritto in questo modo-we'll rendere gli spazi tra- si verifica questo caso. Questo caso, se ha successo, verrà interrotta dalla funzione. Poi si verifica questo caso successivo, e in caso di successo, che consente di regolare il punto finale, e poi continuerà e controllare questo caso. Ma a questo punto, non vogliamo che continui il controllo. Fortunatamente, non abbiamo reimpostare il punto centrale qui, e sappiamo che questo caso non avrà successo. Ma noi vorremmo mettere l'else if in là anche se questo potrebbe, in questo caso dal momento che non è la regolazione del punto medio, si che fanno la differenza? No, perché questi casi sono tutti esclusivi. Ancora una volta, il mio male. Non, credo, bisogno di questo else if. Siamo in grado di fare un tentativo ed eseguirlo e vedere cosa succede. Building, un errore si è verificato. Probabilmente perché ho lasciato questi di b ed e 'qui. Devo più di quelli in cima? Non sembra simile. Noi lo zoom indietro, costruire, lì si va, così ora se cerchiamo per 15, Sì. Fammi Immagine 15, sì. Siamo in grado di funzionare ancora. Caricamento di codice sorgente, la costruzione, l'esecuzione. Siamo in grado di cercare qualcosa di simile a 13, e non si ottiene nulla la stampa, quindi non secondo la quale per noi. E 'fantastico, perché non è nella nostra lista. Ora siamo fuori dal tempo. Che sta per sia per questa settimana. Grazie per essere stati, e ci vediamo dopo. [CS50.TV]