[Powered by Google Translate] [Seção 4] [menos confortável]
[Nate Hardison] [Harvard University]
[Esta é CS50.] [CS50.TV]
>> Tudo bem, bem-vindo de volta à seção.
Na seção desta semana vamos fazer um par de coisas.
Nós vamos primeiro Ajuste repescagem Problema 2,
que é o conjunto de problemas César e Vigenère.
E então vamos mergulhar Quiz de 0 avaliação
e passar um pouco de tempo recapitulando o que nós já conversamos sobre
em cada uma das palestras até agora, e vamos também fazer alguns problemas
a partir de questionários ano anterior.
Dessa forma, vocês têm uma boa maneira de se preparar para isso.
>> Para começar, eu tenha iniciado um par de boas soluções
para o conjunto de problemas anterior, Conjunto de Problemas 2, neste espaço.
Se vocês todos bater este link,
e se você clicar meu nome e clique na minha primeira revisão
você verá caesar.c, que é exatamente o que eu estou olhando.
Vamos falar sobre isso muito rapidamente.
Esta é apenas uma solução de amostra.
Esta não é necessariamente a solução perfeita.
Há muitas maneiras diferentes de escrever isso,
mas há algumas coisas que eu gostaria de destacar
que eu vi como eu estava de classificação, os erros mais comuns que eu acho que
esta solução faz um trabalho muito bom de manuseio.
>> O primeiro é ter algum tipo de comentário de cabeçalho no topo.
Em linhas 1 a 7 você ver os detalhes,
exatamente o que este programa está fazendo.
Uma boa prática padrão quando você está escrevendo código C
independentemente se o seu programa está contido em um único arquivo ou
se ele está dividido em vários arquivos é ter algum tipo de
orientar comentário no topo.
Este também é para as pessoas que vão para fora e escrever código no mundo real.
Este é o lugar onde eles vão colocar informações de copyright.
A seguir estão listadas as inclui #.
Na linha 16 há essa # define, que nós vamos voltar a nos um pouco.
E então, uma vez que a função começa, começa uma vez principais,
porque este programa foi tudo contido em uma única função
a primeira coisa que acontece, e isso é muito idiomática e típica de um programa C
que leva em linha de comando argumentos é que ele verifica imediatamente
>> para a contagem de argumento, argc.
Aqui podemos ver que este programa está esperando dois argumentos exatamente.
Lembre-se que não há primeiro argumento que é o especial
que é sempre o nome do programa que está sendo executado,
o nome do arquivo executável.
E então o que isto significa é que impede o usuário de execução do programa
com argumentos mais ou menos.
A razão que nós queremos para verificar isso de imediato é porque
não podemos realmente acessar essa matriz argv aqui confiável
até que tenhamos verificado para ver o quão grande ela é.
>> Um dos erros mais comuns que eu vi foi pessoas imediatamente ir
e agarrar argv [1].
Eles pegar o argumento chave da matriz e não a um para eu verificar sobre ele,
e então faria o teste para argc, bem como o próximo teste,
com ou sem o primeiro argumento era realmente um número inteiro, ao mesmo tempo,
e que não funciona, porque no caso de que não existem argumentos fornecidos
você vai ser pegar um argumento que não existe, ou tentar pegar uma que não está lá.
>> A outra grande coisa que você deve observar é que
você sempre quer imprimir algum tipo de mensagem de erro útil
para o utilizador a orientar-los.
Tenho certeza de que você tem todos os programas de execução, onde, de repente, ele trava,
e você receber esse diálogo pouco ridículo que aparece e diz
algo terrivelmente enigmático e talvez lhe dá um código de erro ou algo parecido
que não faz sentido.
Isto é onde você realmente quer oferecer algo útil
e orientada para o usuário, de modo que quando executá-lo eles vão "Oh," palma rosto.
"Eu sei exatamente o que fazer. Sei como corrigir isso."
>> Se você não imprimir uma mensagem, então você acaba realmente
deixando o usuário a ir examinar o código-fonte
para descobrir o que deu errado.
Há também algumas vezes que você vai usar os códigos de erro diferentes.
Aqui nós apenas usou um para dizer que houve um erro,
houve um erro, houve um erro.
Programas maiores, muitas vezes, os programas que são chamados por outros programas,
irá retornar algum tipo de códigos de erro especiais em diferentes cenários
programaticamente comunicar o que você faria de outra forma
usar apenas uma bela mensagem Inglês para.
Cool.
Como nós trabalhamos para baixo, você pode ver que puxar a chave.
Testamos para ver se a chave se encaixa.
Recebemos uma mensagem do usuário.
A razão por que fazê-lo nesta fazer enquanto ciclo e isso é algo que vamos cobrir
em um pouquinho, mas acontece que se você digitar o controle D
quando você começa a GetString prompt no terminal
o que isso realmente significa é que envia um caractere especial
para o programa.
É o chamado ELF ou o fim do arquivo de caracteres.
E, nesse caso, a nossa cadeia de mensagem será nulo,
, que não foi algo que verificado para o conjunto de problemas em si.
>> Mas como nós vamos, agora que começamos a falar sobre ponteiros
e alocação dinâmica de memória na pilha,
verificação de nulo sempre que você tem uma função que poderia
retornar nulo como um valor é algo que você vai querer adquirir o hábito de fazer.
Isto é aqui principalmente para fins de ilustração.
Mas quando você vê GetString no futuro,
assim do Conjunto de Problemas 4, você vai querer manter isso em mente.
Novamente, isto não é um problema para Conjunto de Problemas 3 ou uma vez que não tinha coberto isso ainda.
Finalmente, chegamos a esta parte, onde temos para o circuito de criptografia principal,
e há um par de coisas acontecendo aqui.
Primeiro, iterar sobre a cadeia de mensagem inteira em si.
Aqui mantivemos a chamada strlen na condição,
que alguns de vocês têm apontado não é um grande caminho a percorrer.
Acontece que, neste caso, também não é grande,
em parte porque estamos modificando o conteúdo da mensagem em si
dentro do loop for, então se temos uma mensagem que é 10 caracteres,
a primeira vez que iniciar esse ciclo for strlen vai devolver o que?
10.
>> Mas se então modificar mensagem, dizer que modificar seu caráter 5,
e nós jogar em um caracter \ 0 na posição 5,
em uma iteração subseqüente strlen (mensagem) não irá retornar o que ele fez
a primeira vez que iterada,
mas, ao contrário, retornar 5, porque nós jogamos em que terminador nulo,
e comprimento da corda é definido
pelo que a posição de \ 0.
Neste caso, esta é uma ótima maneira de ir porque estamos modificando-o no lugar.
Mas você percebe que este é realmente surpreendentemente simples para criptografar
se você pode obter a matemática correta.
Tudo o que é necessário é verificar se há ou não a letra que você está olhando
é maiúscula ou minúscula.
>> A razão, só temos que verificar isso e não temos para verificar
o caso do alfa é porque
se um personagem é maiúscula ou se é minúscula
então é definitivamente um caractere alfabético,
porque não tem dígitos maiúsculas e minúsculas.
A outra coisa que fazer, e isso é um pouco complicado,
é que já modificou o padrão César cifra fórmula
que demos na especificação do conjunto de problemas.
O que é diferente aqui é que nós subtraído
na capital caso maiúsculas A, e então nós adicionamos maiúsculo
voltar no final.
>> Eu sei que alguns de vocês têm feito isso em seu código.
Será que algum de vocês fazem isso em suas apresentações?
Você fez isso. Pode explicar o que isto significa, SAHB?
Subtraindo-lo, porque você fez um mod logo depois,
você tem que levá-la para fora, assim que você começa maneira [tosse] posição.
E, em seguida, adicionando-lo de volta mais tarde você mudou mais o que você queria.
Sim, exatamente.
O que SAHB disse foi que quando se deseja adicionar
nossa mensagem e nossa chave juntos
e mod mod que, que por NUM_LETTERS,
se não escalar a nossa mensagem para o intervalo 0 a 25 apropriado primeira,
então pode acabar recebendo um número muito estranho
porque os valores que nós estamos olhando quando olhamos mensagem [i],
quando olhamos para o caráter i de nossa mensagem de texto simples,
é um valor algures nesta gama de 65-122
com base nos valores ASCII para letras maiúsculas de A a Z em minúsculas.
E assim, quando nós mod-lo por 26 ou por NUM_LETTERS,
uma vez que era o nosso # define no canto superior direito até aqui,
que vai nos dar um valor que está na faixa de 0 a 25,
e precisamos de uma maneira de escalar então que back-up
e obtê-lo no intervalo apropriado ASCII.
A maneira mais fácil de fazer isso é apenas para escalar tudo para baixo
no intervalo entre 0 e 25 para começar,
e depois mudar tudo de volta no final.
>> Outro erro comum que eu vi as pessoas se é que
se você não realmente fazer isso escalonamento imediato
e você adicionar a mensagem ea chave juntos e você adicioná-los, por exemplo,
em uma variável char, o problema com que
é, desde mensagem [i] é um número relativamente grande para começar-
lembre-se que é pelo menos 65 se for uma maiúscula caracteres
se você tiver uma chave grande, digamos, algo como 100,
e você adicionar os dois juntos em um char assinado você está indo para obter um estouro.
Você está indo para obter um valor que é maior do que 127,
que é o maior valor que uma variável char.
Mais uma vez, é por isso que você gostaria de fazer esse tipo de coisa para começar.
Algumas pessoas tem em torno desse caso, fazendo uma coisa e se testar
para ver se ele seria estouro antes de fazer isso,
mas desta forma fica em torno disso.
E então nesta solução é impresso a corda toda no final.
Outras pessoas impresso um personagem de cada vez. Ambos são impressionantes.
Neste ponto, vocês tem alguma dúvida, algum comentário sobre isso?
Coisas que você gosta, coisas que você não gosta?
>> Eu tinha uma pergunta.
Talvez eu tenha perdido durante a sua explicação, mas como é que este programa
pular os espaços para ligar a chave para o comprimento do texto?
Este é apenas César cifra. >> Ah, desculpe, sim.
Sim, vamos ver isso.
Na cifra de César temos em torno de que, por causa
só capotou caracteres.
Nós só rodada se eles eram maiúsculas ou minúsculas.
Vocês me sentindo muito bem sobre isso?
Sinta-se livre para copiar esta casa, levá-la,
compará-lo com o que vocês escreveram.
Definitivamente, não hesite em enviar perguntas sobre ele também.
E mais uma vez, perceber que o objetivo aqui com o seu problema define
não é obter vocês para escrever código perfeito para seus conjuntos de problemas.
É uma experiência de aprendizagem. Sim.
>> Voltar para o fazer enquanto loop, se for igual nulo,
assim nula apenas significa nada, eles simplesmente pressionar enter?
Nulo é um valor ponteiro especial,
e usamos nulo quando queremos dizer
temos uma variável ponteiro que está apontando para nada.
E assim normalmente isso significa que esta variável, esta variável mensagem
está vazio, e aqui, porque nós estamos usando o CS50 tipo string especial,
qual é o tipo de cadeia CS50?
Você já viu o que é quando David tirou o capuz na aula?
É um funky-que é um ponteiro, certo?
Ok, sim. >> É um char *.
E assim realmente poderíamos substituir este
aqui com a mensagem de char *,
e assim a função GetString, se não conseguir obter uma string do usuário,
não se pode analisar uma seqüência, e um caso em que não se pode analisar uma seqüência
é se o usuário digita o caractere de fim de arquivo, o controle D,
o que não é algo que você costuma fazer, mas se isso acontecer
em seguida, a função irá retornar esse valor nulo como uma maneira de dizer
"Ei, eu não tive uma seqüência."
O que aconteceria se nós não colocamos mensagem = null,
que é algo que não tem feito ainda?
Por que isso seria um problema aqui?
Porque eu sei que nós conversamos um pouco na palestra sobre vazamentos de memória.
Sim, vamos fazer isso, e vamos ver o que acontece.
>> Questão Basílio foi o que acontece se nós realmente não têm
esta mensagem de teste = null?
Vamos deslocar-se para o topo.
Vocês podem comentar isto.
Na verdade, eu vou salvá-lo em uma revisão.
Este será revisão 3.
O que você tem que fazer para executar este programa é que você terá que clicar nesse ícone de engrenagem até aqui,
e você vai ter que adicionar um argumento para ele.
Você tem que dar o argumento-chave, já que queremos passar em um argumento de linha de comando.
Aqui eu vou dar-lhe o número 3. Eu gosto 3.
Agora o zoom para fora, a execução do programa.
Está funcionando, compilação, construindo.
Aqui vamos nós. Ele está à espera de ser solicitado.
Se eu digitar algo como Olá, onde é que isso vai?
Oh, meu programa levou muito tempo para ser executado. Eu estava jawing por muito tempo.
Aqui vai.
Agora eu digitar Olá.
Vemos que ele criptografa de forma adequada.
Agora o que acontece se não fizermos GetString pronta para retornar nulo?
Lembre-se, eu disse que nós fizemos isso pressionando o controle D ao mesmo tempo.
Eu vou rolar por aqui. Vamos executá-lo novamente.
Edifício. Não vai.
Agora, quando eu bati o controle D
Eu tenho essa linha que diz opt/sandbox50/bin/run.sh, falha de segmentação.
Vocês já viram isso antes?
>> [Estudante] Por que não há >>-Desculpe?
[Estudante] Por que não há despejo de núcleo neste caso?
O despejo de núcleo é, a questão é por que não há despejo de núcleo aqui?
A questão é que não pode ser, mas o despejo de núcleo é um arquivo
que fica armazenado no disco rígido.
Neste caso temos desativado core dumps
no servidor de execução para que nós não temos pessoas seg falha
e construção de toneladas de core dumps.
Mas você pode obter um.
Despejos principais são o tipo de coisa que muitas vezes você pode desativar,
e às vezes você faz.
A falha de segmentação, para responder sua pergunta, Basílio,
está dizendo que nós tentamos acessar um ponteiro
que não foi definido para apontar para qualquer coisa.
Lembre-se de Binky no vídeo quando tenta Binky
vá acessar um ponteiro que não está apontando para alguma coisa?
Neste caso, eu acho que, tecnicamente, o ponteiro está apontando para alguma coisa.
Ele está apontando para nulo, o que é tecnicamente 0,
mas que é definido como sendo um segmento em que não está acessível
por seu programa, de modo a obter uma falha de segmentação
porque você não está acessando a memória que está em um segmento válido
como o segmento de pilha ou o segmento de pilha ou o segmento de dados.
Cool.
Mais alguma pergunta sobre César?
>> Vamos seguir em frente. Vamos olhar para Revisão 2 muito rapidamente.
Isso é Vigenère.
Aqui em Vigenère
vamos caminhar por este um muito rapidamente, porque, de novo,
Vigenère e César são bastante semelhantes.
Comentário de cabeçalho é antes,
# Define é antes para evitar o uso desses números mágicos.
O bom é dizer que queria se mudar para
um alfabeto diferente, ou algo assim.
Ao invés de ter que ir alterar manualmente todos os 26 no código
podemos mudar isso para 27 ou deixa-lo cair
se estivéssemos usando alfabetos diferentes, línguas diferentes.
Mais uma vez, temos essa verificação da contagem de argumento,
e realmente você quase pode tomar isso como um modelo.
Praticamente todos os programas que você escreve deve ter-
se leva de linha de comando argumentos, alguns seqüência de linhas
que lê como este no início.
Esse é um dos testes de sanidade primeira que você quer fazer.
>> Aqui o que nós fizemos foi a certeza de que
a palavra-chave era válida, e que foi a segunda verificação que nós fizemos.
Observe mais uma vez que estamos separados isso argc e 2.
Note-se que, neste caso, uma coisa que tinha a fazer era, em vez
de usar um ao i que queríamos para validar toda a cadeia,
e, a fim de fazer o que você realmente tem que ir caractere por caractere
sobre a corda.
Não há nenhuma boa maneira de chamar algo sobre ele
porque, mesmo, por exemplo, um para i retornará 0
se não pode analisar um número inteiro, de modo que nem sequer funciona.
Mais uma vez, bela mensagem dizendo ao usuário exatamente o que aconteceu.
Então, aqui, de novo, nós também lidar com o caso em que
o usuário digita em um personagem D controle aleatória.
>> E então, Charlotte tinha uma pergunta anterior sobre como conseguimos pular espaços
em nossa string aqui.
Esta era uma espécie de semelhante ao que fizemos com o programa do Myspace
que fizemos na seção, ea forma como isto funcionou
é que rastreou o número de cartas que tinha visto.
Enquanto caminhávamos sobre a seqüência de mensagem, como andou caractere por caractere,
que acompanhou o índice como parte do nosso loop for, e então nós também acompanhou
o número de letras, por isso não caracteres especiais, não-dígitos, não-branco espaço
que tinha visto na variável separada.
E, em seguida, esta solução modifica a chave
para obter um inteiro real da chave, e ele faz isso em tempo real,
direita antes que depois vai para criptografar a mensagem real caráter.
Existem algumas soluções que eram perfeitamente muito grande
que modificar a chave até ao testar a validade da chave.
Além de garantir que o caráter ea palavra-chave
foi um caractere alfabético também que virou em um número inteiro
na faixa de 0 a 25 para, em seguida, pular ter que fazer isso mais tarde neste loop.
Mais uma vez, você vê aqui é realmente exatamente o mesmo código
que usamos no Caesar neste momento.
Você está fazendo exatamente a mesma coisa, então o verdadeiro truque é descobrir
como transformar a palavra-chave em um número inteiro.
>> Uma coisa que nós fizemos aqui, que é um pouco densa
é que repetiu essa frase, eu acho que você poderia chamá-lo,
3 vezes separadas nas linhas 58, 59 e 61.
Alguém pode explicar o que exatamente esta frase faz?
Ele está acessando um personagem, como você disse.
Sim, é [inaudível] um personagem na palavra-chave,
e por isso é visto número de letras, porque você só está se movendo ao longo
a palavra-chave, uma vez que você tenha visto a carta,
de modo que vai efetivamente pular espaços e coisas assim.
Sim, exatamente.
E então, uma vez que você viu o branco mod palavra-chave que só assim você se mover de volta.
Exatamente. Essa é uma explicação perfeita.
O que Kevin disse é que queremos índice para a palavra-chave.
Queremos chegar o caráter num_letters_seen, se quiser,
mas se num_letters_seen excede o comprimento da palavra-chave,
a nossa forma de voltar para a faixa apropriada é que usar o operador mod
efetivamente envolvente.
Por exemplo, como a curto, a nossa palavra-chave é bacon,
e é 5 letras.
Mas temos visto seis letras do nosso texto simples neste momento
e criptografada 6.
Vamos acabar acessando o num_letters_seen,
que é de 6, mod o comprimento da palavra-chave, 5,
e assim vamos conseguir um, e assim que nós vamos fazer é que vamos
acesso ao interior do nosso primeiro personagem palavra-chave nesse ponto.
>> Tudo bem, todas as perguntas sobre Vigenère
antes de seguir em frente?
Vocês me sentindo muito bem sobre isso?
Legal, ótimo.
Eu quero ter certeza de que vocês estão tendo a chance de ver o código
que acha que está bom e tem a chance de aprender com ele.
Esta vai ser a última vez que vou estar usando os espaços para o momento,
e nós vamos fazer a transição agora, e eu estou indo para ir para cs50.net/lectures
para que possamos fazer um pouco de análise quiz.
A melhor maneira que eu acho que para começar a fazer teste revisão
é vir para esta página Palestras, cs50.net/lectures,
e debaixo de cada uma das rubricas semanas, então se eu olhar aqui na Semana 0,
Vejo que temos uma lista de tópicos que cobrimos na Semana 0.
>> Se qualquer um desses tópicos parece estranho para você
você definitivamente vai querer voltar e vasculhar as anotações de aula e, possivelmente,
mesmo folhear as palestras, vê-los novamente se quiser
para ter uma idéia de o que está acontecendo com cada um desses temas.
Direi ainda este ano, um dos recursos legais que temos
é destes shorts que criamos, e se você olhar na Semana 0,
não temos todos os temas, mas temos um bom número deles,
algumas das mais complicadas, então assistindo esses shorts de novo
é uma boa maneira para chegar até a velocidade.
Em particular, eu vou colocar em uma ficha para o 3 na parte inferior, uma vez que eu fiz aqueles.
Mas se você está lutando com o binário, bits, hex, esse tipo de coisa,
binário é um ótimo lugar para começar.
ASCII é outro que é bom para ver também.
Você pode até mesmo ver-me na velocidade 1.5x se eu estou indo muito devagar para você.
Desde a sua revisão, sinta-se livre para fazer isso.
>> Só para começar muito rapidamente, nós vamos passar por um casal destes problemas do quiz
apenas para rapidamente churn através destes.
Por exemplo, vamos olhar para 16 problema que eu tenho aqui em cima da placa.
Temos a seguinte cálculo em binário,
e queremos mostrar qualquer trabalho.
Ok, eu vou dar a este um tiro.
Vocês devem seguir junto com o papel,
e nós vamos fazer isso muito rapidamente.
Queremos executar o seguinte cálculo em binário.
Eu tenho 00110010.
E eu estou indo para adicionar a ele 00110010.
Para a matemática gênios acompanhando em casa,
esta é efectivamente multiplicar por 2.
Vamos começar.
Nós vamos seguir o algoritmo disso mesmo que nós fazemos
quando adicionamos números decimais juntos.
Realmente a única diferença aqui é que nós loop de volta em torno de
uma vez que temos 1 + 1 em vez de uma vez ficamos com a 10.
>> Se começarmos a partir da direita, muito rapidamente, o que é o primeiro dígito?
[Estudante] 0. >> [Nate H.] 0.
Grande, o segundo dígito?
[Estudante] 1.
[Nate H.] É um 1? 1 + 1 é?
[Estudante] 10.
[Nate H.] Exatamente, então o que é o dígito que eu escrevo logo abaixo as 2 adicionados juntos?
[Estudante] 1, 0 ou 0 e, em seguida, levar o 1.
[Nate H.] 0 e levar a 1, exatamente.
Em seguida um up, Basil, você está acima.
Qual é o terceiro? >> [Basil] 1.
[Nate H.] 1, perfeito. Kevin?
[Kevin] 0. >> [Nate H.] 0, Charlotte?
[Charlotte] 0. >> [Nate H.] Sim, eo que eu faço?
[Aluno] O 1.
[Nate H.] E o que eu faço? E então eu carrego a 1.
Perfeito, SAHB? >> [SAHB] Agora você tem um.
[Nate H.] E eu faço alguma coisa aqui?
[SAHB] Então, para a próxima que você tem um porque você transitadas 1.
[Nate H.] Ótimo, então aqui nós podemos terminá-lo.
Cool.
[Estudante] O 0 + 0 = 0?
0 + 0 = 0.
1 + 1, como você disse, é de 10, ou 1, 0, sim.
10 é um equívoco, porque para mim 10 significa o número 10,
e é a peculiaridade de como estamos representando-o quando estamos escrevendo.
Nós representar o número 2, por 1, 0, e o número 10 é um pouco diferente.
>> O que é uma espécie de bom sobre o binário é que não há realmente que muitos
casos, você precisa aprender.
Há 0 + 0 = 0, 0 + 1 = 1,
1 + 1 é 0, e, em seguida, carregar um 1,
e então você pode ver aqui na terceira coluna da direita
tivemos este 1, 1 e 1.
E 1 + 1 + 1 é um 1,
e você carrega outro 1.
Quando você está fazendo a adição binária, muito simples.
Eu faria um casal mais desses para verificar a sanidade vós
antes de ir porque este é
provavelmente algo que veremos no questionário.
Agora vamos fazer este próximo também.
Vamos fazer 17 problema.
Nós estamos indo para converter o seguinte número binário para decimal.
Eu tenho 10100111001.
Lembre-se no vídeo binário que eu fiz
Eu andei por um par de exemplos, e mostrei como
tudo funciona quando você está fazendo isso em decimal.
Quando você está trabalhando em representação decimal Acho que estamos
neste momento em nossas vidas tão fluente em que ela
é muito fácil para encobrir a mecânica de como ele realmente funciona.
>> Mas para fazer uma rápida recapitulação, se eu tiver o número 137
isso realmente significa e de novo, isto é, em representação decimal-
o número 137 em decimal significa que tenho 1 x 100 + 3 x 10 + 7 x 1.
Isso tudo é permanecer na tela.
E então, se você olhar para esses números aqui,
100, 10 e 1, você vê que eles são realmente todas as potências de 10.
Eu tenho 10 ², 10 ¹, e 10 para o zero.
Nós temos um tipo semelhante de coisa em binário,
exceto que a nossa base, como o chamamos, é 2 em vez de 10.
Esses 10s que eu escrevi aqui no fundo,
este ² 10, 10 ¹, 10 ao zero, 10 é a nossa base,
e o expoente, 0, 1, ou 2,
está implícita a posição do dígito do número que escrever.
1, se olharmos para ele, este 1 está na posição 2.
A 3 está na posição 1, e o 7 está na posição 0.
É assim que tivermos os vários expoentes abaixo de nossas bases.
>> Após tudo isso we'll-na verdade, você sabe o que?
Nós vamos fazer, onde fiz o meu botão desfazer ir?
Não vai.
Eu amo este desfazer coisa.
Após isso, eu acho que para mim pelo menos,
a maneira mais fácil para começar a converter um número binário
ou um número hexadecimal onde a base é 16
e não 10 ou 2 é ir em frente e escrever
as bases e expoentes para o conjunto de números em meu número binário, na parte superior.
Se começarmos a partir da esquerda para a direita de novo,
que é uma espécie de contra-intuitivo,
Eu vou mudar de volta para o preto aqui, temos a 2 para a posição 0,
e então temos 2 ¹, 2 ²,
e, em seguida, 2 para a 3, 2 a 4, 2 a 5, 6,
7, 8, 9, e 10.
Estes números que eu escrevi para fora são todos os expoentes.
Eu só escrevi as bases aqui no 3 primeiro apenas para o espaço.
>> Neste momento eu estou indo para ir em frente e eu estou indo realmente para apagar
as coisas que fizemos em decimal, se está tudo bem.
Vocês todos tem isso.
Aqueles de vocês assistir online eu tenho certeza que será capaz de voltar-me se você quiser.
De voltar para a caneta.
Agora, o que podemos fazer, se vocês não são totalmente até a velocidade em seus poderes de 2,
que é totalmente legal.
Acontece. Eu entendo.
Uma vez eu tive uma entrevista de emprego onde me foi dito que eu deveria saber todas as potências de 2
-se através de 2 a 30.
Não era um trabalho que eu tenho.
De qualquer forma, vocês podem ir em frente e fazer as contas aqui,
mas com o binário que não faz muito sentido,
e nem faz sentido com decimal ou hexadecimal ou,
a fazer as contas para onde você tem zeros.
Você pode ver que eu tenho 0 aqui, um 0 aqui, 0 aqui, 0 aqui, 0 aqui, 0 aqui.
Por que não faz sentido fazer a matemática real
para calcular a potência adequada, de 2 para essa posição?
Precisamente, como Charlotte disse, será 0.
Poderia muito bem salvar a época se calcular potências de 2 não é o seu forte.
Neste caso, só precisamos calculá-lo para 2 a 0, o que é-?
[Estudante] 1.
[Nate H.] 1, 2 e 3, que é a-?
[Estudante] 8. >> [Nate H.] 8.
2 à 4?
[Estudante] 2. Sinto muito, 1.
[Nate H.] 2 a 4 é 16, exatamente.
2 à 5, Kevin? >> 32.
[Nate H.] 32, 2 a 8?
[Estudante] 32 x 8, 256.
[Nate H.] Perfeito.
E 2 para o 10?
[Estudante] 1024.
[Nate H.] Sim, 1024.
>> Uma vez que temos esses números podemos somar todos eles.
E é aqui que é realmente importante para fazer um par de coisas.
Uma delas é ir devagar e verificar o seu trabalho.
Você pode dizer que há um 1 no final deste número,
então eu deveria ficar definitivamente um número ímpar como o meu resultado,
porque todos os outros vão ser ainda números
dado que é um número binário.
A outra coisa a fazer é se você chegar a este ponto no teste
e você escreveu chegar até este ponto
e você está correndo contra o tempo
olhar para o número de pontos que o problema vale a pena.
Este problema, como você pode ver, se eu virar de volta para o meu laptop muito rapidamente-
este problema vale 2 pontos, de modo que este não é o tipo de adição
você deve estar passando, se você realmente está pressionado pelo tempo.
Mas vamos voltar para o iPad, e nós vamos passar por isso muito rapidamente.
>> Eu gosto de fazer os pequenos números primeira
porque eu acho que mais fácil.
Eu gosto de 32 e 8, porque eles vão juntos muito facilmente, e nós temos 50.
16 e 1 recebe 17.
Não temos 57,
e depois podemos fazer o resto deste, para que possamos fazer 57, 156.
Vamos.
Homem, bem, vamos ver.
Tivemos 57, 256 e 1024.
Neste ponto, eu prefiro passar.
Eu não tenho idéia. Eu claramente precisa de ler sobre isso.
7, 6, e 4, obtém 17.
1, 5, 5, 2, 13.
Então, temos três, e então nós começamos 1.
1337.
Ovo de Páscoa, alguém?
Qualquer pessoa reconhecer esse número?
Chris reconhece o número. O que significa, Chris?
[Chris] Leet.
Leet, por isso, se você olhar para isso, parece que leet.
Material hacker. Cuidado com esse tipo de coisa no meio termo, ou o teste, melhor dizendo.
Se você ver esse tipo de coisa e você está se perguntando "Huh",
que pode realmente significar alguma coisa.
Eu não sei. David gosta de colocá-lo dentro
É uma boa maneira de sanidade verificar.
Como bem, eu posso ver o que está acontecendo.
>> Isso é uma coisa Semana 0/Week.
Se voltar para o nosso laptop agora,
diminuir o zoom, e um par de outras coisas.
Há ASCII, que temos vindo a fazer um monte de com os conjuntos de problemas.
Esta noção de capital A. O que é isso mesmo?
Sabendo que é o inteiro decimal.
65 é o que está mapeado para na tabela ASCII,
e que é, portanto, como o computador, escreve ele,
e é assim que temos vindo a fugir com escrevendo
A personagem da capital e do caráter letras minúsculas de a
em algumas dessas soluções e conjuntos de problemas que você tem feito.
A par de outras coisas.
Temos declarações, expressões booleanas, condições, loops, variáveis ​​e segmentos.
>> Aqueles tudo parece fazer sentido para a maior parte?
Parte dessa terminologia é um pouco descolada, às vezes.
Eu gosto de pensar de uma declaração como para a maior parte algo que termina com um ponto e vírgula.
Declarações como x = 7, que define uma variável,
presumivelmente chamado x = 7.
Presumivelmente x também é um tipo que pode armazenar o número 7,
por isso é um int ou possivelmente uma bóia ou um curto ou um char,
algo assim.
Uma expressão booleana está usando estes dois iguais
eo estrondo igual ou não é igual, menor que, maior que,
inferior ou igual a, todo o tipo de coisas.
Condições então são declarações, se outro lugar.
Gostaria de lembrar que você não pode ter uma pessoa sem um correspondente se.
Da mesma forma, você não pode ter uma pessoa se sem um correspondente se.
Loops, recordar os três tipos de loops estamos martelando em você
para o último par de seções e conjuntos de problemas.
Usando que quando, quando você está recebendo entrada do usuário,
usando while até que uma determinada condição é verdadeira,
e em seguida, usando os loops se você precisa
saber qual iteração do loop que você está no momento é como eu penso sobre isso.
Ou, se você está fazendo um para cada personagem de uma série que eu quero fazer alguma coisa,
para cada elemento em uma matriz que eu quero fazer algo para esse elemento.
>> Tópicos e eventos.
Estes não cobrimos de forma tão explícita em C,
mas lembre-se este a partir do zero.
Esta é a noção de ter roteiros diferentes.
Esta é também a noção de transmitir um evento.
Algumas pessoas não utiliza a transmissão de seus projetos, inicialmente,
que é totalmente legal,
mas estas são duas formas diferentes de lidar com esta questão maior chamados de concorrência,
que é como você começa a executar programas
ou aparentemente executar ao mesmo tempo?
Diferentes tarefas em execução, enquanto outras tarefas também estão em execução.
Esta é a forma como seu sistema operacional parece funcionar.
É por isso que, ainda que, por exemplo,
Eu tenho o meu navegador rodando, eu também posso ligar Spotify e tocar uma música.
Isso é mais uma coisa conceitual para entender.
Gostaria de ter um olhar para os fios curtos
se você quiser saber mais sobre isso.
>> Vamos ver, acredito que poderia ter sido
um problema sobre isso em um desses.
Mais uma vez, acho que tópicos e eventos não são algo que iremos cobrir em C
só porque é muito mais difícil do que em Scratch.
Você não deve se preocupar com isso lá, mas definitivamente entender os conceitos,
entender o que está acontecendo.
Antes de seguir em frente, qualquer dúvida sobre Semana 0 materiais?
Todo mundo se sentindo muito bem?
Variáveis ​​compreensão e que é uma variável?
>> Seguindo em frente. 1 semana.
Um par de coisas aqui que não foram especialmente visados
na revisão questionário necessariamente e também coisas mais conceituais para pensar.
A primeira é a noção de que de código fonte, compiladores e código objeto são.
Alguém? Basil.
É objeto de código, quero dizer código-fonte é o que você colocar bumbum,
e código objeto é o bumbum põe para fora para que o computador possa ler o programa.
Exatamente.
O código-fonte é o código C que você realmente digitar.
Código objeto é o que você sai de bumbum.
É a 0s e 1s em que formato binário.
Então, o que acontece é que quando você tem um monte de arquivos de objeto,
dizer que você está compilando um projeto ou um programa que usa vários arquivos de código fonte,
que, por convenção têm a extensão de arquivo. c.
É por isso que temos caesar.c, vigenère.c.
Se você estiver escrevendo programas em Java você dar-lhes a extensão. Java.
Programas em Python têm a extensão. Aa freqüência.
>> Uma vez que você tem vários arquivos. C, compilá-los.
Clang cospe todo esse lixo binário.
Então, porque você só quer um programa
você tem o link de ligação de todos estes arquivos objeto juntos
em um arquivo executável.
Este é também o que acontece quando você usa a biblioteca CS50, por exemplo.
A biblioteca CS50 é tanto isso. H arquivo de cabeçalho
que você leu, que # includecs50.h.
E então é também um arquivo de biblioteca especial binário
que foi compilado que é 0s e 1s,
e que a L-bandeira, por isso, se voltarmos aos nossos espaços e estamos muito rapidamente
o que está acontecendo aqui, quando olhamos para o nosso comando bumbum,
o que temos é este é o nosso arquivo de código fonte aqui.
Estes são um bando de sinalizadores de compilador.
E então, no final, estes elo l-bandeiras em
os arquivos binários reais para essas duas bibliotecas, a biblioteca CS50 e, em seguida, a biblioteca de matemática.
>> Entender cada tipo de finalidade arquivos '
no processo de compilação é algo que você vai querer ser capaz de
dar, pelo menos, um elevado nível de visão.
Código fonte vem dentro do código objeto sai.
Arquivos de código objeto vincular juntos, e você recebe um arquivo, bonito executável.
Cool.
Esta é também onde você pode obter erros em vários pontos
no processo de compilação.
Este é o lugar onde, por exemplo, se você tirar essa bandeira ligação,
a bandeira CS50, e omitir-lo em espaços ou quando você está executando o seu código,
este é o lugar onde você vai ter um erro na fase de vinculação,
eo vinculador vai dizer: "Ei, você chamou um GetString função
que está na biblioteca CS50 ".
"Você me disse que estava na biblioteca CS50, e eu não consigo encontrar o código para ele."
É aí que você tem que ligar-lo, e que é separado
a partir de um erro do compilador porque o compilador está olhando sintaxe e esse tipo de coisa.
É bom saber o que está acontecendo quando.
>> Outras coisas a conhecer.
Eu diria que você definitivamente quero ter um olhar para o curto no typecasting feito por Jordan
para entender o que ints estão sob o capô,
o que chars estão sob o capô.
Quando falamos em ASCII e nós realmente olhar para a tabela ASCII,
o que está fazendo é dando-nos um olhar sob o capô
a forma como o computador realmente representa o capital A e 7 dígitos
e uma vírgula e um ponto de interrogação.
O computador também tem formas especiais para representar
o número 7 como um inteiro.
Ele tem um jeito especial para representar o número 7 como um número de ponto flutuante,
e aqueles que são muito diferentes.
Typecasting é como você dizer ao computador "Ei, eu quero que você converter
a partir de uma representação a outra representação ".
Por que não vamos dar uma olhada nisso.
>> Também gostaria de dar uma olhada no curto em bibliotecas e em curto compiladores.
Aqueles falar sobre o processo de compilação,
que é uma biblioteca, e passar por cima de algumas dessas perguntas que você pode se perguntou.
Perguntas sobre o material Semana 1?
Há algum tópicos aqui que parecem assustador que você gostaria de cobrir?
Estou tentando explodir na maioria destes tópicos anteriores, para que possamos chegar a
ponteiros e fazer um pouco de recursão.
Pensamentos?
Qualquer coisa para cobrir?
Tempo para um pouco de chocolate, talvez?
Vocês estão trabalhando com ele.
Eu vou continuar a beber o meu café.
Semana 2.
Boa chamada, boa chamada.
Na 2 ª semana falamos um pouco mais sobre funções.
>> Nos primeiros conjuntos de problemas poucas que realmente não escrever quaisquer funções em tudo
diferente do que função?
[Estudante] principal. >> Principal, exatamente.
E assim temos visto os trajes diferentes que veste principal.
Há aquele em que não tem argumentos,
e nós apenas dizer vazio entre os parênteses,
e depois há o outro, onde queremos ter argumentos de linha de comando,
e, como vimos, que é onde você tem argc int e string matriz argv
ou agora que nós realmente expostos string para ser o char que é
Nós vamos começar a escrevê-lo como char * argv e colchetes.
No Conjunto de Problemas 3, vocês viram um monte de funções,
e você implementou um monte de funções, desenhar, olhar para cima, scramble.
Os protótipos foram todos escritos lá para você.
>> O que eu queria falar aqui com funções muito rapidamente
é que existem 3 partes a eles sempre que você escrever uma função.
Você tem que especificar o tipo de retorno da função.
Você tem que especificar um nome para a função, e então você tem que especificar
a lista de argumentos ou a lista de parâmetros.
Por exemplo, se eu fosse escrever uma função para resumir um monte de números inteiros
e depois voltar para mim a soma do que seria o meu tipo de retorno
se eu queria somar inteiros e depois retornar a soma?
Em seguida, o nome da função.
Se eu ir em frente e escrever em verde, essa parte é o tipo de retorno.
Esta parte é o nome.
E então, entre parênteses
é onde eu dou os argumentos,
muitas vezes abreviado como args, às vezes chamado params para os parâmetros.
E se você tem um, você só especificar a um.
Se você tiver vários de separar cada um com uma vírgula.
E para cada argumento que você dê duas coisas que são-Kevin?
[Kevin] Você tem que dar o tipo e em seguida o nome.
E então o nome, eo nome é o nome que você vai usar
para se referir a esse argumento dentro da função soma,
dentro da função que você está escrevendo atualmente.
>> Você não tem que, por exemplo, se eu estou indo para resumir,
dizer, uma matriz de números inteiros: nós fazer matriz int,
e eu vou me dar algumas chaves lá-
então, quando eu passar um array para a função soma
I passá-lo na primeira posição da lista de argumento.
Mas a matriz que passar não tem que ter o nome arr.
Arr. vai ser como eu me refiro a esse argumento dentro do corpo da função.
A outra coisa que temos de ter em conta,
e isso é um pouco diferente de funções, mas eu acho que é um ponto importante,
é que, no C, quando estou escrevendo uma função como esta
como eu sei quantos elementos estão nesta matriz?
Isso é um pouco de uma pergunta capciosa.
Nós conversamos sobre isso um pouco na seção da última semana.
Como eu sei que o número de elementos dentro de uma matriz em C?
Existe uma maneira?
>> Acontece que não há nenhuma maneira de saber.
Você tem que passá-lo em separado.
Existe um truque que você pode fazer
se você estiver na mesma função em que a matriz tenha sido declarado,
e você está trabalhando com uma grande pilha.
Mas isso só funciona se você estiver na mesma função.
Depois de passar uma matriz para outra função ou se você tiver declarado uma matriz
e você colocar essa matriz na pilha, você já usou malloc
e esse tipo de coisa, então todas as apostas estão fora.
Então, você realmente tem que passar em torno de
um argumento especial ou outro parâmetro
dizendo o quão grande é a matriz.
Neste caso, eu gostaria de usar uma vírgula-Sinto muito, vai para fora da tela aqui-
e eu passar em outro argumento
e chamá-lo len int para o comprimento.
>> Uma coisa que possa surgir no questionário
está pedindo para você escrever ou implementar uma função especial chamada algo.
Se não lhe dar o protótipo, então essa coisa toda aqui,
toda essa confusão é chamado de declaração de função ou o protótipo da função,
esta é uma das primeiras coisas que você vai querer pregar para baixo, se não for dado
para você imediatamente no questionário.
O outro truque que eu aprendi é que
dizer que lhe dão um protótipo para uma função, e dizemos: "Ei, você tem que escrever."
Dentro das chaves que você tem no questionário
Se você notar que existe um tipo de retorno e você percebe que o tipo de retorno
é algo diferente de vazio, o que significa que a função não retorna nada,
em seguida, uma coisa que você definitivamente quer fazer é escrever
algum tipo de instrução de retorno no final da função.
Retorno, e neste caso, vamos colocar um em branco, porque queremos preencher o espaço em branco.
Mas isto faz você pensar da maneira correta sobre como é que eu vou abordar esse problema?
E lembra que você vai ter que retornar um valor
à chamador da função.
>> Sim. >> [Estudante] O estilo aplica quando estamos escrevendo código no teste?
Como recuo e esse tipo de coisa? >> [Estudante] Yeah.
Não, não é tão grande.
Eu acho que um monte de-isto é algo que vai esclarecer sobre o teste no dia da,
mas normalmente se preocupar com # inclui e esse tipo de coisa, é uma espécie de fora.
[Estudante] Você precisa comentar seu código escrito à mão?
Você precisa comentar o seu código escrito à mão?
Comentando é sempre bom se você está preocupado com crédito parcial
ou você quer comunicar a sua intenção para o aluno.
Mas eu, mais uma vez, vai esclarecer sobre o questionário em si e no dia quiz,
mas eu não acredito que você vai ser obrigado a escrever comentários, não.
Normalmente não, mas é definitivamente o tipo de coisa que
você pode comunicar a sua intenção, como "Ei, aqui é onde eu estou indo com isso."
E às vezes isso pode ajudar com crédito parcial.
Cool.
>> Basil.
[Basil] Qual é a diferença entre declarar, por exemplo, int lang
nos argumentos ou parâmetros contra declarar uma variável dentro da função?
Uau, o café caiu na traquéia.
[Basil] Como que as coisas que queremos colocar em argumentos.
Sim, essa é uma grande questão.
Como você escolhe as coisas que você quer colocar nos argumentos
versus o que você deve fazer as coisas dentro da função?
Neste caso, incluiu ambos como argumentos
porque é algo que quem vai usar a função soma
precisa especificar essas coisas.
>> A função soma, como falamos, não tem como saber
como é grande a matriz é que fica de seu interlocutor ou quem estiver usando a função soma.
Ele não tem forma de saber o tamanho dessa matriz é.
A razão devemos passar nesse comprimento aqui como um argumento
é porque isso é algo que nós estamos basicamente dizendo o chamador da função,
quem vai usar a função soma: "Ei, você não só tem que nos dar uma matriz
de inteiros, você também tem que nos dizer o quão grande a matriz que você nos deu. "
[Basil] Aqueles serão ambos argumentos de linha de comando?
Não, estes são argumentos reais que você deve passar para a função.
>> Deixe-me fazer uma nova página aqui.
[Basil] Como nome iria passar-
[Nate H.] Se eu tiver int main (void),
e eu vou colocar no meu retorno 0 aqui na parte inferior,
e dizer que eu quero chamar a função soma.
Eu quero dizer int x = soma ();
Para usar a função soma eu tenho que passar em tanto a matriz que eu quero resumir
e o comprimento da matriz, de modo que este é o local onde
supondo que eu tivesse um array de inteiros,
dizem tive Numbaz int [] = 1, 2, 3,
tipo de uso que hackeou sintaxe ali,
então o que eu gostaria de fazer é em suma eu gostaria de passar em
tanto Numbaz e o número 3
para dizer a função de soma "Ok, aqui está a matriz que eu quero que você somar."
"Aqui é o seu tamanho."
Isso faz sentido? Isso responde a sua pergunta?
>> Em muitos aspectos, ele faz paralelo o que estamos fazendo com o principal
quando temos os argumentos de linha de comando.
Um programa como o César cifra, por exemplo, que precisava
argumentos de linha de comando não seria capaz de fazer qualquer coisa.
Ele não saberia como criptografar se você não informar o que a chave para usar
ou se você não disse a ele o que você queria corda para criptografar.
Solicitação de uma entrada, este é o lugar onde temos dois mecanismos diferentes
para a tomada de entrada a partir do utilizador, para a tomada de informação a partir do utilizador.
Para Conjunto de Problemas 1 vimos este GetInt, GetString forma, GetFloat
de solicitação de entrada, e que é chamado usando o fluxo de entrada padrão.
É um pouco diferente.
Isso é algo que você pode fazer em um tempo ao contrário
quando você chamar o programa, quando você iniciar o programa em execução.
Os argumentos de linha de comando são especificados todos quando você iniciar o funcionamento do programa.
Nós temos a mistura dos dois desses.
Quando usamos argumentos para uma função, é muito parecido com os argumentos de linha de comando para a principal.
É quando você chamar a função que você precisa dizer a ele
exatamente o que ele precisa para executar suas tarefas.
Outra coisa boa para olhar, e eu vou deixar você olhar em seu tempo livre,
e foi coberto no questionário, era essa noção de escopo
e as variáveis ​​locais versus variáveis ​​globais.
Preste atenção a isso.
>> Agora que estamos chegando para essas outras coisas,
na Semana 3 começamos a falar sobre pesquisa e classificação.
Pesquisa e classificação, pelo menos no CS50,
é muito mais uma introdução a algumas das partes mais teóricas da ciência da computação.
O problema da pesquisa, o problema da ordenação
são grandes problemas canônicos.
Como você encontrar um número específico em uma matriz de milhares de milhões de inteiros?
Como você encontrar um nome específico dentro de um livro de telefone
que está armazenado em seu laptop?
E, assim, introduzir esta noção de tempos de execução assintóticos
realmente quantificar quanto tempo, o quão duro esses problemas são,
quanto tempo demora para resolver.
Em, acredito, 2011 do questionário há um problema que eu acho que merece
cobrindo muito rapidamente, o que é um presente, problema 12.
O não, é Omega.
>> Aqui nós estamos falando sobre o tempo de execução mais rápido possível
para um determinado algoritmo e, em seguida, o tempo de execução mais lenta possível.
Este Omega e O são realmente apenas atalhos.
Eles são atalhos de notação por dizer
rapidez no caso melhor possível vontade nossa corrida algoritmo,
e como lento no pior caso possível nosso algoritmo irá executar?
Vamos fazer um par destes, e estes foram também abrangidos
no curto sobre notação assintótica, o que eu recomendo.
Jackson fez um trabalho realmente bom.
Com busca binária, falamos de busca binária como sendo um algoritmo,
e costumamos falar sobre isso em termos de sua grande O.
O que é o grande?
Qual é o tempo de execução mais lenta possível de busca binária?
[Estudante] N ²?
Fechar, eu acho semelhante a isso.
É muito mais rápido do que isso.
[Estudante] binário? >> Sim, busca binária.
[Estudante] É log n.
Log n, então o que log n significa?
É metades que cada iteração.
Exatamente, por isso, no caso o mais lento possível,
dizer se você tem um array ordenado
de um milhão de números inteiros eo número que você está procurando
ou é o primeiro elemento da matriz ou o último elemento na matriz.
Lembre-se, o algoritmo de busca binária funciona olhando para o elemento do meio,
ver se esse é o jogo que você está procurando.
Se for, então ótimo, você o encontrou.
>> No melhor caso possível, o quão rápido é executado de busca binária?
[Os alunos] 1.
1, é de tempo constante, grande O do 1. Sim.
[Estudante] Eu tenho uma pergunta. Quando você diz fazer de n, você quer dizer com respeito a base 2, certo?
Sim, de modo que é a outra coisa.
Dizemos n log, e eu acho que quando eu estava na escola
Eu sempre achei que era log base 10.
Sim, isso, sim, fazer 2 base normalmente é o que usamos.
Mais uma vez, voltando a busca binária, se você estiver procurando por um ou outro
o elemento no final ou o elemento no início,
porque você começa no meio e depois de descartar
o que meia não cumprir os critérios que você está procurando,
e você vai para o próximo semestre e do próximo semestre e do próximo semestre.
Se eu estou procurando o maior elemento da matriz de inteiros milhões
Vou reduzir para metade é a mais registro de 1 milhão de vezes
antes de eu finalmente testar e ver que o elemento que eu estou procurando
está na maior ou na maior índice da matriz,
e que terá registro de n, faça o login de 1 milhão de vezes.
>> Espécie de bolha.
Vocês lembrar o algoritmo de ordenação bolha?
Kevin, você pode me dar uma rápida recapitulação do que aconteceu no algoritmo de ordenação bolha?
[Kevin] Basicamente ele passa por tudo na lista.
Ele olha para os dois primeiros.
Se o primeiro é maior do que a segunda ela passa-los.
Em seguida, ele compara, segundo e terceiro, a mesma coisa, swaps,
terceiro e quarto, todo o caminho.
Números maiores seguirá até o fim.
E depois de muitas voltas no entanto você está feito.
Exatamente, por isso que Kevin disse é que nós vamos assistir números maiores
bolha até ao final da matriz.
Por exemplo, você se importa de caminhar conosco através deste exemplo, se esta é a nossa matriz?
[Kevin] Você vai tomar 2 e 3.
3 é maior que 2, então você trocá-los.
[Nate H.] Certo, então nós trocamos estes, e assim temos 2, 3, 6, 4 e 9.
[Kevin] Então você comparar a 3 e 6.
3 é menor que 6, de modo que você deixá-los,
e 6 e 4, você trocá-los por 4 é menor que 6.
[Nate H.] Direito, por isso fico 2, 3, 4, 6, 9.
[Kevin] e 9 é maior do que 6, então você deixá-lo.
E você voltar com ele novamente.
>> [Nate H.] Estou feito neste momento? >> [Kevin] Não.
E por que não estou feito neste momento?
Porque parece que minha matriz é classificada. Estou olhando para ele.
[Kevin] passar por isso novamente e certifique-se de que existem swaps não mais
antes de parar totalmente.
Exatamente, por isso é necessário manter a atravessar e certifique-se de que não existem swaps
que você pode fazer neste momento.
Era realmente apenas sorte, como você disse, que terminou
só ter que fazer uma passagem e estamos classificados.
Mas, para isso, no caso geral, vamos realmente tem que fazer isso uma e outra vez.
E, de fato, este foi um exemplo do melhor caso possível,
como vimos no problema.
Nós vimos que o melhor caso possível foi n.
Passamos por um momento matriz.
Qual é o pior caso possível para este algoritmo?
[Kevin] N ².
E o que isso parece? O que seria um olhar matriz como que levaria tempo n ²?
[Kevin] [inaudível] classificados.
Exatamente, por isso, se eu tivesse a matriz de 9, 7, 6, 5, 2,
primeiro o 9 seria bolha todo o caminho até.
Depois de uma iteração teríamos 7, 6, 5, 2, 9.
Em seguida, a 7 seria borbulhar, 6, 5, 2, 7, 9, e assim por diante e assim por diante.
>> Nós teríamos que passar por toda a matriz n vezes,
e você pode realmente ficar um pouco mais preciso do que isso
porque uma vez que mudamos o 9 todo o caminho até em sua última posição possível
sabemos que nunca temos que comparar com o elemento novo.
Assim que começar a borbulhar o 7-se
sabemos que podemos parar uma vez que o 7 é logo antes da 9
uma vez que já comparou a 9 para ele.
Se você fizer isso de forma inteligente, não é verdade, eu acho, que muito tempo.
Você não vai comparar todas as possíveis combinações de [inaudível]
cada vez que você passar por cada iteração.
Mas, ainda assim, quando falamos sobre este limite superior dizemos que
você está olhando para n ² comparações durante todo o tempo.
>> Vamos voltar, e já estamos começando a ficar um pouco em curto tempo
Eu diria que você deve definitivamente passar o resto desta tabela,
preencher tudo.
Pense em exemplos. Pense em exemplos concretos.
Isso é muito prático e útil para fazer.
Retirá-la.
Este é o tipo de tabela que como você passar em ciência da computação
você deve realmente começar a conhecer estes coração por.
Estes são os tipos de perguntas que você entrar em entrevistas.
Estes são os tipos de coisas que são boas para saber,
e pensar sobre os casos de ponta, realmente descobrir como pensar
sabendo que para bolha classificar a matriz pior possível
de classificar com que é aquele que está em ordem inversa.
>> Ponteiros. Vamos falar um pouco sobre ponteiros.
Nos últimos minutos que temos aqui
Eu sei que isso é algo junto com o arquivo de I / O que é novo.
Quando falamos de ponteiros a razão pela qual quero falar sobre ponteiros
é, pois, um, quando estamos trabalhando em C
estamos realmente em um nível bastante baixo em comparação com linguagens de programação mais modernas.
Nós somos realmente capazes de manipular as variáveis ​​na memória,
descobrir onde eles estão, na verdade, localizado dentro da nossa memória RAM.
Uma vez que você passou a ter aulas de sistema operacional que você verá
que isso é, novamente, uma espécie de abstração.
Isso não é realmente o caso.
Temos memória virtual que está escondendo os detalhes de nós.
>> Mas, por agora você pode assumir que quando você tem um programa,
por exemplo, quando você começar a executar o seu programa de cifra de César
Eu vou voltar para o meu iPad muito rapidamente-
que, no início, o seu programa, se você tem, digamos,
4 gigabytes de memória RAM do seu computador portátil,
você se esquecer esse pedaço, e nós vamos chamar isso de RAM.
E começa em um lugar que nós vamos chamar 0,
e termina em um lugar que nós vamos chamar de 4 gigabytes.
Eu realmente não posso escrever. O homem, que é cortado.
Quando o programa é executado
o sistema operacional esculpe a memória RAM,
e especifica segmentos diferentes para diferentes partes do seu programa para se viver
Aqui em baixo esta área é uma espécie de terra de ninguém.
Quando você vai até um pouco mais aqui
você tem realmente o lugar onde
o código para a vida de seus programas.
Esse código binário real, que na verdade arquivo executável é carregado na memória
quando você executar um programa, e que vive no segmento de código.
E como o programa é executado o processador olha para este segmento de código
para descobrir o que é a instrução seguinte?
Qual é a próxima linha de código que eu preciso para executar?
>> Há também um segmento de dados, e é aí que aqueles constantes da cadeia
ficam armazenados que você está usando.
E depois mais acima há um lugar chamado a pilha.
Nós acessar a memória lá usando malloc,
e depois para o topo do seu programa
há a pilha,
e é aí que temos vindo a jogar a maior parte do início.
Esta não é a escala ou nada.
Muito disso é muito dependente da máquina,
dependentes do sistema operacional, mas isso é como as coisas são relativamente fragmentada cima.
Quando você executar um programa e você declarar uma variável chamada x-
Eu vou chamar a outra caixa em baixo, e isso vai ser RAM também.
E eu vou olhar.
Vamos desenhar linhas irregulares para indicar esta é apenas uma pequena parte da RAM
e não a sua totalidade como se desenhar na parte superior.
>> Se eu declarar uma variável inteira chamada x,
então o que eu na verdade é um mapeamento
que é armazenado na tabela de símbolos do meu programa
que liga o x nome a esta região de memória que eu desenhei
aqui entre as barras verticais.
Se eu tiver uma linha de código no meu programa que diz que x = 7
o processador sabe "Oh, ok, eu sei que vive x neste local na memória."
"Eu estou indo para ir em frente e escrever um 7 lá."
Como ele sabe o que esta localização é na memória?
Bem, tudo isso é feito em tempo de compilação.
O compilador cuida de alocar onde cada uma das variáveis ​​estão a ir para
e criando um mapeamento especial ou melhor ligar os pontos
entre um símbolo e para onde está indo, o nome de uma variável
e onde ele vai viver na memória.
Mas acontece que nós realmente podemos acessá-lo em nossos programas também.
Isso fica importante quando começamos a falar sobre algumas das estruturas de dados,
que é um conceito que vamos introduzir mais tarde.
>> Mas, por agora, o que você pode saber é que eu posso criar um ponteiro para esse local, x.
Por exemplo, posso criar uma variável ponteiro.
Quando criamos uma variável ponteiro usamos a notação estrela.
Neste caso, este diz que eu estou indo para criar um ponteiro para um int.
É um tipo como qualquer outro.
Nós dar-lhe uma variável como y,
e então configurá-lo igual ao endereço, para um endereço.
Neste caso, podemos definir y para apontar para x
tomando o endereço de x, o que fazemos com este comercial,
e, então, definir y para apontar para ele.
O que isso faz é essencialmente se olharmos para a nossa memória RAM
isto cria uma variável separada.
Ele vai chamá-lo de y,
e quando esta linha de código é executado
ele está realmente indo para criar um ponteiro pouco que nós normalmente desenhar como uma flecha,
e define y para apontar para x.
Sim.
[Estudante] Se x é já um ponteiro, que você acabou de fazer
int * y = x em vez de ter o comercial?
Sim.
Se x é já um ponteiro, então você pode definir dois ponteiros iguais uns aos outros,
caso em que y não iria apontar para x,
mas chama a atenção para o que quer que x está apontando.
Infelizmente, estamos fora do tempo.
>> O que gostaria de dizer neste momento, podemos falar sobre isso desligada,
mas eu diria que começar a trabalhar com este problema, # 14.
Você pode ver que há já um pouco preenchido para você aqui.
Você pode ver que quando nós declaramos dois ponteiros, int * x e y *,
e note que apontar o * próximo à variável foi algo que foi feito no ano passado.
Acontece que este é semelhante ao que nós estamos fazendo este ano.
Não importa onde você escreve o * quando você está declarando o ponteiro.
Mas temos escrito o * ao lado do tipo
porque que o torna muito claro que você está declarando uma variável ponteiro.
Você pode ver que declarar os dois ponteiros nos dá duas caixas.
Aqui quando vamos definir x igual a malloc
o que isso está dizendo é deixar de lado a memória no heap.
Essa pequena caixa aqui, este círculo, está localizado na pilha.
X está a apontar para ele.
Note que y ainda não está apontando para qualquer coisa.
Para obter memória para armazenar o número 42 em x
poderíamos usar o que a notação?
[Estudante] * x = 42.
Exatamente, * x = 42.
Isso significa que siga a seta e jogar 42 em lá.
Aqui onde vamos definir y e x temos y apontando para x.
Novamente, isso é como o que Kevin disse onde vamos definir y igual a x.
Y não está apontando para x.
Em vez disso, ele está apontando para o que x está apontando para bem.
>> E então, finalmente nesta última caixa há duas coisas possíveis que poderíamos fazer.
Um deles é, poderíamos dizer * x = 13.
A outra coisa é que poderia dizer-Alex, você sabe o que podemos fazer aqui?
Você poderia dizer * x = 13 ou-
[Estudante] Você poderia dizer o que int.
[Nate H.] Se isso foi referido como uma variável int que poderia fazer isso.
Poderíamos também dizer * y = 13, pois ambos estão apontando para o mesmo lugar,
para que pudéssemos usar uma variável para chegar lá.
Sim. >> [Estudante] Qual seria a sua aparência se apenas dizer que x int é 13?
Isso seria declarar uma nova variável chamada x, que não iria funcionar.
Nós teríamos uma colisão porque declarou x para ser um ponteiro aqui.
[Estudante] Se nós apenas tivemos essa afirmação por si só o que seria a sua aparência em termos do círculo?
Se tivéssemos x = 13, então teríamos uma caixa e, em vez de ter uma seta
saindo da caixa de nós desenhá-lo como apenas um 13.
[Estudante] Na caixa. Okay.
>> Obrigado por assistir, e boa sorte em 0 Quiz.
[CS50.TV]