[Powered by Google Translate] [Article 4] [Menys Còmode]
[Nate Hardison] [Harvard University]
[Aquesta és CS50.] [CS50.TV]
>> Molt bé, benvinguts de nou a la secció.
A la secció d'aquesta setmana farem un parell de coses.
Anem a la primera sèrie de problemes recapitulació 2,
que és el conjunt de problemes Cèsar i Vigenère.
I després anem a bussejar en Concurs 0 opinió
i passar una mica de temps tornar a tapar el que hem parlat
en cadascuna de les classes fins ara, i farem uns quants problemes
de concursos de l'any anterior.
Així que vostès tenen una bona manera de preparar-se per això.
>> Per començar, he arrencat un parell de bones solucions
per al conjunt de problema anterior, problema setembre 2, en aquest espai.
Si vostès tots els afectats en aquest enllaç,
i si fa clic en el meu nom i feu clic a la meva primera revisió
veuràs caesar.c, que és exactament el que estic buscant.
Parlarem d'això molt ràpidament.
Això és només una solució de mostra.
Això no és necessàriament la solució perfecta.
Hi ha moltes maneres diferents d'escriure això,
però hi ha algunes coses que jo volia destacar
que vaig veure quan estava classificació, els errors més comuns que crec que
aquesta solució fa una feina molt bona de la direcció.
>> La primera és tenir algun tipus de comentari encapçalat a la part superior.
En les línies 1 a 7 veuen els detalls,
Què és exactament aquest programa està fent.
Una bona pràctica estàndard quan estàs escrivint codi C
sense tenir en compte si el seu programa està contingut en un sol arxiu o
si està dividit en diversos arxius és tenir algun tipus de
orientar comentari al cim.
Això és també per les persones que surten i a programar en el món real.
Aquí és on posaran la informació de drets d'autor.
A continuació s'inclou el #.
En la línia 16 no és això # defineix, que tornarem a una mica.
I després, una vegada que la funció s'inicia, una vegada que s'inicia principals,
ja que aquest programa ha estat tot contingut en una sola funció
la primera cosa que succeeix-i això és molt idiomàtic i típic d'un programa en C
que acull els arguments de línia de comandes-és que es comprova immediatament
>> per al recompte d'arguments, argc.
Aquí veiem que aquest programa està a l'espera 2 arguments exactament.
Recordeu que cal el primer argument és l'especial
que sempre és el nom del programa que està sent executat,
el nom del fitxer executable.
I el que això fa és que evita que l'usuari executi el programa
amb arguments més o menys.
La raó per la qual desitja comprovar això immediatament és perquè
en realitat no podem accedir a aquesta matriu argv aquí fiable
fins que haguem comprovat per veure el gran que és.
>> Un dels problemes més comuns que vaig veure va ser la gent immediatament aniria en
i apropiació de argv [1].
Havien agafar l'argument clau de la matriu i la hi a a i comprovar-hi,
i després es faria la prova per argc, així com la prova següent,
si el primer argument era de fet un nombre enter, alhora,
i això no funciona, perquè en el cas que no hi hagi arguments proporcionats
et agafar un argument que no hi és o intentar agafar un que no hi és.
>> L'altra cosa important que s'ha de notar és que
un sempre vol imprimir algun tipus de missatge d'error útil
per a l'usuari per orientar.
Estic segur que tinc tots els programes d'execució que de sobte es bloqueja,
i s'obté poc ridícul aquest quadre de diàleg que apareix i diu
alguna cosa terriblement críptic i potser et dóna un codi d'error o alguna cosa per l'estil
que no té sentit.
Aquí és on vostè realment vol oferir alguna cosa útil
i orientades a l'usuari perquè quan s'executi van "Oh," cara de palma.
"Sé exactament què fer. Sé com solucionar aquest problema."
>> Si no s'imprimeix un missatge i després s'acaba realment
deixant a l'usuari anar examinar seves fonts
per esbrinar el que va sortir malament.
També hi ha algunes vegades que vostè va a utilitzar diferents codis d'error.
Aquí hem usat un per dir que va ser un error,
es va produir un error, es va produir un error.
Programes més grans, sovint els programes que són cridats per altres programes,
tornarà algun tipus de codis d'error especials en diferents escenaris
per comunicar-se mitjançant programació quina altra manera
només ha d'utilitzar un missatge agradable per Anglès.
Cool.
A mesura que treballem cap avall, es pot veure que llençar la clau.
Posem a prova per veure si la clau encaixa.
Vam rebre un missatge de l'usuari.
La raó per la qual ho fem en aquest cicle do while, i això és una cosa que anem a cobrir
en poc poc, però resulta que si escriu control D
quan vostè aconsegueix que GetString del sistema en el terminal
el que en realitat fa és que envia un caràcter especial
per al programa.
Es crida l'ELF o el caràcter de fi d'arxiu.
I en aquest cas, la nostra cadena de missatge serà nul,
així que no va ser una cosa que ens registrem en el conjunt de problemes en si.
>> Però a mesura que avancem, ara que hem començat a parlar de punters
i l'assignació dinàmica de memòria en el munt,
comprovar la nul · la sempre que tingui una funció que podria
retornarà un valor nul com a valor és una cosa que vostè vol aconseguir en l'hàbit de fer-ho.
Això és aquí principalment per il · lustració.
Però quan vostè veu GetString en el futur,
per la qual cosa des del 4 de problemes, haurà de tenir això en ment.
Un cop més, això no és un problema per a qualsevol problema 3, ja que no havia cobert encara.
Finalment, arribem a aquesta part on tenim al bucle de xifrat principal,
i hi ha un parell de coses que succeeixen aquí.
En primer lloc, iterar sobre la cadena del missatge complet en si.
Aquí hem mantingut l'anomenada strlen en la condició,
que alguns de vosaltres heu assenyalat, no és un gran camí per recórrer.
Resulta que en aquest cas no ho és també gran,
en part perquè estem modificant el contingut del missatge en si mateix
dins del bucle for, de manera que si tenim un missatge que és 10 caràcters de longitud,
la primera vegada que comencis per bucle strlen tornarà què?
10.
>> Però si a continuació, modifiqui missatge, diguem de modificar el seu caràcter 5th,
i que tirem un caràcter \ 0 en la 5 ª posició,
en una iteració posterior strlen (missatge) no tornarà el que va fer
la primera vegada que va reiterar,
però en comptes tornaran 5 perquè llencem en aquest terminador nul,
i longitud de la cadena es defineix
per la posició que \ 0.
En aquest cas, aquesta és una gran manera d'anar perquè ho estem modificant al seu lloc.
Però t'adones que en realitat és sorprenentment senzilla per encriptar
si vostè pot aconseguir la matemàtica correcta.
Tot el que es requereix és comprovar si la carta que vostè està buscant en
és majúscula o minúscula.
>> La raó per la qual només has de comprovar això i no han de buscar
el cas és alfa és perquè
si un caràcter és en majúscules o minúscules si és
llavors és definitivament un caràcter alfabètic,
perquè no tenim xifres majúscules i minúscules.
L'altra cosa que fer, i això és una mica difícil-
és que hem modificat l'estàndard de xifrat César fórmula
que vam donar en l'especificació de problemes.
La diferència aquí és que ens resta
a la capital del cas en majúscules A, i després afegim majúscula
còpia en al final.
>> Sé que alguns de vosaltres heu fet això en el codi.
O molts de vostès fan això en les seves presentacions?
Tu vas fer això. Pot explicar el que això fa, Sahb?
Restant a terme, ja que va fer un mod dreta després d'ella,
cal treure'l, pel que d'aquesta manera s'obté [tos] posició.
I després afegint-ho més tard canviat amb el que vostè volia.
Sí, exactament.
Què Sahb va dir va ser que quan volem afegir
nostre missatge i la nostra clau junts
i després mod que, mod que per NUM_LETTERS,
si no augmentem el nostre missatge a la corresponent gamma de 0 a 25 en primer lloc,
llavors pot ser que acabi sobre d'aconseguir un nombre molt rar
perquè els valors que estem mirant quan mirem missatge [i],
quan ens fixem en el caràcter i del nostre missatge de text sense format,
és un valor dins d'aquest rang des 65-122
sobre la base dels valors ASCII per majúscules A a través de minúscules z.
I així, quan ho mod per 26 o per NUM_LETTERS,
ja que era el nostre # defineix dalt a la dreta aquí,
que ens donarà un valor que està en el rang de 0 a 25,
i necessitem una manera d'escalar després que una còpia de seguretat
i aconseguir que en el rang ASCII corresponent.
La forma més senzilla de fer-ho és a escala simplement tot sota
en el rang de 0 a 25, per començar,
i després canviar tot de nou fins al final.
>> Un altre error comú que he vist persones es produeixen és que
si no ho fan realment escalament immediat
i afegeix missatge i la clau junts i s'agreguen, per exemple,
en una variable char, el problema amb què
és des del missatge [i] és un nombre relativament gran per començar amb-
recorda que és almenys 65 anys si es tracta d'un caràcter en majúscula-
si vostè té una clau gran, diguem, una mena de 100,
i afegeix els 2 junts en un char signat vostè va a obtenir un desbordament.
Vostè va a obtenir un valor que és més gran que 127,
que és el major valor que una variable de tipus char pot contenir.
Un cop més, és per això que t'agradaria fer aquest tipus de coses, per començar.
Alguna gent té al voltant d'aquest cas, fent una cosa i si les proves
per veure si s'ha sobrepassat abans de fer-ho,
però d'aquesta manera es posa al voltant d'això.
I després, en aquesta solució que imprimeix tota la cadena en l'últim moment.
Altres persones ens va imprimir un caràcter alhora. Tots dos són impressionants.
En aquest punt, és el que vostès tenen alguna pregunta, algun comentari sobre això?
Coses que t'agraden, les coses que no t'agraden?
>> Jo tenia una pregunta.
Potser m'ho vaig perdre durant la seva explicació, però com funciona aquest programa
ometre els espais per a la connexió de la clau de la longitud del text?
Això és només Cèsar xifrat. >> Oh, em sap greu, si.
Sí, anem a veure això.
En el xifrat César ens van donar perquè pel fet que
només voltejat caràcters.
Només els va girar si estiguessin en majúscules o minúscules.
Vostès sentir molt bé sobre això?
Siéntase lliure de copiar aquesta casa, el pren,
comparar-lo amb el que vostès van escriure.
Sens dubte, no dubti en enviar preguntes sobre això també.
I un cop més, s'adonen que l'objectiu en aquest cas amb el seu problema estableix
no és fer vostès per escriure codi perfecte per als conjunts de problemes.
És una experiència d'aprenentatge. Si.
>> Tornar al do while, si és igual a null,
tan nul només significa res, simplement prem enter?
Null és un valor de punter especial,
i usem nul quan volem dir
tenim una variable punter que apunta al no-res.
I pel que generalment significa que aquesta variable, aquesta variable missatge
està buit, i aquí, perquè estem utilitzant el tipus CS50 cadena especial,
Quin és el tipus de sèrie CS50?
Has vist el que és quan David es va retirar la caputxa a la conferència?
És un covard, és un punter, oi?
Bé, sí. >> És un char *.
I així realment podem reemplaçar aquest
aquí amb el missatge char *,
i de manera que la funció GetString, sinó amb èxit obtenir una cadena de l'usuari,
no es pot analitzar una cadena i un cas en el qual no es pot analitzar una cadena
és que si l'usuari escriu el caràcter de fi d'arxiu, el D control,
que no és una cosa que solen fer, però si això succeeix
llavors la funció retornarà el valor nul com una forma de dir
"Escolta, no he tingut una cadena."
Què passaria si no posem missatge = null,
que és una cosa que no hem estat fent ja?
Per què seria això un problema?
Perquè sé que parlem una mica en la conferència sobre pèrdues de memòria.
Sí, farem això, i ja veurem què passa.
>> Basilio era qüestió què passa si en realitat no tenen
aquest missatge = prova nul · la?
Anem a desplaçar-se fins la part superior.
Vostès poden comentar això.
En realitat, ho vaig a guardar en una revisió.
Aquesta serà la Revisió 3.
Què has de fer per executar aquest programa és que vostè ha de fer clic en aquesta icona es preparen aquí,
i que cal afegir un argument a la mateixa.
Vas a haver de donar-li l'argument clau, ja que volem passar en un argument de línia d'ordres.
Aquí em vaig a donar el número 3. M'agraden 3.
Ara el zoom de tornada, l'execució del programa.
S'està executant, la compilació, la construcció.
Aquí anem. S'espera que s'indiqui.
Si escric en alguna cosa com hola-on va ser?
Oh, el meu programa va trigar massa temps a executar-se. Em jawing durant massa temps.
Heus aquí.
Ara escric en hola.
Veiem que el xifra adequada.
Ara, què passa si fem GetString del sistema per tornar nul?
Recorda, vaig dir que ho vam fer prement control D a la vegada.
Vaig a desplaçar-se fins aquí. Anem a córrer de nou.
Construcció. Aquí va.
Ara bé, quan vaig arribar a control D
Tinc aquesta línia que diu opt/sandbox50/bin/run.sh, fallada de segmentació.
Han vist això abans?
>> [Estudiant] Per què no->> Ho sentim?
[Estudiant] Per què no hi ha un bolcat de memòria en aquest cas?
El bolcat de memòria és-la pregunta és per què no hi ha un bolcat de memòria en aquesta llista?
La qüestió és que no pot ser, però el buidatge de memòria és un arxiu
que s'emmagatzema en el disc dur.
En aquest cas hem desactivat els bolcats de memòria
al servidor d'execució perquè no hi hagi persones seg falles
i la creació de tones de bolcats de memòria.
Però vostè pot aconseguir un.
Els buidats de memòria són el tipus de coses que sovint es pot desactivar,
i de vegades ho fa.
La decisió de segmentació, per respondre a la seva pregunta, Basil,
és a dir que tractem d'accedir a un punter
que no s'ha configurat perquè apunti a res.
Recordi Binky en el vídeo quan intenta Binky
anar accedir a un punter que no està apuntant a alguna cosa?
En aquest cas crec que, tècnicament, el punter apunta a alguna cosa.
S'apunta a null, el que tècnicament és 0,
però que es defineix a estar en un segment que no és accessible
pel seu programa, per la qual cosa obtenir una fallada de segmentació
perquè no s'està accedint a la memòria que està en un segment vàlid
com el segment de munt o el segment de la pila o el segment de dades.
Cool.
Alguna pregunta més sobre Cèsar?
>> Seguirem endavant. Fem una ullada a la Revisió 2 molt ràpid.
Això és Vigenère.
Aquí a Vigenère
anem a caminar a través d'aquest amb força rapidesa, ja que, de nou,
Vigenère i César són bastant similars.
COMENTARI DE CAPÇALERA és abans,
# Defineix és abans per evitar l'ús d'aquests nombres màgics.
El millor és dir que volia anar a
un alfabet diferent o alguna cosa per l'estil.
En lloc d'haver d'anar a canviar manualment tots els 26 en el codi
podríem canviar això a 27 o caure cap avall
si estiguéssim usant alfabets diferents, llengües diferents.
Un cop més, tenim la comprovació del recompte d'arguments,
i realment gairebé es pot prendre això com una plantilla.
Gairebé tots els programes que vostè escriu ha de tenir-
si es pren arguments de línia de comandes-alguna seqüència de línies
que diu així des del principi.
Aquesta és una de les proves de seny primer que vull fer.
>> Aquí el que vam fer va ser que es va assegurar que
la paraula clau és vàlida, i que va ser el segon xec que ens va fer.
Noti de nou que ens separem això des argc i 2.
Tingueu en compte que en aquest cas una cosa que havia de fer era lloc
de la utilització d'un a i volíem per validar la cadena completa,
i amb la finalitat de fer que vostè realment ha d'anar caràcter per caràcter
sobre la cadena.
No hi ha una bona manera de cridar a alguna cosa en ell
perquè fins i tot, per exemple, una i tornarà a 0
si no es pot analitzar un nombre enter, de manera que ni tan sols funciona.
De nou, bonic missatge indicant a l'usuari exactament el que va succeir.
Llavors aquí, de nou, també s'ocupen dels casos en
l'usuari escriu un caràcter de control D aleatori.
>> I llavors Charlotte tenia una pregunta anterior sobre la manera com gestionem per saltar espais
en la nostra cadena aquí.
Això va ser una mica semblant al que vam fer amb el programa de Myspace
que vam fer a la secció, i va treballar la manera com aquest
és que ens va tornar la quantitat de lletres que havíem vist.
A mesura que entrem en la cadena del missatge, ja que caminem sobre el caràcter per caràcter,
ens va tornar l'índex com a part del nostre bucle for, i després ens va tornar també
el nombre de lletres, de manera que no caràcters especials, que no són nombres, no blanc l'espai
que havíem vist en la variable independent.
I a continuació, aquesta solució modifica la clau
per obtenir un enter de clau real, i ho fa sobre la marxa,
just abans que després es torna a xifrar el caràcter real del missatge.
Hi ha algunes solucions que eren perfectament genials
que modificaria la tecla de dalt quan les proves de validesa de la clau.
A més d'assegurar-se que el caràcter i la paraula clau
va ser un caràcter alfabètic que també el va convertir en un enter
en el rang de 0 a 25 per saltar llavors haver de fer que més endavant en aquest bucle.
Un cop més, veiem aquí és realment el mateix codi
que es va utilitzar en Caesar en aquest punt.
El estàs fent exactament el mateix, així que el veritable truc és trobar la
com convertir la paraula clau en un nombre sencer.
>> Una cosa que hem fet aquí és una mica dens
És hem repetit aquesta frase, suposo que es podria anomenar,
3 vegades per separat en les línies 58, 59, i 61.
Pot algú explicar què és exactament aquesta frase fa?
S'accedeix a un personatge, com vas dir.
Sí, és [inaudible] un personatge de la paraula clau,
i el que és el nombre de cartes vist perquè només estàs movent al llarg de
la paraula clau una vegada que hagi vist la carta,
pel que passarà amb eficàcia els espais i coses per l'estil.
Sí, exactament.
I després, un cop que hagi vist la paraula clau en blanc que acaba de mod pel que tornar al seu voltant.
Exactament. Aquesta és una explicació perfecta.
¿Què va dir Kevin és que volem indexar a la paraula clau.
Volem obtenir el caràcter num_letters_seen, si es vol,
però si num_letters_seen excedeix la longitud de la paraula clau,
la forma de tornar al rang apropiat és que utilitzi l'operador mod
per embolicar eficaçment voltant.
Per exemple, igual que en el curt, la nostra paraula clau és cansalada,
i és a 5 lletres.
Però hem vist 6 cartes al nostre text pla en aquest moment
i encriptada 6.
Acabarem l'accés a la num_letters_seen,
que és 6, mod la longitud de la paraula clau, 5,
i el que aconseguirem 1, i així ho farem és que anem a
accedir a l'interior del primer caràcter de la nostra paraula clau en aquest punt.
>> Molt bé, qualsevol pregunta sobre Vigenère
abans de seguir endavant?
Vostès sentir molt bé sobre això?
Genial, genial.
Vull per assegurar-se que vostès estan rebent l'oportunitat de veure el codi
que creiem que es veu bé i tenir l'oportunitat d'aprendre d'ell.
Això serà l'última vegada que utilitzarà espais per al moment,
i anem a la transició, i jo aniré a cs50.net/lectures
perquè puguem fer una mica de revisió quiz.
La millor manera que crec que començar a fer test opinió
que ha de venir a aquesta pàgina Conferències, cs50.net/lectures,
i sota de cadascuna de les partides setmana, així que si em veig aquí a la setmana 0,
Veig que tenim una llista de temes que cobrim a la setmana 0.
>> Si qualsevol d'aquests tòpics semblen poc familiars
que sens dubte voldrà tornar enrere i buscar en les notes de classe i, possiblement,
fins i tot llegir-lo a través de les conferències, de veure de nou si voleu
per tenir una idea del que està passant amb cada un d'aquests temes.
Diré, a més, aquest any un dels recursos frescos que tenim
Són aquests pantalons curts que hem creat, i, si ens fixem en la setmana 0
no tenim tots els temes tractats, però tenim un bon nombre d'ells,
alguns dels més difícils, així a veure aquests curts de nou
és una bona manera de posar-se al dia.
En particular, em vaig a posar en un endoll per al 3 a la part inferior, des que vaig fer això.
Però si vostè està lluitant amb el binari, bits, hexadecimal, aquest tipus de coses,
binari és un gran lloc per començar.
ASCII és un altre que és bo per veure també.
Fins i tot pots mirar-me a la velocitat de 1.5x si vaig massa lent per a vostè.
Des de la seva opinió, no dubti en fer-ho.
>> Només per començar molt ràpid, anirem a través d'un parell d'aquests problemes concursos
només per batre ràpidament a través d'aquests.
Per exemple, considerem el cas a 16 problema que tinc aquí dalt al tauler.
Tenim aquest càlcul següent en binari,
i volem mostrar qualsevol treball.
Bé, jo vaig a donar a aquest un tret.
Vostès haurien de seguir juntament amb el paper,
i farem això molt ràpidament.
Volem fer el següent càlcul en binari.
Tinc 00110010.
I vaig a afegir a 00110010.
Per als càlculs genis seguint al llarg a casa,
aquest és efectivament multiplicant per 2.
Anem a començar.
Seguirem el mateix algorisme d'addició que fem
quan sumem nombres decimals entre si.
Realment l'única diferència aquí és que la tornada de bucle
una vegada que tenim 1 + 1 en lloc d'una vegada que arribem a 10.
>> Si partim de la dreta, molt ràpid, quin és el primer dígit?
[Estudiant] 0. >> [Nate H.] 0.
Gran, el segon dígit?
[Estudiant] 1.
[Nate H.] Es tracta d'un 1? 1 + 1 és?
[Estudiant] 10.
[Nate H.] Exactament, quin és el dígit que escric a sota dels 2 sumen?
[Estudiant] 1, 0, o 0 i després portar a la 1.
[Nate H.] 0 i portar a 1, exactament.
El proper un, Basil, que estàs fent.
Quina és la tercera? >> [Basil] 1.
[Nate H.] 1, perfecte. Kevin?
[Kevin] 0. >> [Nate H.] 0, Charlotte?
[Charlotte] 0. >> [Nate H.] Sí, i què faig?
[Estudiant] L'1.
[Nate H.] I què faré? I llavors em porti l'1.
Perfecte, Sahb? >> [Sahb] Ara vostè té 1.
[Nate H.] I Puc fer alguna cosa aquí?
[Sahb] Llavors, d'una banda té 1 perquè et porta a més de 1.
[Nate H.] Great, així que aquí podem acabar.
Cool.
[Estudiant] Té 0 + 0 = 0?
0 + 0 = 0.
1 + 1, com vostè ha dit, és de 10, o 1, 0, més ben dit.
10 és un nom poc apropiat perquè per a mi significa el número 10 10,
i és la peculiaritat de la manera com ho està representant quan estem escrivint.
Ens representen el número 2 per 1, 0, i el nombre 10 és lleugerament diferent.
>> Què és una espècie d'agradable sobre binari és que realment no són molts
casos, cal aprendre.
Hi ha 0 + 0 = 0, 0 + 1 = 1,
1 + 1 és 0, i després portar a un 1,
i llavors vostè pot veure aquí a la tercera columna de la dreta
hem tingut aquest 1, 1 i 1.
I 1 + 1 + 1 és un 1,
i portar a un altre 1.
Quan vostè està fent la suma binària, bastant simple.
M'agradaria fer un parell més al seny comprovar vosaltres mateixos
abans d'anar ja que és
probablement alguna cosa que veurem en el qüestionari.
Ara farem això que ve.
Farem problema 17.
Anem a convertir el següent nombre binari a decimal.
Tinc 10100111001.
Recordeu que en el vídeo que vaig fer binari
Vaig caminar a través d'un parell d'exemples, i em va mostrar com
tot funciona quan vostè ho està fent en decimal.
Quan es treballa en la representació decimal Crec que estem
en aquest moment de les nostres vides tan fluid en el que
que és bastant fàcil de passar per alt la mecànica de com funciona realment.
>> Però per fer un resum ràpid, si tinc el número 137
això significa realment, i de nou, això és en la representació decimal-
el número 137 en decimal significa que tinc 1 x 100 + 3 x 10 + 7 x 1.
Això és tot romandre a la pantalla.
I després, si ens fixem en els números aquí,
100, 10 i 1, es veu que en realitat són totes les potències de 10.
Tinc 10 ², 10 ¹, i 10 per al zero.
Tenim un tipus similar de coses en binari,
excepte que la nostra base, com l'anomenem, és a 2 en lloc de 10.
Aquests resultats entre els 10 que he escrit fins aquí a la part inferior,
aquesta ² 10, 10 ¹, 10 per al zero, 10 és la nostra base,
i l'exponent, 0, 1, o 2,
està implícit en la posició del dígit en el nombre que s'escriu.
1, si ens fixem en ell, aquest 1 es troba a la 2 ª posició.
El 3 està en la posició primera, i el 7 està a la posició 0 ª.
Així és com s'obtenen els exponents que figuren a continuació per a les nostres bases.
>> Arran de tot això ens tornarem-en realitat, saps què?
Ho farem-on va ser la meva botó de desfer anar?
Aquí va.
M'encanta aquesta cosa desfer.
Després d'això crec que per a mi almenys
la forma més fàcil d'iniciar la conversió d'un nombre binari
o un nombre hexadecimal on la base és 16
i no 10 o 2 és seguir endavant i escriure
les bases i exponents per a tots els nombres en el meu número binari a la part superior.
Si partim d'esquerra a dreta, de nou,
que és una mica contradictori,
Vaig a tornar al negre aquí, tenim la 2 a la posició 0 ª,
i llavors tenim 2 ¹, 2 ²,
i després 2 a la 3, 2 a la 4, 2 a la 5, 6,
7, 8, 9, i 10.
Aquests números que he escrit fora són tots els exponents.
Jo només vaig escriure les bases aquí en els 3 primers només per l'espai.
>> En aquest moment em vaig a seguir endavant i de fet vaig a esborrar
les coses que vam fer en decimal, si et sembla bé.
Tots vostès han entendre.
Aquells de vostès veient en línia Estic segur que serà capaç de rebobinar si em vols.
Canvi a la ploma.
Ara, què podem fer, si vostès no estan totalment al dia en les seves potències de 2,
això és totalment cool.
Succeeix. Entenc.
Un cop vaig tenir una entrevista de treball on em van dir que he de saber totes les potències de 2
a través de 2 al 30.
No era una feina que tinc.
De tota manera, vostès poden seguir endavant i fer els càlculs aquí,
però amb el binari que no té molt sentit,
i tampoc té sentit amb decimal o hexadecimal o bé,
per fer els càlculs d'on té zeros.
Vostè pot veure que tinc 0 aquí, un 0 aquí, aquí 0, 0 aquí, aquí 0, 0 aquí.
Per què no podria tenir sentit per fer els càlculs real
per calcular la potència apropiada de 2 per a aquesta posició?
Exactament com va dir Charlotte, serà 0.
Podria estalviar-se el temps si el càlcul de potències de 2 no és el seu punt fort.
En aquest cas, només haurà de calcular per 2 a 0, que és el-?
[Estudiant] 1.
[Nate H.] 1, 2 a la 3 que és-?
[Estudiant] 8. >> [Nate H.] 8.
2 a la 4?
[Estudiant] 2. Em sap greu, 1.
[Nate H.] 2 a la 4 és 16, exactament.
2 a la 5, Kevin? >> 32.
[Nate H.] 32, 2 a la 8?
[Estudiant] 32 x 8, 256.
[Nate H.] Perfect.
I 2 als 10?
[Estudiant] 1024.
[Nate H.] Sí, 1024.
>> Quan tenim aquests nombres podem resumir.
I aquí és on és molt important fer un parell de coses.
Una d'elles és anar lent i revisar el seu treball.
Es pot dir que hi ha un 1 al final d'aquest número,
així que definitivament ha d'obtenir un nombre imparell com el meu resultat,
perquè tots els altres seran nombres parells
atès que es tracta d'un nombre binari.
L'altra cosa a fer és si s'arriba a aquest punt de la prova
i ho has escrit fins aquí
i que està acabant el temps
mirar el nombre de punts que aquest problema val la pena.
Aquest problema, com es pot veure, si li dono la volta al meu ordinador portàtil molt ràpid-
aquest problema val 2 punts, de manera que aquest no és el tipus d'addició
vostè ha d'anar a través si vostè està realment pressionat pel temps.
Però anem a tornar a la iPad, i anirem a través d'ell molt ràpidament.
>> M'agrada fer els números curts primer
perquè em sembla que sigui més fàcil.
M'agrada 32 i 8 perquè van de la mà amb força facilitat, i obtenim 50.
16 i 1 es 17.
No tenim 57 anys,
i llavors podem fer la resta d'això, així que podem fer 57, 156.
Anem.
L'home, bé, anem a veure.
Vam tenir 57, 256 i 1024.
En aquest punt, que prefereixo passar.
No tinc ni idea. Jo clarament que llegir sobre això.
7, 6 i 4, s'obté 17.
1, 5, 5, 2, 13.
Llavors tenim 3, i llavors tenim 1.
1337.
Ou de Pasqua, a ningú?
Algú reconeix aquest número?
Chris reconeix el nombre. Què significa això, Chris?
[Chris] Leet.
Leet, així que si vostè mira això, sembla que leet.
Hacker coses. Compte amb aquest tipus de coses en el mitjà termini o el concurs, millor dit.
Si vostè veu aquest tipus de coses i que s'estigui preguntant "Eh,"
que en realitat podria significar alguna cosa.
No. David li agrada posar polz
És una bona manera de comprovar seny.
Com bé, puc veure el que està passant.
>> Aquesta és la Setmana 1 0/Week coses.
Si canviem de nou al nostre ordinador portàtil ara,
allunyar la imatge, i un parell d'altres coses.
Hi ASCII, el que hem estat fent un munt dels butlletins de problemes.
Aquesta noció de capital A. Què és això realment?
Sabent que és l'enter decimal.
65 és el que s'assigna a la taula ASCII,
i això és per tant l'equip com l'escriu,
i així és com hem estat sortint amb la realitat escrivint
la capital caràcter A i el caràcter a minúscula
en algunes d'aquestes solucions i conjunts de problemes que has estat fent.
Un parell de coses més.
Tenim declaracions, expressions booleanes, condicions, bucles, variables i fils.
>> Aquells tot sembla tenir sentit en la seva major part?
Part d'aquesta terminologia és una mica estrany de vegades.
M'agrada pensar que de la declaració de la majoria dels casos, aquest acaba amb un punt i coma.
Declaracions com x = 7, que estableix una variable,
presumiblement anomenat x = 7.
És de suposar que x és també un tipus que pot emmagatzemar el número 7,
per la qual cosa és un int o un float o possiblement un curtcircuit o una xerrada,
alguna cosa per l'estil.
Una expressió booleana és l'ús d'aquests dos és igual a
i l'explosió igual als iguals o no, menor que, major que,
menys de o igual a, tot aquest tipus de coses.
Les condicions són, llavors, les declaracions if else.
M'agradaria recordar que no es pot tenir una cosa sense la corresponent if.
De la mateixa manera, no es pot tenir una cosa sense la corresponent si si.
Loops, recordar els 3 tipus de llaços que hem estat treballant molt dur en tu
des de fa un parell de seccions i dels butlletins de problemes.
Usant fer mentre que vostè està rebent dades de l'usuari,
Utilització de bucles while fins que una determinada condició és veritable,
i després usant els bucles for si necessita
saber què iteració del bucle Actualment es troba en és com jo penso.
O si vostè està fent una per cada caràcter en una cadena que vull fer alguna cosa,
per a cada element d'una matriu que vull fer alguna cosa a aquest element.
>> Temes i esdeveniments.
Aquests no hem cobert en forma explícita en C,
però recorda això des del principi.
Aquesta és la idea de tenir diferents scripts.
Això també és aquesta noció de radiodifusió d'un esdeveniment.
Hi ha gent que no va fer ús de la radiodifusió en els seus projectes inicialment,
la qual cosa és totalment cool,
però aquestes són dues maneres diferents de manejar aquest problema més gran anomenada la concurrència,
que és com s'arriba a executar els programes de
o aparentment executar a la vegada?
Diferents tasques en execució mentre altres tasques també estan en marxa.
Així és com el sistema operatiu sembla que funciona.
Aquesta és la raó, encara que, per exemple,
Tinc el meu navegador que s'executa, també pot convertir-se en Spotify i reproduir una cançó.
Això és més d'una cosa conceptual d'entendre.
M'agradaria fer una ullada als temes curts
si vols aprendre més sobre això.
>> A veure, crec que podria haver estat
un problema en aquesta en un d'aquests.
Un cop més, crec que les discussions i esdeveniments que no són una cosa que anem a cobrir en C
només perquè és molt més difícil que en Scratch.
No ha de preocupar-se per aquí, però sens dubte a comprendre els conceptes,
entendre el que està passant.
Abans de seguir endavant, qualsevol pregunta sobre la Setmana 0 materials?
Tothom sent bastant bé?
Comprensió de les variables i el que és una variable?
>> Canviant de tema. Setmana 1.
Un parell de coses aquí que no van ser coberts en particular
en la revisió i prova necessàriament també hi ha coses més conceptuals que pensar.
El primer és la noció del que el codi font, compiladors i el codi objecte són.
Algú? Basil.
És de codi objecte, vull dir, el codi font és el que posa en clang,
i el codi objecte és el que posa so metàl · lic de manera que l'ordinador pot llegir el programa.
Exactament.
El codi font és el codi C que en realitat s'escriu dalt.
El codi objecte és el que hi ha de so metàl · lic.
És el 0 i 1 en quin format binari.
Llavors el que passa és quan vostè té un munt d'arxius d'objectes,
dir que s'està compilant un projecte o un programa que utilitza diversos arxius de codi font,
que per convenció se'ls dóna l'extensió. c arxiu.
És per això que tenim vigenère.c caesar.c,.
Si va a escriure programes en Java se'ls dóna l'extensió. Java.
Programes Python tenen l'extensió. Py freqüència.
>> Una vegada que tingui els arxius c múltiples., De compilar.
Clang escup tota aquesta brossa binària.
Llavors, ja que només volen un programa
teniu l'enllaç enllaçador tots aquests fitxers objecte junts
en un arxiu executable.
Això és també el que passa quan s'utilitza la biblioteca CS50, per exemple.
La biblioteca CS50 és al mateix temps que. Arxiu de capçalera h
que llegeixi, que # includecs50.h.
I també és un arxiu binari de la biblioteca especial
que ha estat compilat que és 0s i 1s,
i que-l, de manera que si ens remuntem als nostres espais i esperem realment ràpid
al que està passant aquí quan mirem al nostre abast clang,
el que tenim és que aquest és el nostre arxiu de codi font aquí.
Es tracta d'un munt d'opcions del compilador.
I després, al final, aquests-l enllaç banderes en
els arxius binaris reals d'aquestes dues biblioteques, la biblioteca del CS50 i després la biblioteca matemàtica.
>> Entendre cada tipus d'objecte files '
en el procés de compilació és una cosa que vostè vol ser capaç de
donar almenys un resum d'alt nivell de.
Codi font Codi objecte entra surt.
Arxius de codi objecte unir, i s'obté un arxiu de bell, executable.
Cool.
Aquí és també on vostè pot obtenir errors en múltiples punts
en el procés de compilació.
Aquí és on, per exemple, si vostè pren aquesta bandera d'unió,
la bandera CS50, i el omet en espais o quan s'està executant el codi,
aquí és on vostè obtindrà una errada en la fase de vinculació,
i el vinculador dir: "Escolta, et va cridar una funció GetString
que està a la biblioteca CS50 ".
"Em vas dir que estava a la biblioteca CS50, i no puc trobar el codi per a això".
Aquí és on cal relacionar, i això és independent
d'un error de compilació perquè el compilador està mirant sintaxi i aquest tipus de coses.
És bo saber el que està passant quan.
>> Altres coses que ha de saber.
Jo diria que ha de fer una ullada a la breu sobre encasellament realitzat per Jordan
per entendre el que són sencers sota el capó,
quins caràcters estan sota el capó.
Quan parlem de ASCII i realment es veuen a la taula ASCII,
el que està fent ens està donant una mirada sota el capó
la manera com l'equip representa en realitat majúscula i el dígit 7
i una coma i un signe d'interrogació.
La computadora també té maneres especials per representar
el número 7 com un nombre enter.
Té una forma especial per representar el nombre 7 com un nombre de punt flotant,
i els que són molt diferents.
Encasellament és la forma de dir-li a l'ordinador "Hey, vull que converteixis
d'una representació a una altra representació. "
Per què no fer una ullada a això.
>> També m'agradaria fer una ullada a la breu sobre les biblioteques i la talla en els compiladors.
Els que parlen del procés de compilació,
què és una biblioteca, i repassar algunes de les preguntes que potser et vaig preguntar.
Preguntes sobre la Setmana 1 material?
Hi ha temes que aquí semblen enormes proporcions que li agradaria cobrir?
Estic tractant de bufar a través de la majoria d'aquests temes anteriors perquè puguem arribar a
punters i fer una mica de recursivitat.
Pensaments?
Qualsevol cosa de cobrir?
Temps per una mica de xocolata potser?
Vostès estan treballant a través d'ell.
Jo seguiré bevent meu cafè.
Setmana 2.
Bona idea, bona idea.
A la setmana 2 parlem una mica més sobre les funcions.
>> En els butlletins de problemes primeres que realment no entrar cap funció en absolut
excepte que la funció?
[Estudiant] Principal. >> Principal, exactament.
I pel que hem vist els diferents vestits que vesteix principal.
No és l'únic en el que no pren cap argument,
i acabem de dir nul · la entre els parèntesis,
i després hi ha l'altre en el qual volen prendre els arguments de línia de comandes,
i com hem vist, aquí és on tens int argc i argv matriu de cadenes
o ara que hem estat realment exposats a ser la cadena char * que és
anem a començar a escriure com char * argv i després entre parèntesi.
En Butlletí de problemes 3, vostès van veure un munt de funcions,
i ha implementat un munt de funcions, dibuixar, mirar cap amunt, scramble.
Els prototips van ser escrits allà per a vostè.
>> El que jo volia parlar aquí amb funcions molt ràpid
és que hi ha 3 parts d'ells cada vegada que escrius una funció.
Heu d'especificar el tipus de retorn de la funció.
Ha d'especificar un nom per a la funció, i llavors vostè ha d'especificar
la llista d'arguments o la llista de paràmetres.
Per exemple, si jo hagués d'escriure una funció per resumir un munt de nombres enters
i després torna a mi la suma que seria el meu tipus de retorn
si volia sumar nombres enters i després tornar la suma?
A continuació, el nom de la funció.
Si segueixo endavant i escriure en verd, aquesta part és el tipus de retorn.
Aquesta part és el nom.
I després entre parèntesi
és on em donen els arguments,
sovint abreujat com arguments, de vegades anomenat params per als paràmetres.
I si vostè té un, vostè només ha d'especificar l'elegit.
Si té diversos de separar cadascun amb una coma.
I per a cada argument que li donen 2 coses que són-Kevin?
[Kevin] Cal donar el tipus i després el nom.
I després el nom, i el nom és el nom que s'utilitzarà
per referir-se a aquest argument dins de la funció suma,
dins de la funció que s'està escrivint actualment.
>> Vostè no ha de, per exemple, si jo vaig a resumir,
per exemple, una matriu d'enters-nosaltres fem array int,
i em vaig a donar algunes claus no-
després quan passa una matriu a la funció suma
El pas a la primera posició de la llista d'arguments.
Però la matriu de passar a no ha de tenir el nom arr.
Arr serà com es refereixen al fet que l'argument dins el cos de la funció.
L'altra cosa que cal tenir en compte,
i això és una mica diferent de funcions, però crec que és un punt important,
és que en C quan estic escrivint una funció com aquesta
Com puc saber quants elements hi ha en aquesta sèrie?
Això és una cosa d'una pregunta capciosa.
Hem parlat d'això una mica en la secció de la setmana passada.
Com puc saber el nombre d'elements dins d'un array en C?
Hi ha alguna manera?
>> Resulta que no hi ha manera de saber-ho.
Vostè ha de passar per separat.
Hi ha un truc que pots fer
si estàs en la mateixa funció en la qual s'ha declarat la matriu,
i es treballa amb una àmplia llar de foc.
Però això només funciona si vostè està en la mateixa funció.
Quan es passa una matriu a una altra funció o si s'ha declarat una matriu
i poses aquesta matriu en la pila, que ha utilitzat malloc
i aquest tipus de coses, totes les apostes estan apagades.
Llavors vostè realment ha de trigar
un argument especial o un altre paràmetre
que li diu què tan gran és la matriu.
En aquest cas, m'agradaria utilitzar una coma-ho sento, que va fora de la pantalla aquí-
i m'agradaria passar en un altre argument
i en diuen int len ​​per a la longitud.
>> Una cosa que pogués sorgir en l'examen
Se li demanarà que escrigui o implementar una funció particular que es diu alguna cosa així.
Si nosaltres no li donem el prototip, de manera que tot això aquí,
tot aquest embolic es diu la declaració de la funció o el prototip de funció,
aquesta és una de les primeres coses que vostè voldrà concretar si no se li dóna
a vostè immediatament al qüestionari.
L'altre truc que he après és que
diuen que et donen un prototip per a una funció, i diem: "Escolta, has d'escriure".
Dins de les claus que té en el qüestionari
si vostè nota que hi ha un tipus de retorn i nota que el tipus de canvi
és una mica diferent de buit, el que significa que la funció no retorna res,
llavors una cosa que ha de fer és escriure
algun tipus d'instrucció de retorn al final de la funció.
Retorn, i en aquest cas, posarem un espai en blanc, perquè volem omplir l'espai en blanc.
Però això posa a pensar en la manera correcta de com vaig a abordar aquest problema?
I et recorda que hauràs de retornar un valor
a la crida de la funció.
>> Si. >> [Estudiant] L'estil s'apliquen quan estem escrivint codi en el concurs?
Com sagnia i aquest tipus de coses? >> [Estudiant] Yeah.
No, no com a molt.
Crec que molt d'això és una cosa que anem a aclarir en la prova en el dia de,
però en general inclou preocupar per # i aquest tipus de coses, és una espècie de fora.
[Estudiant] Cal comentar el seu codi escrit a mà?
És necessari comentar el seu codi escrit a mà?
Comentant sempre és bo si vostè està preocupat sobre el crèdit parcial
o desitja comunicar la seva intenció a la motoanivelladora.
Però, de nou, s'aclarirà en el propi concurs i en el dia de concurs,
però no crec que se li requereix per escriure comentaris, no.
Normalment no, però sens dubte és el tipus de coses que
pot comunicar la seva intenció, com "Hey, aquí és on em vaig amb ell."
I de vegades això pot ajudar amb crèdit parcial.
Cool.
>> Basil.
[Basil] Quina és la diferència entre declarar, per exemple, int lang
en els arguments o paràmetres de comparació que es declara una variable dins de la funció?
Wow, cafè va baixar la tràquea.
[Basil] Igual que les coses que volem posar en arguments.
Sí, aquesta és una gran pregunta.
Com es tria quines coses vols posar en els arguments
davant les coses que vostè ha de fer dins de la funció?
En aquest cas es van incloure tant d'aquests com arguments
perquè són una cosa que tot el que es va a utilitzar la funció de suma
d'especificar aquestes coses.
>> La funció de suma, com hem parlat, no té manera de saber
què tan gran és la matriu que rep del seu interlocutor o de qui està utilitzant la funció suma.
No té forma de saber què tan gran és aquesta matriu.
La raó per la qual vam passar en aquesta longitud d'aquí com un argument
és perquè això és una cosa que bàsicament estem dient al picador de la funció,
qui es va a utilitzar la funció de suma, "Hey, no només vostè ha de donar-nos una matriu
d'enters, vostè també ha de dir-nos com de gran és la matriu que vostè ens ha donat és ".
[Basil] Els dos estaran arguments de línia de comandaments?
No, aquests són arguments reals que li passen a la funció.
>> Permetin-me fer una nova pàgina aquí.
[Basil] Igual nom passaria-
[Nate H.] Si tinc int main (void)
i em posaré en el meu retorn 0 fins aquí a la part inferior,
i dic que vull cridar a la funció suma.
Vull dir int x = sum ();
Per utilitzar la funció suma he de passar tant en la matriu que vull resumir
i la longitud de la matriu, pel que aquí és on
suposant que tenia una sèrie d'enters,
dir que tenia int numbaz [] = 1, 2, 3,
tipus d'ús que hacker sintaxi allà mateix,
llavors el que vull fer és en resum m'agradaria passar a
tant numbaz i el número 3
per dir-li a la funció sum "Bé, aquí hi ha la matriu Vull sumar."
"Aquí està la seva mida".
Això té sentit? Respon això a la seva pregunta?
>> En molts sentits, ho fa paral · lel el que estem fent amb els principals
quan tenim els arguments de la línia d'ordres.
Un programa com el xifrat César, per exemple, que cal
arguments de línia d'ordres no seria capaç de fer qualsevol cosa.
No sabria com xifrar si no l'hi vaig dir a ella que tecla utilitzar
o si no l'hi digui quina cadena que volia xifrar.
Sol · licitud d'una entrada, aquí és on tenim dos mecanismes diferents
per a la presa d'entrada des de l'usuari, per prendre la informació des de l'usuari.
Per problemes n 1 vam veure aquest getInt, GetString, forma GetFloat
de sol · licitud d'una entrada, i que es diu mitjançant la seqüència d'entrada estàndard.
És una mica diferent.
És una cosa que es pot fer d'una sola vegada en lloc de
en invocar el programa, en iniciar el programa en execució.
Els arguments de línia d'ordres tot s'especifiquen quan s'inicia el funcionament del programa.
Hem estat barrejant els dos.
Quan fem servir arguments a una funció, que és molt similar als arguments de línia de comandes al principal.
És quan s'invoca la funció que cal dir
què és exactament el que necessita per dur a terme les seves tasques.
Una altra cosa agradable a la vista i et deixaré veure en el seu temps lliure,
i va ser cobert en la prova-va ser la noció d'abast
i les variables locals davant les variables globals.
Es presta atenció a això.
>> Ara que estem arribant a aquestes altres coses,
a la setmana 3 comencem a parlar de recerca i ordenació.
Recerca i classificació, almenys en CS50,
és en gran mesura una introducció a algunes de les parts més teòrics de la informàtica.
El problema de la recerca, el problema de la classificació
són problemes grans i canòniques.
Com es pot trobar un nombre concret d'una matriu de milers de milions de nombres enters?
Com trobar un nom en particular dins d'una llibreta de telèfons
que s'emmagatzema a l'ordinador portàtil?
I, llavors, introduir la noció de temps d'execució asimptòtica
per quantificar realment quant temps, quant aquests problemes són,
el temps que triguen a resoldre.
En, crec, 2011 al quiz que hi ha un problema que crec que mereix
cobrint molt ràpidament, el que és aquest, problema 12.
O no, és Omega.
>> Aquí estem parlant del temps d'execució més ràpida possible
per un algorisme particular i llavors el temps d'execució més lenta possible.
Aquesta Omega i O en realitat només són accessos directes.
Són dreceres de notació per dir
la rapidesa en el cas millor serà el nostre algorisme d'execució,
i el lent que en el pitjor cas possible que el nostre algorisme de córrer?
Anem a fer un parell d'ells, i aquests també van ser coberts
en el curt en notació asimptòtica, que recomano encaridament.
Jackson va fer un treball realment bo.
Amb la recerca binària, parlem de recerca binària com un algoritme,
i solem parlar en termes de la seva gran O.
Quina és la gran O?
Quin és el temps d'execució més lenta possible de cerca binària?
[Estudiant] N ²?
Close, suposo que similar a això.
És molt més ràpid que això.
[Estudiant] Binary? >> Sí, la recerca binària.
[Estudiant] És log n.
Iniciar sessió núm, així que el que fa log n significa?
Es redueix a la meitat cada iteració.
Exactament, en el cas més lent possible,
dir si vostè té una matriu ordenada
d'un milió de nombres enters i el nombre que està buscant
lar és el primer element de la matriu o l'element d'últim en la matriu.
Recordeu, l'algorisme de recerca binària funciona buscant en l'element mitjà,
veure si aquest és el partit que vostè està buscant.
Si és així, llavors bé, vas trobar.
>> En el millor cas possible, la velocitat binària es fa la cerca?
[Els estudiants] 1.
1, és la constant de temps, gran O de 1. Si.
[Estudiant] Tinc una pregunta. Quan dius iniciar de n, que vols dir pel que fa a la base 2, no?
Sí, així és la cosa.
Diem núm de registre, i suposo que quan jo era a la secundària
Sempre vaig assumir que era log base 10.
Sí, això si, log 2 base típicament és el que fem servir.
Un cop més, tornar a la recerca binària, si vostè està buscant, ja sigui per
l'element al final o l'element al principi,
perquè comences al centre i després de rebutjar
qualsevol mitjà no compleix amb els criteris que vostè està buscant,
i te'n vas al següent meitat i l'altra meitat al costat i la mitjana.
Si estic buscant l'element més gran de la matriu d'enters milions
Me'n vaig a reduir a la meitat, com a màxim registre d'1 milió de vegades
abans que finalment provar i veure que l'element que estic buscant
es troba en el més gran o al més alt índex de la matriu,
i que es durà registre de n, iniciar d'1 milió de vegades.
>> Ordenament de bombolla.
Vostès recorden l'algorisme d'ordenament de bombolla?
Kevin, ¿em pot donar un resum ràpid del que va succeir en l'algorisme d'ordenament de bombolla?
[Kevin] Bàsicament es passa a través de tot a la llista.
Es veu en les dues primeres.
Si el primer és més gran que el segon els swaps.
A continuació, es compara la segona i tercera, la mateixa cosa, swaps,
tercer i quart, tot el camí cap avall.
Majors nombres seguiran fins al final.
I després de molts cicles però ja està.
Exactament, és el que Kevin va dir és que veurem grans nombres
bombolla fins al final de la matriu.
Per exemple, ¿t'importa caminar a través d'aquest exemple, si aquesta és la nostra matriu?
[Kevin] Vostè prendrà 2 i 3.
3 és més gran que 2, pel que intercanviar-les.
[Nate H.] Dret, de manera que canviar això, i pel que tenim 2, 3, 6, 4 i 9.
[Kevin] A continuació, es comparen els 3 i 6.
3 és inferior a 6, pel que ells van,
i 6 i 4, que et canviar perquè 4 és inferior a 6.
[Nate H.] Dret, pel que em surt 2, 3, 4, 6, 9.
[Kevin] i 9 és major que 6, de manera que sortir-ne.
I t'agradaria tornar a través d'ell de nou.
>> [Nate H.] M'he fet a hores d'ara? >> [Kevin] No
I per què no es em fa en aquest moment?
Perquè sembla que la meva matriu està ordenada. Estic mirant.
[Kevin] Anar a través d'ell de nou i assegureu-vos que no són els swaps no més
abans que vostè pot parar del tot.
Exactament el que necessita per seguir endavant a través i assegureu-vos que no hi ha swaps
que es pot fer en aquest moment.
En realitat només era afortunat, com vostè ha dit, que acabem
només haver de fer una passada a través de nosaltres i estem ordenats.
Però per fer això en el cas general, que realment haurà de fer això una i altra vegada.
I de fet, aquest va ser un exemple de la millor cas possible,
com vam veure en el problema.
Hem vist que el millor cas possible es n.
Vam anar a través de la matriu 1 vegada.
Quin és el pitjor cas possible per aquest algorisme?
[Kevin] N ².
I això quin aspecte té? Quina seria una mirada àmplia com això portaria temps ² n?
[Kevin] [inaudible] ordenats.
Exactament, així que si tingués la sèrie 9, 7, 6, 5, 2,
primer el 9 seria bombolla tot el camí cap amunt.
Després d'1 repetició tindríem 7, 6, 5, 2, 9.
Llavors el 7 fins burbujearía, 6, 5, 2, 7, 9, i així successivament i així successivament.
>> Hauríem d'anar a través de tota la matriu n vegades,
i de fet pots aconseguir una mica més precís que aquest
perquè una vegada que ens hem mogut del 9 fins al final fins en la seva última posició possible
sabem que mai hem de comparar aquest element nou.
Quan comencem bombollejant del 7
sabem que podem aturar una vegada que el 7 és just abans de les 9
doncs ja hem comparat la 9 a la mateixa.
Si fa això d'una manera intel · ligent, no és veritat, suposo, que de molt temps.
No vas a comparar totes les possibles combinacions de [inaudible]
cada vegada que vostè va a través de cada iteració.
Però tot i això, quan parlem d'aquest límit superior es diu que
vostè està mirant ² n comparacions fins al final.
>> Anem a tornar, i ja que estem començant a aconseguir una mica curt de temps
Jo diria que sens dubte ha de passar per la resta d'aquesta taula,
omplir tot.
Penseu en exemples. Penseu en exemples concrets.
És molt pràctic i útil de fer.
Dibuixa a terme.
Aquest és el tipus de taula que a mesura que avança a través de la informàtica
que realment hauria de començar a conèixer aquestes cor.
Aquests són el tipus de preguntes que vostè aconsegueix en les entrevistes.
Aquestes són les classes de coses que són bones saber,
i pensar en aquests casos extrems, realment trobar la manera de pensar
sabent que per ordenar la matriu bombolla pitjor possible
per ordenar amb que és el que està en l'ordre invers.
>> Punters. Anem a parlar una mica sobre els punters.
En els últims minuts que tenim aquí
Sé que això és com l'arxiu d'E / S que és bastant nou.
Quan parlem sobre els punters de la raó per la qual vull parlar de punters
és perquè, primer, quan estem treballant en C
estem realment en un nivell força baix en comparació amb els llenguatges de programació més moderns.
Som realment capaços de manipular les variables en la memòria,
esbrinar on es troba realment dins la nostra memòria RAM.
Quan hagueu arribat a prendre classes de sistema operatiu que vostè veurà
que és, de nou, una mena d'abstracció.
Això no és realment el cas.
Tenim memòria virtual que està ocultant els detalls de la nostra part.
>> Però per ara es pot assumir que quan es té un programa,
per exemple, quan s'inicia el funcionament del seu programa-xifrat César
Vaig a tornar al meu iPad realment ràpid-
que en els seus inicis el seu programa, si té, per exemple,
4 gigabytes de RAM en el seu ordinador portàtil,
et quedes de banda aquest tros, i anomenarem a aquest RAM.
I comença en un lloc al que anomenarem a 0,
i acaba en un lloc que anomenarem a 4 gigabytes.
Realment no puc escriure. L'home, que és hackejat.
Quan s'executa el programa
el sistema operatiu esculpeix la memòria RAM,
i especifica els diferents segments per diferents parts del seu programa per viure
Aquí sota aquesta zona és una mena de terra de ningú.
Quan es puja una mica més aquí
que tens en realitat el lloc on
el codi de la vida dels seus programes.
Aquest codi binari real, que en realitat arxiu executable es carrega en memòria
quan s'executa un programa, i viu en el segment de codi.
I a mesura que s'executa el programa el processador es veu en aquest segment de codi
per esbrinar quina és la següent instrucció?
Quina és la següent línia de codi que necessita per executar?
>> També hi ha un segment de dades, i és aquí on les constants de cadena
s'emmagatzemen que vostè ha estat utilitzant.
I després més amunt hi ha un lloc anomenat el munt.
Tenim accés a la memòria d'allí usant malloc,
i després cap a la part superior del seu programa
aquí hi ha la pila,
i aquí és on hem estat jugant durant gairebé tot el principi.
Això no és a escala o res.
Molt d'això és molt dependent de la màquina,
depèn del sistema operatiu, però això és relativament com les coses es chunked dalt.
Quan s'executa un programa i es declara una variable anomenada x-
Vaig a dibuixar una altra casella de sota, i això serà una RAM també.
I vaig a mirar.
Anem a dibuixar línies irregulars per indicar que això és només una petita part de RAM
i no tots de la mateixa mida que ens acostem al cim.
>> Si jo declaro una variable sencera anomenada x,
llavors el que realment aconsegueix és un mapatge
que s'emmagatzema a la taula de símbols del programa del meu
que connecta la x nom a aquesta regió de memòria que he dibuixat
aquí entre les barres verticals.
Si tinc una línia de codi en el meu programa que diu que x = 7
el processador sap "Oh, està bé, jo sé que la vida de x en aquesta ubicació en la memòria."
"Vaig a seguir endavant i escriure un 7 Allà."
Com sap quina ubicació és a la memòria?
Bé, que tot es fa en temps de compilació.
El compilador s'encarrega d'assignar a cadascuna de les variables que s'aniran
i creació d'una assignació especial o en lloc de connectar els punts
entre un símbol i on es va, el nom d'una variable
i on va a viure a la memòria.
Però resulta que en realitat podem accedir-hi en els nostres programes també.
Això es fa important quan vam començar a parlar d'algunes de les estructures de dades,
que és un concepte que presentarem en el futur.
>> Però per ara, el que podem saber és que es crea un punter a aquesta ubicació, x.
Per exemple, pot crear una variable punter.
Quan creem una variable punter s'utilitza la notació estrella.
En aquest cas, es diu que jo vaig a crear un punter a un int.
És un tipus com qualsevol altre.
Li donem una variable com i,
i després el va posar igual a la direcció, a una adreça.
En aquest cas, podem establir i assenyalar x
prenent la direcció de x, que fem amb aquest signe,
i després posem i apuntar a la mateixa.
El que això fa és essencialment si mirem al nostre RAM
això crea una variable independent.
Es dirà i,
i quan aquesta línia de codi s'executa
en realitat crearà un punter poc que solem anomenar com una fletxa,
i fixa i per apuntar a x.
Sí
[Estudiant] x Si ja és un punter, que vostè acaba de fer
int * i = x en lloc de tenir el signe?
Sí
Si x és ja un indicador, llavors es pot establir dos punters iguals entre si,
en aquest cas i no indiquen la x,
però seria apuntar a qualsevol x està apuntant.
Malauradament, estem fora de temps.
>> El que vull dir en aquest punt, podem parlar d'això fora de línia,
però jo diria que començar a treballar a través d'aquest problema, # 14.
Vostè pot veure que hi ha ja una mica ple en aquí per tu.
Es pot veure que quan declarem 2 punteres, int * x i i *,
i observi que assenyalar amb el * al costat de la variable va ser una cosa que es va fer l'any passat.
Resulta que això és similar al que estem fent aquest any.
No importa on s'escriu el * quan vostè està declarant el punter.
Però hem escrit la asterisc al costat del tipus de
perquè això fa que sigui molt clar que vostè està declarant una variable punter.
Es pot veure que la declaració dels 2 punters ens dóna 2 caixes.
Aquí quan ens vam posar x igual a malloc
El que això diu és deixar de banda la memòria en el munt.
Aquesta petita caixa aquí, aquest cercle, es troba en el munt.
X està apuntant a la mateixa.
Recordeu que i encara no apunta a res.
Per aconseguir la memòria-per emmagatzemar el nombre 42 en x
usarem la notació què?
[Estudiant] * x = 42.
Exactament, x = 42.
Això significa seguir la fletxa i llençar 42 en aquest país.
Aquí on ens vam posar yyx tenim i que apunta a x.
De nou, això és el mateix que el que Kevin va dir que ens vam proposar i igual a x.
I no apunta x.
Més aviat, està apuntant al que x està assenyalant així.
>> I, finalment, en aquesta última caixa hi ha 2 possibles coses que podríem fer.
Una d'elles és que podríem dir * x = 13.
L'altra cosa és que podríem dir-Alex, saps el que podríem fer aquí?
Es podria dir * x = 13 or-
[Estudiant] Es pot dir qualsevol cosa int.
[Nate H.] Si això es coneix com una variable int que podíem fer això.
També podríem dir * i = 13 perquè els dos estan apuntant al mateix lloc,
per poder utilitzar qualsevol d'elles per arribar-hi.
Si. >> [Estudiant] Quin aspecte tindria si ens limitem a dir x int és de 13?
Això seria declarar una nova variable anomenada x, que no anava a funcionar.
Tindríem una col · lisió perquè va declarar que x sigui un punter fins aquí.
[Estudiant] Si acaba de tenir aquesta declaració per si mateix el que es veuria en termes del cercle?
Si haguéssim de x = 13 llavors tindríem una caixa, i en lloc de tenir una fletxa
que surt de la caixa que havia empat com un 13.
[Estudiant] A la caixa. Bé.
>> Gràcies per mirar i bona sort en el concurs 0.
[CS50.TV]