[Powered by Google Translate] [Sección 4] [menos cómodo]
[Nate Hardison] [Harvard University]
[Esta é CS50.] [CS50.TV]
>> Todo ben, benvido de volta á sección.
Na sección desta semana imos facer un par de cousas.
Nós imos primeiro Axuste repescagem Problema 2,
Que é o conxunto de problemas César e Vigenère.
E entón imos mergullar Quiz de 0 avaliación
e pasar un pouco de tempo Recapitulando o que nós xa conversas sobre
en cada unha das conferencias ata agora, e imos tamén facer algúns problemas
a partir de cuestionarios ano anterior.
Desta forma, vostedes teñen unha boa forma de prepararse para iso.
>> Para comezar, eu iniciado un par de boas solucións
para o conxunto de problemas anterior, conxunto de problemas 2, neste espazo.
Se vostedes todos bater este enlace,
e fai clic meu nome e prema na miña primeira revisión
podes ver caesar.c, que é o que eu estou ollando.
Imos falar sobre iso moi rapidamente.
Esta é só unha solución de mostra.
Esta non é necesariamente a solución perfecta.
Hai moitas formas diferentes de escribir isto,
pero hai algunhas cousas que me gustaría destacar
que vin como estaba de clasificación, os erros máis comúns que eu creo que
esta solución fai un traballo moi bo de manipular.
>> O primeiro é ter algún tipo de comentario de cabeceira na parte superior.
En liñas 1 a 7 ves os detalles,
exactamente o que este programa está facendo.
Unha boa práctica estándar cando está escribindo código C
independentemente de que o seu programa está contido nun único arquivo ou
se está dividido en varios arquivos é ter algún tipo de
orientar comentario na parte superior.
Este tamén é para as persoas que van para fóra, e escribir código no mundo real.
Este é o lugar onde van poñer a información de copyright.
A continuación hai unha lista dos inclúe #.
Na liña 16 hai esa # define, que nós imos volver un pouco.
E entón, xa que a función comeza, comeza unha vez principais,
porque este programa foi todo contido nunha única función
A primeira cousa que acontece, e iso é moi idiomática e típica dun programa C
que leva en liña de comandos argumentos é que verifica inmediatamente
>> para a conta de argumento, argc.
Aquí podemos ver que este programa está esperando dous argumentos exactamente.
Lembre que non hai primeiro argumento que é o especial
que é sempre o nome do programa que está a ser executado,
o nome do ficheiro executable.
E entón o que isto significa que impide o usuario de execución do programa
con argumentos máis ou menos.
A razón que queremos para comprobar iso de inmediato é porque
non podemos realmente acceder a esta matriz argv aquí fiable
ata que teñamos verificado para ver o quão grande é.
>> Un dos erros máis comúns que vin foi xente inmediatamente ir
e coller argv [1].
Eles incorporarse o argumento clave da matriz e non a un para eu comprobar sobre el,
e entón faría a proba para argc, así como o seguinte proba,
con ou sen o primeiro argumento era realmente un número enteiro, ao mesmo tempo,
e que non funciona, porque no caso de que non existen argumentos facilitados
vai ser incorporarse un argumento que non existe, ou tentar incorporarse unha que non está alí.
>> A outra gran cousa que ten que observar é que
sempre quere imprimir algún tipo de mensaxe de erro útil
para o usuario a orientar-los.
Estou seguro de que ten todos os programas de execución, onde, de súpeto, el traba,
e recibir ese diálogo pouco ridículo que aparece e di
algo terriblemente enigmático e quizais lle dá un código de erro ou algo parecido
que non ten sentido.
Isto é onde realmente quere ofrecer algo útil
e orientada ao usuario, de xeito que cando executa-lo eles van "Oh," palma cara.
"Eu sei exactamente o que facer. Sei como corrixir isto."
>> Se non imprimir unha mensaxe, entón acaba realmente
deixando o usuario a ir examinar o código fonte
para descubrir o que deu errado.
Hai tamén algunhas veces que vai usar os códigos de erro diferentes.
Aquí só usou un para dicir que houbo un erro,
Houbo un erro, houbo un erro.
Programas maiores, moitas veces, os programas que son chamados por outros programas,
pode voltar algún tipo de códigos de erro especiais en distintos escenarios
programaticamente comunicar o que faría doutra forma
usar só unha fermosa mensaxe Inglés para.
Cool.
Como traballamos para abaixo, podes ver que tirar a chave.
Probar a ver se a chave encaixa.
Recibimos unha mensaxe do usuario.
A razón por que facelo nesta facer mentres ciclo e iso é algo que imos cubrir
en un pouquiño, pero acontece que se insire o control D
cando comeza a GetString ventá no terminal
o que iso realmente significa é que envía un carácter especial
para o programa.
É o chamado ELF ou fin de ficheiro de caracteres.
E, nese caso, a nosa cadea de mensaxe nulo,
, Que non foi algo que comprobado para o conxunto de problemas en si.
>> Pero como imos, agora que comezamos a falar sobre punteiros
e distribución dinámica de memoria na pila,
verificación de nulo sempre que ten unha función que podería
voltar nulo como un valor é algo que vai querer adquirir o hábito de facer.
Isto é aquí sobre todo para fins de ilustración.
Pero cando ve GetString no futuro,
así do conxunto de problemas 4, vai querer manter isto presente.
De novo, isto non é un problema para conxunto de problemas 3 ou unha vez que non tiña cuberto iso aínda.
Finalmente, chegamos a esta parte, onde temos para o circuíto de cifrado principal,
e hai un par de cousas a suceder aquí.
En primeiro lugar, iterar sobre a cadea de mensaxe enteira en si.
Aquí mantivemos a chamada strlen na condición,
que algúns de vós teñen apuntado non é un gran camiño a percorrer.
Acontece que, neste caso, tampouco é grande,
en parte porque estamos modificando o contido da mensaxe en si
dentro do loop for, entón temos unha mensaxe que é 10 caracteres
a primeira vez que inicie este ciclo é strlen vai devolver o que?
10.
>> Pero entón modificar mensaxe, dicir que modificar o seu carácter 5,
e nós xogar un caracter \ 0 na posición 5,
nunha iteração subseqüente strlen (mensaxe) non pode voltar o que fixo
a primeira vez que iterada,
pero, ao contrario, volver 5, porque xogamos en que terminador nulo,
e lonxitude da corda é definido
polo que a posición de \ 0.
Neste caso, esta é unha boa forma de ir porque estamos modificando o no lugar.
Pero entende que este é realmente sorprendente simple para cifrar
se pode obter a matemática correcta.
Todo o que é necesario é comprobar se hai ou non a letra que está mirando
é maiúscula ou minúscula.
>> A razón, só hai que comprobar iso e non temos para comprobar
o caso do alfa é porque
un personaxe é maiúscula ou se é minúscula
entón é sempre un carácter alfabético,
porque non ten díxitos maiúsculas e minúsculas.
A outra cousa que facer, e iso é un pouco complicado,
é que xa modificou o nivel César cifra fórmula
que demos na especificación do conxunto de problemas.
O que é diferente aquí é que nós subtraído
na capital caso maiúsculas A, e entón nós engadimos maiúscula
volver ao final.
>> Sei que algúns de vostedes fixeron iso no seu código.
Será que algún de vós o fan nas súas presentacións?
Vostede fixo iso. Pode explicar o que isto significa, SAHB?
Subtraindo-lo, porque fixo un mod logo,
ten que leva-la para fóra, así que comeza maneira [tos] posición.
E, a continuación, engadindo-lo de volta máis tarde cambiou máis o que quería.
Si, exactamente.
O que SAHB dixo foi que cando se quere engadir
nosa mensaxe ea nosa clave xuntos
e mod mod que, que por NUM_LETTERS,
se non escalar a nosa mensaxe para o intervalo 0 a 25 apropiado primeira,
entón pode acabar recibindo un número moi raro
porque os valores que nós estamos mirando cando miramos mensaxe [i],
cando miramos para o carácter i da nosa mensaxe de texto simple,
é un valor en calquera parte desta gama de 65-122
con base nos valores ASCII para maiúsculas da a Z en minúsculas.
E así, cando mod-lo por 26 ou por NUM_LETTERS,
unha vez que era o noso # define na esquina superior dereita ata aquí,
que vai dar un valor que está na franxa de 0 a 25,
e necesitamos un xeito de escalar entón que back-up
e obtelo no intervalo axeitado ASCII.
O xeito máis doado de facelo é para escalar todo para abaixo
no intervalo entre 0 e 25 para comezar,
e despois cambiar todo de volta no final.
>> Outro erro común que vin a xente se é que
se non realmente facer iso intercambio inmediato
e engadir a mensaxe ea clave xuntos e engadila los, por exemplo,
nunha variable char, o problema que
é, dende mensaxe [i] é un número relativamente grande para comezar-
Lembre que é polo menos 65 se é unha maiúscula caracteres
se ten unha chave grande, digamos, algo así como 100,
e engadir os dous xuntos nun char asinado está indo para obter un estourido.
Está indo para obter un valor que é maior que 127,
que é o maior valor que unha variable char.
Unha vez máis, é por iso que quere facer este tipo de cousas para comezar.
Algunhas persoas teñen en torno a ese caso, facendo unha cousa e probar
para ver se sería estourido antes de facer iso,
pero deste xeito queda en torno a iso.
E entón nesta solución é impreso a corda toda a finais.
Outras persoas impreso un personaxe de cada vez. Ambos son impresionantes.
Neste punto, vós ten algunha dúbida, algún comentario sobre iso?
Cousas que lle gusta, cousas que non gusta?
>> Eu tiña unha pregunta.
Poida que eu teña perdido durante a súa explicación, pero como é que este programa
saltar os espazos para conectar a chave para a lonxitude do texto?
Este é só César cifra. >> Ah, desculpe, si.
Si, imos ver isto.
Na cifra de César temos en torno a que, por causa
só capotou caracteres.
Nós só rolda se eles eran maiúsculas ou minúsculas.
Vós me sentindo moi ben sobre iso?
Sinto-se libre para editar esta casa, leva-la,
comparalos-lo co que vostedes escribiron.
En definitiva, non dubide en enviar preguntas sobre el tamén.
E unha vez máis, entender que o obxectivo aquí co seu problema define
non é obter vostedes para escribir código perfecto para os seus conxuntos de problemas.
É unha experiencia de aprendizaxe. Si
>> Voltar facelo mentres loop, se é igual nulo,
así nula só significa nada, eles simplemente prema Intro?
Nulo é un valor punteiro especial,
e usan nulo cando queremos dicir
temos unha variable punteiro que está apuntando para nada.
E así normalmente significa que esta variable, esta variable mensaxe
está baleiro, e aquí, porque nós estamos usando o CS50 tipo cadea especial,
cal é o tipo de cadea CS50?
Xa viu o que é cando David tirou o capuz na aula?
É un funky-que é un punteiro, non?
Ok, si. >> É un char *.
E así realmente poderiamos substituír este
aquí coa mensaxe de char *,
e así a función GetString, se non pode obter unha cadea de usuario,
non se pode analizar unha secuencia, e un caso en que non se pode analizar unha secuencia
é o usuario escribe o carácter de fin de ficheiro, o control D,
o que non é algo que adoita facer, pero se isto acontecer
a continuación, a función pode voltar ese valor nulo como unha forma de dicir
"Ei, eu non tiven unha secuencia."
O que sucedería se nós non poñemos mensaxe = null,
que é algo que non fixo aínda?
Por que iso sería un problema aquí?
Porque sei que falamos un pouco na charla sobre vazamentos de memoria.
Si, imos facelo, e imos ver o que acontece.
>> Cuestión Basilio foi o que pasa se nós realmente non teñen
esta mensaxe de proba = null?
Imos cambiar-se para arriba.
Vostedes poden comentar isto.
En realidade, eu vou salvalo nunha revisión.
Este será revisión 3.
O que ten que facer para executar este programa é que terá que facer clic nese icona de engrenaxe ata aquí,
e vai ter que engadir un argumento para el.
Ten que dar o argumento clave, xa que desexamos pasar un argumento de liña de comandos.
Aquí eu vou dar-lle o número 3. Gústame 3.
Agora o zoom cara a fóra, a execución do programa.
Está funcionando, compilación, construíndo.
Aquí imos nós. Está á espera de ser solicitado.
Se eu escribir algo como Ola, onde é que isto vai?
Oh, meu programa levou moito tempo para ser executado. Eu estaba jawing por moito tempo.
Aquí vai.
Agora eu escriba Olá
Vemos que criptografía de forma adecuada.
Agora o que pasa se non facemos GetString listo para volver nulo?
Lembre, eu dixen que nós fixemos iso presionando o control D ao mesmo tempo.
Vou rolar por aquí. Imos executa-lo de novo.
Edificio. Non.
Agora, cando eu bati o control D
Eu teño esa liña que di opt/sandbox50/bin/run.sh, fallo de segmento.
Vós xa viron que antes?
>> [Estudante] Por que non hai >>-Desculpe?
[Estudante] Por que non hai despejo de núcleo neste caso?
O despejo de núcleo, a cuestión é por que non hai despejo de núcleo aquí?
A cuestión é que non pode ser, pero o despejo de núcleo é un arquivo
que queda almacenado no disco duro.
Neste caso temos desactivado core dumps
no servidor de execución para que nós non temos xente seg falla
e construción de toneladas de core dumps.
Pero pode obter un.
Desafiuzamentos principais son o tipo de cousas que moitas veces pode desactivar,
e ás veces fai.
O fallo de segmentación, para responder súa pregunta, Basilio,
está dicindo que nós tratamos acceder a un punteiro
que non foi definido para apuntar para calquera cousa.
Lembre-se de Binky o vídeo cando intenta Binky
vaia acceder a un punteiro que non está a apuntar cara algo?
Neste caso, eu creo que, tecnicamente, o punteiro está a apuntar cara algo.
El está a apuntar cara nulo, o que é tecnicamente 0,
pero que é definido como un segmento en que non está accesible
polo seu programa, para obter un fallo de segmento
porque non está accedendo a memoria que está en un segmento válido
como o segmento de pila ou o segmento de pila ou o segmento de datos.
Cool.
Algunha pregunta sobre César?
>> Imos seguir adiante. Imos ollar para Revisión 2 moi rapidamente.
Isto é Vigenère.
Aquí en Vigenère
imos camiñar por este un moi rápido, porque, de novo,
Vigenère e César son bastante semellantes.
Comentario de cabeceira é antes,
# Define e antes para evitar o uso deses números máxicos.
O bo é dicir que quería cambiar a
un alfabeto diferente, ou algo así.
En vez de ter que ir cambiar manualmente todas as 26 no código
podemos cambiar isto para 27 ou deixar caer
se estivésemos usando alfabetos diferentes, linguas diferentes.
Unha vez máis, temos esa comprobación da conta de argumento,
e realmente ten case pode tomar isto como un modelo.
Practicamente todos os programas que escribe debe-
se leva de liña de comandos argumentos, algúns secuencia de liñas
que le coma este no inicio.
Ese é un dos tests de sanidade primeira que quere facer.
>> Aquí o que nós fixemos foi a certeza de que
a palabra chave era válida, e que foi a segunda verificación que nós fixemos.
Teña en conta unha vez que estamos separados iso argc e 2.
Nótese que, neste caso, unha cousa que tiña que facer era, en vez
usar un ao i que queriamos para validar toda a cadea,
e, a fin de facer o que realmente ten que ir carácter por carácter
sobre a corda.
Non hai ningunha boa forma de chamar algo sobre el
porque, mesmo, por exemplo, un para i volverá 0
non se pode analizar un número enteiro, para que nin sequera funciona.
Unha vez máis, fermosa mensaxe dicindo ao usuario exactamente o que pasou.
Entón, aquí, de novo, nós tamén xestionar o caso en que
o usuario escribe un personaxe D control aleatorio.
>> E entón, Charlotte tiña unha pregunta anterior sobre como podemos saltar espazos
na nosa cadea aquí.
Esta era unha especie de similar ao que fixemos co programa do MySpace
que fixemos na sección, eo xeito en que isto funciona
é que rastreou o número de cartas que vira.
Mentres caminhávamos sobre a secuencia de mensaxes, como andou carácter por carácter,
que acompañou o índice como parte do noso loop for, e entón nós tamén acompañou
o número de letras, polo que non caracteres especiais, non díxitos, non-branco espazo
que vira na variable independente.
E, a continuación, esta solución modifica a clave
para obter un enteiro real da clave, e el fai iso en tempo real,
dereita antes que despois vai para cifrar a mensaxe real carácter.
Existen algunhas solucións que eran perfectamente moi grande
que modificar a clave ata o probar a validez da chave.
Ademais de garantir que o carácter ea palabra clave
foi un carácter alfabético tamén que virou en un número enteiro
na franxa de 0 a 25 para, a continuación, ir ter que facer isto máis tarde neste loop.
Unha vez máis, ve aquí é realmente exactamente o mesmo código
que usan no Caesar neste momento.
Está facendo exactamente a mesma cousa, entón o verdadeiro truco é descubrir
como transformar a palabra chave en un número enteiro.
>> Unha cousa que nós fixemos aquí, que é un pouco denso
é que repetiu esa frase, eu creo que podería chamalo,
3 veces separadas nas liñas 58, 59 e 61.
Alguén pode explicar o que é exactamente esta frase fai?
Está visitando un personaxe, como dixo.
Si, é [inaudível] un personaxe na palabra clave,
e por iso é visto número de letras, porque só se está movendo ao longo
a palabra clave, unha vez que teña visto a carta,
de xeito que vai efectivamente saltar espazos e cousas así.
Si, exactamente.
E entón, unha vez que viu o branco mod contrasinal que só así se mover de volta.
Exactamente. Esta é unha explicación perfecta.
O que Kevin dixo é que queremos índice para a palabra clave.
Queremos chegar o carácter num_letters_seen, se quere,
pero num_letters_seen excede a lonxitude da contrasinal,
a nosa forma de volver á pista apropiada que usar o operador mod
efectivamente contorno.
Por exemplo, como a curto, a nosa palabra clave é Bacon,
e 5 letras.
Pero vimos seis letras do noso texto simple neste momento
e cifrada 6.
Imos acabar acceder ao num_letters_seen,
que é de 6, mod a lonxitude da contrasinal, 5,
e así imos conseguir un, e así que nós imos facer é que imos
acceso ó interior do noso primeiro personaxe contrasinal nese punto.
>> Todo ben, todas as preguntas sobre Vigenère
antes de seguir adiante?
Vós me sentindo moi ben sobre iso?
Legal, gran.
Eu quero estar seguro de que vostedes están tendo a oportunidade de ver o código
que pensa que está bo e ten a oportunidade de aprender con el.
Esta vai ser a última vez que vou estar usando os espazos para o momento,
e nós imos facer a transición agora, e eu estou indo a ir a cs50.net/lectures
para que poidamos facer un pouco de análise quiz.
A mellor forma que eu creo que para comezar a facer probas revisión
é vir a esta páxina Conferencias, cs50.net/lectures,
e debaixo de cada unha das rúbricas semanas, entón se eu ollar aquí na Semana 0,
Vexo que temos unha lista de temas que cobren a Semana 0.
>> Se calquera destes temas parece estraño para ti
definitivamente vai querer volver e percorre as notas de clase e, posiblemente,
mesmo follas as conferencias, ve-los de novo se queres
para ter unha idea do que está a suceder con cada un destes temas.
Direi aínda este ano, un dos recursos legais que temos
e destes shorts que creamos, e se ollar a Semana 0,
non temos todos os temas, pero temos un bo número deles,
algunhas das máis complicadas, entón asistir estes shorts de novo
é unha boa forma para chegar ata a velocidade.
En particular, eu vou poñer unha ficha para o 3 na parte inferior, unha vez que eu fixen aqueles.
Pero se está loitando co binario, bits, hex, este tipo de cousas,
binario é un gran lugar para comezar.
ASCII é outro que é bo para ver tamén.
Podes incluso ver-me na velocidade 1.5x se eu estou indo moi devagar para ti.
Desde a súa revisión, Sinto-se libre para facelo.
>> Só para comezar moi rapidamente, nós imos pasar por unha parella destes problemas do quiz
só para axiña churn a través destes.
Por exemplo, imos ollar para 16 problema que eu teño aquí enriba da placa.
Temos a seguinte cálculo en binario,
e queremos mostrar calquera traballo.
Ok, eu vou dar a este un tiro.
Vostedes deben seguir xunto co papel,
e nós imos facelo moi rapidamente.
Queremos facer o seguinte cálculo en binario.
Eu teño 00110010.
E eu estou indo para engadir a el 00110010.
Para as matemáticas xenios acompañando na casa,
esta é realmente multiplicar por 2.
Imos comezar.
Nós imos seguir o algoritmo diso mesmo que nós facemos
cando engadimos números decimais xuntos.
Realmente a única diferenza aquí é que nós loop de volta en torno a
Unha vez que temos 1 + 1 no canto de unha vez estivemos con 10.
>> Se comezar a partir da dereita, moi rapidamente, o que é o primeiro díxito?
[Estudante] 0. >> [Nate H.] 0.
Grande, o segundo díxito?
[Estudante] 1.
[Nate H.] É un 1? 1 + 1 é?
[Estudante] 10.
[Nate H.] Exactamente, entón o que é o díxito que eu escriba debaixo os 2 engadidos xuntos?
[Estudante] 1, 0 ou 0 e, a continuación, levar o 1.
[Nate H.] 0 e levar a 1, exactamente.
A continuación un up, Basil, está por riba.
Cal é o terceiro? >> [Basil] 1.
[Nate H.] 1, perfecto. Kevin?
[Kevin] 0. >> [Nate H.] 0, Charlotte?
[Charlotte] 0. >> [Nate H.] Si, eo que fago?
[Alumno] O 1.
[Nate H.] E o que fago? E entón eu leva a 1.
Perfecto, SAHB? >> [SAHB] Agora tes un.
[Nate H.] E fago algo aquí?
[SAHB] Entón, a próxima que ten un porque transitadas 1.
[Nate H.] Gran, entón aquí podemos remata-lo.
Cool.
[Estudante] O 0 + 0 = 0?
0 + 0 = 0.
1 + 1, como dixen, é de 10, ou 1, 0, si.
10 é un equívoco, porque para min 10 significa o número 10,
e é a peculiaridade de como estamos representando o cando estamos escribindo.
Nós representar o número 2, por 1, 0, eo número 10 é un pouco diferente.
>> O que é unha especie de bo sobre o binario é que non hai realmente que moitos
casos, ten que aprender.
Hai 0 + 0 = 0, 0 + 1 = 1,
1 + 1 é 0, e, a continuación, subir un 1,
e entón podes ver aquí na terceira columna da dereita
tivemos este 1, 1 e 1.
E 1 + 1 + 1 é un 1,
e leva outro 1.
Cando está facendo a suma binaria, moi sinxelo.
Eu faría unha parella máis destes para verificar a sanidade vós
antes de ir porque este é
probablemente algo que veremos no cuestionario.
Agora imos facer este próximo tamén.
Imos facer 17 problema.
Estamos indo para converter o seguinte número binario para decimal.
Eu teño 10100111001.
Teña en conta que no vídeo binario que eu fixen
Eu andei por un par de exemplos, e mostre como
todo funciona cando está facendo iso en decimal.
Cando se está a traballar en representación decimal Creo que estamos
Actualmente na nosa vida tan fluente en que
é moi doado para encubrir a mecánica de como realmente funciona.
>> Pero para facer unha rápida recapitulação, se eu tivera o número 137
iso realmente significa e de novo, é dicir, en representación decimal-
o número 137 en decimal significa que teño 1 x 100 + 3 x 10 + 7 x 1.
Isto todo é permanecer na pantalla.
E entón, se ollar para eses números aquí,
100, 10 e 1, ve que son realmente as potencias de 10.
Eu teño 10 ², 10 ¹, e 10 para o cero.
Temos un tipo semellante de cousas en binario,
agás que a nosa base, como o chamamos, é 2 en vez de 10.
Estes 10s que escribín aquí no fondo,
este ² 10, 10 ¹, 10 ao cero, 10 é a nosa base,
eo expoñente, 0, 1 ou 2,
está implícita a posición do díxito do número que escribir.
1, miramos para el, este 1 está na posición 2.
A 3 está en posición 1, e o 7 está na posición 0.
É así que temos os distintos expoñentes abaixo das nosas bases.
>> Tras todo isto we'll-en realidade, vostede sabe o que?
Nós imos facer, onde fixen o meu botón desfacer ir?
Non.
Eu amo este desfacer cousa.
Tras iso, eu creo que para min polo menos,
o xeito máis doado para comezar a converter un número binario
ou un número hexadecimal onde a base é 16
e non 10 ou 2 é ir adiante e escribir
as bases e expoentes para o conxunto de números no meu número binario, na parte superior.
Se comezar a partir de esquerda a dereita de novo,
que é unha especie de contra-intuitivo,
Eu vou cambiar de volta para o negro aquí, temos a 2 a posición 0,
e entón temos 2 ¹, 2 ²,
e, a continuación, 2 para a 3, 2 a 4, 2 a 5, 6,
7, 8, 9, e 10.
Estes números que escribín para fóra son todos os expoñentes.
Eu só escribín as bases aquí no 3 primeiro só para o espazo.
>> Neste momento eu estou indo a ir adiante e eu estou indo realmente para borrar
as cousas que fixemos en decimal, se está todo ben.
Vós todos teñen iso.
Aqueles de vós asistir online eu estou seguro que será capaz de volver-me se queres.
De volver para a pluma.
Agora, o que podemos facer, se vostedes non son totalmente ata a velocidade nos seus poderes de 2,
que é totalmente legal.
Acontece. Eu entendo.
Unha vez eu tiven unha entrevista de emprego onde me foi dito que eu debería saber todas as potencias de 2
A través de 2 a 30.
Non era un traballo que eu teño.
De calquera forma, podedes ir adiante e facer as contas aquí,
pero co binario que non fai moito sentido,
e nin ten sentido con decimal ou hexadecimal, ou
a facer as contas para onde ten ceros.
Podes ver que eu teño 0 aquí, un 0 aquí, 0 aquí, 0 aquí, 0 aquí, 0 aquí.
Por que non ten sentido facer as matemáticas real
para calcular a potencia adecuada, de 2 para esa posición?
Precisamente, como Charlotte dixo, será 0.
Podería moi ben salvar a época calcular potencias de 2 non é o seu forte.
Neste caso, só necesitamos calculalas para 2 a 0, o que é-?
[Estudante] 1.
[Nate H.] 1, 2 e 3, que é a?
[Estudante] 8. >> [Nate H.] 8.
2 a 4?
[Estudante] 2. Sinto moito, 1.
[Nate H.] 2 a 4 e 16, exactamente.
2 a 5, Kevin? >> 32.
[Nate H.] 32, 2 a 8?
[Estudante] 32 x 8, 256.
[Nate H.] Perfecto.
E 2 para o 10?
[Estudante] 1024.
[Nate H.] Si, 1024.
>> Unha vez que temos estes números podemos sumar todos eles.
E é aquí que é realmente importante para facer un par de cousas.
Unha delas é ir amodo e comprobar o seu traballo.
Pode dicir que hai un 1 a finais deste número,
entón eu debería estar sempre un número impar como o meu resultado,
porque todos os outros van ser aínda números
dado que é un número binario.
A outra cousa a facer é chegar a este punto a proba
e escribiu chegar ata este punto
e está correndo contra o tempo
mirar para o número de puntos que o problema paga a pena.
Este problema, como podes ver, se eu virar de volta para o meu portátil moi rapidamente-
este problema val 2 puntos, de xeito que este non é o tipo de adición
ten que estar pasando, se realmente está presionado polo tempo.
Pero imos volver para o iPad, e nós imos pasar por iso moi rapidamente.
>> Eu gusto de facer os pequenos números primeira
porque eu creo que máis sinxelo.
Eu gusto de 32 e 8, porque eles van xuntos moi facilmente, e nós temos 50.
16 e 1 recibe 17.
Non temos 57,
e despois podemos facer o resto deste, para que poidamos facer 57, 156.
Imos.
Home, así, imos ver.
Tivemos 57, 256 e 1024.
Neste punto, eu prefiro pasar.
Eu non teño idea. Eu claramente precisa ler sobre iso.
7, 6, e 4, obtén 17.
1, 5, 5, 2, 13.
Entón, temos tres, e entón nós comezamos 1.
1337.
Ovo de Pascua, alguén?
Calquera persoa recoñecer ese número?
Chris recoñece o número. O que significa, Chris?
[Chris] leet.
Leet, por iso, se ollar para iso, parece que leet.
Material hacker. Coidado con este tipo de cousas no medio termo, ou a proba, mellor dito.
Se ves este tipo de cousas e está a se pregunta "Huh",
que realmente pode significar algo.
Eu non sei. David gusta de poñelas dentro
É unha boa forma de sanidade comprobar.
Como ben, podo ver o que está a suceder.
>> Iso é unha cousa Semana 0/Week.
Volver para o noso portátil agora,
diminuír o zoom, e un par de outras cousas.
Hai ASCII, que temos benvida a facer unha chea de cos conxuntos de problemas.
Esta noción de capital A. ¿Que é iso mesmo?
Sabendo que é o enteiro decimal.
65 é o que está mapeado para a táboa ASCII,
e que é, por tanto, como o computador, escribe el,
e é así que temos que chegou a fuxir con escribindo
O personaxe da capital e do carácter letras minúsculas da
nalgunhas desas solucións e conxuntos de problemas que ten feito.
A par de outras cousas.
Temos declaracións, expresións booleanas, condicións, loops, variables e segmentos.
>> Aqueles todo parece facer sentido para a maioría?
Parte desa terminoloxía é un pouco descolada, ás veces.
Eu gusto de pensar unha declaración como a maior parte algo que remata cun punto e coma.
Declaracións como x = 7, que define unha variable,
presuntamente chamado x = 7.
Presuntamente x tamén é un tipo que pode almacenar o número 7,
por iso é un int ou posiblemente unha boia ou un curto ou un char,
algo así.
Unha expresión booleana está a usar estes dous iguais
eo estrondo igual ou non é igual, menor que, maior que,
inferior ou igual a, todo tipo de cousas.
Condicións entón son declaracións, outro lugar.
Quere lembrar que non pode ter unha persoa sen un correspondente se.
Do mesmo xeito, non pode ter unha persoa sen un correspondente se.
Loops, recordar os tres tipos de loops estamos martelé en ti
para o último par de seccións e conxuntos de problemas.
Usando que cando, cando está a recibir entrada do usuario,
usando while ata que unha determinada condición é verdadeira,
e en seguida, usando os loops se precisa
saber cal iteração do loop que está no momento é como eu penso sobre iso.
Ou, se está facendo un para cada personaxe dunha serie que quero facer algo,
para cada elemento nunha matriz que quero facer algo para ese elemento.
>> Temas e eventos.
Estes non cobren de forma tan explícita en C,
pero lembre se este a partir de cero.
Esta é a noción de guións diferentes.
Esta é tamén a noción de transmitir un evento.
Algunhas persoas non utiliza a transmisión dos seus proxectos, inicialmente,
que é totalmente legal,
pero estas son dúas formas diferentes de tratar con esta cuestión maior chamados de competencia,
que é como comeza a executar programas
ou aparentemente executar ó mesmo tempo?
Distintas tarefas en execución, mentres outras tarefas tamén están en execución.
Esta é a forma como o seu sistema operativo parece funcionar.
É por iso que, aínda que, por exemplo,
Eu teño o meu navegador rodando, eu tamén podo conectar Spotify e tocar unha música.
Isto é unha cousa conceptual para entender.
Quere ter un ollar para os fíos curtos
Se queres saber máis sobre iso.
>> Imos ver, creo que podería ser
un problema sobre iso nun deses.
Unha vez máis, creo que temas e eventos non son algo que iremos cubrir en C
só porque é moito máis difícil do que en scratch.
Non debe preocuparse con iso alí, pero sempre entender os conceptos,
entender o que está a suceder.
Antes de seguir adiante, calquera dúbida sobre Semana 0 materiais?
Todo o mundo sentindo moi ben?
Variables comprensión e que é unha variable?
>> Seguindo adiante. 1 semana.
Un par de cousas aquí que non foron especialmente visados
na revisión cuestionario necesariamente e tamén cousas máis conceptuais para pensar.
A primeira é a noción de que fonte, compiladores e código obxecto son.
Alguén? Basil.
É obxecto de código, quero dicir código fonte é o que poñer bumbum,
e código obxecto é o bumbum pon para fóra para que o ordenador poida ler o programa.
Exactamente.
O código fonte é o código C que realmente escribir.
Código obxecto é o que sae de bumbum.
É a 0s e 1s en que formato binario.
Entón, o que pasa é que cando ten unha morea de arquivos de obxecto,
dicir que está compilando un proxecto ou un programa que usa varios arquivos de código fonte,
que, por convención teñen a extensión de arquivo. c.
É por iso que temos caesar.c, vigenère.c.
Se está escribindo programas en Java que darlles a extensión. Java.
Programas en Python teñen a extensión. Aa frecuencia.
>> Unha vez que ten varios ficheiros. C, recompila-los.
Clang cospe todo ese lixo binario.
Entón, porque só quere un programa
tes o enlace de conexión de todos estes arquivos obxecto xuntos
nun arquivo executable.
Este é tamén o que ocorre cando usa a biblioteca CS50, por exemplo.
A biblioteca CS50 é tanto iso. H ficheiro de cabeceira
que leu, que # includecs50.h.
E entón é tamén un arquivo de biblioteca particular binario
que foi compilado que é 0s e 1s,
e que a L-bandeira, por iso, se volvemos aos nosos espazos e estamos moi rapidamente
o que está pasando aquí, cando miramos para o noso comando bumbum,
o que temos e este é o noso arquivo de código fonte aquí.
Estes son unha banda de sinalizados de compilador.
E entón, ao final, estes elo l-bandeiras en
os ficheiros binarios reais para estas dúas bibliotecas, biblioteca CS50 e, a continuación, a biblioteca de matemáticas.
>> Entender cada tipo de finalidade arquivos '
no proceso de compilación é algo que vai querer ser capaz de
dar, polo menos, un nivel elevado de visión.
Código fonte vén dentro do código obxecto sae.
Arquivos de código obxecto vincular xuntos, e recibe un arquivo, bonito executable.
Cool.
Esta é tamén onde pode obter erros en varios puntos
no proceso de compilación.
Este é o lugar onde, por exemplo, se aproveitar esa bandeira conexión,
a bandeira CS50, e omitir-lo en espazos ou cando está executando o seu código,
este é o lugar onde vai ter un erro na fase de vinculación,
eo vinculador vai dicir: "Ei, chamou un GetString función
que está na biblioteca CS50 ".
"Vostede me dixo que estaba na biblioteca CS50, e eu non podo atopar o código para el."
É aí onde ten que conectar-lo, e que está separado
a partir de un erro do compilador porque o compilador está mirando sintaxe e ese tipo de cousas.
É bo saber o que está a suceder cando.
>> Outras cousas a coñecer.
Eu diría que definitivamente quero ter un ollar para o curto no typecasting feito por Jordan
para entender o que ints están baixo o capó,
o que chars están baixo o capó.
Cando falamos en ASCII e nós realmente ollar para a táboa ASCII,
o que está facendo é dando-nos unha mirada baixo o capo
a forma na que o ordenador realmente representa o capital A e 7 díxitos
e unha coma e un punto de interrogação.
O ordenador tamén formas especiais para representar
o número 7 como un enteiro.
El ten un xeito especial para representar o número 7 como un número de coma flotante,
e aqueles que son moi diferentes.
Typecasting é como dicir ao ordenador "Ola, eu quero que converter
a partir dunha representación a outra representación ".
Por que non imos dar un ollo niso.
>> Tamén quere dar un ollo a curto en bibliotecas e en curto compiladores.
Os falar sobre o proceso de compilación,
que é unha biblioteca, e pasar por riba de algunhas desas preguntas que pode se preguntas.
Preguntas sobre o material Semana 1?
Hai algún tema aquí que parecen asustado que desexa cubrir?
Estou tentando explotar na maioría destes temas anteriores, para que poidamos chegar a
punteiros e facer un pouco de recursão.
Pensamentos?
Calquera cousa para cubrir?
Tempo para un pouco de chocolate, quizais?
Vostedes están a traballar con el.
Vou continuar a beber o meu café.
Semana 2.
Boa chamada, boa chamada.
Na 2 ª semana falamos un pouco máis sobre funcións.
>> Os primeiros xogos de problemas poucas que realmente non escribir ningunha función en todo
diferente do que función?
[Estudante] principal. >> Principal, exactamente.
E así vimos os traxes diferentes que viste principal.
Hai aquel en que non ten argumentos,
e nós só dicir baleiro entre os parénteses,
e despois hai outro onde queremos ter argumentos de liña de comandos,
e, como vimos, que é onde ten argc int e cadea matriz argv
ou agora que nós realmente expostos cadea para o char que é
Nós imos comezar a escribilo lo como char * argv e corchetes.
No conxunto de problemas 3, vostedes viron unha morea de funcións,
e aplicou unha morea de funcións, deseñar, ollar para arriba, scramble.
Os prototipos foron todos escritos alí para ti.
>> O que eu quería falar aquí con funcións moi rapidamente
é que hai 3 partes a eles sempre que escribir unha función.
Ten que especificar o tipo de retorno da función.
Ten que especificar un nome para a función, e entón ten que especificar
a lista de argumentos ou a lista de parámetros.
Por exemplo, se eu fose escribir unha función para resumir unha morea de números enteiros
e despois volver para min a suma do que sería o meu tipo de retorno
se eu quería sumar enteiros e despois volver a suma?
A continuación, o nome da función.
Se eu ir adiante e escribir en verde, esa parte é o tipo de retorno.
Esta parte é o nome.
E entón, entre parénteses
é onde eu dou os argumentos,
moitas veces abreviado como args, ás veces chamado params para os parámetros.
E se ten un, só especificar a un.
Se ten varios de separar cada un con comas.
E para cada argumento que dea dúas cousas que son-Kevin?
[Kevin] Ten que dar o tipo e logo o nome.
E entón o nome, eo nome é o nome que vai empregar
para referirse a ese argumento dentro da función suma,
dentro da función que está escribindo actualmente.
>> Non ten que, por exemplo, se eu estou indo para resumir,
dicir, unha matriz de números enteiros: nós facer matriz int,
e eu vou dar algunhas claves alí-
entón, cando eu pasar un array para a función suma
I pasalo na primeira posición da lista de argumentos.
Pero a matriz que pasar non ten que ter o nome arr.
Arr. vai ser como eu me refiro a ese argumento dentro do corpo da función.
A outra cousa que temos que ter en conta,
e iso é un pouco diferente de funcións, pero eu creo que é un punto importante,
é que, no C, cando estou escribindo unha función como esta
Como sei cantos elementos están nesta matriz?
Isto é un pouco de unha pregunta capciosa.
Nós conversas sobre iso un pouco na sección da última semana.
Como sei que o número de elementos dentro dunha matriz en C?
Existe unha maneira?
>> Acontece que non hai ningunha forma de saber.
Ten que pasalo por separado.
Existe un truco que pode facer
se está na mesma función que a matriz fose declarado,
e está a traballar con unha gran pila.
Pero iso só funciona se vostede está na mesma función.
Despois de pasar unha matriz a outra función ou se ten declarado unha matriz
e pór esa matriz na pila, xa usou malloc
e este tipo de cousas, entón todas as apostas están fóra.
Entón, o que realmente ten que pasar en torno a
un argumento especial ou outro parámetro
dicindo o quão grande é a matriz.
Neste caso, eu quere empregar unha coma-Sinto moito, vai a fóra da pantalla aquí-
e eu pasar outro argumento
e chamalo len int ao longo.
>> Unha cousa que poida xurdir no cuestionario
está pedindo para escribir ou implementar unha función especial chamada algo.
Se non lle dar o prototipo, entón esa cousa toda aquí,
toda esa confusión é chamado de declaración de función ou o prototipo da función,
Esta é unha das primeiras cousas que vai querer predicar para abaixo, se non é dado
para vostede inmediatamente no cuestionario.
O outro truco que eu aprendín é que
dicir que lle dan un prototipo para unha función, e dicimos: "Ei, ten que escribir."
Dentro das claves que ten no cuestionario
Se notar que existe un tipo de retorno e entender que tipo de retorno
é algo diferente de carga, o que significa que a función non retorna nada,
a continuación, unha cousa que sempre quere facer é escribir
algún tipo de instrución de retorno ao final da función.
Retorno, e neste caso, imos poñer un en branco, porque queremos encher o espazo en branco.
Pero isto fai pensar da maneira correcta sobre como é que eu vou abordar este problema?
E lembra que vai ter que voltar un valor
á chamador da función.
>> Si >> [Estudante] O estilo aplícase cando estamos escribindo código no exame?
Como recuar e este tipo de cousas? >> [Estudante] Yeah.
Non, non é tan grande.
Eu creo que unha morea de-isto é algo que vai aclarar sobre o exame o día da,
pero normalmente se preocupar con # inclúe e ese tipo de cousas, é unha especie de fóra.
[Estudante] Debe comentar o seu código escrito a man?
Debe comentar o seu código escrito a man?
Comentando sempre é bo se está preocupado con crédito parcial
ou quere comunicar a súa intención para o alumno.
Pero, unha vez máis, vai aclarar sobre o cuestionario en si e día quiz,
pero eu non creo que vai ser obrigado a escribir comentarios, non.
Normalmente non, pero é sempre o tipo de cousas que
pode comunicar a súa intención, como "Ola, aquí é onde eu estou indo con iso."
E ás veces isto pode axudar con crédito parcial.
Cool.
>> Basil.
[Basil] Cal é a diferenza entre establecer, por exemplo, int lang
nos argumentos ou parámetros contra declarar unha variable dentro da función?
Guau, o café caeu na traquea.
[Basil] Como as cousas que queremos poñer en argumentos.
Si, esta é unha gran cuestión.
Como vostede escolle as cousas que quere poñer nos argumentos
versus o que ten que facer as cousas dentro da función?
Neste caso, incluíu ambos como argumentos
porque é algo que quen vai usar a función suma
Debe especificar estas cousas.
>> A función suma, como falamos, non ten como saber
como é grande a matriz que queda do seu interlocutor ou quen está a usar a función suma.
El non ten forma de saber o tamaño desa matriz é.
A razón hai que pasar nese longo aquí como un argumento
é porque iso é algo que nós estamos basicamente dicindo o chamador da función,
quen vai usar a función suma: "Ei, non só ten que dar unha matriz
de enteiros, tamén ten que dicir o quão grande a matriz que nos deu. "
[Basil] Os serán ambos argumentos de liña de comandos?
Non, estes son argumentos reais que ten que pasar para a función.
>> Deixe-me facer unha nova páxina aquí.
[Basil] Como nome pasaría-
[Nate H.] Se eu tivera int main (void),
e eu vou poñer no meu retorno 0 aquí na parte inferior,
e dicir que quero chamar a función suma.
Quero dicir int x = suma ();
Para utilizar a función suma eu teño que pasar tanto a matriz que quero resumir
é a lonxitude da matriz, de xeito que este é o lugar onde
supoñendo que eu tivese un array de enteiros,
din tiven Numbaz int [] = 1, 2, 3,
tipo de uso que hackeou sintaxe alí,
entón o que me gustaría facer é en definitiva gustaríame pasar
tanto Numbaz e número 3
para dicir a función de suma "Ok, aquí está a matriz que quero que sumar."
"Aquí é o seu tamaño."
Isto ten sentido? Isto responde a súa pregunta?
>> En moitos aspectos, fai paralelo o que estamos facendo o principal
cando temos os argumentos de liña de comandos.
Un programa como o César cifra, por exemplo, que precisaba
argumentos de liña de comandos non sería capaz de facer calquera cousa.
Non sabería como Encriptar se non informar que a clave para usar
ou se non dixo a el o que quería corda para cifrar.
Solicitude de unha entrada, este é o lugar onde temos dous mecanismos diferentes
para a toma de entrada a partir do usuario para a toma de información a partir do usuario.
Para conxunto de problemas 1 vimos este GetInt, GetString forma, GetFloat
de solicitude de entrada, e que se chama usando o fluxo de entrada estándar.
É un pouco diferente.
É algo que podes facer nun tempo en oposición a
cando chamar o programa cando inicia o programa en execución.
Os argumentos de liña de comandos especifícanse todos cando se inicia o funcionamento do programa.
Temos a mestura dos dous destes.
Cando usamos argumentos para unha función, é moi parecido cos argumentos de liña de ordes para a principal.
É cando chamar a función que precisa dicir a el
exactamente o que necesita para realizar as súas tarefas.
Outra cousa boa para ollar, e eu vou deixar ollar no seu tempo libre,
e foi cuberto no cuestionario, era esa noción de ámbito
e as variables locais versus variables globais.
Preste atención a iso.
>> Agora que estamos chegando a estas outras cousas,
a Semana 3 comezamos a falar sobre investigación e clasificación.
Busca e clasificación, polo menos no CS50,
é moito máis unha introdución a algunhas das partes máis teóricas da ciencia da computación.
O problema da investigación, o problema da ordenación
son grandes problemas canônicos.
Como atopar un número específico dunha matriz de miles de millóns de enteiros?
Como atopar un nome específico dentro dun libro de teléfono
que está almacenado no seu portátil?
E, así, introducir esta noción de tempo de execución asintótica
realmente cuantificar canto tempo, o quão duro estes problemas son,
Canto tempo leva para resolver.
En, creo, 2011 do cuestionario hai un problema que eu creo que merece
cubrindo moi rápido, o que é un agasallo, problema 12.
O non, é Omega.
>> Aquí estamos falando sobre o tempo de execución máis rápido posible
para un determinado algoritmo e, a continuación, o tempo de execución máis lenta posible.
Este Omega e O son realmente só atallos.
Son atallos de notación por dicir
rapidez no caso mellor posible vontade nosa carreira algoritmo,
e como lento no peor caso posible o noso algoritmo pode executar?
Imos facer un par destes, e estes foron tamén códigos
no curto sobre notación asintótica, o que eu recomendo.
Jackson fixo un traballo realmente bo.
Con busca binaria, falamos de busca binaria como un algoritmo,
e adoitamos falar sobre iso en termos da súa gran O.
O que é o gran?
Cal é o tempo de execución máis lenta posible de busca binaria?
[Estudante] N ²?
Pechar, eu creo semellante a iso.
É moito máis rápido do que iso.
[Estudante] binario? >> Si, busca binaria.
[Estudante] É rexistro n.
Log n, entón o que log n significa?
É metades que cada iteração.
Exactamente, por iso, no caso de que o máis lento posible,
dicir se ten un array ordenado
dun millón de números enteiros eo número que está a buscar
ou é o primeiro elemento da matriz ou o último elemento na matriz.
Lembre, o algoritmo de procura binaria funciona ollando para o elemento do medio,
ver se ese é o xogo que está a procurar.
Se for, entón gran, que o atopou.
>> No mellor caso posible, o quão rápido é executado de busca binaria?
[Os alumnos] 1.
1, é de tempo constante, grande do 1. Si
[Estudante] Eu teño unha pregunta. Cando di facer de n, quere dicir con respecto a base 2, non?
Si, de xeito que é a outra cousa.
Dicimos n log, e eu creo que cando estaba na escola
Eu sempre pensei que era log base 10.
Si, iso si, facer 2 base normalmente é o que usan.
Unha vez máis, volvendo a busca binaria, se está a buscar por un ou outro
o elemento ao final ou o elemento en principio,
porque comeza no medio e despois de descartar
o que media non cumprir os criterios que está a buscar,
e vai ao seguinte semestre e do próximo semestre e do próximo semestre.
Se eu estou buscando o maior elemento da matriz de enteiros millóns
Vou reducir á metade é de máis rexistro de 1 millón de veces
antes de finalmente probar e ver que o elemento que eu estou buscando
está na maior ou en maior índice de matriz,
e que terá rexistro n, faga o login de 1 millón de veces.
>> Especie de burbulla.
Vostedes lembrar o algoritmo de ordenación burbulla?
Kevin, que me pode dar unha rápida recapitulação do que aconteceu no algoritmo de ordenación burbulla?
[Kevin] Basicamente el pasa por todo na lista.
El mira para os dous primeiros.
O primeiro é maior que a segunda ela pasa-los.
A continuación, el compara, segundo e terceiro, a mesma cousa, swaps,
terceiro e cuarto, todo o camiño.
Números máis grandes seguirá ata o final.
E despois de moitas voltas con todo está feito.
Exactamente por iso que Kevin dixo é que nós imos ver números maiores
burbulla até o final da matriz.
Por exemplo, se importa de camiñar connosco a través deste exemplo, esta é a nosa matriz?
[Kevin] Vai tomar 2 e 3.
3 é maior que 2, entón troca-los.
[Nate H.] Certo, entón nós trocamos estes, e así temos 2, 3, 6, 4 e 9.
[Kevin] Entón comparar a 3 e 6.
3 é menor que 6, de modo que deixalos,
e 6 e 4, que troca-los por 4 é menor que 6.
[Nate H.] Dereito, por iso fico 2, 3, 4, 6, 9.
[Kevin] e 9 é maior que 6, entón deixalo.
E volver con el de novo.
>> [Nate H.] Estou feito neste momento? >> [Kevin] Non
E por que non estou feito neste momento?
Porque parece que a miña matriz é clasificada. Estou mirando para el.
[Kevin] pasar por iso de novo e asegúrese de que hai swaps non máis
antes de deixar totalmente.
Exactamente, por iso é necesario manter a atravesar e asegúrese de que non existen swaps
que podes facer neste momento.
Era realmente só sorte, como dixen, que rematou
só ter que facer unha pasaxe e estamos clasificados.
Pero, para iso, no caso xeral, imos realmente ten que facer iso unha e outra vez.
E, de feito, este foi un exemplo do mellor caso posible,
como vimos no problema.
Nós vimos que o mellor caso posible foi n.
Pasamos por un momento matriz.
Cal é o peor caso posible para este algoritmo?
[Kevin] n ².
E o que iso parece? O que sería un ollar matriz como que levaría tempo n ²?
[Kevin] [inaudível] clasificados.
Exactamente, por iso, se eu tivese a matriz de 9, 7, 6, 5, 2,
primeiro o 9 sería burbulla todo o camiño ata.
Despois dunha iteração teriamos 7, 6, 5, 2, 9.
A continuación, a 7 sería borbulhar, 6, 5, 2, 7, 9, e así por diante e así por diante.
>> Nós teriamos que pasar por toda a matriz n veces,
e realmente pode estar un pouco máis preciso do que iso
porque unha vez que cambiamos o 9 de todo o camiño ata a súa última posición posible
sabemos que nunca temos que comparar co elemento novo.
Así que comezar a borbulhar 7-se
sabemos que podemos deixar unha vez que o 7 é pronto antes da 9
unha vez que xa comparou a 9 para el.
Se fai iso de forma intelixente, non é verdade, eu creo que moito tempo.
Non vai comparar todas as posibles combinacións de [inaudível]
cada vez que pasar por cada iteração.
Pero, aínda así, cando falamos sobre este límite superior dicimos que
vostede está ollando para n ² comparacións durante todo o tempo.
>> Imos volver, e xa estamos empezando a estar un pouco en curto tempo
Eu diría que ten que definitivamente pasar o resto da táboa,
cubrir todo.
Debería exemplos. Debería exemplos concretos.
Iso é moi práctico e útil para facelo.
Retirala la.
Este é o tipo de táboa que como pasar en ciencia da computación
ten que realmente comezar a coñecer estes corazón por.
Estes son os tipos de preguntas que vostede poñerse en entrevistas.
Estes son os tipos de cousas que son boas para saber,
e pensar sobre os casos de punta, realmente descubrir como pensar
sabendo que a burbulla clasificar a matriz peor posible
de clasificar que é aquel que está en orde inversa.
>> Punteiros. Imos falar un pouco sobre punteiros.
Nos últimos minutos que temos aquí
Sei que iso é algo xunto co arquivo de I / O que é novo.
Cando falamos de punteiros a razón pola que quero falar sobre punteiros
é, pois, un, cando estamos a traballar en C
estamos realmente en un nivel moi baixo en comparación con linguaxes de programación máis modernas.
Somos realmente capaces de manipular as variables na memoria,
descubrir onde eles están, en realidade, situado dentro da nosa memoria RAM.
Unha vez que pasou a ter aulas de sistema operativo que ver
que iso é, de novo, unha especie de abstracción.
Isto non é realmente o caso.
Temos memoria virtual que está escondendo os detalles de nós.
>> Pero, por agora pode asumir que cando ten un programa,
por exemplo, cando comezar a realizar o seu programa de cifrado de César
Vou volver para o meu iPad moi rapidamente-
que, en principio, o seu programa, se ten, digamos,
4 gigabytes de memoria RAM do seu ordenador portátil,
se esquecer ese anaco, e nós imos chamar iso de RAM.
E comeza nun lugar que nós imos chamar 0,
e remata nun lugar que nós imos chamar de 4 gigabytes.
Eu realmente non podo escribir. O home, que é cortado.
Cando o programa é executado
o sistema operativo esculpe a memoria RAM,
e especifica segmentos diferentes para distintas partes do seu programa para vivir
Aquí abaixo esta área é unha especie de terra de ninguén.
Cando vai ata un pouco máis aquí
ten realmente o lugar onde
o código para a vida dos seus programas.
Este código binario real, que en realidade arquivo executábel é cargado na memoria
cando executar un programa, e que vive no segmento de código.
E como o programa é executado o procesador mira para este segmento de código
para descubrir o que é a instrución seguinte?
Cal é a seguinte liña de código que eu teño para executar?
>> Hai tamén un segmento de datos, e é aí onde os constantes da cadea
quedan almacenados que está a usar.
E despois máis arriba hai un lugar chamado a pila.
Nós acceder á memoria usando malloc,
e despois para arriba do seu programa
hai a pila,
e é aí onde temos que chegou a xogar a maior parte do inicio.
Esta non é a escala ou nada.
Moito diso é moi dependente da máquina,
dependentes do sistema operativo, pero iso é como as cousas son relativamente fragmentada arriba.
Cando executar un programa e declarar unha variable chamada x-
Vou chamar a outra caixa de abaixo, e iso vai ser RAM tamén.
E eu vou mirar.
Imos debuxar liñas irregulares para indicar esta é só unha pequena parte da RAM
e non a súa totalidade como deseñar na parte superior.
>> Se eu declarar unha variable enteira chamada x,
entón o que eu en realidade é un mapeamento
que é almacenado na táboa de símbolos do meu programa
que une o X nome a esta rexión de memoria que eu deseño
aquí entre as barras verticais.
Se eu tivera unha liña de código no meu programa que di que x = 7
o procesador sabe "Oh, ok, eu sei que vive x neste lugar na memoria."
"Eu estou indo a ir adiante e escribir un 7 alí."
Como el sabe o que esta situación é na memoria?
Ben, todo isto está feito en tempo de compilación.
O compilador coida de reservar onde cada unha das variables están a ir
e creando un mapeamento especial ou mellor conectar os puntos
entre un símbolo e onde está indo, o nome dunha variable
e onde vai vivir na memoria.
Pero acontece que nós realmente podemos acceder a ela nos nosos programas tamén.
Iso queda importante cando comezamos a falar sobre algunhas das estruturas de datos,
que é un concepto que imos introducir máis tarde.
>> Pero, por agora, o que pode saber é que podo crear un punteiro para este local, x.
Por exemplo, podo crear unha variable punteiro.
Cando creamos unha variable punteiro usan a notación estrela.
Neste caso, este di que eu estou indo para crear un punteiro para un int.
É un tipo como calquera outro.
Dar-lle unha variable como y,
e entón configurar-lo igual ao enderezo a un enderezo.
Neste caso, podemos definir y para apuntar para x
tomando o enderezo de x, o que facemos con este comercial,
e, entón, establecer y para apuntar para el.
O que isto fai é esencialmente se miramos para a nosa memoria RAM
Isto crea unha variable independente.
El vai chamalo de y,
e cando esta liña de código é executado
Está realmente indo para crear un punteiro pouco que normalmente deseñar coma unha frecha,
e define y para apuntar para x.
Si
[Estudante] Se x é xa un punteiro, que acaba de facer
int * y = x en vez de ter o comercial?
Si
Se x é xa un punteiro, entón podes definir dous punteiros iguais uns aos outros,
caso en que y non ía apuntar para x,
pero chama a atención sobre o que quere que x está a apuntar.
Desafortunadamente, estamos fóra do tempo.
>> O que quere dicir neste momento, podemos falar sobre iso desconectada,
pero eu diría que comezar a traballar con este problema, # 14.
Podes ver que hai xa un pouco cuberto para vostede aquí.
Podes ver que cando declaramos dous punteiros, int * x e y *,
e teña en conta que apuntar o * próximo á variable foi algo que se fixo o ano pasado.
Acontece que este é semellante ao que nós estamos facendo este ano.
Non importa onde vostede escribe o * cando está declarando o punteiro.
Pero temos escrito o * ó lado do tipo
porque que o fai moi claro que está declarando unha variable punteiro.
Podes ver que declarar os dous punteiros nos dá dúas caixas.
Aquí cando imos definir x igual a malloc
o que iso está dicindo é deixar de lado a memoria no heap.
Esta pequena caixa aquí, este círculo, está situado na pila.
X está a apuntar cara a el.
Teña en conta que y non está a apuntar cara algo.
Para memoria para almacenar o número 42 en x
poderiamos usar o que a notación?
[Estudante] * x = 42.
Exactamente, * x = 42.
Isto significa que siga a frecha e xogar 42 en alí.
Aquí onde imos definir y e x temos y apuntando para x.
De novo, iso é como o que Kevin dixo onde imos definir y igual a x.
Y non está a apuntar cara x.
En vez diso, está apuntando para o que x está a apuntar cara ben.
>> E entón, finalmente nesta última caixa hai dúas cousas posibles que poderiamos facer.
Un deles é, poderiamos dicir * x = 13.
A outra cousa é que podería dicirse Alex, vostede sabe o que podemos facer aquí?
Vostede podería dicir * x = 13 ou-
[Estudante] Vostede podería dicir o que int.
[Nate H.] Se isto foi referido como unha variable int que podería facelo.
Poderiamos tamén dicir * y = 13, pois ambos están apuntando para o mesmo lugar,
para que pudéssemos usar unha variable para chegar alí.
Si >> [Estudante] Cal sería a súa aparencia só dicir que x int é 13?
Iso sería declarar unha nova variable chamada x, que non ía funcionar.
Nós teriamos unha colisión porque declarou x para ser un punteiro aquí.
[Estudante] Se só tivemos esa afirmación por si só o que sería o seu aspecto en termos do círculo?
Se tivésemos x = 13, entón teriamos unha caixa e, en vez de ter unha frecha
saíndo da caixa de nós deseña-lo como só un 13.
[Estudante] Na caixa. Okay.
>> Grazas por asistir, e boa sorte en 0 Quiz.
[CS50.TV]