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