[Powered by Google Translate] [Secció 3 - Més Còmode]
[Rob Bowden - Harvard University]
>> [Aquesta és CS50. - CS50.TV]
>> Així que la primera pregunta és estranyament redactada.
GDB li permet "depurar" un programa, sinó, més específicament, què farem?
Vaig a respondre a això, i jo no sé què és exactament l'esperat,
així que suposo que és una cosa al llarg de les línies de deixa pas a pas
caminar a través del programa, interactuar-hi, les variables del canvi, fer totes aquestes coses -
bàsicament completament controlar l'execució d'un programa
i inspeccionar qualsevol part donada de l'execució del programa.
Així que aquestes funcions li permeten depurar les coses.
Bé.
Per què la recerca binària que requereixen un arranjament poden ordenar?
Qui vol respondre a això?
[Estudiant] Perquè no funciona si no està ordenada. Sí >>. [Rialles]
Si no està ordenat, llavors és impossible que dividir per la meitat
i saber que tot a l'esquerra és menor i tot a la dreta
és major que el valor mitjà.
Així que ha de ser resolt.
Bé.
Per què és una espècie de bombolla a O del quadrat n?
Hi ha algú que primer vol donar una molt ràpida visió general d'alt nivell de bombolla quin tipus és?
[Estudiant] És, bàsicament, a través de cada element i comprovi els elements primers.
Si estan fora d'on canviar, després de comprovar els elements pròxims i així successivament.
En arribar a la final, llavors vostè sap que el major element es col · loca a l'extrem,
de manera que ignorar aquell temps segueixes passant,
i cada vegada que ha de comprovar un element menys fins que es faci cap canvi. Sí >>.
Es diu tipus bombolla, perquè si li dóna la volta el conjunt del seu costat pel que és a dalt i cap a baix, vertical,
a continuació, els valors grans s'enfonsen fins al fons i els valors petits es bombolla fins a dalt.
Aquesta és la manera com va obtenir el seu nom.
I sí, que acaba de passar.
Segueixes anant a través de la matriu, canviant el valor més gran
per obtenir els valors més grans per a la part inferior.
>> Per què és O quadrat de n?
En primer lloc, ¿algú vol dir això que és de O n al quadrat?
[Estudiant] A causa que per a cada carrera es va n vegades.
Només es pot estar segur que vostè ha pres l'element més gran fins al fons,
llavors vostè ha de repetir això per a tanta elements. Sí >>.
Així que tingui en compte el gran O significa i quins grans mitjans Omega.
L'O gran és com el límit superior del lent que en realitat es pot executar.
Així que dir que és de O n al quadrat, no és de O n o del que seria capaç d'executar
en el temps lineal, però és O de n cubs
perquè està limitada per O de n cubs.
Si està acotat per O quadrat de n, llavors és fitada també per n en cubs.
Per tant, és n al quadrat, i en el cas pitjor absolut que no pot fer millor que quadrada n,
que és per això que és O de n al quadrat.
Així que per veure les matemàtiques lleu en la manera com ve a ser n al quadrat,
si tenim cinc coses a la nostra llista, per primera vegada com els swaps molts podríem potencialment necessiten per prendre
per tal d'aconseguir-ho? Que en realitat només -
Com swaps molts haurem de fer en la primera execució de l'ordenació de bombolla a través de la matriu?
[Estudiant] n - 1. Sí >>.
>> Si hi ha 5 elements, haurem de fer n - 1.
Després, a la segona com swaps molts haurem de fer?
[Estudiant] n - 2. Sí >>.
I la tercera serà n - 3 i, a continuació per conveniència escriuré els dos últims
com llavors haurem de fer 2 swaps i swaps 1.
Suposo que l'últim pot o no pot necessitar realment a succeir.
Es tracta d'un intercanvi? No.
Així que aquestes són les quantitats totals de swaps o almenys comparacions que han de fer.
Encara que no intercanvia, vostè encara necessita per comparar els valors.
Així que hi ha n - 1 comparacions en la primera passada a través de la matriu.
Si reorganitza aquestes coses, anem a realment fer sis coses per apilar les coses molt bé,
i després vaig a fer 3, 2, 1.
Així que reorganitzar aquestes sumes, volem veure com moltes comparacions que fem
en l'algorisme complet.
Així que si portem a aquests nois per aquí,
llavors estem sent només suma comparacions però molts no ho eren.
Però si sumem aquests i sumem aquests i sumem aquests,
que segueix sent el mateix problema. Acabem de resumir aquests grups en particular.
>> Així que ara estem sumant els 3 n. No es tracta només de 3 n.
Sempre serà n / 2 n de.
Així que aquí passa que té 6.
Si tinguéssim 10 coses, llavors podríem fer aquesta agrupació per a 5 parells diferents de coses
i acabar amb n + n + n + n + n.
Així que sempre obtindràs n / 2 n, i pel que aquest ho anem a apuntar a n al quadrat / 2.
I així, tot i ser el factor de la mitjana, que passa a ser en
pel fet que a través de cada iteració en la matriu es comparen menys 1
així és com vam aconseguir el sobre 2, però segueix sent n al quadrat.
No m'importa el factor constant de la meitat.
Així que un munt de grans coses O com això es basa en un sol tipus de fer aquesta classe de matemàtiques,
fent sumes aritmètiques i coses sèrie geomètrica,
però la majoria d'ells en aquest curs són bastant senzills.
Bé.
Per què és l'ordenació per inserció en Omega de n? Què omega dir?
[Dues estudiants que parlen alhora - inintel · ligible] >> Yeah.
Omega es pot considerar com el límit inferior.
>> Així que no importa què tan eficient és el seu algoritme d'ordenació per inserció és,
independentment de la llista que es passa a dins, sempre cal comparar almenys n coses
o ha de iterar núm coses.
Per què és això?
[Estudiant] Perquè si la llista ja està ordenat, i després a través de la primera iteració
només es pot garantir la primera tasca és el menor,
i la segona iteració només es poden garantir les dues primeres són
perquè no saben que la resta de la llista està ordenada. Sí >>.
Si vostè passa en una llista completament ordenats, si més no has d'anar a través de tots els elements
per veure que res necessita ser mogut al voltant.
Així que passant per sobre de la llista i dient oh, això ja està classificat,
és impossible que vostè sàpiga que està ordenats fins que marqui cada element
per veure que estan en l'ordre establert.
Així que el límit inferior de l'ordenació per inserció és Omega de n.
Què és el pitjor dels casos el temps de funcionament de tipus fusió,
pitjor cas és O grans de nou?
Així que en el pitjor dels casos, com ordenar fusió córrer?
[Estudiant] N log n. Sí >>.
Els més ràpids algorismes generals d'ordenació són n log n. No es pot fer millor.
>> Hi ha casos especials, i si tenim temps avui - però probablement no veuran -
vam poder veure un que ho faci millor que n log n.
Però en el cas general, no es pot fer res millor que n log n.
I combinar espècie passa a ser el que vostè ha de saber per a aquest curs que és n log n.
I pel que en realitat serà l'aplicació d'aquest avui.
I, finalment, en no més de tres frases, com funciona la selecció de classe?
Algú vol contestar, i jo et conte les seves penes
perquè si vostè es passa de 3 -
Algú recorda tipus de selecció?
Tipus de selecció és en general bastant fàcil de recordar només pel nom.
Vostè acaba de recórrer l'array, trobar el que és el valor més gran o més petit -
l'ordre que li toqui rentar polz
Així que diguem que estem ordenar de menor a major.
Vostè iterar sobre la matriu, a la recerca del que és l'element mínim,
seleccioneu i, a continuació, només canviar el que està en el primer lloc.
I després, en la segona passada a través de la matriu, busqui l'element mínim de nou,
seleccioneu i, a continuació, intercanviar amb el que està en la segona posició.
Així que només estem escollint i seleccionant els valors mínims
i la seva inserció en la part frontal de la matriu fins que s'ordena.
Les preguntes sobre això?
>> Aquests inevitablement apareixen en els formularis que s'han d'emplenar quan vostè està presentant el conjunt de processadors.
Aquests són, bàsicament, les respostes a ells.
Bé, ara codificació problemes.
Ja he enviat per correu electrònic - Ningú aconseguir que el correu electrònic? Bé.
Ja he enviat per correu electrònic l'espai que utilitzarem,
i si fas clic en el meu nom - així que crec que estaré al fons
causa de la r cap enrere - però si fas clic en el meu nom veuràs dues revisions.
Revisió 1 serà que ja copiar i enganxar el codi en els espais
de manera que la recerca haurà de posar en pràctica.
I Revisió 2 serà el tipus que posem en pràctica després d'això.
Així que vostè pot fer clic en el meu Revisió 1 i treballar des d'allà.
I ara volem implementar la recerca binària.
>> Algú vol donar només un pseudocodi d'alt nivell explicació
del que haurem de fer per a la recerca? Si.
[Estudiant] Vostè acaba de prendre el centre de la matriu i veure si el que estàs buscant
és menor que o més que això.
I si és menys, vas a la part que és menys,
i si és més, te'n vas a la mitjana que és més i repetir fins que vostè acaba d'aconseguir una cosa.
[Bowden] Yeah.
Tingueu en compte que la nostra matriu de nombres ja està ordenat,
i pel que significa que podem prendre avantatge d'això i vam poder comprovar en primer lloc,
bé, estic buscant el número 50.
Perquè pugui entrar al centre.
Mitjà és difícil de definir, quan és un nombre parell de coses,
però diguem que sempre anem a truncar a la meitat.
Així que aquí tenim 8 coses, de manera que la mitjana seria de 16.
Estic buscant a 50, així que 50 és més gran que 16.
Així que ara, bàsicament, pot tractar la meva matriu com aquests elements.
Puc llençar tot a partir de 16 anys.
Ara la meva matriu és només aquests 4 elements, i ho repeteixo.
Així que vull trobar el mitjà més, que serà 42.
42 és inferior a 50, pel que puc tirar aquests dos elements.
Aquest és el meu arsenal restant.
Vaig a trobar el mitjà de nou.
Suposo que 50 era un mal exemple perquè sempre estava tirant coses a l'esquerra,
però en la mateixa mesura, si estic buscant alguna cosa
i és menor que l'element que estic mirant,
llavors vaig a tirar tot a la dreta.
Així que ara hem d'aplicar això.
Recordeu que hem de passar de mida.
No podem també han codificar mida.
Així que si ens desfem que # defineix -
Bé.
Com puc esbrinar molt bé quin és la mida de la matriu de nombres en l'actualitat és?
>> Quants elements hi ha a la matriu números?
[Estudiants] Els nombres, parèntesis,. Longitud?
[Bowden] Això no existeix en C.
Necessitat. Longitud.
Les matrius no tenen propietats, de manera que no hi ha cap propietat de les matrius de longitud
que només li donarà el temps que passa a ser.
[Estudiant] Veure la quantitat de memòria que té i dividir per la quantitat - >> Yeah.
Llavors, com podem saber quanta memòria té? >> [Estudiant] sizeof. >> Sí, sizeof.
Sizeof és l'operador que tornarà la mida de la matriu de nombres.
I això serà sencers però hi ha moltes vegades la mida d'un sencer
ja que és la quantitat de memòria que realment prenent.
Així que si voleu que el nombre de coses en la matriu,
llavors vaig a voler dividir per la grandària d'un sencer.
Bé. Així que em permet passar de mida aquí.
Per què he de passar en grandària després de tot?
Per què no puc fer aquí int size = sizeof (paller) / sizeof (int)?
Per què no funciona?
[Estudiant] No és una variable global.
[Bowden] Haystack existeix i estem passant en números com paller,
i això és una mena de presagi del que vindrà. Si.
[Estudiant] Haystack és només la referència a la mateixa, de manera que tornaria el gran que és de referència.
Si.
Dubto que en la conferència que ha vist la pila encara realment, oi?
Hem parlat sobre això.
Així que la pila és on totes les variables s'han d'emmagatzemar.
>> Qualsevol memòria que assignada per les variables locals va a la pila,
i cada funció té el seu propi espai a la pila, el seu propi marc de pila és el que es diu.
Així que té el seu principal marc de pila, i dins d'ella va a existir aquesta matriu nombres,
i que serà de mida sizeof (nombres).
Va a tenir la mida dels nombres dividit per la mida dels elements,
sinó que totes les vides dins de marc de pila principal.
Quan cridem a la recerca, recerca obté el seu propi marc de pila,
seu propi espai per emmagatzemar totes les variables locals.
Però aquests arguments - així paller no és una còpia d'aquesta matriu completa.
No lliurem a tot el conjunt com una còpia en la recerca.
Tot just passa una referència a la matriu.
Així recerca pot accedir a aquests números a través d'aquesta referència.
És encara l'accés a les coses que viuen a l'interior del marc de pila principal,
però en el fons, quan arribem als punters, que ha de ser breu,
això és el que els punters són.
Els punters són només referències a les coses, i es pot utilitzar punters per accedir a les coses
que es troben en els marcs de pila altres coses.
Així que, encara que el nombre és local principal, encara pot accedir a través d'aquest punter.
Però ja que és simplement un punter i és només una referència,
sizeof (paller) només retorna la grandària de la mateixa referència.
No torna la mida del que està assenyalant.
No torna la mida real dels nombres.
I perquè això no funcionarà com es desitja.
>> Les preguntes sobre això?
Els punters s'haurà anat en detall molt més sagnant en les setmanes per venir.
I aquesta és la raó per un munt de coses que es veuen, la majoria de les coses o les coses d'ordre de recerca,
són gairebé tots haurem de prendre la mida real de la matriu,
perquè en C, no tenim idea del que la mida de la matriu és.
Has de passar manualment polz
I no es pot passar manualment a tota la matriu, ja que està de pas en la referència
i no es pot obtenir la mida de la referència.
Bé.
Així que ara volem posar en pràctica el que s'ha explicat anteriorment.
Pot treballar-hi durant un minut,
i vostè no ha de preocupar d'aconseguir tot perfectament 100% de treball.
Només ha d'escriure el pseudocodi mitjà de com crec que hauria de funcionar.
Bé.
No hi ha necessitat d'estar completament acabat amb això.
Però, ¿algú se senti còmode amb el que tinc fins ara,
com una cosa que podem treballar de forma conjunta?
Algú vol ser voluntari? O escolliran aleatòriament.
No ha de ser just per qualsevol mesura, sinó alguna cosa que pot modificar en un estat de treball.
[Estudiant] Clar. >> Okay.
Així es pot estalviar la revisió fent clic a la petita icona Guardar.
Vostè és Ramya, oi? >> [Estudiant] Yeah. >> [Bowden] Bé.
Així que ara puc veure la seva revisió i tothom pot aixecar la revisió.
I aquí tenim - Està bé.
Així va ser amb Ramya la solució recursiva, que és definitivament una solució vàlida.
Hi ha dues maneres que vostè pot fer aquest problema.
Vostè pot fer-ho iterativament o recursivament.
La majoria dels problemes que trobi que es pot fer de forma recursiva també pot realitzar iterativament.
Així que aquí ho hem fet de forma recursiva.
>> Algú vol definir el que significa fer una funció recursiva?
[Estudiant] Quan es té una funció pròpia anomenada
i després trucar a si mateix fins que surti amb veritable i cert. Sí >>.
Una funció recursiva és una funció que es diu a si mateixa.
Hi ha tres coses importants que una funció recursiva ha de tenir.
La primera és, òbviament, es diu a si mateixa.
El segon és el cas base.
Així que en algun punt la funció ha de deixar de cridar a si mateix,
i això és el que el cas base és per.
Així que aquí sabem que hem de deixar, hem de renunciar a la nostra recerca
quan l'inici és igual a extrem - i anem a repassar el que això significa.
Però, finalment, l'última cosa que és important per a les funcions recursives:
les funcions d'alguna manera ha d'abordar la causa base.
Igual que si vostè no està realment actualitzar res quan vostè fa la crida recursiva en segon lloc,
si vostè està literalment a la crida a la funció de nou amb els mateixos arguments
i no hi ha variables globals han canviat ni res,
vostè mai arribarà al cas base, en aquest cas això és dolent.
Serà una repetició infinita i un desbordament de pila.
Però aquí veiem que l'actualització està passant des que s'inicia l'actualització + final / 2,
estem actualitzant l'argument final aquí, estem actualitzant l'argument d'inici aquí.
Així, en totes les trucades recursives estem actualitzant alguna cosa. Bé.
Vols que ens guiarà a través de la seva solució? >> Clar.
Estic usant SearchHelp de manera que cada vegada que faig aquesta crida de funció
Tinc el principi d'on jo estic buscant en la matriu i la fi
d'on jo estic buscant la matriu.
>> A cada pas, on es diu que és l'element central, que és inici + final / 2,
que és igual al que estem buscant?
I si és així, llavors que el trobem, i suposo que es passa als nivells de recursivitat.
I si això no és cert, llavors es comprova si el valor mitjà de la matriu és massa gran,
en aquest cas ens fixem en la meitat esquerra de la matriu per va des del començament fins l'índex mitjà.
I una altra cosa que fem la mitjana final.
[Bowden] Bé.
Això sembla bé.
Està bé, així que un parell de coses, i de fet, això és una cosa molt alt nivell
que vostè no haurà de saber per aquest curs, però és cert.
Les funcions recursives, que sempre se sent que són un mal negoci
perquè si es diu a si mateix de forma recursiva massa vegades, s'obté desbordament de pila
ja que, com he dit abans, cada funció té el seu propi marc de pila.
Així que cada crida de la funció recursiva obté el seu propi marc de pila.
Així que si vostè fa 1.000 trucades recursives, s'obté 1.000 marcs de pila,
i ràpidament el portarà a tenir marcs de pila massa coses i acaba de trencar.
Per això és que les funcions recursives són generalment dolents.
Però hi ha un subconjunt de les funcions recursives agradable anomenat cua de funcions recursives,
i aquest passa a ser un exemple d'un en el que si el compilador nota això
i ha de ser, crec - en Clang si se li passa la bandera-O2
llavors es donarà compte d'això és la cua recursiva i fer les coses bé.
>> Es tornarà a utilitzar el mateix marc de pila i una altra per a cada crida recursiva.
I ja que estàs utilitzant el mateix marc de pila, vostè no ha de preocupar sobre
mai apilar desbordant, i alhora, com vas dir abans,
què, després que torni cert, llavors cal tornar tot el d'aquests marcs de pila
i la crida del 10 al SearchHelp ha de tornar als dies 9, ha de tornar a la 8a.
Així que no cal que passi quan les funcions són col recursiva.
I així, el que fa que aquesta funció recursiva de cua és un avís de que per a qualsevol crida d'atenció a searchHelp
la crida recursiva que està fent és el que està tornant.
Així, a la primera crida a SearchHelp, que sigui immediatament tornar false,
immediatament tornar true, o es fa una crida recursiva a SearchHelp
on el que estem tornant és el que aquesta crida està tornant.
I no podríem fer això si ho féssim alguna cosa com int x = SearchHelp, return x * 2,
només alguns canvis a l'atzar.
>> Així que ara aquesta crida recursiva, aquesta int x = SearchHelp crida recursiva,
ja no és la cua recursiva, ja que en realitat ha de tornar
de nou a un marc de pila anterior perquè aquesta trucada prèvia a la funció
A continuació, pot fer alguna cosa amb el valor de retorn.
Així que això no és la cua recursiva, però el que teníem abans és ben cua recursiva. Si.
[Estudiant] No hauria el cas de la segona base es comprova en primer lloc
perquè podria haver una situació en què quan se li passa l'argument
ha començar = fi, sinó que són el valor de l'agulla.
La pregunta va ser no podem córrer en el cas extrem és el valor d'agulla
o començar = fi, apropiadament, iniciï final =
i no s'han comprovat que determinat valor, però,
a continuació, iniciar + final / 2 és només serà el mateix valor.
Però ja hem tornat fals i que en realitat mai comprovat el valor.
Així que almenys, en la primera convocatòria, si la mida és 0, llavors volem tornar false.
Però si la mida és 1, llavors començament no acabarà igual,
i anem a comprovar almenys l'únic element.
Però crec que tens raó en que pot acabar en un cas en l'inici + final / 2,
inici acaba sent la mateixa que inici + final / 2,
però mai hem fet el check aquest element.
>> Així que si busquem en primer lloc és un dels eixos del valor que estem buscant,
llavors pot tornar immediatament veritat.
Perquè si són iguals, llavors no hi ha raó per continuar
ja que només anem a actualitzar a un cas en què ens trobem en una matriu d'un sol element.
Si aquest element no és el que estem buscant,
llavors tot el que està malament. Si.
[Estudiant] El cas és que ja que la mida és més gran que el nombre d'elements en la matriu,
ja hi ha un offset - >> Passa el mateix amb la mida -
[Estudiant] Digues si la matriu era de mida 0, llavors el SearchHelp realment comprovar paller de 0
a la primera trucada.
La matriu té una mida 0, de manera que el 0 és - >> Yeah.
Hi ha una altra cosa que - pot ser bo. Anem a pensar.
Així que si la matriu amb 10 elements i el del mitjà que revisarem és l'índex de 5,
pel que estem comprovant 5, i diguem que el valor és menor.
Així que estem tirant tot a rodar a partir del 5 d'ara endavant.
Així que comença a + final / 2 serà el nostre nou final,
així que sí, que sempre estarà més enllà del final de la matriu.
Si es tracta d'un cas si era parell o senar, llavors podríem comprovar, per exemple, 4,
però encara estem desaprofitant -
Així que sí, al final sempre estarà més enllà del final real de la matriu.
De manera que els elements que ens estem centrant, final sempre serà el que després d'això.
I així, si fa arrencada acaba mai igual, estem en una matriu de mida 0.
>> L'altra cosa que estava pensant és que estem actualitzant el principi fins al final es va iniciar + / 2,
de manera que aquest és el cas que estic tenint problemes amb, per on començar + final / 2
és l'element que està comprovant.
Anem a dir que vam tenir aquesta matriu de 10 elements. El que sigui.
Així que comença a + final / 2 serà una cosa així com aquest,
i si aquest no és el valor, diguem que voleu actualitzar.
El valor és més gran, de manera que desitgi veure en aquesta meitat de la matriu.
Llavors, ¿com estem actualitzant principi, estem actualitzant principi per ser ara aquest element.
Però això encara pot funcionar, o si més no, pot fer start + final / 2 + 1.
[Estudiant] No cal que es comenci final + [inaudible] >> Si.
Ja hem comprovat aquest element i sé que no és la que estem buscant.
Així que no cal actualitzar principi per ser aquest element.
Només podem saltar i actualitzar començar a ser aquest element.
I hi ha mai un cas, direm, que això fos final,
així llavors començar seria això, iniciï + final / 2 seria això,
començar final + - Sí, crec que pot acabar en una recursió infinita.
Anem a dir que és una matriu de mida 2 o una matriu de mida 1. Crec que això va a funcionar.
Així en l'actualitat, és que inici i final element és 1 més enllà d'ella.
De manera que l'element que anem a comprovar és aquest,
i després, quan ens posem al dia d'inici, estem actualitzant principi per ser 0 + 1/2,
que ens acabarà de nou amb arrencada sent aquest element.
>> Així que estem comprovant l'element mateix una i una altra.
Així que aquest és el cas en què cada crida recursiva en realitat ha d'actualitzar alguna cosa.
Així que hem de fer start + final / 2 + 1, o si no hi ha un cas
on no estem en realitat l'actualització inicial.
Tothom veu això?
Bé.
Algú té alguna pregunta sobre aquesta solució o més comentaris?
Bé. Algú té una solució iterativa que tots puguem mirar?
Sabia que tots ho fan de forma recursiva?
O també suposo que si ella es va obrir, llavors vostè podria tenir anul · lat el seu anterior.
Es guarda automàticament? Jo no sóc positiu.
Algú ha iteratiu?
Podem caminar a través d'ella junts si no.
La idea serà el mateix.
Solució iterativa.
Anem a voler fer bàsicament la mateixa idea
on volem portar el compte del nou final de la matriu i el nou començament de la matriu
i fer això una i altra vegada.
I si el que estem fer el seguiment de com l'inici i el final mai es creuen,
llavors nosaltres no el trobem i ens pot tornar false.
Llavors, com puc fer això? Algú té suggeriments o codi perquè jo tiri cap amunt?
[Estudiant] Fer un bucle while. Sí >>.
Vostè va a voler fer un bucle.
>> Vostè té un codi que podria tirar amunt, o el que se li va a suggerir?
[Estudiant] Crec que sí. >> Està bé. Això fa les coses més fàcils. Quin era el seu nom?
[Estudiant] Lucas.
Revisió 1. Bé.
Menor és el que anomenem començar abans.
Fins no és exactament el que dèiem abans de final.
En realitat, està ara al final de la matriu. És un element que hem de considerar.
Així sota és 0, a dalt és la mida de la matriu - 1,
i ara estem bucle, i la comprovació es -
Suposo que es pot caminar a través d'ell.
Quin va ser el seu pensament a través d'això? Camina amb nosaltres a través del seu codi.
[Estudiant] Clar. Fixeu-vos en el valor paller al centre i comparar-la amb l'agulla.
Així que si és més gran que la seva agulla, llavors vostè vol - Oh, en realitat, hauria de ser al revés.
Vostè va a voler tirar la meitat dreta, de manera que si, que ha de ser el camí.
[Bowden] Així que això ha de ser menys? És això el que vas dir? >> [Estudiant] Yeah.
[Bowden] Bé. Menys.
Així que si el que estem veient és més petit que el que volem,
llavors sí, volem tirar la meitat esquerra,
el que significa que estem actualitzant tot el que estem considerant
movent sota a la dreta de la matriu.
Això es veu bé.
Crec que té el mateix problema que hem dit en l'anterior,
on si baixa és 0 i fins és 1, llavors sota fins + / 2 s'establirà a ser el mateix una altra vegada.
>> I fins i tot si aquest no és el cas, encara és més eficient si més no
a tir de lluny l'element que acabem de veure que sabem que està malament.
Així que sota + dalt / 2 + 1 - >> [estudiant] Això hauria de ser al contrari.
[Bowden] O això hauria de ser - 1 i l'altre ha de ser + 1.
[Estudiant] I ha d'haver un doble signe igual. >> [Bowden] Yeah.
[Estudiant] Yeah.
Bé.
I, finalment, ara que tenim aquest 1 + - 1 cosa,
és que - potser no és - és sempre possible baix per acabar amb un valor major de fins?
Crec que l'única manera en què pot succeir - És possible? >> [Estudiant] No ho sé.
Però si es posa truncada i després es fa menys que 1 i després - >> Yeah.
[Estudiant] És, possiblement, arribar en mal estat.
Crec que hauria de ser bo només perquè
perquè acabi inferior haurien de ser igual, crec.
Però si són iguals, llavors no hauria fet el bucle while per començar
i ens hauria tornat el valor. Així que crec que estem bé ara.
Observi que encara que aquest problema ja no és recursiu,
el mateix tipus d'idees s'apliquen en què podem veure com això tan fàcilment es presta
a una solució recursiva pel fet que estem només l'actualització dels índexs d'una i altra vegada,
estem fent el problema més petit, ens estem centrant en un subconjunt de la matriu.
[Estudiant] Si baixa és 0 i fins és 1, els dos estarien 0 + 1/2, que aniria a 0,
i llavors un seria + 1, un seria - 1.
[Estudiant] On estem comprovant la igualtat?
Igual que si el medi és realment agulla?
No estem actualment fent això? Oh!
Si és -
Sí No podem limitar-nos a fer la prova aquí perquè diguem que la primera meitat -
[Estudiant] De fet, és com no llençar el enquadernat.
Així que si vostè llança lluny el límit, vostè ha de comprovar primer o el que sigui.
Ah. Si. >> [Estudiant] Yeah.
Així que ara que hem tirat la que actualment mirat,
el que significa que ara hem de tenir també
if (paller [(baixa + fins) / 2] == agulla), llavors es pot tornar realitat.
I si em poso més o simplement si, significa literalment la mateixa cosa
perquè això hauria tornat realitat.
Així que vaig a posar un altre si, però no importa.
>> Així que si aquesta cosa, en cas contrari això, i això és una cosa comuna que faig
on fins i tot si és el cas en què tot està bé aquí,
com sota no pot ser mai superior a la pota, no és digne de raonament sobre si això és cert.
Així que vostè pot també dir mentre baixa és menor o igual a
o mentre baix és menor que
pel que si és que alguna vegada passa igual o menor a deixar-la passar,
llavors podem sortir d'aquest bucle.
Preguntes, inquietuds, comentaris?
Bé. Això es veu bé.
Ara volem fer una espècie.
Si anem a la meva segona revisió, veiem aquests mateixos nombres,
però ara ja no estan en ordre.
I volem implementar utilitzant qualsevol tipus algoritme en O de n log n.
Llavors, què algorisme creus que hauríem d'aplicar aquí? >> [Estudiant] tipus de mescla.
[Bowden] Yeah. Combinar tipus és O (n log n), així que això és el que farem.
I el problema serà bastant similar,
on es presta fàcilment a una solució recursiva.
També podem arribar a una solució iterativa si volem,
però recursió serà més fàcil aquí i hem de fer recursivitat.
Suposo que tindrem una caminada per tipus de mescla en primer lloc,
encara que hi ha un vídeo preciós sobre tipus de combinació ja. [Rialles]
Així merge sort hi ha - m'estic perdent gran part d'aquest treball.
Oh, només hi ha una esquerra.
Així es fusionen.
Oh, 1, 3, 5.
Bé.
Merge pren dues matrius independents.
Individualment aquestes dues matrius són dos ordenats.
Així aquesta matriu, 1, 3, 5, ordenats. Aquesta matriu, 0, 2, 4, ordenats.
Ara, què combinació ha de fer és combinar en una sola matriu que és al seu torn ordenats.
Per això volem una matriu de mida 6 que tindrà aquests elements dins d'ella
de manera ordenada.
>> I així podem aprofitar el fet que aquests dos conjunts s'ordenen
fer-ho en un temps lineal,
sentit del temps lineal si aquesta matriu és x mida i aquesta és i mida,
llavors l'algorisme total ha de ser O (x + i). Bé.
Així suggeriments.
[Estudiant] Podríem començar per l'esquerra?
Així que vaig a posar el 0 a baix primer i després el 1 i després aquí estàs en el 2.
Així que és com té una fitxa que es mou cap a la dreta. >> [Bowden] Yeah.
Per a tots dos conjunts si només es centren en l'element més a l'esquerra.
Com que tots dos conjunts s'ordenen, se sap que aquests dos elements
són els elements més petits, ja sigui en matriu.
Així que això significa que 1 dels 2 elements han de ser l'element més petit de la nostra gamma combinada.
El que passa és que el més petit és el de la dreta aquest cop.
Així que prenem 0, inserir-lo a l'esquerra, perquè 0 és menor que 1,
així que 0, la inserida en la nostra posició, i després actualitzem aquesta
a centrar ara en el primer element.
I ara ho repetim.
Així que ara comparem 2 i 1. 1 és més petita, així que anem a inserir 1.
Actualitzem aquest punter per apuntar a aquest noi.
Ara hem de fer-ho de nou, així que 2. Açò actualitzarà, comparar aquests 2, 3.
Això actualitza, després 4 i 5.
Així que és de mescla.
>> Ha de ser bastant obvi que és el temps lineal ja que només ha d'anar a través de cada element d'una vegada.
I aquest és el pas més important per a la implementació espècie de barreja està fent això.
I no és tan difícil.
Un parell de coses que preocupar és que anem a dir que ens fusió 1, 2, 3, 4, 5, 6.
En aquest cas, acaben en l'escenari en què aquest serà més petit,
després actualitzem aquest punter, aquest serà més petits, actualitzar això,
aquest és més petit, i ara vostè ha de reconèixer
quan realment has quedat sense elements per comparar.
Com que ja hem utilitzat aquest arsenal sencer,
tot aquest conjunt ara s'acaba d'inserir en aquí.
Així que si mai arribes a tenir al punt que un dels nostres arrays està totalment fusionat ja,
llavors simplement prendre tots els elements de l'altra matriu i inserir-los al final de la matriu.
Així que només es pot inserir 4, 5, 6. Bé.
Això és una cosa a tenir en compte.
Implementació que ha de ser el pas 1.
Combinar ordenar després en base a això, és 2 passos, 2 passos ximples.
Anem a donar a aquesta matriu.
Així merge sort, el pas 1 és trencar la matriu recursivament en dues meitats.
Així que dividir aquest conjunt en dues meitats.
Ara tenim 4, 15, 16, 50 i 8, 23, 42, 108.
I ara ho fem de nou i ens separem aquests en dues meitats.
Jo només vaig a fer en aquest costat.
Així 4, 15 i 16, 50.
Faríem el mateix aquí.
I ara ho dividim per la meitat una altra vegada.
I tenim 4, 15, 16, 50.
Així que aquest és el nostre cas base.
Quan les matrius són de grandària 1, llavors s'atura amb la divisió en dues meitats.
>> Ara, què fem amb això?
Acabem això també es divideixen en 8, 23, 42, i 108.
Així que ara que estem en aquest moment, ara pas dos tipus de combinació és simplement la fusió de parells per les llistes.
Així que volem fusionar aquests. Acabem de trucar a fusionar-se.
Sabem fusió tornarà aquests en l'ordre establert.
4, 15.
Ara volem unir aquests, i que tornarà una llista amb els registres en ordre,
16, 50.
Ens fusionem aquells - que no puc escriure - 8, 23 i 42, 108.
Així que tenim parells fusionats vegada.
Ara només ens queda unir de nou.
Tingueu en compte que cadascuna d'aquestes llistes s'ordenen per si mateixa,
i llavors només pot combinar aquestes llistes per obtenir una llista de mida 4, que es classifica
i fusionar aquestes dues llistes per obtenir una llista de mida 4, que està ordenada.
I, finalment, podem fusionar aquests dos llistes de mida 4 per obtenir una llista de mides de 8, que està ordenada.
Així que a veure que això és general n log n, ja vam veure que merge és lineal,
així que quan ens enfrontem a la fusió d'aquests, així com el cost total de fusió
per aquestes dues llistes és a 2 perquè -
O bé, és de S n, n però aquí és només aquests dos elements, de manera que és 2.
I aquests 2 serà 2 i aquests 2 serà 2 i aquests 2 serà 2,
així que a través de totes les fusions que hem de fer, acabem fent núm.
Igual que 2 + 2 + 2 + 2 és 8, que és N,
de manera que el cost de la combinació d'aquest conjunt és n.
I el mateix aquí.
Anem a combinar aquests 2, llavors aquests 2, i de forma individual aquesta fusió es durà a quatre operacions,
aquesta fusió es durà a quatre operacions, però un cop més, entre tots ells,
acabem la fusió n les coses en conjunt, de manera que aquest pas pren núm.
I així, cada nivell té n elements es van fusionar.
>> I Quants nivells hi ha?
A cada nivell, la nostra matriu creix en mida 2.
Aquí les nostres matrius són de grandària 1, aquí són de mida 2, aquí són de grandària 4,
i, finalment, són de mida 8.
Així que ja que es duplica, hi haurà un total de log n d'aquests nivells.
Així que amb log n nivells, cada nivell individual tenint núm total d'operacions,
obtenim un log n n algorisme.
Preguntes?
La gent ja s'ha avançat en la forma d'aplicar això?
Hi ha algú ja en un estat en el qual només pot aixecar el seu codi?
Em pot donar un minut.
Aquest serà més llarga.
Recomano altament recurrents -
No ha de fer recursivitat per fusió
perquè per fer recursivitat per merge, hauràs de passar un munt de diferents mides.
Es pot, però és molest.
Però recursivitat per ordenar en si és bastant fàcil.
Simplement truqui espècie literalment a la meitat esquerra, més o menys a la meitat dreta. Bé.
Algú té alguna cosa que pugui aixecar ja?
O si no vaig a donar un minut.
Bé.
Algú té alguna cosa que puguem treballar?
Del que només haurem de treballar amb això i després expandir des d'allà.
>> Qualsevol persona que tingui més d'això que jo puc aixecar?
[Estudiant] Yeah. Vostè pot aixecar la meva. >> Està bé.
Sí!
[Estudiant] Hi havia un munt de condicions. >> Oh, dispara. Pot vostè -
[Estudiant] He de guardar. Sí >>.
Així ho vam fer fer la fusió per separat.
Oh, però no és tan dolent.
Bé.
Així classe en si és simplement trucar mergeSortHelp.
Explica'ns què mergeSortHelp fa.
[Estudiant] MergeSortHelp pràcticament fa els dos passos principals:
que és classificar cada mitjà de la matriu i, a continuació per fusionar els dos.
[Bowden] Està bé, dóna'm un segon.
Crec que això - >> [estudiant] Necessito -
Si. M'estic perdent alguna cosa.
En combinació, m'adono que he de crear una nova matriu
perquè jo no podia fer-ho en el seu lloc. Sí >>. No es pot. Corregir.
[Estudiant] Per tant, crear una nova matriu.
Em vaig oblidar al final de fusionar-se per tornar a canviar.
Bé. Necessitem una nova matriu.
En tipus de mescla, això és gairebé sempre cert.
Una part del cost d'un algorisme millor pel que fa a temps
és gairebé sempre la necessitat d'usar la memòria una mica més.
Així que aquí, no importa el que facis merge sort,
que inevitablement hauria d'utilitzar una mica de memòria extra.
Ell o ella va crear una nova matriu.
I després diuen que al final només hem de copiar nova matriu a la matriu original.
[Estudiant] Crec que sí, sí.
No sé si això funciona en termes de comptatge per referència o el que sigui -
Sí, va a treballar. >> [Estudiant] Bé.
Ha intentat executar aquest? >> [Estudiant] No, encara no. >> Okay.
Intenta executar, i després vaig a parlar d'això per un segon.
[Estudiant] Necessito tenir tots els prototips de funcions i tot, però, no?
Els prototips de funció. Oh, et refereixes a - si.
Ordenar diu mergeSortHelp.
>> Així que per sort de cridar mergeSortHelp, mergeSortHelp han d'haver estat definit
abans d'ordenar o només tenim el prototip. Només has de copiar i enganxar això.
I de la mateixa manera, mergeSortHelp crida fusió,
però fusió no s'ha definit encara, així que podem deixar saber mergeSortHelp
que això és el que va a fusionar veurà així, i això és tot.
Així mergeSortHelp.
Tenim un problema aquí on tenim cap cas base.
MergeSortHelp és recursiu, de manera que qualsevol funció recursiva
va a necessitar algun tipus de cas base per saber quan parar de forma recursiva es fa dir.
Quin és el nostre cas base estarà aquí? Si.
[Estudiant] Si la mida és 1? >> [Bowden] Sí
Així que, com vam veure allà, ens vam aturar arrays divisió
una vegada que arribem a matrius de mida 1, el que inevitablement s'estan ordenades.
Així que si la mida és igual a 1, sabem que la sèrie ja està ordenat,
de manera que només pot tornar.
>> Tingueu en compte que és nul, de manera que no torna res especial, simplement tornar.
Bé. Així que aquest és el nostre cas base.
Suposo que el nostre cas base també podria ser si ens toca ser la fusió d'una matriu de mida 0,
és probable que desitgi aturar en algun moment,
de manera que només pot dir mida de menys de 2 o menys d'o igual a 1
per tal que això funcionarà per a qualsevol matriu ara.
Bé.
Així que aquest és el nostre cas base.
Ara, vols que ens guiarà a través de fusió?
Què signifiquen tots aquests casos?
Fins aquí, només estem fent la mateixa idea, la -
[Estudiant] Necessito que em passa mida amb totes les trucades mergeSortHelp.
He afegit una mida com a principal addicional i no hi és, com la mida / 2.
[Bowden] Oh, mida / 2, mida / 2. >> [Estudiant] Sí, i també en la funció anterior també.
[Bowden] Aquí? >> [Estudiant] Just mida. >> [Bowden] Oh. Mida, la mida? >> [Estudiant] Yeah.
[Bowden] Bé.
Deixa pensar per un segon.
No ens trobem amb un problema?
Sempre estem tractant l'esquerra com a 0. >> [Estudiant] No
Això està malament també. Em sap greu. Ha de ser inici. Si.
[Bowden] Bé. M'agrada més.
I final. Bé.
Així que ara vols que ens guiarà a través de fusió? >> [Estudiant] Bé.
Estic caminant a través d'aquesta nova matriu que he creat.
La seva grandària és la mida de la porció de la matriu que volem ser ordenats
i tractant de trobar l'element que he de posar en l'etapa de nova matriu.
Així que per fer això, primer estic comprovant si la meitat esquerra de la matriu continua tenint elements més,
i si no és així, llavors cal baixar a la condició de cosa, que només diu
bé, ha d'estar en la matriu dreta, i posarem això en l'índex actual de newArray.
>> I a continuació, en cas contrari, estic comprovant si el costat dret de la matriu també és acabat,
en aquest cas només cal posar a l'esquerra.
Això no podria ser en realitat necessari. No estic segur.
Però de tota manera, els altres dos controls que els dos són més petites en l'esquerra o la dreta.
I també en cada cas, estic incrementant qualsevol d'incrementar marcador de posició.
[Bowden] Bé.
Això es veu bé.
Algú té algun comentari o inquietud o preguntes?
Així que els quatre casos que hem de fer les coses en només ser - o sembla que cinc -
però hem de tenir en compte si la matriu de l'esquerra s'ha quedat sense coses que hem d'unir,
si la matriu de la dreta s'ha quedat sense coses que hem de fusionar -
Estic apuntant a res.
Així que si la matriu de l'esquerra s'ha quedat sense coses o la matriu de la dreta s'ha quedat sense coses.
Es tracta de dos casos.
També tenim el cas trivial que la cosa esquerra és menor que el correcte.
Llavors volem triar el esquerre.
Aquests són els casos.
Així que això estava bé, així que això és tot.
Matriu de l'esquerra. És 1, 2, 3. Bé. Així que sí, aquestes són les quatre coses que pot ser que vulgui fer.
I no anem a anar a través d'una solució iterativa.
Jo no recomanaria -
Unir tipus és un exemple d'una funció que és alhora no cua recursiva,
no és fàcil de fer cua recursiva,
però també no és molt fàcil de fer iteratiu.
Això és molt fàcil.
Aquesta implementació del tipus de mescla,
fusionar, no importa el que facis, has de construir combinació.
>> Així fusionar tipus construït al cim de fusió recursiva és només aquestes tres línies.
Iterativament, és més molest i més difícil de pensar.
Però cal notar que no és recursiu cua des mergeSortHelp - quan es diu a si mateixa -
que encara ha de fer les coses després d'aquesta crida recursiva.
Així que aquest marc de pila ha de seguir existint fins i tot després de cridar a això.
I després, quan es diu a això, el marc de pila ha de seguir existint
perquè fins i tot després d'aquesta trucada, encara hem de combinar.
I és trivial per fer aquesta cua recursiva.
Preguntes?
Està bé.
Així que tornant a ordenar - oh, hi ha dues coses que vull mostrar. Bé.
Tornant a la classe, farem això ràpidament.
O cerca. Ordenar? Sort. Si.
Tornant als començaments de l'espècie.
Volem crear un algoritme que ordena la matriu mitjançant qualsevol algoritme
a O de n.
Llavors, com és això possible? Algú té alguna mena de -
Em va donar a entendre abans de -
Si estem a punt de millorar a partir de n log n a O de n,
hem millorat el nostre algoritme quant a temps,
el que significa que haurem de fer per compensar això?
[Estudiant] Space. Sí >>. Estarem usant més espai.
I ni tan sols només més espai, és exponencialment més espai.
Així que crec que aquest tipus d'algorisme és una cosa pseudo polinomi pseudo -
pseudo - No puc recordar. Pseudo alguna cosa.
Però és perquè hem d'utilitzar tant espai
que es pot aconseguir, però no realista.
>> I com s'aconsegueix això?
Podem aconseguir això si et garantim que qualsevol element particular de la matriu
està per sota d'una certa mida.
Així que anem a dir que la mida és de 200,
qualsevol element d'una matriu es troba per sota de la mida 200.
I això és realment molt realista.
Vostè pot fàcilment tenir una matriu que ja saps tot el que conté
serà menor que cert nombre.
Igual que si vostè té algun vector absolutament massiu o alguna cosa
però ja saps que tot estarà entre 0 i 5,
llavors serà molt més ràpida de fer això.
I la envoltant en qualsevol dels elements és 5,
de manera que aquest límit, que és la quantitat de memòria que utilitzarà.
Així que el límit és 200.
En teoria no sempre és un salt des d'un nombre sencer només pot ser de fins a 4 milions de dòlars,
però això és poc realista ja que llavors estaríem utilitzant l'espai
l'ordre de 4 mil milions. Així que això és poc realista.
Però aquí direm que el nostre límit és de 200.
El truc per fer-ho en O de n és que fem una altra matriu anomenada càrrecs de mida OBLIGAT.
Així que en realitat, es tracta d'un accés directe - Jo en realitat no sé si Clang fa això.
Però en GCC com a mínim - Clang estic suposant que també ho fa -
això només inicialitzar la matriu completa per ser 0.
Així que si no vols fer això, llavors jo podria fer per separat for (int i = 0;
i <BOUND, i + +) i compta amb [i] = 0;
Així que ara tot s'inicialitza a 0.
Jo iterar sobre la meva matriu,
i el que estic fent és que estic comptant el nombre de cada un - Baixem aquí.
Tenim 4, 15, 16, 50, 8, 23, 42, 108.
El que estic comptant és el nombre d'ocurrències de cada un d'aquests elements.
Anem a afegir un parell realment més aquí amb algunes repeticions.
Per tant el valor que tenim aquí, el valor que serà matriu [i].
Així val podria ser 4 o 8 o el que sigui.
I ara que estic comptant quants d'aquest valor que he vist,
així recomptes [val] + +;
Un cop fet això, el recompte es veurà alguna cosa com 0001.
Farem recompte de [valor] - SUBJECTE + 1.
>> Ara això és només per explicar el fet que estem començant des de 0.
Així que si 200 serà la nostra major nombre,
llavors 0-200 és de 201 coses.
Així que compte, es veurà com 00001, perquè tenim un 4.
Llavors tindrem 0001 on tindrem un 1 en l'índex de 8 de comptatge.
Tindrem un 2 al índex 23 de la compte.
Tindrem un 2 al índex 42 del recompte.
Així que podem utilitzar el compte.
Així num_of_item = compte [i].
I si és així num_of_item és 2, significa que desitja inserir 2 de la sèrie i
en la nostra matriu ordenada.
Així que hem de fer un seguiment del lluny que estem en la matriu.
So = índex 0.
Array - Vaig a escriure.
Comptes -
array [índex + +] = i;
És això el que vols? Crec que això és el que vull.
Sí, això es veu bé. Bé.
Llavors, tothom entén el que el propòsit del meu compte és la matriu?
S'explica el nombre d'ocurrències de cada un d'aquests nombres.
Llavors estic iterar sobre aquesta matriu compte,
i la posició i-èsima de la matriu dels recomptes
és el nombre d'i és que hauria d'aparèixer en la meva matriu ordenada.
És per això que els recomptes de 4 serà un
i els recomptes de 8 serà 1, els recomptes de 23 serà 2.
Així és com molts dels que voleu inserir en el meu matriu ordenada.
Llavors m'acaba de fer això.
Estic inserint num_of_item is en la meva matriu ordenada.
>> Preguntes?
I així, un cop més, aquest és el temps lineal, ja que estem només iterar sobre un cop i
però també és lineal en el que aquest nombre passa a ser,
pel que en gran mesura depèn del que el seu límit és.
D'un salt de 200, que no és tan dolent.
Si el límit serà 10.000, llavors això és una mica pitjor,
però si el seu límit serà de 4 milions de dòlars, que és completament irreal
i aquest acord es va a haver de ser de mida 4 mil milions, la qual cosa és poc realista.
Així que això és tot. Preguntes?
[Resposta dels estudiants inaudible] >> Okay.
Em vaig adonar de res més quan estàvem passant.
Crec que el problema estava en Lucas, i probablement cada un que hem vist.
Em vaig oblidar del tot.
L'únic que volia comentar és que quan vostè està tractant amb coses com índexs,
vostè mai realment veure això quan vostè està escrivint un bucle for,
però tècnicament, quan vostè està tractant amb aquests índexs,
vostè ha gairebé sempre tracten amb nombres enters sense signe.
La raó d'això és quan vostè està tractant amb enters amb signe,
així que si vostè té 2 sencers amb signe i sumar-los
i acaben massa gran, llavors vostè acaba amb un nombre negatiu.
Així que això és el que és de desbordament de sencers.
>> Si afegeixo 2000000000 i 1 mil milions, terme amb negatiu 1 mil milions.
Així és com funciona en equips sencers.
Així que el problema amb l'ús -
Això està bé, excepte si baixa passa a ser de fins a 2 mil milions i passa a ser d'1 mil milions,
llavors això serà negatiu 1000000000 i després anem a dividir això per 2
i acabar amb negatiu 500 milions.
Així que això és només un problema si li passa que es busca a través d'una matriu
de milers de milions de coses.
Però si baixa + fins que passa el desbordament, llavors això és un problema.
Així que els fem sense signar, a continuació, 2 milions més de mil milions és de 3 milions de dòlars.
3000000000 dividit per 2 és de 1,5 milions de dòlars.
Així que tan aviat com estiguin sense signar, tot és perfecte.
I això és també un problema quan vostè està escrivint el seu bucles for,
i, de fet, és probable que ho faci de forma automàtica.
En realitat, s'acaba de cridar a tu.
Així que si aquest nombre és massa gran per ser just en un enter però cabria en un enter sense signe,
va a cridar a tu, així que per això mai et arribes a tenir el problema.
Es pot veure que l'índex mai serà negatiu,
així que quan vostè està interactuant sobre una matriu,
gairebé sempre es pot dir unsigned int i, però que en realitat no ha de fer-ho.
Les coses van a funcionar més o menys igual de bé.
Bé. [Xiuxiueja] Quina hora és?
L'últim que volia mostrar - i jo només vaig a fer-ho molt ràpid.
Saps com hem # defineix pel que pot definir # MAX com 5 o alguna cosa així?
No fem MAX. # Defineix OBLIGAT 200. Això és el que vam fer abans.
Això defineix una constant, que només serà copiat i enganxat
on ens ha tocat escriure OBLIGAT.
>> Així que en realitat pot fer més amb # defineix.
Hem # pot definir funcions.
No són realment funcions, però anomenarem funcions.
Un exemple podria ser alguna cosa com MAX (x, i) es defineix com (x <i i:? X). Bé.
Pel que s'ha d'acostumar a la sintaxi de l'operador ternari,
però és x menor que i? Torneu a, o torni x.
Així es pot veure que pot fer aquesta funció, per separat,
i la funció podria ser com bool MAX té 2 arguments, torni aquest.
Aquesta és una de les més comuns que veig fet així. Els anomenem macros.
Aquesta és una macro.
Això és només la sintaxi per a això.
Vostè pot escriure una macro per fer el que vulguis.
Es veuen amb freqüència per depurar macros printfs i aquestes coses.
Així que un tipus de printf, hi ha constants especials al carrer com subratllen LÍNIA subratllat,
2 subratlla LÍNIA subratllat,
i també cal pensar dos guions FUNC. Això podria ser. Una cosa per l'estil.
Aquestes coses es reemplaçarà amb el nom de la funció
o el nombre de la línia que et trobis.
Sovint, s'escriu printfs depuració que aquí em podria simplement escriure
DEBUG i s'imprimirà el nombre de línia i la funció que em toca estar en
que va trobar que la declaració DEBUG.
I també es pot imprimir altres coses.
Així que una cosa que has de tenir en compte és si se m'acut per definir # DOUBLE_MAX
alguna cosa així com 2 * i 2 * i x.
Així que per raó, li toca fer molt d'això.
Així que el converteixen en un macro.
Això és realment trencat.
Jo diria que és per fer alguna cosa com DOUBLE_MAX (3, 6).
Llavors, quin ha de ser retornat?
[Estudiant] 12.
Sí, 12 han de ser retornats, i 12 es torna.
3 és reemplaçat per x, 6 és reemplaçat per i, i tornem 2 * 6, que té 12 anys.
Ara, què passa amb això? Quin ha de ser retornat?
[Estudiant] 14. >> Idealment, 14.
La qüestió és que la forma de hash defineix el treball, recordi que és una còpia literal i enganxar
de gairebé tot, així que el que això serà interpretada com
és 3 menys que 1 més 6, 2 vegades 1 més 6, 2 vegades 3.
>> Així, per aquesta raó per la qual gairebé sempre envolten tot entre parèntesis.
Qualsevol variable que gairebé sempre envolten a parèntesi.
Hi ha casos en què no han de, com jo sé que no és necessari fer-ho aquí
perquè menys és gairebé sempre només es treballarà,
tot i que ni tan sols podria ser cert.
Si hi ha alguna cosa ridícul com DOUBLE_MAX (1 == 2),
llavors això quedarà substituït per 3 menys 1 és igual a igual a 2,
i pel que també farà 3 menys que 1, és igual que 2,
que no és el que volem.
Així que per evitar qualsevol problema de prioritat d'operador,
emboliqui sempre entre parèntesi.
Bé. I això és tot, 5:30.
Si vostè té alguna pregunta sobre el conjunt de processadors, contacteu amb nosaltres.
Ha de ser divertit, i l'edició pirata informàtic també és molt més realista
que l'edició pirata de la de l'any passat, així que esperem que molts de vostès ho intenti.
L'any passat va ser molt aclaparador.
>> [CS50.TV]