>> JASON HIRSCHHORN: Welcome a semana três, todos.
Temos um ocupado, mas emocionante seção à frente de nós.
Então, primeiro, porque fizemos alguns progresso com o curso, mas ainda
tem um monte de aprendizagem deixou de fazer, eu sou vai mostrar a vocês alguns recursos
que deve provar ser incrivelmente útil, você não só se aproxima de seu
conjuntos de problemas, mas também digerir todos o material que dar a vocês em
palestras e shorts e seção.
>> Então vamos passar a primeira 20 25 minutos de seção passando por cima
GDB, que você pode ou não pode ter usado neste momento, mas isso é uma
ferramenta incrivelmente útil que vai ajudar a depurar seus programas.
Muitos de vocês podem ter usado printf no meio de seu programa para descobrir
o que uma variável igualado.
GDB é ainda melhor do printf e não estrague o seu código, porque você
executá-lo em um arquivo executável.
Então, vamos passar por cima dos 10 mais útil os comandos que você precisa para o GDB, e estamos
indo para ir em um exercício conjunto para no conjunto de problemas de três e além, você
pode usar GDB para ajudar a depurar seus programas.
E, finalmente, vamos passar por cima de alguns classificação e pesquisa de algoritmos
que você viu na aula, e nós somos vai realmente código, não apenas
pseudocódigo, mas o código de busca binária, bubble sort, e seleção de classificação.
>> Então, primeiro, eu quero ir sobre os recursos.
Esta é uma lista extensa, e é fonte menor, porque eu tinha um monte de
caber aqui.
Mas estes não só irá ajudá-lo, novamente, com os conjuntos de problemas e
digerindo informações que você aprendeu, mas definitivamente, chegou a hora do teste, estes serão
ser extremamente útil.
Então, primeiro, a palestra observa.
Se você vai para cs50.net/lectures e desloque-se para a semana e dia específico,
você vai ver que existem notas para cada palestra, que não é simplesmente uma
transcrição, mas uma versão editada de o que foi abordado em palestra com código
trechos e outros petiscos úteis.
Eu recomendo ir sobre aqueles.
E depois, bem, não há código fonte disponível a partir de cada palestra.
E, novamente, esses slides também será disponível online em cs50.net/sections
esta noite.
>> Assim, segundo são os shorts cada semana que abrangem temas, geralmente de 5 a 15
minutos de duração.
E aqueles espero venha a dar-lhe uma grande cartilha sobre diferentes temas.
Terceiro -
e isso é novo este ano - é study.cs50.net.
Se você ainda não verifiquei, eu recomendo que você faça isso.
Você começa a escolher um tema.
Temos dezenas de tópicos sobre lá.
Assim, por exemplo, você escolhe Funções.
Dá-lhe alguns slides e notas sobre funções.
Esses são realmente os slides que TFs são incentivados a usar durante a nossa
apresentações na seção.
Há também dicas e truques para lidar com funções, e não há
problemas práticos que ajudam você trabalha com funções.
Nós também dar-lhe links para o curto no funções e os tempos que as funções
vêm-se na palestra.
Então study.cs50.net, a nova marca presente ano, um recurso fantástico.
>> Em seguida, eu tenho o homem, que é o manual comando que pode ser executado no
linha de comando.
Então, se você tem alguma dúvida sobre a comando, por exemplo, rand, que nós
encontrou na semana passada durante a seção e você provavelmente encontrou em
seu conjunto de problemas quando passar pelo gerar o código, mas se você digitar homem
rand, você terá a página que diz-lhe tudo sobre o rand.
Dá-lhe o que é preciso, a parâmetros que leva, assim como o retorno
tipo e uma breve descrição dessa função.
>> Então confira rand.
Ele pode ser um pouco prolixo e confuso, por isso às vezes eu acho que
simplesmente pesquisando o que eu quero saber é a melhor maneira de encontrar a resposta.
Assim, a prática com o Google.
Obter bons no Google.
Vai tornar-se seu melhor amigo.
>> Assim como o Google, se você não pode encontrá-lo no Google, cs50.net/discuss, é
o fórum de discussão.
Provavelmente, se você tem uma pergunta, uma de seus 700 + pares também tem que
questão e pode ter pedido já na discussão
fóruns e tê-lo respondido.
Então se você tem uma pergunta comum ou Você tem uma pergunta que você pensa
talvez outras pessoas possam ter executado em, confira cs50.net/discuss.
>> Finalmente, os dois últimos, se você quiser falar com um ser humano real, escritório
horas de segunda a sexta-feira.
Há também o horário de expediente on-line para os alunos de extensão.
E por último mas não menos importante, me, ponto de exclamação.
Vocês todos têm a minha informação de contato.
Se você precisar de alguma coisa, por favor, nunca hesite em contactar-me.
Sempre à vontade para fazê-lo.
Muito poucos de vocês já me adicionou no Gchat, de modo que tem sido decepcionante,
mas espero que isso vai mudar entre neste e no próximo seção.
Qualquer dúvida até agora sobre os recursos?
Grande.
>> Finalmente, uma outra ficha para feedback, sayat.me/cs50.
Você pode me dar um feedback anônimo sobre como eu estou fazendo.
Isso foi muito útil na semana passada.
Eu tenho um par de comentários de vocês logo após a seção, mais de
outros alunos que assistiram durante a semana, e
foi incrivelmente útil.
Vou tentar limitar o meu uso de a palavra "doce", mas vou mostrar o meu
entusiasmo e emoção em outras formas.
Mas havia outro adicional feedbacks substantivas,
ambos os prós e delta.
Então, por favor, eu dou a vocês um feedback em seus conjuntos de problemas.
Sinta-se livre para me dar feedback no meu ensino.
Estou aqui para vocês.
>> Grande.
Isso é tudo o que eu tenho para a primeira seção.
Alguém tem alguma perguntas até agora?
E eu tenho uma nota para o centro de controle.
Os alunos têm me enviado mensagens de Extensão dizendo que não está recebendo qualquer áudio,
mas que está fora do meu alcance para corrigir.
Portanto, esperamos, que recebe resolvido em breve.
Se você está assistindo on-line, oi, mas você não pode me ouvir.
>> Então, primeiro, vamos passar por GDB.
GDB, como sugerido anteriormente, é uma ferramenta de depuração
muito melhor do que printf.
Então, para começar com o GDB, gente, se você quiser abrir o seu aparelho
e levar o arquivo que eu enviado para você anteriormente - este arquivo também será
disponível on-line em um pouco -
e executar GDB. / o nome do arquivo.
Primeiro, é claro, você tem que compilar arquivo porque GDB só funciona em
arquivos executáveis.
>> Mas se você quer começar GDB, a primeira coisa que você faz,
você executar GDB. / César.
Então esse é o nome do programa que estamos indo para ir com ele agora.
Então eu vou escrever fazer César, que vai me dar um arquivo executável
aqui destacadas em verde.
E então eu vou correr GDB. / Cesar.
>> E lá vai você.
Você vê que temos um texto a dizer-me sobre a versão do GDB, dando-me
algumas informações sobre a garantia, e então nós ter o prompt do PIB, o que parece tipo
de como a nossa linha de comandos, mas você vê que é aberto
paren, GDB, paren próximos.
Antes de continuarmos e depurar este arquivo que enviei a todos vocês, vamos olhar para
alguns comandos úteis para que ter um sentido de que estamos indo para cobrir.
>> Estes comandos estão listados aqui no ordem em que eu geralmente uso deles.
Então eu começo o meu programa, executando GBD. / Nome do programa,
neste caso, César.
E então a primeira coisa que faço de 99,9% do tempo é dizer tipo de quebra.
Isso define um ponto de ruptura na principal.
Essencialmente, o que você está fazendo lá é o programa que vai parar em
principal para que você possa começar a examiná-lo linha por linha, em vez de correr tudo
o caminho.
Você pode quebrar em diferentes pontos o seu código, mas principal é geralmente uma
bom lugar para começar.
>> O próximo comando eu corro é executado.
Isso inicia o programa em execução, e se você precisa digitar linha de comando
argumentos, você executá-lo o comando.
Correr com os argumentos.
Então, já que estamos passando por cima de uma versão de C, que é o programa que vocês
escreveu para pset dois -
este, é claro, tem alguns bugs nele que espero que nós vamos encontrar -
vamos correr correr com algum comando argumentos de linha porque César,
como vocês sabem por o problema definir especificações, leva algum
Argumentos da linha de comando.
>> O próximo par de comandos, o próximo um é realmente chamado em seguida.
Aquela leva linha por linha através de seu programa.
Então bater n depois Enter leva você para a próxima linha, a execução de
a linha anterior.
Passo não só leva você para a próxima linha, mas
leva-funções dentro.
Portanto, se você escreveu uma função em o seu código ou se você quiser explorar um
para i, por exemplo, você pode bater s, e ao invés de ir para a próxima linha de
o arquivo que você está passando agora, você vai realmente entrar
esta função e ver o seu código.
>> Lista mostra, em muito amigável formato, os 10 ou mais linhas ao redor
onde você está atualmente em seu código assim você pode realmente ver o arquivo
ao invés de ter de trocar de volta e outro entre diferentes pontos de vista.
Imprimir é como printf, como o próprio nome indica.
Isso mostra o que uma variável é igual.
>> Informações locais é realmente útil.
Esta é uma versão especial de impressão.
Informações locais mostra todo o local, variáveis, imprime todos eles para você para fora
que estão atualmente disponíveis.
Então, eu geralmente, ao invés de ter que imprimir as quatro variáveis ​​que eu sou
curioso sobre se eu estou em um loop, por exemplo, eu só escrevo informações locais,
e ele vai me que o meu contador eu mostro é igual a, bem como a matriz que eu sou
trabalhando em pares.
>> Finalmente, continue.
Digitando pausa você pára no ponto de quebra.
Você pode andar através da linha por linha com o próximo e passo.
Continuar executa o programa para o seu próximo ponto de quebrar ou até a conclusão se
não há mais pontos de quebra.
Desativar remove pontos de quebra, se você decidiu que a pausa no principal era
impróprio, você quer defini-lo em outro lugar.
E, finalmente, q, sair, sai do GDB.
>> Portanto, este programa,. / César, vamos a olhar através de agora e nós
vai usar GDB para encontrar os erros neste programa.
Corri este programa anterior com Confira 50, e eu tenho uma carranca.
Tudo o que existia, compilado, passaram muitos dos testes, mas para
alguma razão, ele não passou da quinta teste, transformando BARFOO, todas as letras maiúsculas, em
E-D-U-I-R-R, todas as tampas, usando três como uma chave.
Eu tenho muito perto.
Desci por uma letra.
Portanto, há um pequeno erro aqui.
Eu olhei através do meu código.
Eu não conseguia entender.
Espero que vocês possam me ajudar descobrir o que é esse bug.
>> Então esse é o erro que estamos procurando.
Vamos passar em GDB.
Mais uma vez, eu correr GDB. / César, então agora estamos em GDB.
E o que é a primeira coisa que eu devo fazer?
Acabei entrou GDB.
Alguém me dê uma boa comando para entrar.
>> ALUNO: Quebre principal.
>> JASON HIRSCHHORN: Quebre principal.
Fantástico.
Vamos digitar que dentro
Vocês podem ver aqui em cima ou seguir ao longo de seus computadores.
Quebre principal, e você verá uma ponto de ruptura foi fixado em -
dá-me algum endereço de memória estranho, e também me dá o número da linha.
Se eu olhar para trás, este arquivo, Eu iria perceber que o principal
aconteceu na linha 21.
O que devo executar o próximo?
É o meu programa em execução?
Não.
Então, o que eu deveria executar o próximo?
>> ALUNO: Correr.
>> JASON HIRSCHHORN: Executar.
Devo apenas correr correr, ou deveria Eu adicionar algumas outras coisas em?
>> ALUNO: Correr com o argumento.
>> JASON HIRSCHHORN: Corra com os argumentos do comando.
E já que estou a depuração de um bem específico caso, eu deveria entrar nesse
argumento de linha de comando.
Então, eu vou fazer correr três, o que é, novamente, a saída que eu tenho de check 50.
Começando programa.
Passamos por um par de linhas.
Você vai ver agora que estamos na linha 21.
Como eu sei que estamos na linha 21?
Porque se você olhar para a esquerda da minha janela do terminal, não
ele diz que linha 21.
E isso me dá, na verdade, a código que está na linha 21.
Então eu misspoke antes.
Principal não é realmente na linha 21.
Principal é um par de linhas acima de 21.
Mas na linha 21, que é onde nós estamos quebrando.
Esta linha de código tem ainda não executados.
Isso é importante.
A linha que você vê não tem foi executado ainda.
Essa é a próxima linha de código você está prestes a executar.
>> Portanto, a próxima linha, como vocês são provavelmente está familiarizado com, isso é
condição verificando para ver se eu tenho entrou em um argumento de linha de comando.
E a até i, que é o segundo parte do que está fazendo?
O que é um ai?
>> ALUNO: alterá-lo para um número inteiro.
>> JASON HIRSCHHORN: Desculpe?
>> ALUNO: Está mudando o argumento para um número inteiro.
>> JASON HIRSCHHORN: Então ao i muda arg v1 de uma string para um inteiro.
E então o que é que a verificação?
>> ALUNO: Se houver uma segunda argumento de linha de comando, além
com a execução do programa.
>> JASON HIRSCHHORN: E o que é o segundo semestre deste
Expressão booleana corrente?
Esta parte aqui, ao i?
>> ESTUDANTE: Se é negativo.
>> JASON HIRSCHHORN: Certificar-se de que?
>> ALUNO: Certificar-se de que É, de facto, positiva.
>> JASON HIRSCHHORN: Exatamente.
Esta é a verificação para ver se é negativo e se for negativo, eu
tenho um sentimento a linha seguinte força ser-me gritar com o usuário.
Então, vamos bater final para executar esta linha.
Nós não vemos que a linha que vocês talvez esperava ver a gritar com o
usuário e, em seguida, retornar, porque esta linha não foi executada.
Entrei 3.
Então eu tinha, de fato, entrar dois comando argumentos de linha, e 3 é
maior do que zero.
Então vimos que a linha, assinamos, mas não passo
se dentro do estado.
>> Então, agora, ao lado, eu vejo que eu estou definindo chave int é igual ao i arg v1.
Então esse é me criando uma chave variável.
Então, se eu imprimir chave agora, porque que permite que você veja o
valor dentro da variável, chave é igual a 47.
Isso é estranho, mas é claro, isso é porque eu não tenho
executada essa linha ainda.
Portanto, agora se eu bater n, executar essa linha, e fazer tecla de impressão, a chave será igual a 3,
que é o que nós esperamos que seja igual.
>> Então, novamente, em GDB, a linha que ver que você não tenha executado ainda.
Você tem que bater N ou S ou um número de outros comandos para realmente
executar essa linha.
Chave de impressão.
Da chave em 3.
Tão longe, tão bom.
String é texto simples.
Vamos executar essa linha.
Estou recebendo uma seqüência de usuário.
>> Vamos ver no meu check 50, I entrar BARFOO todas as tampas, de modo
isso é o que eu vou entrar.
Se eu agora imprimir texto puro.
Você verá que é igual a uma string.
Dá-me algum outro hexadecimal estranho número, mas não em
fato de dizer que a minha string é BARFOO.
Se eu quisesse ver o que equivalia a chave Neste ponto, como eu poderia verificar-chave?
>> ALUNO: chave de impressão.
>> JASON HIRSCHHORN: chave de impressão, exatamente.
E, na verdade, há um atalho.
Se você ficar cansado de digitar impressão, você pode apenas digitar p.
Assim chave p faz a mesma coisa exata.
E mais uma vez, eu vejo isso é igual a 3.
>> Se eu quisesse descobrir o que tanto chave e BARFOO igualado ao mesmo tempo
mas eu estava cansado de escrever cada um individualmente, eu
pode digitar informações locais.
Isso me dá iguais chave 3.
Texto simples é igual BARFOO.
Ele também me dá essas duas coisas estranhas no topo, esta variável i e
isso n variável.
>> Essas são realmente existente no meu programa principal.
Nós não os encontrou ainda, mas como um preview, aqueles
existe no meu loop for.
Então, agora, eles igual algum estranho números, porque eles não têm sido
inicializado ainda, mas eles ainda existem na memória, por isso eles são apenas definir
para um valor de lixo.
Mas nós vemos chave na planície texto ali mesmo.
>> Então, eu estou indo para executar esta linha, linha 34, o loop para.
Vamos saltar para o loop for por bater n.
E nós estamos dentro do loop for.
Estamos em nosso primeiro cheque.
E, novamente, estes devem tipo de olhar familiar para você, porque esta era uma
Programa César que foi escrito, mas mais uma vez, tem algum tipo de bug.
>> E agora, se eu fizer informações locais, porque eu sou dentro daquele loop for, você verá
que i é igual a zero, como esperamos.
Isso é o que defini-lo como e inicializado ele no loop for.
n é igual a 6.
Isso também faz sentido, porque partimos lo para o strlen de texto simples.
Então, eu gostaria de fazer Informações moradores ou impressão a variável muitas vezes para se certificar de que
tudo é sempre o que Espero que seja igual.
Neste caso, tudo está o que eu espero que seja igual.
>> Então, vamos começar a se mover através de isso por loop.
A linha que eu estou é a linha 36, ​​se simples i texto é maior do que uma simples e
i texto é inferior ou igual a z.
Eu sei que meu problema não é com o meu primeiro carta, é com a segunda carta.
Se olharmos para trás no Check 50, B vai para E bem.
Estou levando a A e deixá-lo como um A, não alterá-lo para D. Assim,
algo está errado com a segunda letra.
Então, eu estou indo para mover lá em um segundo.
>> Mas se eu queria verificar o que simples texto que igualou nesse particular
caso, eu acho que deveria ser o quê?
O que deve texto simples eu igualar neste primeira rodada através do loop for?
>> ALUNO: Zero?
>> JASON HIRSCHHORN: Texto simples de I?
Por isso, deve ser de capital B. I, é claro, é igual a zero, mas de texto simples
suporte de zero suporte fechado é igual a B porque cordas, como vimos na semana passada,
são array, por isso estamos recebendo o primeiro caractere a partir daí.
Então, novamente, se eu impressos texto simples Eu, eu, de fato, obter o caractere
B. E isso é puro, certo?
Eu realmente não tiver texto simples I. Isso não é uma das variáveis ​​que estabeleci
ou inicializado, mas você pode imprimir toda uma série de coisas
se você gostaria.
>> Mas vamos percorrer.
Se o texto simples que é maior do que um e texto simples que é inferior ou igual a
Z, que claramente é verdade, porque nós temos um capital B. Eu vou correr
algum comando sobre ele.
Vimos que a matemática, na semana passada, por isso vamos é um dado adquirido que ele funciona
direito de acordo com Confira 50.
>> Estas chaves, o primeiro mostrou que eu estava saindo do caso
condição, o segundo mostrou que eu estou saindo do loop for.
E agora quando eu bati A seguir, vamos ver estamos de volta no loop novamente.
Estamos atravessando o loop novamente.
Vamos realmente entrar na segunda iteração do loop e tipo
Informações locais.
>> Então, nós estamos na segunda iteração do nosso loop for.
I é igual a 1, o que esperamos.
N é igual a 6, o que esperamos.
Chave é igual a 3, o que esperamos.
E de texto simples, você vai ver, é igual a EARFOO agora, não mais porque BARFOO
no nosso iteração anterior, o B foi alterado para um capital E. Então, nós estamos sobre
para encontrar o problema, de modo que este é o lugar onde nós estamos indo
mergulhar na depuração.
Mas alguém tem alguma dúvida sobre o que temos feito até agora?
Fantástico.
>> Então, nós estamos prestes a executar este se condição, suporte de texto simples Fechei
suporte maior do que A e texto simples I inferior ou igual a Z. Mas antes
Eu vou entrar nisso, porque é onde Eu sei que meu erro é que eu quero apontar
fora de texto simples de I. Assim, vamos colocar impressão.
Ele faz igual a um personagem, de modo que parece até agora, tudo está bem e bom.
>> Então, eu espero que esta linha por minha lógica, esta linha deve ser verdadeira.
É uma letra maiúscula.
Mas se eu acertar n, nós percebemos que este linha, de fato, não foi executada.
Eu pulei até o else if.
Por que isso aconteceu?
>> ALUNO: Porque você tem a sua condição de texto simples é maior
do que A, não é igual ou maior do que.
>> JASON HIRSCHHORN: Então, eu tinha o meu texto simples I é maior do que A, não maior
que ou igual a.
Então, claramente, a capital A não desencadear esta condição se, e nós fizemos
não entrar nele, e nós fizemos não fazer a mudança necessária.
Então é isso, na verdade.
Eu descobri o meu erro.
Eu pudesse voltar no meu arquivo de origem, mudá-lo, e atualizá-lo e
executar Confira 50 novamente.
>> Mas vamos ver, apenas por pedagogia de bem, se eu continuar.
O outro se não executar qualquer um, mas o que equivale a vez é o comando
que não muda.
Por isso, não mudou em tudo, e se eu imprimir texto puro aqui, vamos ver indo
através desse laço for não, na verdade, mudar esse segundo personagem em tudo.
É ainda um capital A.
>> Então, novamente, nós depurado nosso erro.
Percebemos que não havia alguma lógica em falta.
E nós depurado-lo antes do tempo antes realmente executar essa linha,
mas você teria notado se tivéssemos apenas Em seguida bater e saltar para que else if,
isso significa que que se a condição não era verdade.
Nós não, na verdade, obter o resultado que esperávamos.
Então nós poderia ter sido solicitado, teve não foram tão astuto, a olhar para
que se a condição e verificar se, de fato, nossa condição deve avaliar a
verdade no contexto atual.
>> Isso é tudo para a depuração deste programa.
Alguém tem alguma dúvida?
O comando que eu poderia bater para sair GDB?
Q. E então eu vou ser solicitado, sair de qualquer maneira?
Sim ou não.
Eu vou bater sim, e eu vou ter desistido GDB.
>> Então isso foi um primer rápido para GDB.
Na verdade, em um cenário real, Eu fiz isso em horário de expediente.
Eu GDBed este programa exato em horário de expediente com um estudante.
E se voltar para os comandos que vimos antes, usamos ruptura principal, em primeiro lugar
coisa que fizemos.
Nós costumávamos correr com argumentos de linha de comando, segunda coisa que fizemos.
Usamos muito próximo de se mover nós através de linhas.
E, novamente, a versão curta de seguida é n.
Isso é entre parênteses em cinza no slide.
>> Nós não utilizar o passo, mas não o fizemos necessariamente precisa para este caso.
Mas podemos usá-lo em um pouco mais tarde hoje se está depurando, por
exemplo, busca binária quando binário pesquisa é chamado em um separado
função, mas não há algum erro com ele.
Nós vamos querer entrar a chamada para busca binária e
realmente depurá-lo.
Lista que não use, porque tivemos um bom senso de nosso código, mas se eu
queria ter uma noção do código que eu estava por perto, eu poderia apenas lista usar.
>> Imprimir usamos, informações locais que usamos.
Continuar nós não precisamos usar neste caso, também não é preciso usar
desativar, mas fizemos uso desistir.
Mais uma vez, estes 10 mandamentos, praticá-los.
Se você entender esses 10 mandamentos, você deve ser definido para a depuração de qualquer
Problema com GDB.
>> Então, nós estamos prestes a ir, de novo, para o cerne da seção de hoje, passando por cima
estes classificação e pesquisa algoritmos.
Antes de fazê-lo, mais uma vez, todas as perguntas, comentários, preocupações para GDB?
Então está todo mundo vai usar GDB em vez de printf?
Então todo mundo, pelo amor de perpetuidade, todo mundo está balançando a cabeça direita
agora, então eu vou te ver no horário de expediente e todos os TFs vai vê-lo e
eles vão dizer, me mostrar como usar GDB, e você vai ser capaz
para mostrá-los, certo?
Mais ou menos?
Talvez eu espero.
Legal.
>> Então vamos passar para classificação e pesquisa.
Você vai ver que eu tenho uma lista já classificadas para nós, mas que não vai
ser o caso sempre.
Assim, no problema de especificação definida para conjunto de problemas de três, você tem calções
que você pode assistir, e ele realmente pede-lhe para ver os calções.
Também em palestra na semana passada, fomos muitos desses algoritmos, por isso estou
não vai passar o tempo na sala de aula vai sobre estes algoritmos novamente ou desenho
fotos de como estes algoritmos funcionam.
Mais uma vez, essa informação você pode re-relógio palestra, ou que as informações
é capturado excepcionalmente nos calções para essas pesquisas, todas
que estão disponíveis em cs50.net.
>> Então, em vez disso, o que nós vamos fazer é escrever esses programas.
Nós temos um sentido, um modelo mental, de como eles trabalham, e assim o que vamos
fazer é codificá-las de verdade.
Vamos transformar esse modelo mental, essa imagem, se quiser, para o
código real.
E se você fosse um pouco confuso ou nebuloso sobre o modelo mental, eu totalmente
entender.
>> Nós não estamos indo realmente para saltar para o código imediatamente.
Assim, enquanto este pedido neste slide pergunta você codificar busca binária, e
na verdade, uma versão interativa de busca binária, a primeira coisa que eu
realmente quero que você faça é escrever um pseudocódigo.
Então, você tem esse modelo mental de como funciona a busca binária.
Pegue uma folha de papel se você tiver um prontamente disponível, ou abrir uma
editor de texto, e eu gostaria todo mundo para escrever.
Tomar quatro minutos para escrever a pseudocódigo para a busca binária.
>> Mais uma vez, pensar sobre esse modelo mental.
Eu virei ao redor se você tiver dúvidas e nós podemos desenhar a imagem para fora.
Mas em primeiro lugar, antes de começar a programação, Eu gostaria de escrever a
pseudocódigo para busca binária então quando nós mergulhar, temos alguma direção que
para onde devemos ir.
>> ESTUDANTE: Podemos assumir a matriz de valores que recebemos já estão classificados?
>> JASON HIRSCHHORN: Então por busca binária para o trabalho - excelente pergunta - você
tem que levar em um ordenado matriz de valores.
Então suponho que vai funcionar.
Nós vamos voltar a este slide.
Você verá em roxo a função declaração é bool binary_search int
valor, valores int, int n.
Este deve ser familiar se você tiver já se aproximou ou obtido o seu
as mãos sujas com o conjunto de problemas.
>> Mas essa é a sua declaração da função.
Mais uma vez, não precisa se preocupar com tanto neste momento.
O que eu realmente quero que você a fazer é tomar quatro minutos para binário pseudocódigo
pesquisar, e depois vamos mais de que, como um grupo.
E eu vou chegar perto.
Se você tem perguntas, sinta livre para levantar sua mão.
>> Por que você não tomar mais de dois minutos para terminar o pseudocódigo?
Eu sei que isto pode parecer ridículo que estamos gastando tanto tempo com
algo que não é verdade, mesmo em C, mas especialmente para estes mais
algoritmos desafiadoras e problema conjuntos que temos de descobrir,
começando em pseudocódigo não se preocupando sobre a sintaxe, apenas se preocupar com
a lógica, é incrivelmente útil.
E dessa forma, você não está resolvendo dois problemas extremamente difíceis ao mesmo tempo.
Você está apenas se concentrar na lógica, e então você se move para a sintaxe.
>> OK.
Vamos começar passando o pseudocódigo.
Já escrevi aqui em cima, binário Pesquisa pseudocódigo.
Vamos escrever isso na embarcar juntos.
Ou eu vou escrevê-lo e você vai dar me as instruções que eu preciso.
Então, alguém pode me dar o primeiro linha do pseudocódigo você
escreveu para busca binária?
Sim, Annie?
>> ALUNO: Enquanto o comprimento do lista é maior do que zero.
>> JASON HIRSCHHORN: Enquanto comprimento de uma lista maior do que zero.
E mais uma vez, vemos alguns C-looking sintáticas coisas aqui.
Mas a maior parte desta está em Inglês.
Alguém tem alguma linha puseram antes disso em sua pseudo-código?
>> ESTUDANTE: Obter uma matriz classificados de números.
>> JASON HIRSCHHORN: Você escreveu: "ter uma matriz de números ordenados. "Per o
declaração da função, estaremos passando uma matriz de números ordenados.
>> Estudante: [inaudível].
>> JASON HIRSCHHORN: Então teremos isso.
Mas sim, se nós não temos isso, nós seria necessário para ordenar a nossa gama de
números, porque de busca binária só funciona em matrizes ordenada.
Assim, enquanto o comprimento da lista é igual a zero, eu sou indo para colocar em algumas chaves
para torná-la um pouco mais como C. Mas enquanto, parece ser mapeado para uma
while, para que dentro deste tempo loop de que precisamos para
fazer por busca binária?
>> Alguém que não tenha me dado um responder ainda, mas quem escreveu isso?
>> ESTUDANTE: Vá para o meio da lista.
>> JASON HIRSCHHORN: Tom.
Ir para o meio da lista.
E a pergunta follow-up, o que fazemos uma vez que estamos no
meio da lista?
>> ALUNO: Faça uma verificação se isso é o número que você está procurando.
>> JASON HIRSCHHORN: Excelente.
Vá a meio da lista e verifique se o nosso valor está lá -
fantástico.
Alguém tem mais alguma coisa que era diferente do que isso?
Isto é exatamente correto.
>> A primeira coisa que fazemos em busca binária é ir para o meio da lista e
verificar para ver se o nosso valor está lá.
Então eu suponho que se nosso valor é lá, o que vamos fazer?
>> ALUNO: Nós retornar zero [inaudível].
>> JASON HIRSCHHORN: Sim, se a nossa valor está lá, nós a encontramos.
Assim, podemos dizer alguma forma, no entanto, este função é definida, nós dizemos que o usuário
que encontraram.
Se ele não estiver lá, porém, que é onde isso fica complicado.
Então, se ele não estiver lá, alguém que estava trabalhando em busca binária ou
tem uma idéia, agora, o que vamos fazer?
>> ALUNO: Pergunta.
>> JASON HIRSCHHORN: Sim?
>> ALUNO: É a matriz já classificadas?
>> JASON HIRSCHHORN: Sim, nós estamos assumindo a matriz já está classificada.
>> ALUNO: Então você tem que verificar se o valor que você vê é maior do que
o valor que você quiser, você pode mover-se para o meio da outra metade.
>> JASON HIRSCHHORN: Então, se o meio de a lista é maior do que o que estamos
procurando, então nós fazemos o que?
Nós nos movemos para onde?
>> ALUNO: Você quer se mudar para a metade da lista com
Números mais baixos do que a.
>> JASON HIRSCHHORN: Então nós vamos chama isso de esquerda.
Então, se meio é maior, podemos pesquisar a metade esquerda da lista.
E, em seguida, por meio de busca, o que quero dizer com pesquisa?
>> Estudante: [inaudível].
>> JASON HIRSCHHORN: Vamos para o meio.
Nós realmente repetir isso.
Voltamos através do nosso loop while.
Eu vou dar-lhe o último -
então, se, meio é menos do que o que o que fazemos, o que fazemos aqui?
>> ALUNO: Vá para a direita.
>> JASON HIRSCHHORN: Busca à direita.
Este parece ser bom, mas alguém tem qualquer coisa que pode estar faltando ou
qualquer outra coisa que você colocar no seu pseudo-código?
Então, isso é o que temos até agora.
Enquanto que o comprimento da lista é maior que zero, nós estamos indo para ir
para o meio da lista e verificar se o nosso valor está lá.
>> Se o meio é maior, nós vamos procurar à esquerda, mais se o meio é
menos, vamos pesquisar a direita.
Então, todos nós tivemos alguma familiaridade com os termos que usamos em ciência da computação
e as ferramentas que temos.
Mas você já vai notar que estávamos falar em Inglês, mas encontramos um
monte de coisas que pareciam mapear para ferramentas que temos em nosso kit de ferramentas de codificação.
Então, logo de cara, não estamos vai realmente codificar ainda.
>> O que vemos aqui em Inglês que os mapas para coisas que podemos escrever em C?
>> ALUNO: While.
>> JASON HIRSCHHORN: While.
Portanto, este tempo aqui mapas sobre o que?
>> ESTUDANTE: Um loop while.
>> JASON HIRSCHHORN: Um loop while?
Ou, provavelmente, mais geralmente, um ciclo.
Queremos fazer algo mais e mais.
Então, nós estamos indo para codificar um loop.
E já sabemos, porque nós fizemos isso um par de vezes e nós
temos muitos exemplos por aí, como realmente de escrever
este índice para um loop.
Então isso deve ser muito fácil.
Devemos ser capazes de obter essa começou muito rapidamente.
>> O que mais vemos aqui?
Que outras estruturas sintaxes, as coisas que estamos familiarizados com a C, que nós
já tem um sentido de com base fora das palavras que usamos?
Sim, Anna?
[Inaudível]
apenas brincando.
Anna, vá em frente.
>> ALUNO: Se e mais.
>> JASON HIRSCHHORN: Se e mais - bem aqui.
Então, o que aqueles se parece?
>> ALUNO: Uma instrução if else.
>> JASON HIRSCHHORN: Sim, condições, certo?
Por isso, provavelmente vai precisar escrever algumas condições.
E, novamente, embora talvez confuso no em primeiro lugar, nós geralmente têm um sentido agora
de como escrever as condições e a sintaxe para as condições.
E se não o fizermos, nós só procurar o sintaxe para condições, cortar e colar
isso, porque sabemos que precisamos aqui uma condição.
Quaisquer outras coisas que vemos que o mapa em coisas que talvez você precise fazer em C?
Sim, Aleha?
>> ALUNO: Isso pode ser óbvio, apenas verificar se um
valor é igual a alguma coisa.
>> JASON HIRSCHHORN: Então, como vamos verificar e - por isso, ir para o meio da lista
e verifique se o nosso valor não é?
Como é que vamos fazer isso em C?
Qual é a sintaxe para isso?
>> ALUNO: Igual, é igual.
>> JASON HIRSCHHORN: Igual, é igual.
Então, esta verificação é provavelmente vai para ser um igual, é igual.
Então, vamos saber que precisamos que em algum lugar.
E, na verdade, apenas a escrevê-lo, vemos essas outras coisas.
Nós vamos ter que fazer alguma operadores de comparação em lá -
fantástico.
Então, ele realmente se parece, por e um grande, não ter escrito
palavra de código C ainda.
Mas nós temos o modelo mental para baixo através de palestras e os shorts.
>> Nós escrevemos pseudo-código como um grupo.
E já temos 80% se não 90% do que precisamos fazer.
Agora, só precisamos de codificar , o que mais uma vez, é um
problema não-trivial para resolver.
Mas pelo menos nós estamos presos na lógica.
Pelo menos agora quando vamos para o horário de expediente, Eu posso dizer, eu sei o que eu preciso
de fazer, mas você pode lembrar me da sintaxe?
Ou mesmo se o horário de expediente estão lotados, você pode Google para a sintaxe, em vez
do que ficar preso na lógica.
>> E, novamente, ao invés de tentar resolver a lógica e os problemas de sintaxe todos
ao mesmo tempo, muitas vezes é muito melhor quebrar esses dois problemas difíceis fora em
dois os mais gerenciáveis ​​e fazer o pseudo-código e, em seguida, primeiro código em C.
Então vamos ver o que eu fiz para o pseudo-código antes do tempo.
>> Enquanto que o comprimento da lista é maior que zero, olhe para o meio
da lista.
Se o número encontrado retorna verdadeiro, caso contrário se o número mais elevado, busca esquerdo.
Else if menor número, pesquisa direita, retornará false.
De modo que parece quase idêntico, se não quase idêntico ao que escreveu.
Na verdade, Tom, o que você disse em primeiro lugar, quebrar no meio da lista, e se
número encontrado em duas instruções é realmente o que eu fiz.
>> Eu combinei-los lá.
Eu deveria ter escutado você pela primeira vez.
Então esse é o pseudo-código que temos.
Se você quiser agora, desculpe, vá De volta ao nosso problema inicial.
Código binary.c Vamos.
Então implementar uma versão interativa de pesquisa binária com a seguinte
declaração da função.
>> E você não precisa copiar -lo ainda.
Na verdade, estou indo para abrir até aqui binary.c.
Portanto, há a declaração da função no meio do ecrã.
E você vai ver que eu tomou o pseudo-código de em meus lados, mas quase idêntico
com o que escreveu, e colocar isso para você.
Então, agora, vamos levar cinco minutos para codificar esta função.
>> E, novamente, se você tiver quaisquer perguntas, levantar a mão, me avise, eu vou
vêm por aí.
>> Estudante: [inaudível].
>> JASON HIRSCHHORN: Então eu peguei o binário definição de pesquisa no
topo, na linha 12.
Isso é o que eu tenho para o meu slide.
E depois de tudo isso pseudo-código que apenas copie e colei do slide,
slides pseudo-código.
Eu ainda não estou ouvindo [inaudível].
>> Então, se você tiver terminado o seu implementação, eu quero verificar.
Eu lhe enviou o arquivo Helpers.h anteriormente nesta classe.
E vai estar disponível on-line também para download para as pessoas assistindo
Neste momento secção retardada.
E eu usei apenas a distribuição genérico código de pset3.
Então eu peguei find.C, use meu arquivo Helpers.h em vez do arquivo Helpers.h
que é dada no código de distribuição.
>> E eu tive que fazer uma outra mudança no find.C ao invés de chamar simplesmente
pesquisa, chamada binary_search.
Então, se você quiser testar seu código, sei que isso é como fazê-lo.
Na verdade, quando nós estaremos executando este código agora, eu fiz apenas uma cópia do
meu diretório pset3, mais uma vez, trocados os arquivos de ajudantes e depois fez que
alterar em find.C chamar binary_search , em vez de simplesmente procurar.
>> JASON HIRSCHHORN: sim.
Você tem uma pergunta?
>> ALUNO: de Nevermind.
>> JASON HIRSCHHORN: Não se preocupe.
Bem, vamos começar.
Vamos codificar este como um grupo.
Uma outra nota.
Novamente, isto é, podem ser facilmente trocados no Conjunto de Problemas para três.
Eu tenho o meu arquivo Helpers.h que, em vez que o Helpers.h estamos dado,
declara busca binária, bolha classificar e seleção tipo.
E em find.c você notará on line, o que é isso, a linha 68, que chamamos de binário
pesquisar em vez de pesquisa.
Então, novamente, o código que está disponível on-line ou o código que você está
criando agora podem ser facilmente trocados in para p set 3 para verificá-lo.
>> Mas, primeiro, vamos codificar busca binária.
Nossa declaração de função, retornamos um booleano.
Tomamos um inteiro chamado valor.
Tomamos um array de inteiros chamado valores, e tomamos n ser
o tamanho da matriz.
Na linha 10, aqui, eu tenho afiada incluem stdbool.h.
Alguém sabe por que está lá?
Então, o que essa linha de código faz?
>> ALUNO: Ele permite que você usar um tipo de retorno booleano.
>> JASON HIRSCHHORN: Exatamente.
>> ALUNO: Ou é uma biblioteca que permite a utilização de um tipo de retorno booleano.
>> JASON HIRSCHHORN: Então o forte incluir linha stdbool.h me dá alguma
definições e declarações para coisas que eu estou autorizado a usar em
esta biblioteca.
Assim, entre os que está dizendo que não há este tipo chamado booleano, e que pode ser
verdadeira ou falsa.
Então é isso que essa linha faz.
E se eu não tiver essa linha, eu o faria ficar em apuros para escrever este
palavra certa aqui, bool, ali mesmo.
Exatamente.
Então eu preciso que neste código.
OK.
Portanto, este, de novo, é um iterativo versão, e não uma recursiva.
Por isso, vamos começar.
>> Vamos começar com este primeiro linha de código pseudo.
E espero que, nós - ou não espero.
Nós estamos indo para ir ao redor da sala.
Vamos linha por linha, e eu vou ajudar você descobrir a linha que precisamos
para gravar em primeiro lugar.
Assim, enquanto o comprimento da lista é maior do que zero.
Vamos começar na frente.
Que linha devo escrever aqui, em código?
>> ALUNO: Enquanto parêntese n é maior do que 0.
>> JASON HIRSCHHORN: Enquanto n é grande a 0.
Assim, n é o tamanho de uma lista, e estamos verificando se -
>> [VOZES interpondo]
>> JASON HIRSCHHORN: - Perdão?
>> ESTUDANTE: Como sabemos que n é o tamanho da lista de?
>> JASON HIRSCHHORN: Desculpe.
Por especificação pset, a pesquisa e classificar as funções que você precisa para escrever,
n é o tamanho da lista.
Eu esqueci de explicar isso aqui.
Mas sim. n é o tamanho de lista, neste caso.
Assim, enquanto que n é maior do que 0.
OK.
Isso pode revelar-se um pouco problemático porém, se as coisas continuarem.
Porque vamos continuar a conhecer a Tamanho da lista ao longo deste
função, mas dizer que começar com uma matriz de 5 inteiros.
E nós passamos e temos agora reduzi-lo a
uma matriz de dois inteiros.
Que dois inteiros que é isso?
O tamanho é de 2 agora que queremos olhar, mas que 2 é isso?
Isso faz sentido, essa pergunta?
>> OK.
Vou perguntar de novo.
Então começamos com esse conjunto de 5 inteiros, e n é igual a 5, certo?
Nós vamos passar por aqui.
provavelmente vamos mudar o tamanho, direita, como as coisas continuarem.
Que é o que dizemos que queremos fazer.
Nós não deseja pesquisar a coisa completa novamente.
Então, dizer que mudá-lo para 2.
Levamos metade da lista que é estranho.
Então, basta escolher 2.
Então agora n é igual a 2.
Peço desculpas para os pobres marcadores de apagar a seco.
Certo?
E nós estamos procurando através da lista novamente com uma lista de tamanho 2.
Bem, a nossa disposição ainda é de tamanho 5.
Dizemos que só querem pesquisar 2 pontos na mesma.
Assim que dois pontos são esses?
>> Será que isso faz sentido?
São eles os deixaram dois pontos?
Eles são o direito 2 pontos?
Eles são o Oriente 2 pontos?
Nós quebramos o problema para baixo, mas realmente não sei que parte do
o problema ainda estamos olhando, apenas por ter essas duas variáveis.
Então precisamos de um pouco mais então, enquanto que n é maior do que 0.
Precisamos saber onde esse n está na nossa disposição real.
>> Então, alguém tem um mudar para essa linha?
A maior parte desta linha é perfeitamente correta.
Existe uma outra adição?
Podemos trocar alguma coisa para a n fazer esta linha um pouco melhor?
Mm-hm?
>> ALUNO: Você pode inicializar uma variável como o comprimento de n que vai ser usado
posteriormente a função?
>> JASON HIRSCHHORN: Então inicializar um comprimento variável para n,
e nós usamos isso mais tarde?
Mas, então, apenas atualizar comprimento e nós ainda executar para esse problema em que
reduzir o comprimento do nosso problema, mas nunca se sabe onde, na verdade,
que o comprimento mapeia para.
>> ALUNO: Não é que vai acontecer mais tarde, quando você está dizendo, procure à esquerda,
pesquisar certo?
Você está indo para ir para um diferente área de sua -
>> JASON HIRSCHHORN: Nós estamos indo para ir para uma área, mas como nós sabemos
que devem ir?
Se só temos a matriz e este n, como é que vamos saber onde
ir para a matriz.
Na parte de trás, não é?
>> ALUNO: Você tem, assim, um menor amarrado e uma variável de limite superior ou
uma coisa dessas?
>> JASON HIRSCHHORN: OK.
Portanto, esta é uma outra idéia.
Ao invés de apenas manter o controle da tamanho, nós manter o controle do mais baixo e
variável limite superior.
Então, como podemos calcular o tamanho da um limite superior e limite inferior?
>> [VOZES interpondo]
>> JASON HIRSCHHORN: Subtração.
E também manter o controle de quanto menor amarrado e limite superior para que possamos saber,
estamos buscando esses dois?
Estamos buscando esses dois aqui?
Estamos procurando os dois meio?
Provavelmente não os dois do meio, porque isto, na verdade, é de pesquisa binária.
Mas agora nós vamos ser capazes de obter o tamanho, mas também os limites da matriz.
Em essência, se temos o nosso gigante livro de telefone, nós rasgá-lo ao meio.
Agora sabemos onde esse menor livro de telefone é.
Mas nós não estamos realmente rasgando o livro de telefone pela metade.
Nós ainda precisamos de saber onde o novos limites de nosso problema.
Alguém tem alguma dúvida sobre isso?
Sim?
>> ALUNO: Será que funciona através da criação de um variável, i, que depois é só mudar
a posição da i em relação ao seu posição actual, e o comprimento, n?
>> JASON HIRSCHHORN: E o que é que eu?
>> ESTUDANTE: Como eu ser como uma espécie de -
Como você inicializar i para ser o posição central da matriz.
E então, se o valor na posição i em no meio da matriz in encontrado para
ser menor que o valor que você precisa, eu agora torna-se o comprimento da matriz, além
o valor de i dividido por 2.
Como, veja, você muda i -
>> JASON HIRSCHHORN: Certo.
>> ALUNO: - até o -
>> JASON HIRSCHHORN: Então, eu estou quase positivo que vai funcionar.
Mas o ponto é, você precisa de dois pedaços de informação aqui.
Você pode fazê-lo com início e fim, ou você pode fazê-lo com tamanho e, em seguida,
algum marcador.
Mas você precisa de duas peças de informações aqui.
Você não pode ficar com apenas um.
Será que isso faz sentido?
>> Então, vamos passar, e vamos fazer [inaudível]
e criar alguns marcadores.
Então o que você escreve no seu código?
>> ALUNO: Eu só disse int limite é igual a 0.
>> JASON HIRSCHHORN: Vamos chamar que int, começando.
>> ALUNO: OK.
>> JASON HIRSCHHORN: Isso faz mais sentido para mim.
E?
>> ALUNO: Eu disse, eu acho, int fim.
>> JASON HIRSCHHORN: int fim.
>> ALUNO: Eu acho, n menos 1, ou algo parecido.
Como, o último elemento.
>> JASON HIRSCHHORN: Então você escreveu, int começando igual a 0, ponto e vírgula, e int
final é igual a n menos 1, ponto e vírgula.
Então, basicamente, o que estamos fazendo aqui, 0 a primeira posição.
E como sabemos em matrizes, eles não vão até n, eles vão até n menos 1.
Portanto, temos alguns limites da nossa matriz.
E esses limites iniciais que ser os limites iniciais de nosso problema.
OK.
Então, isso parece bom.
Então, se voltarmos a essa linha, enquanto comprimento da lista é maior do que 0,
o que, em vez de n, deve vamos colocar aqui?
>> ALUNO: Escrever terminando menos começo.
>> JASON HIRSCHHORN: Ao término menos começando é maior do que 0?
OK.
E nós poderíamos, se quiséssemos fazer isso um pouco mais agradável, o que
mais poderíamos fazer?
Se quiséssemos limpar este código um pouco?
Como podemos nos livrar do 0?
Esta é apenas uma questão de estilo.
É correto agora.
>> ALUNO: Final não igual começo?
>> JASON HIRSCHHORN: Nós podemos fazer o que?
>> [VOZES interpondo]
>> ALUNO: Terminar é maior?
>> JASON HIRSCHHORN: Yeah.
Podemos apenas fazer ao terminar é maior do que o início.
Certo.
Nós adicionamos começando para o outro lado disso, e nos livramos do 0.
Então, isso só parece um pouco mais limpo.
OK.
Assim, enquanto o comprimento da lista é 0, escrevemos que, ao terminar é maior
do que no início.
Vamos colocar em nosso necessário chaves, e em seguida, a primeira coisa
nós queremos fazer é olhar para los em uma pequena lista.
Você?
Você pode me dar o -
>> ALUNO: Se parêntese valor colchete -
>> JASON HIRSCHHORN: Se parênteses colchete valor.
>> ESTUDANTE: acabar dividido por 2.
>> JASON HIRSCHHORN: Ending?
>> ALUNO: Eu vejo um problema com o seu -
>> JASON HIRSCHHORN: OK.
Bem, olhe para o meio.
Como é que sabemos o que o meio é?
É.
Então deixe-me apagar esse código.
Como é que sabemos o que o meio é?
Em qualquer coisa, quando você tem o começo eo fim, como você encontra
no meio?
>> ALUNO: Você média.
>> ALUNO: Você adiciona-los em conjunto e, em seguida, -
>> JASON HIRSCHHORN: Adicione- juntos e depois?
>> ALUNO: E você média.
Divida-o por 2.
>> JASON HIRSCHHORN: Adicione- juntos e dividir por 2.
Assim, int meio é igual?
Tom, você pode dar isso para mim?
>> ALUNO: Começando mais fim -
>> JASON HIRSCHHORN: Início mais fim.
>> ALUNO: All, suporte, dividido por 2.
>> JASON HIRSCHHORN: Todos, entre parênteses, dividido por dois.
Então isso me dá a média de qualquer coisa, certo?
>> ALUNO: Você também precisa arredondar.
>> JASON HIRSCHHORN: O que você faz Quer dizer, eu preciso arredondar?
>> [VOZES interpondo]
>> ALUNO: Porque se é um estranho número, então é como -
>> JASON HIRSCHHORN: Bem, OK.
Assim eu poderia arredondar.
Mas se for um número ímpar, a 5, eu posso tomar um fora do meio.
Ou se é um número par, ao contrário, isso é um caso melhor.
Se for 4, só temos 4, eu posso tomar o primeiro "meio", citações, fecha aspas ou
o segundo "meio".
Ou iria trabalhar para uma busca binária, então eu realmente não precisa arredondar.
Mas há uma outra coisa que eu precisa olhar para esta linha.
Podemos não perceber, ainda, mas vamos voltar a ele.
Porque esta linha, na verdade ainda precisa de uma outra coisa.
>> Mas até agora, nós escrevemos quatro linhas de código.
Nós temos o nosso começo e terminando marcadores.
Temos o nosso loop while, que mapeia em diretamente para o nosso pseudocódigo.
Nós estamos olhando para o meio que mapeia diretamente em nosso pseudocódigo.
Eu diria que este vai para o meio da lista, esta linha de código.
E então, quando vamos para o meio da Na lista, a próxima coisa que precisamos fazer
é verificar se o nosso valor está lá para o pseudocódigo que escrevemos anteriormente.
>> Então, como vamos verificar se o nosso valor está no meio da lista?
Você.
Por que você não faz isso?
>> ALUNO: Se o nosso valor de é no meio é igual
tudo o que definir o -
Quero dizer igual igual a -
>> JASON HIRSCHHORN: It -
OK.
>> ALUNO: Eu não tenho certeza o que o variável que estamos procurando
pois, embora, é porque -
>> [VOZES interpondo]
>> Estudante: [inaudível].
>> JASON HIRSCHHORN: Exatamente.
Por a declaração da função, estamos à procura de um valor.
Então, nós estamos procurando por um valor em uma matriz de valores.
Então você está exatamente certo.
Você vai fazer, se faixa de valor parêntese aberto meio fechado iguais suporte
igual valor, e lá dentro o que precisamos fazer?
Se o nosso valor está lá, o que que precisamos fazer?
>> [VOZES interpondo]
>> ESTUDANTE: Return zero.
>> JASON HIRSCHHORN: Return verdade.
>> ALUNO: Retorna true.
>> JASON HIRSCHHORN: Michael, o que é que esta linha faz?
>> Estudante: [inaudível] o programa foi executado o seu curso, e que é mais, e
você tem o que você precisa fazer?
>> JASON HIRSCHHORN: O programa ou o quê?
Neste caso?
>> ALUNO: A função.
>> JASON HIRSCHHORN: A função.
E assim, para voltar para o que chamou lo e dar-lhe o valor, é verdade.
Exatamente.
Main.
Qual é o tipo de retorno de principal, Michael?
>> ESTUDANTE: int, integer?
>> JASON HIRSCHHORN: int, exatamente.
Um inteiro.
Isso foi apenas uma pergunta para se certificar Vocês têm estado em cima dela.
O que geralmente retornam, se todas as coisas estão funcionando bem?
>> ALUNO: Zero.
>> JASON HIRSCHHORN: Zero.
Exatamente.
>> ESTUDANTE: Se este apenas retorna true, não há nenhuma informação a ser dada
sobre o que o -
Oh, este é apenas dizer que esse valor está dentro da matriz.
>> JASON HIRSCHHORN: Exatamente.
Este programa não está dando informações de onde exatamente é o valor.
Ele só está dizendo, sim, encontramos -lo, ou não, nós não encontrá-lo.
Assim, se o número encontrado, retorna true.
Bem, na verdade nós fizemos que realmente rapidamente com que uma linha de código.
Então eu vou passar essa linha de pseudocódigo.
>> ALUNO: Não precisamos para alterar a matriz?
Deve ser valores, não o valor, certo?
>> JASON HIRSCHHORN: Desculpe.
Obrigado.
>> ESTUDANTE: Yeah.
>> JASON HIRSCHHORN: Esta linha devem ser valores.
Exatamente.
OK.
Então, nós olhamos a lista meio.
Se o número encontrado return true.
Continuando com nosso pseudocódigo, se média é maior, a busca para a esquerda.
Então eu tive aqui, se o número de superior, de pesquisa à esquerda.
Constantino, você pode dar me esta linha de código?
>> ESTUDANTE: Se o valor de meia -
>> JASON HIRSCHHORN: Então, se o valor -
se parêntese aberto valoriza suporte próximo suporte do meio -
>> ALUNO: É menor do que valor?
>> JASON HIRSCHHORN: É menos do que.
>> ALUNO: Menos de valor.
>> JASON HIRSCHHORN: Valor.
Bem, na verdade, você quer verificar se o número -
Desculpe.
Isso é um pouco confuso.
Mas o resto, se o número do meio da lista é maior.
>> ALUNO: Oh, OK.
>> JASON HIRSCHHORN: Eu vou mudar isso.
Else if média é mais elevada, deseja pesquisar esquerda, OK?
E o que fazemos dentro isso se condição?
>> ALUNO: Posso fazer uma pequena alteração a condição, alterá-lo para outra pessoa se?
>> JASON HIRSCHHORN: Else if?
OK.
Portanto, este código será executado sobre o mesmo.
Mas a coisa boa sobre o uso de if, else if, else if ou if, else if, else
significa que somente um desses vai ser verificado, não todos os três,
potencialmente.
E isso faz com que seja um pouco mais agradável no computador que está
executar o seu programa.
>> Assim, [? Constantino,?]
estamos dentro desta linha, mais se os valores, próximo suporte do meio suporte
é maior do que o valor.
O que precisamos fazer?
Precisamos pesquisar a esquerda.
Como fazemos isso?
Vou dar-lhe um começo.
>> Temos essas duas coisas chamadas começando e terminando.
Então, o que precisa acontecer para o começo?
Se você quiser pesquisar a esquerda do lista, temos nosso começo atual.
O que precisamos fazer isso?
>> ALUNO: Nós ajustamos o início a média mais 1.
>> JASON HIRSCHHORN: Então, se estamos buscando a esquerda?
>> ESTUDANTE: Desculpe, meio menos -
de modo que o meio final seria menos 1 e no início -
>> JASON HIRSCHHORN: E o acontece com o início?
>> ALUNO: Ele permanece o mesmo.
>> JASON HIRSCHHORN: Então, a significado permanece o mesmo.
Se estamos buscando a esquerda, estamos usando o mesmo princípio -
exatamente correto.
E o final?
Desculpe, o que faz o terminando igual de novo?
>> ALUNO: menos Oriente 1.
>> JASON HIRSCHHORN: menos Oriente 1.
Agora, por menos 1, e não apenas do meio?
>> ALUNO: O meio está fora de já imaginar, porque tivemos
verificado que ele está fora?
>> JASON HIRSCHHORN: Isso é exatamente correto.
O meio é fora de cogitação.
Já verifiquei o meio.
Então, nós não queremos "meio", citação fecha aspas, para continuar a estar no
matriz que estamos à procura.
Então, isso é fantástico.
>> Else if meio suporte de valores é maior do valor final iguais
meio menos 1.
Jeff, que sobre esta última linha?
>> ALUNO: Else.
Valores médio é menor que o valor?
>> JASON HIRSCHHORN: Nós vamos você está me dando mais.
Então, se você não me der -
>> ALUNO: Então começando seria mais um meio.
>> JASON Hirschhorn: iguais Começando além de um meio, de novo, para a mesma
razão que Constantino deu-nos mais cedo.
E, no final, que não tenha dado me uma linha de código ainda?
Return false, Aleha, o que podemos escrever aqui?
>> ALUNO: Return false.
>> JASON HIRSCHHORN: Return false.
E precisamos fazer isso, porque se nós não encontrá-lo, é preciso dizer que
não encontrá-lo.
E nós dissemos que vamos retornar um bool, então nós definitivamente tem que voltar
um em algum lugar bool.
>> Então, vamos executar este código.
Na verdade, estou indo para -
então estamos no terminal.
Nós vamos limpar nossa janela.
Vamos fazer toda.
Descobrimos que há um erro.
Há um erro na linha 15, que deverá vírgula no final do
declaração.
Então, o que eu esqueci?
>> ALUNO: Ponto e vírgula.
>> JASON HIRSCHHORN: Ponto e vírgula até aqui.
Acho que foi o código do Tom.
Então, Tom, [inaudível].
Brincadeirinha.
Vamos fazem tudo de novo.
>> ALUNO: O diretório Dropbox devemos estar em para isso?
>> JASON HIRSCHHORN: Então você pode apenas assistir para este bit.
Mas, novamente, se você queria mudar isso código em seu diretório pset3 para tentar
com isso, isso é o que eu fiz.
Se você observar aqui - desculpe, boa pergunta.
>> [? LS,?]
Eu tenho aqui o código find.c a partir do código distro desta semana.
Tenho Helpers.h.
Eu tenho um arquivo Marca que eu realmente editado um pouco para incluir esses novos
arquivos que estamos escrevendo.
Tudo que o código estará disponível, não o código de distribuição, mas a nova
Faça arquivo, o novo arquivo será Helpers.h estar disponível on-line para download.
Mais uma vez, então esses são os códigos extras que temos.
>> Então, faça de tudo, por esta linha, faz encontrar, binária, a seleção bolha - marcas
todos os três e compila este achado código executável.
Então, geralmente, nós não queremos para direto para check50.
Nós queremos fazer alguns exames por conta própria.
Mas apenas para que possamos agilizar isso um pouco, check50 2013 pset3.find passará
em helpers.c-- o meu mal.
>> Eu não tenho esse direito agora.
Então, nós estamos indo realmente para executar o código de verdade.
Usage.find /, você sabe o que isso significa?
>> ALUNO: Você precisa de um segundo linha de comando sobre ele.
>> JASON HIRSCHHORN: Eu preciso uma segunda linha de comando.
E por a especificação, o que eu preciso para entrar o que estamos procurando.
Então, vamos olhar para 42.
Vamos mantê-lo em ordenada, porque nós não ter escrito uma função de classificação ainda -
42, 43, 44.
>> E Controle D não encontrou o agulha no palheiro.
Isso é ruim.
É definitivamente lá.
Vamos tentar outra coisa.
Talvez seja porque eu coloquei -lo no início.
>> Vamos fazer 41, 42, 43.
Lá vamos nós.
Ele encontrou.
Vamos colocá-lo no final agora, só para que possamos ser completo -
40, 41, 42.
Não encontrou a agulha.
Então, eu mencionei isso antes.
Infelizmente, eu sabia que isso ia acontecer.
>> Mas, para fins pedagógicos, é bom para explorar isso.
Não funciona.
Por alguma razão, ele não pode encontrá-lo.
Nós sabemos o que está lá dentro, mas não estamos encontrando.
Então, uma coisa que podemos fazer é passar por GDB para encontrá-lo, mas não qualquer um,
sem passar por GDB, ter um noção de onde nós asneira?
[? Madu? ?]
>> ALUNO: Eu acho que pode ser quando terminar é igual ao início, e é
apenas uma lista de um único elemento.
Em seguida, ele simplesmente ignora-lo em vez de realmente verificar.
>> JASON HIRSCHHORN: Isso é exatamente correto.
Ao final é igual a princípio, nós ainda tem um elemento em nossa lista?
>> ESTUDANTE: sim.
>> JASON HIRSCHHORN: Sim, na verdade, nós tem um e somente um elemento.
E isso provavelmente vai acontecer quando, acordo com o código que testamos, estamos no
frente do palheiro ou pelo No final do palheiro.
É aí que começo e final vai igual
um, com busca binária.
Então, nesses dois casos, não funcionou, porque terminando foi igual ao início.
>> Mas se acabar é igual a princípio, que isso loop while executar?
Isso não acontece.
E nós poderíamos ter verificado que mais uma vez através GDB.
Então, como podemos corrigir esse código, porque quando ao terminar é igual a
começando, nós também queremos isso while para executar.
>> Então, o que podemos fazer correção para a linha 18?
>> Estudante: [inaudível] é maior que ou igual a.
>> JASON HIRSCHHORN: Exatamente.
Enquanto final é maior do que ou igual ao início.
Então, agora, temos a certeza de conseguir que caso esquina no final.
E vamos ver.
Vamos correr isso mais uma vez.
>> Vamos fazer tudo.
Mais uma vez, você vai ter que apenas acompanhar aqui.
Encontre 41 desta vez.
Basta mantê-lo consistente.
>> Encontre 42.
Vamos colocá-lo no início -
42, 43, 44.
Encontrámo-lo.
Assim que foi de fato a mudança precisávamos fazer.
>> Isso foi um monte de codificação que fez, busca binária.
Alguém tem alguma dúvida antes Eu passo em linhas que escrevemos em
busca binária ou como achamos o que nós fizemos descobrir?
Antes de seguir em frente, eu também quero apontar que, em geral, mapeamos
nossa pseudo-código de um para uma para o nosso código.
>> Tivemos que coisa complicada descobrir com o
começando e terminando.
Mas se você não tivesse percebido isso, você teria escrito praticamente o
código idêntico, exceto por essas duas linhas principais.
E então você teria percebido quando você fez isso em cheques e casos que
você precisa de algo mais.
Assim, mesmo se você tivesse seguido o nosso linha pseudo-código para a linha, você teria
conseguido tudo, mas duas linhas de código que você precisava para escrever.
>> E eu estaria disposto a apostar que vocês teria descoberto isso tudo
muito rapidamente, o que você precisava para colocar algum tipo de marcador lá para descobrir
de onde você estava.
Isso, novamente, é o poder de fazer pseudo-código antes do tempo.
Assim, podemos fazer a lógica primeiro, e depois podemos preocupar com a sintaxe.
>> Se tivéssemos sido confundido sobre a lógica ao tentar escrever esse código em C,
teríamos conseguido toda desarrumada.
E então nós estaríamos fazendo perguntas sobre a lógica ea sintaxe e entrosamento
todos eles juntos.
E nós teria se perdido no que pode rapidamente tornar-se um
problema muito difícil.
Então, vamos seguir em frente agora para a seleção de tipo.
>> Temos 20 minutos.
Então, eu tenho a sensação de que não será capaz de passar por todos seleção tipo
e bubble sort.
Mas vamos pelo menos tentar para concluir a seleção tipo.
Então implementar seleção tipo usando o seguinte declaração da função.
>> Mais uma vez, este é retirado do conjunto de problemas de especificação.
Valores Int é parênteses, é uma matriz de números inteiros.
E int.n é o tamanho da matriz que.
Tipo de seleção vai para classificar essa matriz.
>> Então, por nosso modelo mental de seleção tipo, puxamos o -
primeiro, percorrer a lista da primeira tempo, encontrar o menor número,
colocá-lo no início, encontrar a segunda menor número, coloque-o no
segunda posição, se quisermos Ordenar em ordem crescente.
Eu não estou forçando você a escrever pseudo-código no momento.
>> Mas antes de fazer o código como uma classe em cinco minutos, vamos escrever
pseudo-código por isso temos algum sentido de para onde estamos indo.
Então, tentar escrever pseudo-código em seu próprio país.
E em seguida, tentar transformar essa pseudo-código em código.
Nós vamos fazer isso como um grupo em cinco minutos.
>> E, claro, deixe-me saber se você tem alguma dúvida.
>> ALUNO: É isso?
>> JASON HIRSCHHORN: Veja quão longe você pode entrar em mais de dois minutos.
Eu entendo que você não vai ser capaz de terminar.
Mas vamos falar sobre isso como um grupo.
>> Você é tudo de codificação para que [inaudível], por isso estou desculpe interromper o que está fazendo.
Mas vamos passar por isso como um grupo.
E, novamente, busca binária, todos dão me um, se não mais linhas de código.
Obrigado por isso.
Nós vamos fazer a mesma coisa aqui, o código em conjunto, como um grupo.
>> Assim, a seleção tipo - vamos escrever algumas rápidas pseudo-código.
Por modelo mental, alguém pode me dar a primeira linha de pseudo-código, por favor?
O que eu quero fazer?
>> ALUNO: Enquanto a lista está fora de ordem.
>> JASON HIRSCHHORN: OK, enquanto a lista está fora de ordem.
E o que você quer dizer "fora da ordem?"
>> ALUNO: Enquanto [inaudível]
não foi classificada.
>> JASON HIRSCHHORN: Enquanto a lista está fora de ordem, o que vamos fazer?
Dá-me a segunda linha, por favor, Marcus.
>> Estudante: Então, encontrar o próximo menor número.
Isto será recuado.
>> JASON HIRSCHHORN: Então, encontrar o próximo menor número.
E então outra pessoa?
Assim que encontrar o próximo menor número, o que vamos fazer?
Eu vou dizer encontrar o menor número.
Isso é o que nós queremos fazer.
>> Então, encontrar o menor número.
Então, o que vamos fazer?
>> Estudante: [inaudível] para início.
>> JASON HIRSCHHORN: Desculpe?
>> ALUNO: Coloque-o no no início da lista.
>> JASON HIRSCHHORN: Então, coloque-o no o início da lista.
E o que podemos fazer para a coisa que era no princípio
da lista, certo?
Estamos substituindo alguma coisa.
Então, onde é que vamos colocar isso?
Sim, Anna?
>> ALUNO: Onde o menor número era?
>> JASON Hirshhorn: Então coloque o início da lista, onde o
menor número era.
Assim, enquanto a lista está fora de ordem, encontrar o menor número, coloque-o em
o início da lista, coloque o início da lista, onde o
menor número era.
Marcus, você pode reformular esta linha enquanto a lista está fora de ordem?
>> ALUNO: Embora os números não foram classificadas?
>> JASON Hirshhorn: OK, então, a fim de sabe que os números não foram
classificadas, o que precisamos fazer?
Quanto precisamos passar por essa lista?
>> ALUNO: Então eu acho que um loop, ou tempo, enquanto os números verificados é menor
do que o comprimento da lista de?
>> JASON Hirshhorn: OK, isso é bom.
Acho que misphrased minha pergunta mal.
Eu só estava tentando chegar nós vamos ter que ir
toda a lista.
Assim, enquanto a lista está fora de ordem, para mim, é difícil mapear diante.
Mas, basicamente, é assim que Eu penso sobre isso.
Vá até a lista inteira, encontrar o menor número, coloque-o no
começando - na verdade, você está certo.
Vamos colocá-los ambos.
>> Assim, enquanto a lista está fora de ordem, nós precisa passar por toda a lista
uma vez, encontrar o menor número, lugar que no início da lista, colocar
o início da lista onde o menor número era, e em seguida, se o
lista ainda está fora de ordem, nós temos tem que passar por isso
processo novo, certo?
É por isso que a seleção tipo, Big-O tempo de execução de seleção tipo, alguém?
>> ESTUDANTE: n ao quadrado.
>> JASON Hirshhorn: n ao quadrado.
Porque como Marcus e eu só percebi aqui, nós vamos ter que
percorrer a lista lista número de vezes.
Então passando por algo de comprimento n n número de vezes
é, de fato, n ao quadrado.
>> Então, este é o nosso pseudocódigo.
Isso parece muito bom.
Alguém tem alguma dúvida sobre o pseudocódigo?
Porque na verdade a seleção tipo deve provavelmente vir um para um, o código de
pseudocódigo.
Assim, qualquer dúvida sobre a lógica do pseudocódigo?
Por favor, pergunte-lo agora.
>> Tipo de seleção - enquanto a lista está fora de ordem, nós vamos passar por isso
e encontrar o menor de cada vez e colocá-lo na frente.
Assim, enquanto a lista está fora de ordem, pode alguém me venha com essa linha de código que
não me deu uma linha de código, no entanto, por favor?
Parece uma coisa?
>> ALUNO: Isso é um loop for.
>> JASON Hirshhorn: Parece gosto de um loop for.
OK, você pode me dar o loop?
Por -
>> ALUNO: i é igual a 0.
>> JASON Hirshhorn: i ou -
o que é que falta?
O que se passa aqui?
>> ALUNO: Int.
>> JASON Hirshhorn: Exatamente.
(Int i = 0; -
>> ALUNO: i <n; i + +).
>> JASON Hirshhorn: pregado isso, Jeff.
Estamos passando por uma lista, certo?
Já vimos que o código antes.
Perfeito.
Então, vamos colocar nossas chaves aqui.
Vou colocar alguns chaves aqui.
>> Assim, embora seja 0, é preciso ir toda a lista.
Assim, cada vez que vamos a lista, o que queremos para acompanhar?
>> ALUNO: Se algum swaps são feitas.
>> JASON Hirshhorn: Encontre o menor número.
Então, nós provavelmente deve manter o controle de o número mais pequeno de cada vez.
Então linha que posso fazer para manter o controle do menor número?
Aleha, como posso manter pista de alguma coisa?
>> ALUNO: Iniciar uma nova variável.
>> JASON Hirshhorn: Iniciar uma nova variável.
Então vamos criar uma variável.
Qual o tipo?
>> ALUNO: Int.
>> JASON Hirshhorn: Int.
Vamos chamá-lo o menor.
E o que o faz igual quando nós estamos apenas começando?
Nós não passaram pela lista ainda.
Estamos na primeira parte do listar a nossa primeira vez.
O que não é igual, o menor número?
>> ALUNO: valores que eu.
>> JASON Hirshhorn: valores que eu.
Isso soa exatamente certo, certo?
O menor número no início é o lugar onde estamos.
Portanto, agora temos nosso menor, e precisamos para percorrer a lista inteira e
comparar este menor para tudo o resto.
Assim é que vamos percorrer a lista de novo?
Michael?
>> ALUNO: Você precisa fazer outro para loop.
>> JASON Hirshhorn: Outra loop for.
Vamos fazê-lo.
Dê-me algum código.
>> ALUNO: Para loop -
para os mais pequenos -
apenas int j, você poderia dizer?
= 0; tal que -
>> JASON Hirshhorn: Bem, se quisermos para percorrer a lista inteira -
>> ALUNO: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Nós vamos passar por o loop for mais uma vez.
E como é que vamos encontrar o menor número?
Tom?
Temos a corrente menor número, então como é que vamos encontrar o novo menor?
>> ALUNO: Podemos verificar se o menor número que temos é maior do que
valoriza suporte j.
>> JASON Hirshhorn: Então, se é menor maior do que os valores do suporte j.
Portanto, se o nosso atual menor é maior do que -
Vou mover estas duas linhas de código lá fora por um segundo.
Porque, antes de fazer qualquer troca, nós precisa passar por toda a lista.
Portanto, este pseudocódigo deve realmente estar fora que interna para loop.
Então, percorrer a lista inteira.
Se é maior do que o menor valores j, então o que?
>> ALUNO: Então menor é igual a valores j.
>> JASON Hirshhorn: Fantastic.
Uma pergunta rápida -
a primeira vez que passar por este ciclo, i vai ser igual a 0, j vai
para igualar 0 uma vez que temos aqui.
Então, nós vamos estar comparando um certo número de si.
Isso é eficiente?
Não, ele não é realmente eficiente.
O mesmo acontece com o nosso j precisa ir de 0 a N de cada vez?
Será que sempre precisa verificar toda a lista?
[Inaudível]?
>> ALUNO: Comece com i vez.
>> JASON Hirshhorn: j lata começar com o que?
>> ESTUDANTE: i.
>> JASON Hirshhorn: j pode começar com i.
Então, agora nós comparar começando com aquele em que estamos.
Mas, mesmo assim, é que, como eficiente possível?
>> ALUNO: i + 1.
>> JASON Hirshhorn: i + 1 parece ser o mais eficiente, porque nós
já tem i.
Estamos afirmando que, como o menor na linha 15.
Vamos começar com o próxima automaticamente.
Então, nós passamos pelo loop for.
Vamos passar por cada vez.
Nós vamos passar por um número de vezes.
Agora que temos obtido através este interior para loop.
Temos o menor valor salva.
Precisamos colocá-lo no no início da lista.
Então, como faço para colocá-lo no no início da lista?
O que é a variável que se refere para o início da lista?
Estamos nisso fora para o laço, então o que se refere à
no início da lista?
>> ALUNO: valores que eu.
>> JASON Hirshhorn: Exatamente.
Os valores de i é o começo da -
ou desculpe, não o começo.
Isso foi confuso.
É onde estamos no início de a parte indiferenciados da lista.
Assim, os valores i.
E o que faz que a igualdade?
>> ALUNO: Menor.
>> JASON Hirshhorn: valores i é igual a quê?
>> ALUNO: Menor.
>> JASON Hirshhorn: Menor.
Exatamente.
Então, nós estamos colocando-o no início da lista, e agora é preciso colocar
o início da lista quando o menor número era.
Então como é que eu escrevo, onde o menor número foi?
Valores de quê?
>> ESTUDANTE: 0.
>> JASON Hirshhorn: O pequeno número está em 0?
>> ESTUDANTE: Yeah.
>> JASON Hirshhorn: E se o menor número foi no final
esta lista não ordenada?
>> ESTUDANTE: Desculpe, mas o que era a pergunta?
>> JASON Hirshhorn: Onde está o menor número?
Pegamos o menor e colocá-lo no começando com essa linha aqui.
>> ALUNO: Ela deve ter foram armazenados em algum -
>> ESTUDANTE: Os valores de j.
>> JASON Hirshhorn: Bem, é não necessariamente os valores j.
Ele nem sequer existe neste momento.
>> ALUNO: Você tem que declarar uma variável anteriormente e
em seguida, atribuí-la a -
quando você encontrar o menor número, atribuir o índice de que o número de
alguma variável ou algo parecido.
>> JASON Hirshhorn: Então pode você dizer isso de novo?
>> Estudante: Então, onde você declarou int menor, você também deve declarar int
menor índice = i, ou algo parecido.
>> JASON Hirshhorn: Então, onde eu int menor, não só deve manter o controle
do valor mas a localização.
int smallest_location = neste caso, vamos apenas fazer i.
Precisamos saber onde ele está.
Chegamos ao final do código, e nós percebemos que não tinha idéia de onde estava.
E assim, mais uma vez, estamos mapeamento este em um para um.
Vocês codificação isso em sua própria vontade provavelmente chegar ao mesmo problema.
Como diabos eu encontrá-lo?
E então você percebe, espere, eu precisa manter o controle disso.
>> Então, se é menor maior de valores j.
Nós estabelecemos menor é igual aos valores j.
O que mais é preciso mudar?
Constantin, o que mais é preciso mudar?
>> ALUNO: A localização.
>> JASON Hirshhorn: Exatamente.
Então me dê essa linha no código.
>> ALUNO: smallest_location = j.
>> JASON Hirshhorn: Exatamente.
E, em seguida, para baixo, no final, se quisermos colocar o início da lista, onde
o menor número era, como que nos referimos, onde o
menor número foi?
Marcus?
>> ALUNO: O menor número foi localizado em menor local.
>> JASON Hirshhorn: Então, em valores smallest_location.
E o que é que vamos colocar lá?
O início da lista, o que é isso?
>> ESTUDANTE: Bem, nós realmente não sabemos mais porque substituiu.
Portanto, é um locais trocados destas duas linhas?
Se você alternar essas duas linhas ao redor.
>> JASON Hirshhorn: OK, então nós não mais, porque nós redefinir a linha
antes de valores i para o menor.
Então, nós perdemos esse valor inicial.
Então você disse que troca essas duas linhas.
Então agora coloque o início da lista onde o menor número era.
Então smallest_location iguala valores i.
Isso está se movendo no início deste indiferenciados parte da lista para o
menor local.
E, em seguida, em valores i estamos nos movendo que menor número.
>> Isso faz sentido porque nós tinha que fazer essa troca?
Gostaríamos de ter substituído o valor - outra coisa que você provavelmente teria
descoberto e encontrado no PIB.
Então, nós temos tido o cuidado de tudo o pseudocódigo.
Há mais alguma coisa que precisa escrever aqui?
Alguém pode pensar em nada?
>> ESTUDANTE: Como você sabe quando você é feito?
>> JASON Hirshhorn: Como é que nós sabe quando estamos a fazer?
Ótima pergunta.
Então, como vamos saber quando estamos a fazer.
>> ALUNO: Crie uma variável para manter a contagem de se há uma troca feita ou não
e passar por um passe.
>> JASON Hirshhorn: OK.
Isso iria trabalhar em bubble sort.
Mas para a seleção de tipo, se não o fizermos fazer uma troca, que pode ser apenas
porque o menor valor é nele a sua localização.
Podemos ter uma lista 1, 2, 4, 3.
O segundo tempo através de nós não vai fazer nenhuma swaps.
Estaremos no número 2, mas vamos ainda precisa continuar.
Portanto, é preciso manter o controle de quando estamos a fazer, ou nós só quero ir
até que isso seja concluído?
>> ALUNO: Nós podemos apenas ir até que esteja terminado.
>> JASON Hirshhorn: podemos apenas ir até que isso seja concluído.
Em bubble sort, você está absolutamente certo, Jeff e Aleha, com a sua solução -
ele é ótimo para manter o controle de quantas swaps que você fez, porque na bolha
tipo, se você de fato não fazem swaps, você está feito e você pode talvez cortar o
problema um pouco.
Mas para a seleção de tipo, você tem realmente tem que ir até o fim do
listar cada vez.
>> Portanto, esta é isso.
Temos dois minutos do fim.
Vamos fazer tudo.
Deixe-me apenas aberta Encontre aqui e faça certeza que estou, de fato, chamar-se -
Não estou pedindo bubble sort.
Vamos mudar isso para seleção tipo.
fazer tudo. / find.
Vamos encontrar 42.
Desta vez, vamos passar um lista não ordenada, porque ele deve classificar
em primeiro lugar, por o Código de busca - deve classificar o primeiro a utilizar a nossa função de classificação e, em seguida,
procurar algo.
Dedos cruzados todos.
>> Oh meu Deus.
Whoa, meu coração estava batendo.
Então, isso é correto.
Na verdade, se nós corremos este mais extensivamente, o código, tanto quanto eu puder
dizer, é perfeitamente correta.
Existem algumas sugestões Eu tenho para você.
Por exemplo, 15 e 16 parecem um pouco redundante.
Parece que você não necessariamente precisa economizar tanto aqueles.
Se você tem o menor local, você pode facilmente encontrar o menor valor por
apenas digitando valores de i.
>> Então, se eu fosse o seu código de classificação, que eu vou ser de fato, eu o faria
provavelmente tirar um ponto, se você incluído ambos, porque você
não precisa de ambos.
Se você tem a localização, você pode facilmente obter o valor.
E parece um pouco estranho para armazenar os dois.
Talvez nem mesmo tomar um ponto, mas certamente comentar que essa é talvez
não é uma escolha estilística você precisa fazer.
Claro que, o código ainda funciona perfeitamente bem.
>> Então, infelizmente, não fez chegar a bubble sort.
Eu sinto muito por isso.
Fizemos acabamento seleção tipo.
Alguém tem alguma perguntas finais sobre a seleção de tipo?
>> OK, antes de sair, quero que você para abrir o seu navegador Chrome.
Desculpe, isso foi apenas um plug flagrante para um tipo de navegador de internet.
Você pode abrir qualquer tipo de navegador, mas provavelmente vai ser Chrome.
E ir a este seguinte site -
sayat.me/cs50.
Se você não está digitando em seu computador agora, você está claramente
não fazê-lo, Tom.
>> E, por favor fazê-lo também direito agora ou na próxima hora -
dar-me algum feedback.
Esta é apenas a seção dois.
Temos muitos mais juntos, então eu tem um monte de espaço para melhorar.
Eu espero que também fez bem algumas coisas.
Então você pode me fazer sentir de todo ruim, mas se você também quiser me dar um smiley
cara, eu gostaria de receber isso também.
Encha que dentro
>> E com um minuto para a esquerda, que foi de três semanas.
Eu vou ficar fora por um tempo se você tiver quaisquer perguntas.
Eu vou ver vocês em palestra amanhã.