JASON Hirschhorn: Benvingut a la setmana tres, tothom. Tenim una concorreguda però apassionant secció per davant de nosaltres. Així que en primer lloc, perquè hem fet alguns avançar en el curs, però encara tenen una gran quantitat d'aprenentatge més que fer, estic apareixerà vostès alguns recursos que ha d'arribar a ser increïblement útil ja que no només s'acosta a la seva butlletins de problemes, sinó també a digerir tots el material que li donem nois a conferències i pantalons curts i secció. A continuació passar els primers 20 a 25 minuts de la secció repassant GDB, que vostè pot o no pot tenir s'utilitza en aquest punt, però és una eina increïblement útil que li ajudar a depurar els seus programes. Molts de vostès poden haver utilitzat printf al mitjà del seu programa d'esbrinar el que equivalia a una variable. GDB és fins i tot millor que printf i no arruïnar el seu codi perquè executar en un arxiu executable. Així que anem a repassar els 10 més útils les comandes que necessita per l'IAE, i estem anirà en un exercici junts per en el problema d'establir tres i més enllà, que pot usar GDB per ajudar a depurar seus programes. I, finalment, anem a repassar alguns classificació i recerca d'algorismes que has vist a classe, i estem anar a la realitat de codi, no només pseudocodi, però el codi binari de recerca, ordenament de bombolla, i la selecció de classificació. Així que en primer lloc, vull anar sobre els recursos. Aquesta és una llista extensa, i és petita font, perquè tenia molt a encaixar aquí. Però aquests no només li va a ajudar, de nou, amb els butlletins de problemes i informació per digerir que va aprendre, però sens dubte, arribat el moment concurs, aquests es ser increïblement útil. Així que en primer lloc, la ponència assenyala. Si vostè va a cs50.net/lectures i desplaçar-se a la setmana i un dia específic, veuràs que hi ha notes per a cada donar una conferència, la qual no és més que una transcripció, però una versió editada de el que va ser cobert en la conferència amb el codi de fragments i altres cosetes útils. Recomano anar sobre aquells. I llavors, així, no hi ha codi font disponible de cada conferència. I de nou, aquestes diapositives també estaran disponible en línia a cs50.net/sections aquesta tarda. Així segons són els curts cada setmana que temes de cobertura, en general de 5 a 15 minut de longitud. I aquells amb sort li donarà una gran introducció a diferents temes. En tercer lloc - i això és nou aquest anys - és study.cs50.net. Si no ha comprovat cap a fora, jo altament recomanable que ho faci. Tens l'oportunitat de triar un tema. Tenim dotzenes de temes sobre els que hi ha. Així, per exemple, has de triar les funcions. Li dóna algunes diapositives i pren nota de les funcions. Aquestes són en realitat les diapositives que TFS se'ls anima a utilitzar durant la nostra presentacions a la secció. També hi ha consells i trucs per fer front amb funcions, i hi ha problemes pràctics que ajuden a treballar amb funcions. També li donem enllaços a la curta en funcions i les vegades en què les funcions han sorgit en la conferència. Així study.cs50.net estrenar aquesta any, un recurs fantàstic. A continuació, tinc l'home, que és el manual de comandament que es pot executar en el línia d'ordres. Així que si vostè té alguna pregunta sobre un comandament, per exemple, Rand, que ens trobat la setmana passada durant la secció i és probable que hagi trobat en el seu problema s'ajusta al passar pel generar codi, però si escriu man rand, obtindrà la pàgina que et diu tot sobre rand. Li dóna el que es necessita, la paràmetres que es necessita, així com el retorn tipus i una breu descripció d'aquesta funció. Així que fes un cop d'ull a rand. Pot ser una mica prolix i confús, així que de vegades em sembla que simplement buscar a Google el que vull saber és la millor manera de trobar la resposta. Així que la pràctica amb Google. Ser bo a Google. Es convertirà en el seu millor amic. A més de Google, si no pots trobar a Google, cs50.net/discuss, és el fòrum de discussió. És probable que si vostè té una pregunta, una dels seus més de 700 companys també ha de qüestió i va poder haver demanat ja en el discutir fòrums i faci que sigui contestada. Així que si vostè té una pregunta comuna o vostè té una pregunta que vostè pensa potser altres persones podrien haver quedat a, fes un cop d'ull a cs50.net/discuss. Finalment, els dos últims, si vols parlar amb un ésser humà real, oficina hores de dilluns a divendres. També hi ha hores d'oficina en línia per als estudiants d'extensió. I per últim però no menys important, mi, signe d'exclamació. Tots vostès tenen la meva informació de contacte. Si necessites alguna cosa, si us plau, mai dubti en posar-se en contacte amb mi. Sempre fóssiu lliure de fer-ho. Molt pocs de vostès m'han agregat en Gchat, pel que ha estat decebedor, però espero que això canviarà entre aquest i el proper apartat. Qualsevol pregunta fins ara sobre els recursos? Gran. Finalment, un altre tap per retroalimentació, sayat.me/cs50. Vostè em pot donar informació anònima de com ho estic fent. Això va ser molt útil la setmana passada. Tinc un parell de comentaris de vostès just després de la secció, a més de altres estudiants que el van veure durant la setmana, i era increïblement servicial. Vaig a tractar de limitar la meva ús de la paraula "dolça", però jo et mostraré la meva entusiasme i emoció en altres formes. Però hi havia una altra addicional avaluacions substantives, ambdues avantatges i delta. Així que si us plau, li dono vostès retroalimentació en els seus butlletins de problemes. Siéntase lliure de donar la seva opinió en el meu ensenyament. Estic aquí per vostès. Gran. Això és tot el que tinc per la primera secció. Algú té alguna preguntes fins ara? I tinc una nota per el centre de control. Estudiants d'extensió m'han contactat a dient que no van a obtenir qualsevol arxiu d'àudio, però això està fora del meu abast per solucionar. Així que espero, que obté resolt en breu. Si estàs veient en línia, hi, però vostè no em pot sentir. Així que primer, anem de passar pel BGF. GDB, com ja he insinuat abans, és una eina de depuració molt millor que printf. Així que per començar amb GDB, nois, si vol obrir el seu aparell i prendre l'arxiu que vaig enviar a vostè abans - aquest fitxer també serà disponible en línia en una mica - i executar BGF. / el nom del fitxer. En primer lloc, per descomptat, vostè ha de compilar presentar perquè BGF només funciona en arxius executables. Però si mai voleu iniciar GDB, el primer que es fa, executa GDB. / Cèsar. Així que aquest és el nom del programa que estem va a anar amb ell a hores d'ara. Així que vaig a escriure fer César, que em donarà un arxiu executable aquí ressaltada en verd. I després em vaig a córrer GDB. / Cesar. I aquí el tens. Ja veus que tenim una mica de text dient-me sobre la versió de GDB, donant-me alguna informació sobre la garantia, i després tenen el símbol del PIB, el que sembla una mica que la nostra petició de la línia d'ordres, però ja veus que està obert parin, GDB, prop parin. Abans de continuar i depurar l'arxiu que vaig enviar a tots vostès, veurem alguns comandaments útils perquè tinguin un sentit del que anem a cobrir. Aquestes ordres són llistats aquí, al ordre en el que en general els utilitzo. Així que començo el meu programa executant GBD. / Nom del programa, en aquest cas, César. I llavors el primer que faig 99,9% de les vegades és dolent tipus de trencament. Això estableix un punt d'inflexió en el principal. En essència, el que està fent allà és el programa que va a parar a principal perquè pugui començar a examinar línia per línia, en lloc de córrer tot el camí a través. Vostè pot trencar en diferents punts el seu codi, però principal és generalment un bon lloc per començar. L'ordre següent Corro és un negoci. Això comença el programa en execució, i si vostè necessita per entrar a la línia d'ordres arguments, l'executa aquest comando. Executar amb els arguments. Així que ja que anem sobre una versió de C, que és el programa que vostès va escriure per al conjunt de processadors de dos - aquest, per descomptat, té alguns errors en el que és d'esperar que trobarem - anem a córrer córrer amb alguns comandaments arguments de la línia, perquè César, com vostès saben pel problema estableix les especificacions, pren una mica de arguments de la línia d'ordres. El següent parell d'ordres, el següent un es diu en realitat següent. Aquest pren vostè línia per línia a través del seu programa. Així colpejar n després Enter et porta a la següent línia, l'execució de la línia anterior. No es mira només el porta a la següent línia, però et porta a l'interior de funcions. Així que si vostè ha escrit una funció en el codi o desitja explorar un a i, per exemple, vostè pot colpejar s, i en lloc d'anar a la següent línia d' l'arxiu que estàs passant Ara, vostè realment pas en aquesta funció i veure el seu codi. Llista mostra, molt fàcil d'utilitzar format, el 10 o així les línies al voltant de on es troba actualment en el codi així que vostè pot veure realment l'arxiu en lloc d'haver de canviar cap enrere i cap a diferents punts de vista. Imprimir és com printf, com el seu nom indica. Això demostra el que és igual a una variable. Vilatans informació és realment útil. Es tracta d'una versió especial d'impressió. Informació vilatans et mostra tots els locals les variables, totes elles imprimeix cap a fora per a vostè que estan actualment disponibles. Així que en general, en lloc d'haver de imprimir les quatre variables que estic curiositat sobre si estic en un bucle, per exemple, acabo d'escriure informació locals, i em el que el meu comptador et mostro iguals, així com la matriu que sóc treballant en les mateixes. Finalment, continuï. Escrivint pausa que s'atura en el punt de ruptura. Es pot caminar a través de la línia de línia amb la propera i pas. Continuar executa el programa de la seva pròxima trencar punt o fins a la finalització si no hi ha més punts de trencament. Desactivar elimina punts de trencament si decidir trencar en la principal era inadequada, vols establert en un altre lloc. I, finalment, q, abandonat, se surt de GDB. Així que aquest programa,. / César, anem mirar a través d'aquest moment i van a usar GDB per trobar els errors en aquest programa. Em vaig trobar aquest programa abans amb Comproveu el 50, i jo en tinc un nas. Tot el que existia, el va recopilar, es passat una gran quantitat de les proves, però per alguna raó, no va passar del cinquè prova, girant barfoo, tot en majúscules, en E-D-O-I-R-R, tot en majúscules, usant tres com una clau. Tinc bastant a prop. Em vaig baixar per una lletra. Així que hi ha algun petit error aquí. He mirat a través del meu codi. Jo no podia entendre-ho. Amb sort, vostès poden ajudar esbrinar el que aquest error és. Així que aquest és l'error que estem buscant. Anem a passar a GDB. Un cop més, m'he trobat GDB. / Cèsar, de manera que ara estem en el BGF. I el que és el primer El que hauria de fer? Jo només he entrat GDB. Algú em dóna una bona comanda per entrar. ESTUDIANT: Trencar principal. JASON Hirschhorn: Trencar principal. Fantàstic. Fem que polz Vostès poden veure aquí o seguir al llarg dels seus ordinadors. Main Break, i veuràs un punt de ruptura es va fixar en - em fa una mica de direcció de memòria estrany, i també em dóna el número de línia. Si hagués de mirar cap enrere en aquest fitxer, Em faria adonar que la principal ocorregut en la línia 21. Què he de executar el següent? Està el meu programa en execució? No Llavors, què hauria de funcionar ara? ESTUDIANT: Run. JASON Hirschhorn: Run. He córrer córrer, o hauria Afegeixo algunes altres coses en? ESTUDIANT: Executar amb l'argument. JASON Hirschhorn: Executar amb els arguments de comandes. I ja que estic depuració d'una molt específica cas, que hauria d'entrar en aquest argument de la línia d'ordres. Així que em vaig a fer córrer 3, que és, de nou, la sortida que vaig rebre de Check 50. Programa d'inici. Anem a través d'un parell de línies. Ara veuràs que estem en la línia 21. Com sé que estem en la línia 21? Perquè si mires a l'esquerra de la meva finestra de terminal, hi ha que diu la línia 21. I això em fa, en realitat, la codi que es troba a la línia 21. Així que em vaig equivocar abans. Principal no és en realitat a la línia 21. Principal és un parell de línies per sobre de 21. Però en la línia 21, que és on estem trencant. Aquesta línia de codi té encara no executat. Això és important. La línia que es veu no té estat executat encara. Aquesta és la següent línia de codi vostè està a punt d'executar. Així que la següent línia, com vostès són probablement està familiaritzat amb, és aquest condicions comprovació per veure si tinc entrat en un argument de línia d'ordres. I una d'i, el que és el segon part que va? Què és un ai? ESTUDIANT: Si ho canvia a un nombre sencer. JASON Hirschhorn: Ho sents? ESTUDIANT: Està canviant la argument en un enter. JASON Hirschhorn: Així que una d'i canvis arg v1 d'una cadena a un enter. I llavors com és de xecs? ESTUDIANT: Si hi ha una segona argument de línia d'ordres, a un costat d'executar el programa. JASON Hirschhorn: I el que és la segona meitat d'aquest Comprovar expressió booleana? Aquesta part d'aquí, una d'i? ESTUDIANT: Si és negatiu. JASON Hirschhorn: Assegurar-se que? ESTUDIANT: Assegurar-se que és, de fet, positiva. JASON Hirschhorn: Exactament. Aquesta és la comprovació per veure si és negatiu, i si és negatiu, el tenir una sensació de la propera línia de força ser jo cridant en l'usuari. Així que anem a colpejar tal d'executar aquesta línia. No veiem que la línia que els nois potser esperava veure a cridar a la 'usuaris i, perquè aquesta línia no s'ha executat. Vaig entrar 3. Així ho vaig fer, de fet, introduir dos comandaments arguments de la línia, i 3 és més gran que zero. Així que vam veure aquesta línia, executem, però no ens trepitgem dins de la condició if. Així que ara, al costat, veig que estic establint clau int és igual a una i arg v1. Així que això és crear-me una contrasenya variable. Així que si imprimeixo clau en aquest moment, perquè que li permet veure la valor dins de la variable, clau és igual a 47. Això és estrany, però és clar, això és perquè no ho he fet executat aquesta línia encara. Així que ara si li pego n, executar aquesta línia, i fer tecla d'impressió, clau serà igual a 3, que és el que esperem que sigui igual a. Així que de nou, al BGF, la línia que Veig que ho has executat encara. Vostè ha de colpejar n o s o un nombre d'altres comandaments a realitat executar aquesta línia. Tecla Imprimeix. La clau està en 3. Fins ara, tot bé. String és text pla. Anem a executar aquesta línia. M'estic posant una cadena d'usuari. Anem a veure en el meu Check 50, I introduir barfoo majúscules, per això és el que vaig a entrar. Si ara puc imprimir text pla. Veuràs que és igual a una cadena. Em fa una mica d'una altra hexadecimal rar nombre, però ho fa en fet de dir que la meva cadena és barfoo. Si jo volia veure el que va igualar clau en aquest punt, com podria comprovar clau? ESTUDIANT: tecla Imprimeix. JASON Hirschhorn: tecla Print, exactament. I de fet, hi ha un accés directe. Si et canses d'escriure d'impressió, que pot simplement escriure pàg. Així tecla p fa exactament el mateix. I de nou, jo ho veig és igual a 3. Si volgués saber tant clau i barfoo igualar a la vegada però jo estava cansat d'escriure cada un de forma individual, que podria escriure info vilatans. Això me fa claus 3. Text sense format és igual barfoo. També em dóna aquestes dues coses rares a la part superior, aquesta variable ii aquesta variable n. Aquests són realment existent en el meu programa principal. No els hem trobat, però, sinó com una vista prèvia, els existir en el meu bucle for. Així que ara mateix, que equivalen a una mica estrany números perquè no han estat s'inicialitzen encara, però que encara hi ha en la memòria, de manera que només estan fixats a algun valor d'escombraries. Però sí veiem clau en la plana text allà. Així que vaig a executar aquesta línia, la línia 34, el bucle per. Anem a saltar al bucle prement n. I estem dins del bucle. Estem en el nostre primer xec. I un cop més, aquest tipus de han de buscar familiar per a vostè, perquè es tractava d'un Programa de César que va ser escrit, però de nou, té algun tipus d'error. I ara, si ho faig d'informació locals, perquè sóc dins d'aquest bucle, veuràs que i és igual a zero, ja que esperem. Això és el que ens vam proposar a e inicialitzat que en el bucle for. n és igual a 6. Això també fa sentit perquè establim al strlen de text sense format. Així que m'agrada fer informació locals o d'impressió a la variable sovint per assegurar-se que tot és sempre el Espero que per igualar. En aquest cas, tot està el que espero que sigui igual a. Així que anem a començar a moure a través aquest bucle. La línia que estic és la línia 36, ​​si plana text i és més gran que una i la plana text i és menor que o igual a z. Sé que el meu problema no és amb la meva primera carta, que és amb la segona lletra. Si mirem cap enrere a l'arribada 50, B va a E bé. Estic prenent l'A i deixar-lo com una A, no la canvia per D. Així alguna cosa va malament amb la segona lletra. Així que em vaig a moure en un segon. Però si jo volia comprovar el senzill text que va igualar en aquest particular, cas, jo crec que hauria de ser què? Què hauria de text pla de ser igual en aquesta primera ronda a través del bucle? ESTUDIANT: Zero? JASON Hirschhorn: Text simple de R? Així hauria de ser capital B. Jo, per descomptat, és igual a zero, però el text sense format suport de brida tancada és igual a zero B perquè les cadenes, com vam veure la setmana passada, som matriu, pel que estem rebent la primer caràcter d'això. Així que de nou, si vaig imprimir text pla d' Jo, jo, de fet, aconseguir el caràcter B. I això és net, oi? Jo en realitat no tinc text pla I. Això no és una de les variables que vaig establir o inicialitzat, però pot imprimir a terme tot un seguit de coses si voleu. Però anem a passar a través. Si text pla I és més gran que A i text pla I és menor que o igual a Z, que clarament és cert perquè tenim una capital de B. Vaig a córrer algun comandament en ell. Vam veure que les matemàtiques la setmana passada, així que anem a donar per fet que funciona correcte segons Check 50. Aquestes claus, el primer demostrar que estava sortint de la si condició, el segon un va mostrar que m'estic sortint del bucle for. I ara quan vaig colpejar A continuació, veurem estem de tornada en el bucle de nou. Anem a través de la per al bucle de nou. Anem realment pas en el segon iteració del bucle i el tipus info vilatans. Així que estem en la segona iteració del nostre bucle per. I és igual a 1, el que esperem. N és igual a 6, que esperem. És igual a la tecla 3, la qual esperem. I de text sense format, veuràs, és igual a EARFOO ara, no més perquè barfoo en la nostra iteració anterior, el B va ser canviat a una capital E. Així que estem a punt per trobar el problema, de manera que aquest és on anem a submergir-se en la depuració. Però algú té alguna pregunta sobre el que hem fet fins ara? Fantàstic. Així que estem a punt d'executar això si condició, suport de text pla Vaig tancar suport més gran que A i text pla I menys d'o igual a la Z. Però abans Entro a això, perquè aquí és on Sé que el meu error és, vull assenyalar fora de text sense format de I. Així posarem impressió. Ho fa igual al caràcter A, de manera que sembla fins ara, tot està bé i bo. Així que espero que aquesta línia per la meva lògica, aquesta línia ha de ser veritat. És una lletra majúscula. Però si li pego n, ens adonem que aquest línia, de fet, no s'ha executat. Vaig saltar a l'altra persona si. Per què va passar això? ESTUDIANT: Com que té la condició de text pla és més gran que A, no és igual o major que. JASON Hirschhorn: Així que vaig tenir el meu text pla I és més gran que A, no major que o igual a. Així que, clarament, la capital A no va fer desencadenar aquesta condició si, i ho vam fer no entrar-hi, i ho vam fer no fer el canvi necessari. Així que és això, en realitat. Em vaig adonar del meu error. Pogués tornar enrere en el meu arxiu d'origen, canviar-la i actualitzar-la i Executeu una comprovació 50 de nou. Però anem a veure, només per la pedagogia de bé, si segueixo endavant. L'altra persona si no s'executa bé, però el que en canvi és igual a és la comanda això no canvia. Pel que no ha canviat en absolut, i si imprimir text pla aquí, anem a veure que va a través d'aquest bucle no ho va fer, de fet, canviar aquest segon caràcter en absolut. És encara un capital d'A Així que de nou, estem depurant el nostre error. Ens vam adonar que no hi havia una lògica que falta. I hem depurat abans d'hora abans realment executar aquesta línia, però s'hauria adonat si haguéssim només Següent colpejar i saltar a aquesta persona si, això vol dir que que si la condició No era cert. Nosaltres no, de fet, obtenim el resultat que s'esperava. Així que ens podria haver estat incitat, vam tenir si no haguéssim estat tan astut, de mirar que si l'estat i comprovar si, de fet, nostra condició d'avaluar a cert en el context actual. Això és tot per a la depuració d'aquest programa. Algú té alguna pregunta? Què comandament podria colpejar a deixar de GDB? P. I llavors li demanarà, surt de totes maneres? Sí o no. Vaig a colpejar si, i t'he deixat GDB. Així que va ser una cartilla ràpida de GDB. En realitat, en un escenari real, Ho vaig fer en horari d'oficina. Em GDBed aquest programa exacte en hores d'oficina amb un estudiant. I si ens remuntem als comandos que vam veure abans, es va utilitzar ruptura principal, primer cosa que vam fer. Utilitzem carrera amb els arguments de línia de comandes, segona cosa que vam fer. Utilitzem pròxima molt per moure nosaltres a través de les línies. I de nou, la versió curta de la propera és n. Això està en els parèntesis en gris a la diapositiva. No fem servir el pas, però no ho vam fer necessàriament han de per a aquest cas. Però podríem utilitzar-lo en una mica més tard en l'actualitat si s'està depurant, per exemple, la recerca binària quan binari recerca es diu en una separada funció, però hi ha algun error amb ell. Anem a voler entrar en la crida a la recerca binària i realitat depurar. Llista que no utilitzeu ja sigui perquè teníem un bon sentit del nostre codi, però si ha volgut tenir una idea del que el codi que era a prop, podia simplement utilitzo llista. Imprimir utilitzem, els locals d'informació que utilitzem. Continuar nosaltres no necessitem utilitzar aquí cas, tampoc hem d'utilitzar desactivem, però vam fer ús renunciar. Un cop més, aquests 10 manaments, practicar-les. Si enteneu aquests 10 manaments, vostè ha d'estar preparat per depurar qualsevol emetre amb GDB. Així que seguirem, un cop més, a la quid de la secció d'avui, repassant aquests ordenació i recerca algoritmes. Abans de fer-ho, un cop més, qualsevol pregunta, comentaris, inquietuds per GDB? Així tothom va a utilitzar BGF en lloc de printf? Així que tothom, per l'amor de perpetuïtat, tothom assenteix amb el seu cap a la dreta ara, així que vaig a veure't en horari d'oficina i tots els TFS et veuran i que diran, mostreu-me com utilitzar GDB, i podràs per mostrar, no? Una mica? Potser amb sort. Genial. Així que anem a passar a ordenació i recerca. Vas a veure que tinc una llista ja ordenada per a nosaltres, però això no va ser el cas sempre. Així, en el conjunt de problemes d'especificacions per problema va fixar tres, tens pantalons curts que es pot veure, i que en realitat li pregunta a veure aquests pantalons curts. També en la conferència la setmana passada, vam molts d'aquests algoritmes, així que estic No passarà un temps a la classe va sobre aquests algoritmes de nou o dibuix fotos per veure com es algoritmes funcionen. Una vegada més, que la informació que pugui tornar a veure conferència, o que la informació és capturat extraordinàriament en els pantalons per a aquestes recerques, tots que estan disponibles en cs50.net. Així que en lloc, el que farem fer és escriure aquests programes. Tenim un sentit, un model mental, de com treballen, i així ho anem fer és codificar els de veritat. Anem a convertir aquest model mental, aquest quadre, si es vol, al codi real. I si fossis una mica confós o nebulós en el model mental, estic totalment d' entendre. No estem realment va a saltar al codi immediatament. Així, mentre que aquest indicador en aquesta diapositiva pregunta a codi de cerca binària, i en realitat, una versió iteratiu de recerca binària, el primer que Realment vull que facis és escriure alguna cosa de pseudocodi. Pel que té aquest model mental de com els treballs de recerca binària. Prengui un full de paper si té un fàcil accés, o obrir un editor de text, i m'agradaria a tothom a escriure. Prendre quatre minuts per a escriure la pseudocodi per a la recerca binària. Un cop més, pensar en aquest model mental. Vindré per aquí si té preguntes i podem dibuixar la imatge fora. Però primer, abans de començar la programació, M'agradaria escriure la pseudocodi per recerca binària així que quan ens bussejar, tenim una certa direcció com on hem d'anar. ESTUDIANT: Podem assumir el conjunt de valors que obtenim ja està ordenat? JASON Hirschhorn: Així que per recerca binària treballar - excel · lent pregunta - prendre en una ordenada matriu de valors. Així que suposem que funcionarà. Tornarem a aquesta diapositiva. Vostè veurà en porpra de la funció declaració és bool binary_search int valor, valors int, int n. Això hauria de resultar familiar si has ja abordat o aconseguit el seu les mans brutes amb el conjunt de problemes. Però aquest és el seu declaració de la funció. Un cop més, no hauria de tenir de preocupar per que tant en aquest moment. El que realment vull fer és prendre Quatre minuts per binari pseudocodi Cercar i, a continuació, anirem més que com un grup. I vaig a entrar en raó. Si vostè té preguntes, per llibertat perquè aixequi la mà. Per què no et prens dos minuts més per acabar el pseudocodi? Sé que això pot semblar ridícul que estem gastant tant de temps a cosa que ni tan sols és realment en C, però sobretot per a aquests més algoritmes difícils i problemes conjunts que hem d'esbrinar, començant en pseudocodi no preocupar sobre la sintaxi, només preocupar la lògica, és increïblement útil. I d'aquesta manera, no vas a resoldre dos problemes molt difícils alhora. No ets més que centrar-se en la lògica, i llavors vostè es mou en la sintaxi. D'acord. Comencem passar per el pseudocodi. He escrit aquí, binari Cerca pseudocodi. Anem a escriure això en el abordar junts. O el escriuré i et donaré me les indicacions que necessito. Llavors, pot algú donar-me la primera línia del pseudocodi que escriure per a la recerca binària? Sí, Annie? ESTUDIANT: Si bé la longitud de la llista és més gran que zero. JASON Hirschhorn: Mentre que la longitud de la llista superior a zero. I un cop més, veiem alguns C-buscant coses sintàctiques d'aquí. Però la major part d'això està en anglès. Algú té alguna línia que posen abans d'això en el seu pseudo-codi? ESTUDIANT: Obté un array d'ordenar nombres. JASON Hirschhorn: Vostè va escriure "obté una matriu de nombres ordenats. "Per la declaració de la funció, estarem passant una matriu de nombres ordenats. ESTUDIANT: [inaudible]. JASON Hirschhorn: Així tindrem això. Però sí, si no teníem això, hauria d'ordenar la nostra gamma de números, perquè la recerca binària només funciona a una matriu ordenats. Així, mentre que la longitud de la llista és igual a zero, estic posarà en algunes claus perquè es vegi una mica més com C. Però mentre, sembla en un mapa while, de manera que dins d'aquest temps loop Què necessitem per fer per recerca binària? Una altra persona que no m'ha donat una respondre encara, però que va escriure això? ESTUDIANT: Aneu a la meitat de la llista. JASON Hirschhorn: Tom. Anar a la meitat de la llista. I la pregunta de seguiment, la qual cosa què fem un cop estiguem a la meitat de la llista? ESTUDIANT: Feu una revisió de si això és el nombre que està buscant. JASON Hirschhorn: Excel · lent. Veu la meitat de la llista i comprovar si el nostre valor està allà - fantàstic. Algú té alguna cosa més que era diferent a això? Això és exactament correcte. El primer que fem en la recerca binària és anar a la meitat de la llista i comprovar per veure si el nostre valor hi és. Així que suposo que si el nostre valor és allà, què fem? ESTUDIANT: Tornem a zero [inaudible]. JASON Hirschhorn: Sí, si el nostre valor hi és, el trobem. Així que podem dir d'alguna manera, però, això funció es defineix, li diem a l'usuari el trobem. Si no hi és, però, això és on això es complica. Així que si no hi és, algú que estava treballant en la recerca binària o té una idea ara, què fem? ESTUDIANT: Pregunta. JASON Hirschhorn: Sí? ESTUDIANT: És la matriu ja ordenada? JASON Hirschhorn: Sí, estem assumint la matriu ja està ordenat. ESTUDIANT: Llavors vostè ha de comprovar si el valor que vostè veu és més gran que el valor que vostè vol, vostè pot moure a la meitat de l'altra meitat. JASON Hirschhorn: Llavors, si el mitjà de la llista és més gran que el que estem buscant, llavors nosaltres què? Realitzem moviments interns d'on? ESTUDIANT: Vols anar a la meitat de la llista amb números més baixos que això. JASON Hirschhorn: Així que anem a trucar a que l'esquerra. Així que si enmig és més gran, podem buscar la meitat esquerra de la llista. I després per la recerca, el que Què vull dir amb la cerca? ESTUDIANT: [inaudible]. JASON Hirschhorn: Anem a la mitjana. En realitat ens repetim aquesta cosa. Tornem a través del nostre bucle while. Et vaig a donar l'últim - una altra cosa, si, enmig és menys del que el que fem, què fem aquí? ESTUDIANT: Anar a la dreta. JASON Hirschhorn: Recerca de la dreta. Això es veu bé, però algú té res del que pot estar present o qualsevol altra cosa que es posa en el seu pseudo-codi? Així que això és el que tenim fins ara. Mentre que la longitud de la llista és més gran de zero, anirem a la meitat de la llista i comprovar si el nostre valor hi és. Si el mitjà és més gran, anem a buscar a l'esquerra, més si el mitjà és menys, anem a buscar la dreta. Així que tots hem tingut alguna familiaritat amb els termes que fem servir en informàtica i les eines que tenen. Però vostè ja notarà que érem parlant en anglès, però hi trobem un Moltes coses que semblaven un mapa a partir de eines que tenim a la nostra caixa d'eines de codificació. Així que tot d'una, no estem va codificar en realitat encara. Què és el que veiem aquí en anglès que els mapes a coses que podem escriure en C? ESTUDIANT: While. JASON Hirschhorn: While. Així que aquest temps aquí mapes sobre a què? ESTUDIANT: Un bucle while. JASON Hirschhorn: Un bucle while? O probablement, més en general, un bucle. Volem fer alguna cosa una i altra vegada. Així que anem a codificar un bucle. I ja sabem, perquè hem fet això un parell de vegades i ens tenen un munt d'exemples per aquí, com en realitat per escriure aquest índex per a un bucle. Així que hauria de ser bastant fàcil. Hem de ser capaços d'aconseguir que començat amb força rapidesa. Quina altra cosa és el que veiem aquí? Quines altres estructures de sintaxi, les coses que estem familiaritzats en C, ¿ens ia tenir un sentit de l'Based fora de les paraules que utilitzem? Sí, Anna? [Inaudible] és broma. Anna, endavant. ESTUDIANT: Si i més. JASON Hirschhorn: Si i una altra cosa - aquí mateix. Llavors, què els veu? ESTUDIANT: Un if-else. JASON Hirschhorn: Sí, condicions, no? Així que probablement haurà de escriure algunes condicions. I de nou, encara que potser confús al en primer lloc, en general tenen un sentit ara de com escriure les condicions i la sintaxi per a les condicions. I si no ho fem, només mirem el sintaxi de condicions, tallar i enganxar que, pel fet que sabem que necessitarà una condició aquí. Qualssevol altres coses que veiem aquest mapa a coses que podríem necessitar fer en C? Sí, Aleha? ESTUDIANT: Això pot ser obvi, per només la comprovació si un valor és igual a alguna cosa. JASON Hirschhorn: Llavors, com vam comprovar i - per tal d'anar a la meitat de la llista i comprovar si el nostre valor està allà? Com fem això en C? Quina és la sintaxi per això? ESTUDIANT: És igual, és igual. JASON Hirschhorn: igual, és igual. Així que aquest xec és, probablement, va ser un signe d'igual, és igual. Així sabrem el que necessitem que en algun lloc. I, de fet, només en escriure, veiem aquestes altres coses. Haurem de fer una mica de operadors de comparació en allà - fantàstic. Així que en realitat s'assembla, en termes un gran, no hem escrit paraula de codi de C encara. Però tenim el model mental cap avall a través de conferències i els pantalons curts. Escrivim pseudocodi com un grup. I ja tenim el 80% si no es 90% del que necessitem fer. Ara, només hem de codificar , El que de nou, és un problema no trivial de resoldre. Però almenys estem atrapats en la lògica. Si més no ara, quan anem a les hores d'oficina, El que puc dir, jo sé el que necessito fer, però pot vostè recordar em de la sintaxi? O fins i tot si les hores d'oficina estan plenes, vostè Pot Google per a la sintaxi, en lloc d'estar atrapat en la lògica. I de nou, en lloc de tractar de resoldre la lògica i els problemes de sintaxi tots alhora, sovint és molt millor trencar aquests dos problemes difícils apagat en 2 més manejables i fer el pseudocodi primer i després el codi en C. Així que anem a veure el que vaig fer pel pseudocodi abans d'hora. Mentre que la longitud de la llista és més gran que zero, mira la mitjana de la llista. Si el nombre es troba retornat cert, una altra cosa si el nombre més alt, recerca esquerre. Perquè si el nombre més baix, recerca dret, tornar false. Així que es veu gairebé idèntic, si no gairebé idèntica al que escrivim. En realitat, Tom, el que vas dir en primer lloc, trencar el mitjà de la llista i si nombre que es troba en dos estats és en realitat el que vaig fer. Jo els he combinat allà. Jo hauria d'haver escoltat que la primera vegada. Així que aquest és el pseudo-codi que tenim. Si vols ara, ho sento, vagi De tornada al nostre problema inicial. Del codi binary.c Let. Així implementar una versió iterativa de recerca binària utilitzant el següent declaració de la funció. I no cal per copiar cap avall de moment. De fet vaig a obrir fins aquí binary.c. Així que no és la declaració de la funció al centre de la pantalla. I veuràs que vaig prendre el pseudo-codi a partir dels meus costats, però gairebé idèntic al que escrivim, i posar això per vostè. Així que ara, anem a trigar cinc minuts per codificar aquesta funció. I de nou, si vostè té qualsevol pregunta, aixecar la mà, que em faci saber, vaig a entrar en raó. ESTUDIANT: [inaudible]. JASON Hirschhorn: Així que va prendre el binari definició de la recerca a la A dalt, en la línia 12. Això és el que tinc per la meva diapositiva. I llavors tot aquest pseudo-codi que acabo d' copiar i enganxar de la diapositiva, pseudo-codi de diapositives. Encara no estic sentint [inaudible]. Així que si vostè ha acabat la seva aplicació, vull comprovar-ho. Els vaig enviar un correu electrònic el fitxer helpers.h anteriorment en aquesta classe. I estarà disponible en línia, així per a baixar per observar la gent aquesta vegada la secció retardat. I acabo d'utilitzar la distribució genèrica codi de pset3. Així que vaig prendre find.C, utilitzar el meu arxiu helpers.h en lloc de l'arxiu helpers.h que és donat en el codi de distribució. I vaig haver de fer un altre canvi en find.C en lloc de cridar simplement recerca, trucar binary_search. Així que si vols provar el codi, saben que així és com es fa. De fet, quan estarem corrent aquest codi a hores d'ara, acabo de fer una còpia de el meu directori pset3, de nou, intercanvia els arxius d'ajudants i després va fer que canviar en find.C per cridar binary_search en comptes de buscar. JASON Hirschhorn: Si. Tens una pregunta? ESTUDIANT: No importa. JASON Hirschhorn: No es preocupi. Bé, anem a començar. Anem a codificar això com un grup. Una nota a part. De nou, això és, pot ser fàcilment intercanviat per Problemes de Tres. Tinc el meu arxiu helpers.h que, en lloc que el helpers.h se'ns dóna, declara recerca binària, bombolla ordenar i ordenació per selecció. I en find.c et donaràs compte en línia, Què és això, la línia 68, que anomenem binari en lloc de buscar en aquesta categoria. Així que de nou, el codi que es troba disponible en línia o el codi que són creant en aquests moments es pot intercanviar fàcilment per p el set 3 a comprovar-ho. Però primer, anem a codi de cerca binària. La nostra declaració de la funció, tornem una bool. Prenem un enter anomenat valor. Prenem una matriu d'enters anomenat valors, i prenem n ser la mida de la matriu. En la línia 10, aquí, tinc aguda inclouen stdbool.h. Algú sap per què està aquí? Llavors, què aquesta línia de codi fa? ESTUDIANT: Permet utilitzar un tipus de retorn void. JASON Hirschhorn: Exactament. ESTUDIANT: O és una biblioteca que permet utilitzar un tipus de retorn void. JASON Hirschhorn: Així que l'aguda inclouen line stdbool.h em fa una mica de definicions i declaracions de les coses que em permet utilitzar en aquesta biblioteca. Així que entre els que està dient que no hi ha aquest tipus bool flama, i pot ser vertader o fals. Així que això és el que fa aquesta línia. I si jo no tenia aquesta línia, ho faria tenir problemes per escriure aquest paraula aquí, bool, just aquí. Exactament dreta. Així que necessito que en aquest codi. D'acord. Així que això, de nou, és un procés iteratiu versió, no una recursiva. Així que anem a començar. Anem a començar amb aquesta primera línia de codi de pseudo. I és d'esperar, ho farem - o no és d'esperar. Anirem al voltant de l'habitació. Anirem línia per línia, i jo t'ajudarem a determinar la línia que necessitem per escriure primer. Així, mentre que la longitud de la llista és més gran que zero. Anem a començar a la part davantera. Quina línia he d'escriure aquí, al codi? ESTUDIANT: Si bé el parèntesi n és més gran que 0. JASON Hirschhorn: Mentre n és gran que 0. Per tant n és la mida d'una llista, i estem comprovant si - [VEUS interposant] JASON Hirschhorn: - Com? ESTUDIANT: Com sabem que n és la mida de la llista? JASON Hirschhorn: Ho sento. Per l'especificació PSET, la recerca i ordenar les funcions que necessita per escriure, n és la mida de la llista. Em vaig oblidar d'explicar que aquí. Però si. n és la mida de la llista, en aquest cas. Així, mentre que n és més gran que 0. D'acord. Això pot resultar una mica problemàtic però, si les coses segueixen. Perquè seguirem per conèixer la mida de la llista al llarg d'aquest funció, però diuen que partim amb una sèrie de 5 nombres enters. I anem a través i no tenim ara reduït a una matriu de 2 punts. Quin febrer sencers és això? La mida és de 2 ara que volem a veure, però que 2 és això? Això té sentit, aquesta pregunta? D'acord. L'hi preguntaré de nou. Així que vam començar amb aquest conjunt de 5 sencers, i n és igual a 5, no? Realitzarem aquí. és probable que canviarem la mida, dreta, com les coses segueixen. Què és el que diem que volem fer. No volem buscar l'omple de nou. Així que diguem el canviem a 2. Prenem la meitat de la llista que és rar. Tan just esculli 2. Així que ara n és igual a 2. Demano disculpes per la mala marcadors d'esborrat en sec. Cert? I estem buscant a través de la llista de nou amb una llista de mida 2. Bé, la nostra gamma és encara de mida 5. Nosaltres diem que només volem buscar 2 punts en el mateix. Així que 2 punts són aquests? Això té sentit? Són els que queden 2 punts? Són les correctes 2 punts? Són els mitjans 2 punts? Hem trencat el problema cap avall, però En realitat no sé quina part de el problema que encara estem veient, només per tenir aquestes 2 variables. Així que necessitem una mica més i després, mentre que n és més gran que 0. Necessitem saber on és aquest n és en la nostra gamma actual. Així que algú té un canviar a aquesta línia? La major part d'aquesta línia és perfectament correcte. Hi ha una altra addició? Podem canviar alguna cosa que n que aquesta línia una mica millor? Mm-hm? ESTUDIANT: Es pot inicialitzar una variable com la longitud de n que va a continuació, pot utilitzar més endavant en la funció? JASON Hirschhorn: Així inicialitzar una longitud variable a N, i fem servir aquesta tarda? Però llavors ens actualitzem longitud i encara amb aquest problema en el qual reduir la durada del nostre problema, però mai se sap on, en realitat, que la longitud dels mapes en. ESTUDIANT: No és el que passarà més tard, quan vostè està dient, busca a l'esquerra, buscar no? Vas a anar a una diferent àrea de la seva - JASON Hirschhorn: Anirem a una àrea, però com sabem que han d'anar? Si només tenim la matriu i això n, com sabem on anar a la de la matriu. En el fons, no? ESTUDIANT: Té vostè, com, una menor lligat i una variable de cota superior o alguna cosa així? JASON Hirschhorn: OK. Així que aquesta és una altra idea. En comptes de fer el seguiment de la mida, fem un seguiment de la menor i variable de cota superior. Llavors, com es calcula la mida de un límit inferior i límit superior? [VEUS interposant] JASON Hirschhorn: Resta. I també fer el seguiment de la menor lligat i límit superior de deixar-nos saber, estem buscant aquests dos? Estem buscant a aquests dos aquí? Estem buscant als dos del medi? Probablement no és el centre dels dos, perquè això, de fet, és la recerca binària. Però ara serem capaços d'obtenir la mida, sinó també dels límits de la matriu. En essència, si tenim el nostre gegant guia telefònica, que esquinçar per la meitat. Ara sabem que quan més petit llibreta de telèfons és. Però no estem realment esquinça la guia telefònica per la meitat. Encara hem de saber on és el nous límits del nostre problema és. Algú té alguna pregunta sobre això? Sí? ESTUDIANT: Funcionaria mitjançant la creació d'un variable i, que llavors tot just moc la posició d'i respecte al seu posició actual, i la longitud, n? JASON Hirschhorn: I què és i? ESTUDIANT: Com he de ser com una mena de - Igual que vostè inicialitza i per ser el posició mitjana de la matriu. I després, si el valor en la posició i en el mitjà de la matriu en trobat que ser menor que el valor que vostè necessita, i ara es converteix en la longitud de la matriu, més el valor d'i dividit per 2. Igual, veure, vostè canvia d'i - JASON Hirschhorn: així. ESTUDIANT: - fins al - JASON Hirschhorn: Així que estic gairebé positiu que funcionarà. Però el punt és, que necessita dues peces d'informació aquí. Vostè pot fer-ho amb principi i fi, o pot fer-ho amb la mida, i després algun marcador. Però vostè no necessita dues peces de la informació aquí. No es pot arribar a funcionar amb només un. Això té sentit? Així que anem a anar a través de, i farem [inaudible] i crear alguns marcadors. Així que què s'escriu en el codi? ESTUDIANT: Em acaba de dir int límit un és igual a 0. JASON Hirschhorn: Cridem que int, començant. ESTUDIANT: OK. JASON Hirschhorn: Això fa més sentit per a mi. I? ESTUDIANT: Jo vaig dir, suposo, int fi. JASON Hirschhorn: int fi. ESTUDIANT: Suposo, n menys 1, o alguna cosa per l'estil. Igual que, l'últim element. JASON Hirschhorn: Així que vostè va escriure, int començant igual a 0, i coma, i int final és igual a n menys 1, punt i coma. Així que, essencialment, el que estem fent aquí, 0 la primera posició. I com sabem, en arranjaments, ells no van fins an, van fins a n almenys 1. Així que tenim alguns límits de la nostra matriu. I aquests límits inicials resulten ser els límits inicials del nostre problema. D'acord. Així que això sona bé. Llavors, si ens remuntem a aquesta línia, mentre que Longitud de la llista és més gran que 0, el que, en lloc de n, ha posem aquí? ESTUDIANT: Escriu acabant minus principi. JASON Hirschhorn: Mentre que acaba menys començament és més gran que 0? D'acord. I podríem, si volguéssim fer que una mica més bonic, el que una altra cosa podíem fer? Si volguéssim netejar aquest codi una mica? Com podem desfer-nos del 0? Aquesta és només una qüestió d'estil. És correcte en aquests moments. ESTUDIANT: Ending no igualtat de principi? JASON Hirschhorn: Podem fer què? [VEUS interposant] ESTUDIANT: Ending és més gran? JASON Hirschhorn: Si. Només podem fer mentre que acaba és més gran que principi. Dreta. Afegim principi fins a l'altre costat d'això, i ens lliurem de la 0. Així que això només es veu una mica més neta. D'acord. Així, mentre que la longitud de la llista és 0, escrivim que, si bé és més gran que acaba de començar. Posarem a la nostra necessària claus, i llavors el primer que que volem fer és mirar a en una petita llista. Vostè? Em pot donar el - ESTUDIANT: Si parèntesi valor claudàtor - JASON Hirschhorn: Si parèntesi claudàtor valor. ESTUDIANT: Ending dividit per 2. JASON Hirschhorn: Ending? ESTUDIANT: Jo veig un problema amb el seu - JASON Hirschhorn: OK. Bé, miri el centre. Com sabem el que el medi és? Sí Així que permetin-me esborrar aquest codi. Com sabem el que el medi és? En qualsevol cosa, quan vostè té el principi i al final, com trobar el medi? ESTUDIANT: Promedias. ESTUDIANT: Vostè afegir junts i després - JASON Hirschhorn: Afegiu-lo junts i després? ESTUDIANT: I ​​vostè fa una mitjana. Divideixi per 2. JASON Hirschhorn: Afegiu-lo junts i dividir per 2. Així int mitjana és igual? Tom, vostè pot donar a mi? ESTUDIANT: A partir del plus de cap - JASON Hirschhorn: Inici a més d'acabar. ESTUDIANT: Tots, suport, dividit per 2. JASON Hirschhorn: All, entre parèntesis, dividit per 2. Així que això em dóna el medi de res, correcte? ESTUDIANT: També cal arrodonir això. JASON Hirschhorn: El que es fa significa, necessito arrodonir això? [VEUS interposant] ESTUDIANT: perquè si és un estrany nombre, llavors és com - JASON Hirschhorn: Bé, està bé. Així que podria arrodonir això. Però si és un nombre imparell, a 5, el que pugui tenint gener lluny de la meitat. O si és un nombre parell, més aviat, això és un millor cas. Si es tracta de 4, només tenim 4, puc prendre la primera "mitjana", van dir ells o el segon "mitjà". Qualsevol podria treballar per a una recerca binària, així que en realitat no necessito arrodonir. Però hi ha una altra cosa que em de mirar a aquesta línia. Nosaltres no podríem adonar-nos encara, però anem a tornar-hi. Com que aquesta línia en realitat encara necessita una cosa més. Però fins ara, hem escrit quatre línies de codi. Tenim el nostre principi i acabant marcadors. Tenim el nostre bucle while, que assigna de manera directa al nostre pseudocodi. Estem pensant en el mitjà que s'assigna directament sobre el nostre pseudocodi. Jo diria que això va a la mitjana de la llista, aquesta línia de codi. I després, una vegada que anem a la meitat del la llista, el següent que hem de fer és comprovar si el nostre valor hi és per el pseudocodi que va escriure abans. Llavors, com vam comprovar si el nostre valor és a la meitat de la llista? Vostè. Per què no fas això? ESTUDIANT: Si el nostre valor és en el medi és igual a el posem el - Vull dir igual igual a - JASON Hirschhorn: It - D'acord. ESTUDIANT: No estic segur del que el variables que estem buscant doncs encara, és perquè - [VEUS interposant] ESTUDIANT: [inaudible]. JASON Hirschhorn: Exactament. Per la declaració de la funció, estem buscant un valor. Així que estem a la recerca d'un valor en una matriu de valors. Així que estàs en el cert. Que farà, si el suport de valor parin oberta centre tancat iguals suport igual valor, i en el seu interior Què necessitem fer? Si el nostre valor està aquí, el que Què hem de fer? [VEUS interposant] ESTUDIANT: Retorn zero. JASON Hirschhorn: Retorna true. ESTUDIANT: Retorna true. JASON Hirschhorn: Michael, Què fa aquesta línia? ESTUDIANT: [inaudible] el programa s'ha executat el seu curs, i que ha acabat, i tens el que cal fer? JASON Hirschhorn: El programa o què? En aquest cas? ESTUDIANT: la funció. JASON Hirschhorn: la funció. I així, per tornar al que s'anomena i donar-li el valor, és cert. Exactament dreta. Principal. Quin és el tipus de retorn de principal, Michael? ESTUDIANT: int, sencer? JASON Hirschhorn: int, exactament. Un sencer. Això va ser només una pregunta per a assegurar vostès han estat al cim de la mateixa. Què se sol tornar, si totes les coses estan funcionant bé? ESTUDIANT: Zero. JASON Hirschhorn: Zero. Exactament dreta. ESTUDIANT: Si això només retorna true, no hi ha informació que ofereixen sobre el que el - Oh, això és només dir que aquesta valor que està dins de la matriu. JASON Hirschhorn: Exactament. Aquest programa no està donant la informació d'on exactament és el valor. Només està dient, sí, hem trobat ella, o no, nosaltres no el trobem. Així que si hi ha el nombre, retorna true. Bé, en realitat que acabem de fer que realment rapidesa amb que una sola línia de codi. Així que vaig a passar aquesta línia de pseudocodi. ESTUDIANT: No necessitem per canviar la matriu? Ha de ser valors, no de valor, no? JASON Hirschhorn: Ho sento. Gràcies. ESTUDIANT: Sí JASON Hirschhorn: Aquesta línia han de ser valors. Exactament dreta. D'acord. Així hem vist la llista mitjana. Si el nombre es troba return true. Continuant amb el nostre pseudocodi, si mitjana és més gran, la recerca es va anar. Així que vaig tenir aquí, si el nombre de superior, la recerca es va anar. Constantí, li pot donar em aquesta línia de codi? ESTUDIANT: Si el valor de la mitjana - JASON Hirschhorn: Així que si el valor - si parin oberta valora suport claudàtor de tancament mitjana - ESTUDIANT: És més petit que el valor? JASON Hirschhorn: És menor que. ESTUDIANT: Inferior al valor. JASON Hirschhorn: Valor. Bé, en realitat, desitja comprovar si el nombre - Ho sento. Això és una mica confús. Però la resta, si el nombre de la mitjà de la llista és més gran. ESTUDIANT: Oh, està bé. JASON Hirschhorn: canviaré això. Perquè si enmig és més alt, vulgueu cercar esquerre, OK? I què fem a l'interior això si condició? ESTUDIANT: Puc fer un petit canvi en la condició, el canvi a una altra persona si? JASON Hirschhorn: Else if? D'acord. Així que aquest codi s'executarà sobre el mateix. Però el millor d'usar if, else if, else if o if, else if, else significa que només un dels que va a comprovar, no els tres d'ells, potencialment. I això ho fa una mica millor en l'equip que està funcionament del seu programa. Així [? Constantí,?] estem dins d'aquesta línia, en cas contrari, si els valors, claudàtor de tancament mig suport és major que el valor. Què necessitem fer? Hem de buscar l'esquerra. Com fem això? Vaig a donar-li un nou començament. Tenim aquestes dues coses anomenades començant i acabant. Llavors, què ha de succeir al principi? Si voleu cercar a la banda esquerra de la llista, vam aconseguir el nostre inici de corrent. Què necessitem per fer-ho? ESTUDIANT: Fixem l'inici a meitat més 1. JASON Hirschhorn: Llavors, si estem la cerca de l'esquerra? ESTUDIANT: Ho sentim, almenys mitja - de manera que el final seria medi almenys 1 i inici - JASON Hirschhorn: I què que succeeix al principi? ESTUDIANT: Es manté igual. JASON Hirschhorn: Així que el significat segueix sent el mateix. Si estem buscant l'esquerra, estem utilitzant el mateix principi - exactament correcte. I el final? Ho sentim, el que fa el acabant igual altra vegada? ESTUDIANT: minus Mitjà 1. JASON Hirschhorn: minus Mitjà 1. Ara, per què almenys 1, no només del medi? ESTUDIANT: L'intermediari es queda fora de la imaginar ja, perquè teníem comprova que està fora? JASON Hirschhorn: Això és exactament correcte. El mitjà està fora de la imatge. Ja hem comprovat la mitjana. Així que no volem "el mitjà", cita Ho van dir ells, per seguir sent en el matriu que estem buscant. Així que això és fantàstic. Perquè si hi ha brida valors és major de valor final iguals almenys la meitat gener. Jeff, què passa amb aquesta última línia? ESTUDIANT: Else. Valors mitjà és menor que el valor? JASON Hirschhorn: Anem a que m'estàs donant més. Així que si no em dones - ESTUDIANT: Llavors començant seria més mitjà 1. JASON Hirschhorn: iguals Començant més mitjà 1, de nou, per al mateix raó per la qual Constantí ens va donar abans. I al final, que no ha donat em una línia de codi encara? Return false, Aleha, el què escrivim aquí? ESTUDIANT: Retorn falsa. JASON Hirschhorn: Torna fals. I ho hem de fer, perquè si no el troba, hem de dir que no el vaig trobar. I vam dir que tornarem a bool, de manera que definitivament hem de tornar una a algun lloc bool. Així que anem a executar aquest codi. De fet vaig a - així que estem en el terminal. Netejarem la nostra finestra. Farem tot. Trobem que hi ha un error. Hi ha un error a la línia 15, que s'espera punt i coma al final de l' declaració. Llavors, què se m'oblida? ESTUDIANT: Punt i coma. JASON Hirschhorn: Punt i coma fins aquí. Crec que va ser el codi de Tom. Així que Tom, [inaudible]. És broma. Fem-ho Marca Totes les de nou. ESTUDIANT: Què directori de Dropbox hem d'estar en això? JASON Hirschhorn: Així que vostè pot simplement veure per aquest bit. Però, de nou, si es volia moure aquesta codificar en el seu directori pset3 intentar a terme, això és el que vaig fer. Si et fixes aquí - ho sento, bona pregunta. [? LS,?] Tinc aquí el codi find.c des de les vostres distro d'aquesta setmana. Tinc helpers.h. Tinc un arxiu Make que en realitat editat una mica per incloure aquests nous arxius que estem escrivint. Tot aquest codi estaran disponibles, no el codi de distribució, però el nou Fer d'arxius, el nou arxiu es helpers.h estarà disponible en línia per a baixar. Una vegada més, de manera que aquests són els codis extra que tenen. Així que fan de tot, per aquesta línia, fa que trobar, binari, la selecció de la bombolla - marques els tres d'ells i compila en aquest codi troballa executable. Així que en general, no volem a directament a check50. Volem fer algunes proves pel nostre compte. Però només perquè puguem agilitzar això una mica, check50 2013 pset3.find passarà en helpers.c-- el meu mal. Jo no tinc això en aquest moment. Així que estem realment va a executar el codi de veritat. Usage.find /, ja saps el que això significa? ESTUDIANT: Es necessita un segon línia d'ordres en ella. JASON Hirschhorn: Necessito una segona línia d'ordres. I per l'especificació, necessito per entrar en el que estem buscant. Així que anem a veure el 42. El mantindrem en ordenada, perquè no han escrit una funció de classificació amb tot - 42, 43, 44. I Control D No s'ha trobat la l'agulla al paller. Això és dolent. És, sens dubte existeix. Intentarem alguna cosa més. Potser és perquè em poso que al principi. Farem 41, 42, 43. Això és. Es va trobar. Anem a posar-ho al final ara, només perquè puguem ser a fons - 40, 41, 42. No has trobat l'agulla. Així que he esmentat això abans. Per desgràcia, jo sabia que això que anava a succeir. No obstant això, per a fins pedagògics, és bo per a explorar-lo. No treballa. Per alguna raó, no ho pot trobar. Sabem el que hi ha allà, però no està resultant. Així que una cosa que podem fer és anar a través GDB per trobar-lo, però no fa a ningú, sense passar pel BGF, tenen una sentit d'on vam ficar la pota? [? Maduració? ?] ESTUDIANT: Jo crec que pot ser quan s'acaba és igual al principi, i és només una llista d'un sol element. Llavors, només fa cas omís que en lloc de fet revisant. JASON Hirschhorn: Això és exactament correcte. Al final és igual principi, oi encara tenen un element en la nostra llista? ESTUDIANT: Sí JASON Hirschhorn: Sí, de fet, tenir un i només un element. I que el més probable passar quan, pel codi que vam provar, ens trobem en el davant d'un paller o en al final de la paller. Aquí és on començament i final va a la igualtat de un, amb recerca binària. Així que en aquests dos casos no va funcionar, perquè acaba va ser igual al principi. Però si acaba és igual al principi, no executar aquest bucle while? No ho fa. I podríem haver comprovat que de nou mitjançant BGF. Llavors, com podem solucionar aquest codi, perquè quan, en posar fi és igual a començant, també volem aquesta while s'executi. Llavors, què solució podem fer a la línia 18? ESTUDIANT: [inaudible] és més gran que o igual a. JASON Hirschhorn: Exactament. Mentre final és més gran que o igual al principi. Així que ara, ens assegurem d'aconseguir que cas cantonada al final. I veurem. Anem a executar això un cop més. Farem tot. Una vegada més, vostè ha de tot just segueixi per aquí. Troba 41 aquesta vegada. Si prefereixes alguna cosa més consistent. Troba 42. Anem a posar-lo al començament - 42, 43, 44. El trobem. Així que va ser realment el canvi havíem de fer. Això va ser un munt que la codificació acaba de fer, la recerca binària. Algú té alguna pregunta abans de Segueixo endavant en les línies que escrivim en recerca binària o com ens imaginem el que vam fer esbrinar? Abans de seguir endavant, també vull assenyalar que en general, estudiem nostra pseudo-codi d'un a un en el nostre codi. Vam haver cosa difícil esbrinar amb el començant i acabant. Però calia no vaig imaginar que fos, vostè hauria escrit més o menys la Codi idèntics, excepte per aquestes dues línies superiors. I llavors s'hauria adonat quan que ho va fer en els controls i els casos que necessita alguna cosa més. Així que fins i tot si s'hagués seguit el nostre línia de pseudo-codi de línia, el haguessis fet aconseguit, excepte en dues línies de codi que necessita per escriure. I jo estaria disposat a apostar que vostès tot hauria esbrinat bastant ràpid, que necessitava per posar algun tipus de marcador en allà per esbrinar on estaves. Que de nou, és el poder de fer pseudocodi abans d'hora. Així que podem fer de la lògica, i després podem preocupar-se per la sintaxi. Si ho haguéssim confós sobre la lògica en intentar escriure el codi en C, ens hauria aconseguit tot en mal estat. I llavors estaríem fent preguntes sobre la lògica i la sintaxi i mallat tots ells junts. I nosaltres hauríem entrat perduda en el que pot convertir ràpidament en un problema molt difícil. Així que anem a passar ara a la selecció de classificació. Tenim 20 minuts per al final. Així que tinc la sensació que no serem capaços de aconseguir a través de tots ordenació per selecció i l'ordenació de bombolla. Però anem ben bé intent per acabar la selecció de classificació. Així implementar ordenació per selecció utilitzant el següent declaració de la funció. De nou, això es pren de la problema estableix especificacions. Valors int es claudàtors, és una matriu d'enters. I int.n és la mida de la matriu. Selecció espècie va per ordenar aquesta matriu. Així que pel nostre model mental de la selecció Ordena, tirem del - en primer lloc, anem a través de la llista de la primera temps, trobar el nombre més petit, posar-lo al principi, trobar la segona nombre més petit, el va posar al segona posició si volem ordenar en ordre ascendent. No estic obligant a escriure pseudocodi en aquests moments. Però abans de fer el codi com una classe en cinc minuts, anem a escriure pseudo-codi, així que tenim una mica de sentit d'on anem. Així que intentarà escriure pseudo-codi pel seu compte. I després tractar de convertir aquesta pseudo-codi al codi. Farem tot el que com a grup en cinc minuts. I, per descomptat, que em faci saber si té alguna pregunta. ESTUDIANT: És tot? JASON Hirschhorn: Veure fins on pot arribar en dos minuts més. Entenc que no ho faràs ser capaç d'acabar. Però anem a anar sobre això com un grup. Tots estan de codificació de manera que [inaudible], així que estic ho sento per fer una pausa el que estàs fent. Però anirem a través d'aquest grup. I de nou, la recerca binària, tots vostès donen m'uneixo si no més línies de codi. Gràcies per això. Anem a fer el mateix aquí, codi junts com un grup. Així ordenació per selecció - anem a escriure alguns pseudo-codi ràpid. Segons el model mental, algú pot donar-me la primera línia de pseudo-codi, si us plau? Què vull fer? ESTUDIANT: Si bé la llista està fora d'ordre. JASON Hirschhorn: OK, mentre que la llista està fora de servei. I què vol dir "fora de servei?" ESTUDIANT: Mentre [inaudible] no s'ha solucionat. JASON Hirschhorn: Si bé la llista està fora de servei, què fem? Dóna'm la segona línia, si us plau, Marcus. ESTUDIANT: Llavors trobar la següent nombre més petit. Aquesta serà una sagnia. JASON Hirschhorn: Així que trobar la següent nombre més petit. I llavors algú més? Quan trobem la immediata inferior nombre, què fem? Vaig a dir trobar el nombre més petit. Això és el que volem fer. Així que trobar el nombre més petit. Llavors, què fem? ESTUDIANT: [inaudible] a principi. JASON Hirschhorn: Ho sents? ESTUDIANT: Poseu al principi de la llista. JASON Hirschhorn: Així que el col · loca en el principi de la llista. I ho fem al que era al principi de la llista, no? Estem sobreescriure alguna cosa. Llavors, on posem això? Sí, Anna? ESTUDIANT: On els més petits nombre era? JASON Hirshhorn: Així que posi l'inici de la llista on la nombre més petit era. Així, mentre que la llista està fora d'ordre, trobar el nombre més petit, poseu-la a el principi de la llista, posar el principi de la llista, on el nombre més petit era. Marcus, pot reformular aquesta línia mentre que la llista està fora de servei? ESTUDIANT: Si bé les xifres no han estat ordenats? JASON Hirshhorn: OK, de manera que per tal de saben que els números no han estat ordenats, què hem de fer? Quant hem de anar a través d'aquesta llista? ESTUDIANT: Així que suposo que un bucle for, o mentre que, mentre que els números revisats és menys que la longitud de la llista? JASON Hirshhorn: OK, això és bo. Crec que misphrased la meva pregunta malament. Jo només estava tractant d'arribar a anem a haver d'anar a través de tota la llista. Així, mentre que la llista està fora de servei, per a mi, és difícil assignar successivament. Però, bàsicament, això és el Penso en això. Anar a través de tota la llista, busqui el nombre més petit, poseu-la a l' començant - en realitat, tens raó. Anem a posar a tots dos. Així, mentre que la llista està fora d'ordre, de passar per tota la llista una vegada, trobar el menor nombre, el lloc en el principi de la llista, posar el principi de la llista, on el nombre més petit era, i llavors, si la llista és encara fora d'ordre, no tenim ha d'anar a través d'aquest procés de nou, oi? És per això que la selecció de gènere, temps d'execució de Big-O d'ordenació per selecció, qualsevol persona? ESTUDIANT: n al quadrat. JASON Hirshhorn: n al quadrat. Perquè igual que Marcus i jo acabo de donar compte aquí, haurem de passar per la llista de la llista nombre de vegades. Així que passant per una mica de longitud n n nombre de vegades és, de fet, n al quadrat. Així que aquest és el nostre pseudocodi. Això es veu molt bé. Algú té alguna pregunta sobre el pseudocodi? Perquè en realitat ordenació per selecció ha de Probablement vingui un a un, el codi de pseudocodi. Així que qualsevol pregunta sobre la lògica del pseudocodi? Si us plau, pregunteu ara. Selecció classe - mentre que la llista està fora d'ordre, anirem a través d'ell i trobar el més petit cada vegada i el va posar al davant. Així, mentre que la llista està fora de servei, pot algú em doni aquesta línia de codi que No m'ha donat una línia de codi, però, si us plau? Sona com un què? ESTUDIANT: És un bucle for. JASON Hirshhorn: Sona Vols un bucle for. Bé, em pot donar el bucle? Forma - ESTUDIANT: i és igual a 0. JASON Hirshhorn: io - el que ens estem perdent? Què passa aquí? ESTUDIANT: Int JASON Hirshhorn: Exactament. (Int i = 0; - ESTUDIANT: i