[Powered by Google Translate] [Article 3] [Menys Còmode] [Nate Hardison] [Harvard University] [Aquesta és CS50.] [CS50.TV] Molt bé, anem a començar. Benvinguts a la Setmana 4 de CS50. Si vostès obren un navegador web i obrir pset 3, Scramble amb CS50, començarem a anar a través de la secció de preguntes allí. Igual que la setmana passada, estarem treballant en CS50 Spaces, si també va a tirar cap amunt, així que, i si segueixes endavant i visiti aquest enllaç que tinc aquí a la part superior. És hora de començar. Tenim el nostre programa hi poc aquí. Res boig. Una de les primeres coses que vull fer amb vostès avui és repassar algunes solucions Set per al problema 1, el tipus d'exemple solucions, només perquè pugui tenir una idea de quin tipus de personal està escrivint codi, Quin tipus d'estudiants estan escrivint altres codis, i fer que vostè prengui una mirada en ella, perquè sé que és estrany al moment d'enviar la solució a un conjunt de problemes i obtenir comentaris en la seva pròpia versió, però de vegades és útil veure com altres persones ho van fer, especialment els que estan ben buscant. En la seva major part, jo estava molt impressionat amb les solucions que vostès produeixen. Encara no he començat a buscar en els seus 2s conjunt de problemes, però si ets com la primera, no significa res més que coses bones. Si ens fixem en els meus revisions, anem a començar fins al fons en Revisió 1, i anem a fer una ullada ràpida a una solució de Mario. Si tira d'això, els programes que presentarem són els correctes. No hi havia problemes amb la correcció d'aquests problemes, sinó més aviat, volem parlar una mica sobre els problemes de disseny diferents que s'utilitzen aquí. Una de les coses que era interessant sobre la solució és que utilitza aquest nou constructe anomenat lliures definir, de vegades també es refereix com un hash definir. Permetin-me fer un zoom sobre ella aquí. A # define li permet donar nom a aquests números en el seu programa. En aquest cas, l'alçada màxima d'una piràmide en Mario tenia 23 anys i en lloc de posar 23 en el meu codi volem dir que tan dur codi 23 - això dóna lloc la MAX_HEIGHT nom a aquest nombre, de manera que aquí al meu do-while en realitat es pot fer referència a MAX_HEIGHT en lloc de posar el número 23 polz [Estudiant] Quina és l'avantatge de fer això? Aquesta és una gran pregunta. Una d'elles és la lectura. Un avantatge d'utilitzar aquest # defineix és la llegibilitat. Quan estic llegint el codi, puc veure el que està passant. Puc veure en aquesta condició que aquí estem provant per l'altura és <0, el que podríem haver definit també ser d'una alçada mínima o una alçada min. L'altre avantatge és que es pot llegir la resta de la línia per veure que també estem comprovant per assegurar-se que l'alçada no és més gran que l'altura màxima, perquè seguirem mentre que l'altura és major que l'altura màx. L'altre avantatge és, si puc ampliar una mica aquí- si executo aquest programa i ho executo, per exemple, amb un 23 en aquest moment, que mostra tots 23 files així com així. Però dir que era hora de canviar l'alçada màxima, i ara vol limitar l'alçada màxima de les piràmides ser només dir-man, que era modern. # Include, # defineix MAX_HEIGHT, i diguem que volia posar igual a 10. Ara, en aquest punt, tot el que havia de fer era canviar-lo en aquesta ubicació. Em pot tornar a compilar el codi, i ara si que intento escriure en el 12, va a preguntar de nou. En aquest cas, només estem utilitzant MAX_HEIGHT vegada. No és tan gran d'una molèstia d'anar a i canviar-lo en el bucle mentre que si és necessari. No obstant això, en els programes en què s'està fent referència al mateix nombre màgic una i altra vegada, aquest mecanisme és # defineix molt útil perquè vostè acaba de canviar un cop a la part superior de l'arxiu, és en general en el qual els va posar- i el canvi es filtra per la resta de l'arxiu. Altres coses que volia destacar en aquesta tasca que em va semblar es veia molt bé, un va ser el nomenament de les variables. Aquí es pot apreciar que tenim les variables senceres trucades fila i es diu altura. Espais, hashes, ajuda a fer que el codi una mica més llegible, fa que sigui una mica més comprensible el que realment està passant. Això està en contrast amb l'ús, per exemple, lletres a l'atzar o simplement gobbledygook complet. Una última cosa vaig a assenyalar és que en els bucles for, sovint aquestes variables Iterador, aquests comptadors que s'utilitzen en la seva bucles for, és estàndard i convencional per començar amb i i j i k I passant d'allí si necessites més variables, i això és només una convenció. Hi ha un munt de convencions. Depèn del llenguatge de programació que està utilitzant. Però en C, en general comencen amb i. No té sentit utilitzar, per exemple, A o B depenent de la situació. Això és tot per aquesta. Si ara aixecar Revisió 2, veurà un altre Mario, i aquest és similar a la d'un altre tipus que acabem de veure, però sí una cosa una mica freda. Si ens fixem en aquesta secció aquí a l'interior de l'interior de bucle, que estan utilitzant una sintaxi boig buscant aquí just en aquesta línia. Això es diu un operador ternari. És una sentència if else condensada en una sola línia. La condició és aquesta part dins de parèntesis. És equivalent a dir si j > Sam. Sam. Igual que Sam va dir que el procés de recerca lineal que serà molt lent, i en el seu lloc amb la recerca binària, la manera com funciona és que cada vegada que anem a través d'una iteració del nostre algorisme de recerca, anem a dividir la llista en dues, essencialment, en dues llistes més petites. I després, en la següent iteració del bucle, ho anem a dividir de nou en altres llistes més petites. Com es pot veure, el problema es fa cada vegada més petit i més petit perquè guardem 1/2 descarti de la llista cada vegada. Com funciona això de descart? Així com un recordatori, el que farem si ens quedem un ordinador i estàvem, per exemple, la recerca per al número 5 a la llista és que es tria un nombre al centre. Al mig d'aquesta llista, ja que hi ha 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 números, ens agradaria escollir el nombre, ja sigui en la posició 4 o en la 5 ª posició, i que en diria el mitjà de la nostra llista. Trieu el nombre enmig. Llavors, igual que Sam va dir, anem a provar per veure si aquest nombre és igual al número que volem aconseguir o el nostre número desitjat. Si és igual, llavors l'hem trobat. Nosaltres vam guanyar. Si no és igual, llavors hi ha un parell de casos. Els dos casos són ja sigui el nombre ha de ser més gran que el nombre que està mirant, o és menor que. Si és major, ens movem cap a la dreta. I si és menys, ens movem cap a l'esquerra. I després repetir el procés de nou ja sigui en la meitat dreta o la meitat esquerra de la llista. El primer problema a la secció d'avui és esbrinar la manera com pot començar a expressar això en codi C. Tenim el pseudocodi aquí. El que anem a començar a fer és que em vaig a aixecar un nou espai, guardar aquesta revisió perquè tinguem aquestes notes per més endavant, anem a esborrar tot això, i després copiar i enganxar des del conjunt de problemes aquesta informació en els nostres espais, i espero que això no es trenca. Perfecte. Si vostès tot això, copiar i enganxar aquest codi en el nou espai, en un en blanc. Tractarem de Daniel. Si Donat aquest programa, funciona? >> No Què diu? Diu el control arriba al final de la no funció void. Sí, així que tractaré d'executar. Han vist això abans? Sap vostè el que això significa? Bé, anem a analitzar això una mica. És com dir a file.c en la línia 9, columna 1 tenim un error, com vostè ha dit, i es diu que està derivada de l'advertència d'error i l'advertència de tipus de retorn. Sembla que alguna cosa està passant amb el tipus de canvi, la qual cosa té sentit. Tenim una funció no nul · la, el que significa que tenim una funció que no tornarà buida. Una funció de buit és el que són aquestes: void foo (), i és nul perquè el tipus de retorn és nul, el que significa que si tinguéssim alguna cosa aquí com return 1, obtindríem un error del compilador per això. Però tenim una funció no nul · la. La nostra funció no nul · la en aquest cas és la nostra funció de recerca perquè té un tipus de retorn de bool. Quan es diu que el control arriba al final d'una funció no nul · la, és perquè la recerca no té una sentència return. No està tornant una mica de tipus bool. Podem arreglar això, i el que crec que vostès recerca ha de retornar per defecte? Quin ha de ser el valor de retorn per defecte de la recerca? Perquè això és el que podem fer al final. Charlotte, té vostè alguna-? ¿Vertader o fals? >> Veritable o fals. Quin? Fals. No. Fals? Anem a intentar-ho. Per què dius return false? Això és una gran intuïció. [Charlotte] No ho sé. Anem a tornar falsa en aquest cas, perquè aquesta serà la nostra defecte Si per alguna raó la llista és buida o l'agulla que estem buscant no existeix. Després, al final, si no tornar true anteriorment en aquesta funció, sempre sabem que aquesta funció dirà No, no és a la matriu. No és al paller. Ara bé, si compilar i executar, em deixa guardar això perquè puguem estirar-lo cap amunt. Ara bé, si compilar i executar el nostre programa, que es basa. Vam aconseguir el nostre sistema poc. Si ho cop 4-uh-oh. No imprimiu res. Sembla que tot va acabar bé. Hem d'omplir aquest polz Parlem sobre l'algorisme en pseudocodi una mica enrere. Anem a veure, excepte això, i vaig a tirar d'aquest algorisme de nou. Anem a colpejar a aquest tipus. Nope. Aquí està. Com podem fer això? Quina seria una bona estratègia per iniciar la marxa aquest codi? Has de triar un número al centre. Com escollir un número al mig d'una matriu? Alguna suggeriment? [Estudiant] Strlen dividit per 2. Strlen dividit per 2. Això és un gran un. Strlen treballa amb tipus especials de matrius. Quin tipus d'arranjaments? Arranjaments de cordes, conjunts de caràcters. És el mateix tipus de concepte que volem aplicar, però no tenim suport per strlen perquè no tenim una gran varietat de personatges. Tenim una matriu d'enters. Però, què strlen aconseguir per a nosaltres? Sap el que li pot passar a nosaltres? [Estudiant] Strlen ens porta a la longitud. Exactament, ens porta a la longitud. Strlen obté la longitud de la matriu per a nosaltres. Com aconseguim que en el nostre programa de recerca binària? Com obtenir la longitud d'un array? [Estudiant] Strlen? Vostè pot obtenir la longitud d'una matriu de cadenes amb el format correcte C strlen. El problema, però, és que no tenim una matriu de cadenes. Si mirem cap enrere en aquest codi, tenim aquesta matriu d'enters. Com sabem quant temps és? [Estudiant] Hi ha un equivalent de punt final, com l int o alguna cosa així? Resulta que hi ha en realitat no ho és, i així, en certa manera, és aquesta una d'aquestes coses que és bo saber sobre C, que no hi ha manera d'obtenir la longitud d'una matriu si tot el que et donen és la matriu. La raó que funciona amb cadenes, la raó strlen obres, és perquè si una cadena té el format correcte, que tindrà aquest especial caràcter \ 0 al final. També es pot imaginar si vostè té una cadena amb format incorrecte i no hi ha caràcter \ 0 existeix, llavors la cosa no funciona. [Estudiant] Es pot afegir el \ 0? Podríem en aquest cas. Podríem afegir algun tipus de \ 0 o algun tipus de significar personatge i després utilitzar això. Però això no funcionarà bastant perquè el 0 \ és per a un tipus char, i aquí tenim INT. L'altra cosa és que si haguéssim de utilitzar un valor especial com -1 per marcar el final d'una matriu llavors mai podria emmagatzemar un -1 en els nostres arrays sencers. Estaríem atrapats. Resulta que l'única manera d'aconseguir la longitud d'una matriu en C és en realitat el record quan el va crear i després passar per aquí amb la matriu de manera que cada vegada que tinc una funció que realitzarà algun treball en una matriu d'enters o flotadors o dobles, o el que sigui, També he de donar la funció de la longitud de la matriu, i això és exactament el que hem fet aquí a la funció de cerca. Si ens fixem, el que hem fet quan passem en la nostra àmplia aquí, també passem a la longitud, la mida. El que passa és que hem anomenat aquí aquesta variable, aquest paràmetre o argument. Això es coneix com a llista d'arguments d'una funció o una llista de paràmetres, i aquests també es diuen arguments o paràmetres. La gent utilitza termes diferents en moments diferents. Jo de vegades em intercanviar. El que passa és que aquesta variable aquí és un nom semblant a aquest # defineix aquí. Però no són la mateixa cosa. La capitalització és important. Si ens fixem en el que passa aquí, declarem nostra matriu int, que hem anomenat nombres. Ho hem donat el nostre mida, el que correspon al nostre # defineix a la part superior. Serà 8. I llavors va ser quan ens cridi a la nostra funció de recerca de sota, passem al número que voleu cercar, que hem sol · liciti, obtingut de l'usuari. Passem de la matriu, aquests nombres, i llavors també ha de passar en la grandària de la matriu, i després el valor de mida 8 s'emmagatzema o passat a aquest nombre enter mida variable anomenada. Tenim la mida de la matriu. Ara bé, si ens remuntem al que estàvem parlant abans, Crec Missy va portar a col · lació el punt que el que havíem de fer és aconseguir la longitud de la matriu i el divideix per 2, i que ens donarà el punt mitjà. Anem a veure. Puc tenir algú escriure això i ho guarda en el seu espai? Què hi ha de Leila? Puc haver d'escriure això en? Escriviu la primera línia on es pren la longitud de la matriu i obtenir el punt mig i emmagatzemar-lo en una variable nova. Et vaig a donar un parell de segons. Estàs llest? [Estudiant inaudible] És clar, podria haver es calcula el punt mitjà de la matriu paller dins la funció de cerca utilitzant la longitud de la matriu haystack, que és la variable de mida? No hi ha res complicat aquí. [Leila] Just mida / 2 i només I guardar, i premi el botó Desa per dalt aquí a la part superior, i anem a estirar-lo cap amunt. Perfecte. Aquí anem. Awesome. Com és, aquesta compilació? [Leila] No, ha de ser més alt. [Nate] Sí, i què hem de fer? [Leila] Com punt mitjà int o alguna cosa així. Awesome. Sí, farem això, int = punt mida mitjana. ¿Aquesta compilació? Anem a esborrar aquest comentari i treure'l del camí. El que no es compilarà sobre això? No estem fent res amb número sencer, així que hem d'imprimir o alguna cosa per l'estil. Sí, exactament. Tindrem una variable no utilitzada. Quina altra cosa no funcionarà això? Crec que va dir alguna cosa, Sam. Punt i coma. Sí, m'estic perdent els punts i comes. Serà una cosa constant durant tot el transcurs del termini. L'última cosa que faré és que vaig a posar una mica d'espai en blanc a banda i banda d'aquest operador aquí, ja que és típicament com ho fem d'acord amb la nostra guia d'estil. Tenim el punt mitjà de la nostra matriu. Ara bé, si recordem al nostre algorisme, el que va ser el segon pas que havíem de fer un cop tinguem el punt mig? [Estudiant] Si és major [inaudible]. Sí, per la qual cosa hem de fer algun tipus de comparació, i què estem comparant aquí? Vas dir que si és més gran que. Què hi ha en aquesta frase es refereix? El nombre que apareix, si és més gran que el punt mig, i després pujar a la matriu? Exactament el que el nombre que apareix quan nosaltres- L'agulla, de manera que estem comparant a l'agulla, i què estem comparant contra l'agulla? Com que l'agulla és el que estem buscant. Ho estem comparant per arribar al punt mitjà. Però té sentit per verificar si l'agulla del punt mitjà =? Això té sentit? Algú no està d'acord? Anem a donar-li una oportunitat, si (== agulla punt mitjà). [Estudiant] printf No el va trobar. [Nate] printf ("L'hem trobat \ n"); En cas contrari-Vaig a començar a fer alguna cosa diferent aquí. Vaig a començar a posar claus al voltant de si les declaracions de tot el temps perquè si afegim més coses, llavors no obtenim els compiladors. Sí, Sam. Tens un punt. El problema és que el punt mig representa una posició en la matriu, però vostè pot aconseguir que representen el valor en aquesta posició de la matriu. Això és un gran punt. Tots sentir el que va dir Sam? Va dir que el punt mitjà com és representa només una posició en la matriu, però no és l'element real en la matriu. Si es pensa en el codi com està escrit en aquest moment, si ens fixem en aquesta sèrie aquí baix, que compta amb 8 elements en ella, Quin és el valor del punt mitjà estarà en aquesta funció? [Estudiant] 4. [Nate] 4. Si busquem el número 4 - i que només pot executar aquest codi i posar una cara trista aquí perquè no trobar-lo si executa aquest codi com està ara, pujar-lo, edifici, deixa desplaçar-se cap avall, i si busquem el número 4, que el trobem, però no arribem a aquest printf si. Una de les raons és que no ens tornarà true, però en realitat trobar el número 4? I Sam diu no. Què trobem? Realment trobat el punt mig, que si ens fixem en la matriu aquí baix, que serà l'element en l'índex 4 que estem veient, que té 23 anys. Com podem realment aconseguir aquest element en el punt mitjà i no només el propi punt mitjà? [Estudiant] Ens agradaria introduir caràcters o alguna cosa així? Què faria això, només per curiositat? Ens pots explicar una mica més? Cal transformar la posició en el nombre, pel que he de fer alguna connexió-Crec que és char, però no va poder ser. Sí, això és un bon punt. Hem estat fent un munt de llocs d'aquesta conversió en caràcters, aquests personatges, en els butlletins d'exercicis dues primeres. Resulta que aquí, això és gairebé similar a l'accés a la i-èsima caràcter dins d'una cadena, si això té sentit. Aquí volem accedir a l'element del punt mitjà. Com podem fer això? Kevin, ¿té vostè algun suggeriment de com podem fer això? Vostè podria fer paller, claudàtor obert, medi, tancat suport. Pots escriure això per a nosaltres? Guardi'l a aquí, i tirarem això. Estem pensant en aquesta línia 9, i ens estem adonant que no volem comparar l'agulla cap al punt mig, però en canvi, volem comparar l'agulla l'element en el punt mitjà lloc dins la nostra gamma paller. Cool. Aquí anem. Sí, això es veu molt bé, si (== paller agulla [punt mig]). El trobem. Ara bé, si ens trobem de nou el codi-nosaltres una mica de bits compila, executa, i ara si ens fixem per a 4, no el troba perquè ara estem aconseguint realment el número 23. Estem rebent el valor de 23, i això és el que estem comparant al nostre agulla. Però això és bo. Això és un pas en la direcció correcta. Això és el que estem tractant de fer. No estem tractant de comparar l'agulla contra les posicions de la matriu sinó més aviat contra els elements reals en la matriu. Si mirem cap enrere de nou ara en el següent pas en el nostre algorisme, Quin és el següent pas? Leila ja ho va esmentar breument. [Estudiant] Reviseu per veure si és més o menys que i després decidir en quina direcció moure. [Nate] Sí, com ho faríem? Es pot posar en un cert I'Ll d'estalvi d'aquesta revisió, i després, si poses en algunes línies que faran això. Sí, Charlotte. >> Tinc una pregunta. No hauria de ser el punt mitjà - 1, perquè el primer és està indexat 0, així que si posem 4, això no és realment el personatge que estàs buscant? Sí, i l'altre problema que és- això és una gran captura, perquè el que acabarà passant possiblement si estem en moviment i no sempre ajustar inicialment? Suposo que el que podria acabar fent és tractar d'accedir a l'element en la posició 8 de la matriu, que en aquest cas no existeix. Estarem disposats a fer algun tipus de comptabilitat pel fet de que tenim una indexació zero. [Charlotte] Ho sento, em referia punt mitjà - 1 en els claudàtors. Podem fer això. Tornarem a aquest tema en una mica. Quan vam començar a arribar al bucle actual, que és quan realment va a veure això entren en joc. De moment, no podem fer això, però vostè és totalment correcte. Que la indexació de zero tindrà un efecte que cal explicar. Anem a veure. Com és la més gran que i menor que-? [Estudiant] tinc com fer el més gran que i menor que part. Jo no estava segur del que voleu imprimir si vostè troba que és menys de la meitat paller o superior. Aquí puc salvar el que he- [Nate] Sí, si guarda el que tens, i anem a estirar-lo cap amunt. Aquí anem. [Estudiant] I vaig posar signes d'interrogació per al que jo no sabia. [Nate] Això es veu molt bé. Aquí tenim signes d'interrogació perquè encara no sabem el que farem encara. Què volem fer-oops, tenim unes claus tots covards de nosaltres. Anem a corregir aquests aparells. Aquí anem. I així, què és el que volem fer, d'acord al nostre algorisme, si no trobem l'agulla? Diguem, en el cas que l'agulla és menys del que estem veient. Kevin. Cerca només a la meitat esquerra. Bé, llavors anem a posar un comentari aquí que diu "mira la meitat esquerra". I si l'agulla és més gran que la pallissa al punt mig, què és el que volem fer? [Estudiant] Llavors ens fixem en la meitat dreta. Mira la meitat dreta, "mira a mitges." No està malament. Bé, en aquest punt, les coses es veuen bastant bé. El problema amb el codi com està escrit és el que? [Estudiant] No té punts finals de les dues meitats. Cert, no tenim punts finals per les dues meitats. Així mateix, només es passarà per això una vegada. Només veurem un punt mitjà. O bé l'element hi és, o no ho és. Per completar això, haurem de fer algun tipus de repetició. Hem de seguir repetint fins que ens trobem que o bé l'element hi és perquè hem reduït i finalment el va trobar, o no hi és perquè hem buscat a través de totes les coses en les meitats corresponents de la matriu i es va trobar que no hi ha res a allà. Cada vegada que tenim aquesta repetició passant, què utilitzarem? [Estudiant] Un bucle. Una espècie de bucle. Sí [Estudiant] Podem fer un bucle do-while i en tinguin a fer això i després, mentre l'agulla no és igual, estic segur d'on anava amb això. Però una cosa així com fer que el temps que no és igual al valor que l'entrada de l'usuari. Sí, així que anem a veure, com podria escriure? Vostè ha dit que anem a utilitzar un bucle do-while. D'on ve el començament fer? [Estudiant] Immediatament després de la talla / 2. [Nate] Bé, i què farem? Anem a omplir l'estona. Què farem? [Estudiant] No volem fer totes les coses que tenim a la part de si? [Nate] És tot això, genial. Copiar i enganxar. Oh, home. A veure si això funciona, si podem fitxa sobre això. Bella. Molt bé, i ens estalviem això perquè vostès ho tenen. Molt bé, i ho farem mentre- Quina va ser la condició mentre que buscaves? [Estudiant] Mentre que l'agulla no és igual, així com el signe d'exclamació. Però no estic segur del que és encara. [Nate] Sí, aquesta és una manera de fer-ho. Sam, tens algun comentari? [Sam] vaig recordar quan vaig veure els vídeos, Vaig prendre una captura de pantalla d'una de les semblant a quan vam fer el pseudocodi per a això, hi ha una certa relació entre MAX i MIN. Crec que va ser alguna cosa així com si el màxim és sempre menor que min. Ho tinc. [Sam] O com si Max no és menys minuts o alguna cosa així, perquè això significaria que ha buscat en tot. Sí, i què fa que soni com a màxim i mínim es refereix? [Sam] Valors sencers-que els que canviaran respecte al lloc on posem el punt mitjà. Exactament. [Sam] En aquest moment, serà [inaudible] calcular el màxim i el mínim. Punt mitjà és aquesta idea màx i min. Té sentit per a la gent? Si haguéssim de començar a veure com farem aquesta iteració, tens tota la raó que volem utilitzar algun tipus de do-while. Però suposo que si tenim en compte el que està passant en el lloc d'aquesta matriu i el que està passant en realitat-Vaig a escriure per aquí- en la iteració molt primer de recerca binària, tenim- Vaig a utilitzar B i E per indicar el començament. I després, al final de la nostra matriu. Sabem que l'inici és a les 4 per aquí, i sabem que la fi està a 108. Diguem que està buscant el número 15. La primera vegada que fem això, com hem vist anteriorment, el punt mitjà és o serà de 16 o 23 depenent de com calcular les coses. Des uniformement divisòria en el medi ens donaria aquest espai entre 16 i 23, no es pot dividir uniformement o dividir i arribar a un punt mitjà veritable. Veurem als 16. Ens adonarem "Hey, 16> 15 que estem buscant". Per buscar llavors en la meitat esquerra de la matriu el que acabarem fent està rebutjant aquesta porció superior sencer i dir: "Bé, ara el nostre punt final estarà aquí." La següent iteració del nostre bucle, ara estem mirant aquest acord, efectivament haver descartat aquesta part perquè ara si ens està prenent el punt mitjà de la diferència entre el principi i la fi, trobem el nostre punt mitjà a ser 8, que després pot provar 8 per veure on es troba en relació amb el nombre que busquem, 15, trobem que 15 és major, així que hem d'anar a la part dreta de la llista, que coneixem perquè som éssers humans, i ho podem veure. Sabem que la part dreta estarà on el trobem, però l'equip no ho sap, així que el que vaig a fer és que en realitat va a han aquesta puja, i ara el principi i la fi són el mateix lloc, de manera que el punt mitjà es converteix en l'únic número a la llista en aquest punt, que té 15 anys, i ho hem trobat. Això donar una mica de llum sobre on aquesta tota màx i min notació va, fer el seguiment dels punts finals de la matriu per tal d'esbrinar com reduir les coses? Què passaria si això no fos igual al 15 ara? Què passa si buscàvem 15 i, en canvi, aquest nombre també van ser 16? Dèiem: "Oh, és major. Volem anar de nou a l'esquerra. " I ens agradaria traslladar la nostra direcció cap a la dreta, moment en què tenim un punt final que seria contradictòria. No seria capaç de cercar qualsevol elements més perquè ara tenim el nostre punt final i el nostre punt de partida, nostre màx i min nostre, ara es va bolcar. Busquem a través de tota la matriu. No podem trobar res. Aquest és el punt en què ens agradaria dir: "Bé, anem a deixar aquest algorisme. No hem trobat res. Sabem que no és aquí. " Com va? [Estudiant] Com funciona exactament l'ordinador canviar el final? Com funciona el final abans d'acabar el principi? L'extrem acaba abans del començament a causa de les matemàtiques que farem cada vegada que fem això. La forma de canviar és que si ens fixem en la primera vegada que fem aquest canvi on tenim el començament i el final 4 a la tot el camí cap avall en 108 i el nostre punt mitjà, per exemple, en 16 - Vaig a tornar a zero el 15-si estem buscant als 15, sabíem que el que vam fer quan ens registrem el 16 i va veure que era major i volia descartar tota la part dreta de la llista, vam veure que el que volíem fer és moure aquest missatge aquí. Efectivament, el correu ens van canviar a un abans del punt mitjà. De la mateixa manera, quan vam fer aquesta iteració de l'algorisme i el punt mitjà era menys 8, trobem que 8 <15, així que volíem que ens canviessin la b 1 passat el punt mitjà. Ara, el principi i el final són tots dos junts en aquest 15. Si haguéssim estat succeint a la recerca d'algun altre valor, no 15, o si aquest havia estat 15 en comptes de 16, hauríem trobat que el correu que voleu moure un abans del punt mitjà. Ara l'e estaria allà voltejat menys de la b. Anem a veure com podem realment arribar a codificar aquest algorisme. Sabem que volem tenir aquest càlcul del punt mitjà. Sabem també que volem per seguir el principi i el final de la matriu de la nostra gamma actual per poder entendre on aquesta meitat esquerra de la llista és i on la meitat dreta de la llista és. Fem el que sigui amb inici i fi, o podem anomenar min i max. Vaig a utilitzar començar i acabar aquest temps. Quan vam començar, si mirem cap enrere en el nostre exemple aquí baix, nostre principi es va establir al principi de la matriu, com una cosa natural. Què índex és això? El nostre s'ha de començar? Daniel. [Daniel] Haystack [0]. [Nate] Sí, així que vam poder igual a paller [0]. El problema, però, és que aquesta no ens dóna la posició del primer element. Això ens dóna l'índex del primer element o el valor real en què la primera posició. [Estudiant] Que es converteixi al 0,20? [Nate] Què farà és, bé, no farà cap conversió. El que farà és que emmagatzemarà un 4 en començar, i llavors serà difícil fer comparacions amb començar perquè begin durà a terme el valor de 4, que és el principi de la nostra matriu, però volem fer un seguiment dels índexs de la matriu en contraposició als valors. En realitat, farem servir un 0, per l'estil. Per al final de la matriu-Charlotte va portar això una mica abans. Aquí és on anem a prendre en compte la indexació zero. Charlotte, quin és el final de la matriu? Quin és l'índex de l'extrem? [Charlotte] Mida - 1. Sí, i ¿quina talla d'usar? ¿Hem d'utilitzar la mida de capital o de mida minúscul? Capital mida. En aquest cas, podríem utilitzar la mida de capital. Si volem que aquesta funció estigui portàtil i utilitzar aquesta funció en altres programes, de fet podem utilitzar la mida minúscules. És bo també. Però Charlotte és totalment correcte que volem tenir una mida - 1. En aquest punt [Estudiant] Com és que vostè pot utilitzar la mida majúscules? Com és que podem utilitzar majúscules mida? Resulta que aquests # defineix són molt, sota el capó, un text com buscar i reemplaçar, si això té sentit. Quan es compila el codi, la fase de preprocessament del compilador passa per l'arxiu, i busca per tot arreu que vostè ha escrit mida del capital, i reemplaça el text literalment, amb un 8, així com així. En aquest sentit, és molt diferent d'una variable. No ocupa espai a la memòria. És un truc Substitueix text simple. En aquest cas, utilitzarem la mida. Des d'aquí vull fer una mena de repetició, i estem en el camí correcte amb el nostre do-while. Volem fer alguna cosa fins que una condició no es compleix ja, i com hem vist anteriorment, vam veure que aquesta condició era en veritat que no volem que al final a ser menor que el començar. Aquesta és la nostra condició de parada. Si això passa, volem aturar i declarar com, "Hey, no hem trobat res". Per expressar això, es vol utilitzar algun tipus de bucle. En aquest cas, seria un bucle do-while, un bucle, un bucle while? Tenim un bucle do-while aquí. És que els agradi aquest enfocament? Creus que hauríem d'intentar un enfocament diferent? Kevin, alguna idea? Podríem tenir un bucle while perquè sabem màxim seria més gran que min en les maneres d'arrencada. Sí, així que no hi ha inicialització que ha de succeir. Els bucles do-while són grans quan s'ha de inicialitzar alguna cosa abans d'aquesta prova, mentre que aquí sabem que no anem a mantenir reinicialitzar tots dos comencen i acaben cada ronda del bucle. Sabem que volem iniciar, a continuació, comprovar la nostra condició. En aquest cas, en realitat anirà amb un bucle while simple. Resulta que do-while s'utilitzen amb poca freqüència. Un munt de llocs ni tan sols ensenyen què bucles while. Són bons per al maneig de dades de l'usuari, pel que hem vist a molts d'ells fins ara. Però normal i bucles while són molt més comuns. Resulta que aquesta condició com escrit realment no ens fan molt bé, i per què és això? Ho sento, no sé el seu nom. Sóc Jerry. >> Com? És B-O-R-O-I. Oh, està bé. Jo no et veig a la meva llista. Oh, és perquè-oh, això té sentit. Té una idea de per què aquest bucle while no funcioni com es pretén, tal com està escrita amb la condició? [Jerry] Vols dir com vol que totes les coses després que al-? Sí, per la qual cosa hi ha una. Potser haguem de posar totes aquestes coses en el bucle while, que és totalment cert. L'altra cosa que és una mica més problemàtic, però, és que aquesta condició no funciona. [Estudiant] Ha de donar la volta. Bé, pel que aquesta condició no sempre serà així inicialment la manera com parlem d'això. Volem fer alguna cosa fins > Plus començar? [Estudiant] al final. Perquè es calcula únicament la meitat de la longitud. Cal afegir l'inici. [Nate] Què faria aquest càlcul per a nosaltres? Si pensem en la final d'aquesta primera iteració del bucle, final serà en l'índex de posició 7. Comenceu a la posició 0. Recorda que estem buscant, ja sigui per posició 3 o la posició 4. Si ens fixem en aquesta matemàtica, només per fer-ho una mica més tangible, posar alguns números aquí, tenim 7, 0, així 7 a 0, i després 2 / és 3 a la divisió entera, és a dir. Llavors hem d'afegir després de tornada a la nostra començar? No ho fem en aquest cas. A la primera iteració, estarà bé perquè begin és 0. Però a mesura que avancem, fem realment tot només té final - comença / 2. Hi ha un truc aquí un altre, i això és a dir, una de precedència. [Estudiant] Necessitem parèntesi? [Nate] Exactament, i això és perquè si no posem els parèntesis, llavors aquesta línia s'interpretaran en lloc com (final) - (iniciar / 2), que definitivament no volen. Compte amb les regles de precedència. [Estudiant] Per què no eliminar-la + començar? Per què no eliminar-la + començar? [Estudiant] Per què no és això? Per què seria +? Crec que tens raó. [Estudiant] Perquè és normal? [Nate] + Fi començar, tens tota la raó. Wow, estic totalment ficat la pota. Tens raó. Si estiguéssim fent el signe menys, ens agradaria afegir el començar cap a dins En aquest cas, és molt just que volem prendre la mitjana dels dos, de manera que les vull afegir, en lloc de restar-. [Estudiant] També funcionaria si hagués acabat - begin / 2 + de començar. Ho faria si ho fem-Crec que sí. Per exemple, si estiguéssim mirant a començar, i ho va canviar per aquí als 15. Ara comenci a la posició 2. End està en la posició 7. Si els restem, obtenim 5. Divideixi això per 2, obtenim 2. I després hi afegim 2 de nou, i que ens porta a la quarta posició, que és aquí, que és el punt mitjà. [Estudiant] Hem de tenir cura d'embolicar? En quin sentit hem de tenir cura d'embolicar? Si la suma o la diferència entre depenent de com ho fem no és un nombre parell. A continuació, l'equip es confon si quan és 2,5; Com es mou cap a l'esquerra o cap a la dreta per determinar quin és el punt mig? Ho tinc. Resulta que la divisió entera, no sempre obtenir aquests nombres en coma flotant. Mai obtenir el decimal. Està totalment descartat. Si vostè té un ordinador dividir dues variables int, i un és 7, i l'altre és 2, vostè no rebrà 3,5 com a resultat. S'obtindrà 3. La resta es descarta, pel que és efectivament l'arrodoniment no una ronda, sinó més aviat un pis, si vostès estan familiaritzats amb el de les matemàtiques, on descartar completament el decimal, i pel que està essencialment truncar la baixa fins a la posició general, al nombre enter més pròxim. [Estudiant] Però llavors això és un problema perquè si vostè té un conjunt de 7 elements a continuació, que automàticament pren l'element tercer del punt mig en lloc de la 4 ª. Què fem amb això? És problemàtic perquè si tinguéssim una matriu de 7, ho tornaria a escollir el tercer en lloc de la 4 ª. Podria explicar una mica més? [Estudiant] Perquè si vostè té 7 elements llavors el 4 º element seria el punt mig, no? Recordi que el seu comentari sobre ser zero indexat, però. [Estudiant] Sí, pel que en la posició 3. Aquest seria el punt mitjà. Si. Oh, està bé. Ja veig el que vols dir. És una mica estrany, ja que ens acostumem a aquesta noció de desfer-se de decimals. Això és un gran punt. Acabarem amb això. Hem calculat nostre punt mitjà. Estem provant per veure si la nostra agulla és igual al valor mitjà. Estem impressió que el trobem, però en realitat, què és el que volem fer en aquesta situació? Hem trobat, pel que volem deixar que la persona que truca sap que l'hem trobat. Tenim una funció que és una funció amb tipus booleà. La forma d'indicar a la persona que truca de la nostra funció que estem preparats per anar Se'ns diu, "Hey, això és cert." Com fem això, Kevin? Ets assentir amb el cap. >> [Kevin] Afegir return true. [Nate] Exactament, retorna true. Ara, si no és igual, com veiem la meitat esquerra? Alguna idea? Stella, alguna idea? Cal establir una nova posició per al final. Si. Així que hem de fer càrrec de la meitat - el final. Gran. Hem d'establir una nova posició per a la final per mirar la meitat esquerra. Això va ser el que parlem abans, on Segueixo tornant a aquest exemple. Aquest és el començament, i després he de al final tot el camí fins aquí. Un cop més, si estem buscant a 15, i el nostre punt mitjà és als 16 anys, i ens adonem, "Oops, 16 és major. Volem passar a la meitat esquerra ". A continuació, es traslladaria al final dels 15, i ho fem mitjançant l'adopció d'una distància des del punt mig i establint que, com el nostre nou final. De la mateixa manera, si volem mirar la meitat dreta, com ho fem? Té una idea? [Estudiant] Vostè acaba d'establir comencen a punt mitjà + 1. [Nate] Great. I ara, en el cas que no trobem res, ha d'obtenir cures per a nosaltres? Daniel, ¿això et atesos per nosaltres? [Daniel] No [Nate] Si ho fem a través de tota la matriu i no trobem res, on seria aquest ésser atesos, o hem de cuidar d'ell? [Daniel] La condició de temps. [Nate] Sí, la condició de temps, exactament. Es farà càrrec d'anar a través de tota la matriu si no trobem res. Aquest bucle while acabarà. Mai he trobat amb aquesta condició, i podem tornar false. També pot deixar aquest cas aquí d'aquesta perquè si aquesta afirmació és vertadera si, i la nostra funció retornarà, així que bàsicament va a avortar aquesta funció en aquest moment quan tornem veritat. Però què passa amb aquesta estructura aquí? Això funciona del tot, o hi ha algun error lògic aquí? Hi ha alguna falla lògica en allà, amb la manera com està establert. Què podria ser? [Estudiant] Per què necessita el - i + 1 s? Que estableix la nostra àmplia per ser el nostre nou mitjà a l'esquerra i la meitat dreta. [Estudiant] Però per què no podria fer-ho sense el - i + 1s 1s? [Nate] Podríem igual a la meitat? Quin podria ser problemàtic en això? [Estudiant] Suposo que és ineficient perquè vostè està comprovant un valor que ja s'ha comprovat. [Nate] Exactament, així que Sam és totalment correcte. Establint el final i l'inici igual al punt mitjà en lloc de - 1 i + 1 reflexivament, en algun moment en el futur anem a acabar fent el registre de la meitat altra vegada. [Estudiant] Vaig començar el conjunt de processadors, i després vaig tenir una cosa així on es va oblidar l'1 +, i es va quedar encallat en un bucle infinit. És clar, perquè en algun moment vostè mai va a aconseguir comencen i acaben a superposar en realitat. Cool. Hi ha una falla més lògic, i és que aquest dubte ha de ser 1 else if. Per què podria ser? La raó és que si no és una cosa-si et veig, Kevin? [Kevin] Sí, perquè s'està canviant el punt final. [Nate] Exactament. Estem canviant el punt final, i si s'escriu així-ens tornarem fer espais entre- es comprovarà aquest cas. Aquest cas, si té èxit, es cancel · larà de la funció. A continuació, es comprovarà aquest cas següent, i si té èxit, serà ajustar el punt final, i després seguirà en marxa i verificar aquest cas. Però en aquest punt, no volem que continuï xecs. Afortunadament, no hem restablir el punt mig aquí, i sabem que aquest cas no tindrà èxit. Però definitivament vol posar la cosa en si hi ha tot i que podria, en aquest cas ja que no està ajustant el punt mitjà, que faria una diferència? No, perquè aquests casos són tots exclusius. Un cop més, el meu mal. No, crec que necessita aquesta persona si. Podem donar-li una oportunitat i executar i veure què passa. Construcció, va ocórrer un error. És probablement perquè vaig deixar d'aquests by i aquí. M'agradaria saber més dels de dalt a la part superior? No ho sembla. Ens allunyar la imatge, construir, aquí va, així que ara si busquem per 15, Sí Permetin-me zoom in 15, sí. Podem tornar a executar-lo. Càrrega de codi font, construcció, corrent. Podem buscar per alguna cosa així com 13, i no rebem res d'imprimir, de manera que no està trobant que per a nosaltres. Això és genial, perquè no està en la nostra llista. Ara estem fora de temps. Això serà per a aquesta setmana. Gràcies per acompanyar-nos i ens veiem més tard. [CS50.TV]