1 00:00:00,000 --> 00:00:06,370 2 00:00:06,370 --> 00:00:08,150 >> JASON HIRSCHHORN: Welcome a semana três, todos. 3 00:00:08,150 --> 00:00:11,650 Temos um ocupado, mas emocionante seção à frente de nós. 4 00:00:11,650 --> 00:00:17,010 Então, primeiro, porque fizemos alguns progresso com o curso, mas ainda 5 00:00:17,010 --> 00:00:20,570 tem um monte de aprendizagem deixou de fazer, eu sou vai mostrar a vocês alguns recursos 6 00:00:20,570 --> 00:00:24,160 que deve provar ser incrivelmente útil, você não só se aproxima de seu 7 00:00:24,160 --> 00:00:28,130 conjuntos de problemas, mas também digerir todos o material que dar a vocês em 8 00:00:28,130 --> 00:00:30,800 palestras e shorts e seção. 9 00:00:30,800 --> 00:00:34,790 >> Então vamos passar a primeira 20 25 minutos de seção passando por cima 10 00:00:34,790 --> 00:00:38,630 GDB, que você pode ou não pode ter usado neste momento, mas isso é uma 11 00:00:38,630 --> 00:00:42,570 ferramenta incrivelmente útil que vai ajudar a depurar seus programas. 12 00:00:42,570 --> 00:00:46,060 Muitos de vocês podem ter usado printf no meio de seu programa para descobrir 13 00:00:46,060 --> 00:00:47,430 o que uma variável igualado. 14 00:00:47,430 --> 00:00:52,060 GDB é ainda melhor do printf e não estrague o seu código, porque você 15 00:00:52,060 --> 00:00:53,320 executá-lo em um arquivo executável. 16 00:00:53,320 --> 00:00:56,500 Então, vamos passar por cima dos 10 mais útil os comandos que você precisa para o GDB, e estamos 17 00:00:56,500 --> 00:01:00,540 indo para ir em um exercício conjunto para no conjunto de problemas de três e além, você 18 00:01:00,540 --> 00:01:03,320 pode usar GDB para ajudar a depurar seus programas. 19 00:01:03,320 --> 00:01:06,420 E, finalmente, vamos passar por cima de alguns classificação e pesquisa de algoritmos 20 00:01:06,420 --> 00:01:10,590 que você viu na aula, e nós somos vai realmente código, não apenas 21 00:01:10,590 --> 00:01:17,360 pseudocódigo, mas o código de busca binária, bubble sort, e seleção de classificação. 22 00:01:17,360 --> 00:01:20,090 >> Então, primeiro, eu quero ir sobre os recursos. 23 00:01:20,090 --> 00:01:23,530 Esta é uma lista extensa, e é fonte menor, porque eu tinha um monte de 24 00:01:23,530 --> 00:01:24,390 caber aqui. 25 00:01:24,390 --> 00:01:26,950 Mas estes não só irá ajudá-lo, novamente, com os conjuntos de problemas e 26 00:01:26,950 --> 00:01:30,760 digerindo informações que você aprendeu, mas definitivamente, chegou a hora do teste, estes serão 27 00:01:30,760 --> 00:01:32,130 ser extremamente útil. 28 00:01:32,130 --> 00:01:34,700 Então, primeiro, a palestra observa. 29 00:01:34,700 --> 00:01:39,480 Se você vai para cs50.net/lectures e desloque-se para a semana e dia específico, 30 00:01:39,480 --> 00:01:43,120 você vai ver que existem notas para cada palestra, que não é simplesmente uma 31 00:01:43,120 --> 00:01:47,250 transcrição, mas uma versão editada de o que foi abordado em palestra com código 32 00:01:47,250 --> 00:01:49,610 trechos e outros petiscos úteis. 33 00:01:49,610 --> 00:01:52,220 Eu recomendo ir sobre aqueles. 34 00:01:52,220 --> 00:01:55,340 E depois, bem, não há código fonte disponível a partir de cada palestra. 35 00:01:55,340 --> 00:02:00,050 E, novamente, esses slides também será disponível online em cs50.net/sections 36 00:02:00,050 --> 00:02:01,480 esta noite. 37 00:02:01,480 --> 00:02:06,860 >> Assim, segundo são os shorts cada semana que abrangem temas, geralmente de 5 a 15 38 00:02:06,860 --> 00:02:08,090 minutos de duração. 39 00:02:08,090 --> 00:02:12,310 E aqueles espero venha a dar-lhe uma grande cartilha sobre diferentes temas. 40 00:02:12,310 --> 00:02:12,870 Terceiro - 41 00:02:12,870 --> 00:02:16,370 e isso é novo este ano - é study.cs50.net. 42 00:02:16,370 --> 00:02:20,110 Se você ainda não verifiquei, eu recomendo que você faça isso. 43 00:02:20,110 --> 00:02:21,100 Você começa a escolher um tema. 44 00:02:21,100 --> 00:02:23,040 Temos dezenas de tópicos sobre lá. 45 00:02:23,040 --> 00:02:24,770 Assim, por exemplo, você escolhe Funções. 46 00:02:24,770 --> 00:02:27,270 Dá-lhe alguns slides e notas sobre funções. 47 00:02:27,270 --> 00:02:31,190 Esses são realmente os slides que TFs são incentivados a usar durante a nossa 48 00:02:31,190 --> 00:02:32,710 apresentações na seção. 49 00:02:32,710 --> 00:02:35,040 Há também dicas e truques para lidar com funções, e não há 50 00:02:35,040 --> 00:02:37,290 problemas práticos que ajudam você trabalha com funções. 51 00:02:37,290 --> 00:02:41,500 Nós também dar-lhe links para o curto no funções e os tempos que as funções 52 00:02:41,500 --> 00:02:42,750 vêm-se na palestra. 53 00:02:42,750 --> 00:02:46,550 Então study.cs50.net, a nova marca presente ano, um recurso fantástico. 54 00:02:46,550 --> 00:02:52,180 >> Em seguida, eu tenho o homem, que é o manual comando que pode ser executado no 55 00:02:52,180 --> 00:02:52,770 linha de comando. 56 00:02:52,770 --> 00:02:57,880 Então, se você tem alguma dúvida sobre a comando, por exemplo, rand, que nós 57 00:02:57,880 --> 00:03:00,900 encontrou na semana passada durante a seção e você provavelmente encontrou em 58 00:03:00,900 --> 00:03:05,380 seu conjunto de problemas quando passar pelo gerar o código, mas se você digitar homem 59 00:03:05,380 --> 00:03:09,980 rand, você terá a página que diz-lhe tudo sobre o rand. 60 00:03:09,980 --> 00:03:14,040 Dá-lhe o que é preciso, a parâmetros que leva, assim como o retorno 61 00:03:14,040 --> 00:03:16,530 tipo e uma breve descrição dessa função. 62 00:03:16,530 --> 00:03:17,500 >> Então confira rand. 63 00:03:17,500 --> 00:03:22,270 Ele pode ser um pouco prolixo e confuso, por isso às vezes eu acho que 64 00:03:22,270 --> 00:03:26,150 simplesmente pesquisando o que eu quero saber é a melhor maneira de encontrar a resposta. 65 00:03:26,150 --> 00:03:27,940 Assim, a prática com o Google. 66 00:03:27,940 --> 00:03:28,600 Obter bons no Google. 67 00:03:28,600 --> 00:03:30,600 Vai tornar-se seu melhor amigo. 68 00:03:30,600 --> 00:03:34,300 >> Assim como o Google, se você não pode encontrá-lo no Google, cs50.net/discuss, é 69 00:03:34,300 --> 00:03:35,550 o fórum de discussão. 70 00:03:35,550 --> 00:03:39,390 Provavelmente, se você tem uma pergunta, uma de seus 700 + pares também tem que 71 00:03:39,390 --> 00:03:42,110 questão e pode ter pedido já na discussão 72 00:03:42,110 --> 00:03:43,540 fóruns e tê-lo respondido. 73 00:03:43,540 --> 00:03:48,130 Então se você tem uma pergunta comum ou Você tem uma pergunta que você pensa 74 00:03:48,130 --> 00:03:52,300 talvez outras pessoas possam ter executado em, confira cs50.net/discuss. 75 00:03:52,300 --> 00:03:55,450 >> Finalmente, os dois últimos, se você quiser falar com um ser humano real, escritório 76 00:03:55,450 --> 00:03:57,770 horas de segunda a sexta-feira. 77 00:03:57,770 --> 00:04:00,850 Há também o horário de expediente on-line para os alunos de extensão. 78 00:04:00,850 --> 00:04:04,370 E por último mas não menos importante, me, ponto de exclamação. 79 00:04:04,370 --> 00:04:05,960 Vocês todos têm a minha informação de contato. 80 00:04:05,960 --> 00:04:11,940 Se você precisar de alguma coisa, por favor, nunca hesite em contactar-me. 81 00:04:11,940 --> 00:04:14,020 Sempre à vontade para fazê-lo. 82 00:04:14,020 --> 00:04:17,490 Muito poucos de vocês já me adicionou no Gchat, de modo que tem sido decepcionante, 83 00:04:17,490 --> 00:04:20,410 mas espero que isso vai mudar entre neste e no próximo seção. 84 00:04:20,410 --> 00:04:22,105 Qualquer dúvida até agora sobre os recursos? 85 00:04:22,105 --> 00:04:25,670 86 00:04:25,670 --> 00:04:27,450 Grande. 87 00:04:27,450 --> 00:04:34,280 >> Finalmente, uma outra ficha para feedback, sayat.me/cs50. 88 00:04:34,280 --> 00:04:37,050 Você pode me dar um feedback anônimo sobre como eu estou fazendo. 89 00:04:37,050 --> 00:04:38,320 Isso foi muito útil na semana passada. 90 00:04:38,320 --> 00:04:41,890 Eu tenho um par de comentários de vocês logo após a seção, mais de 91 00:04:41,890 --> 00:04:44,750 outros alunos que assistiram durante a semana, e 92 00:04:44,750 --> 00:04:46,830 foi incrivelmente útil. 93 00:04:46,830 --> 00:04:50,250 Vou tentar limitar o meu uso de a palavra "doce", mas vou mostrar o meu 94 00:04:50,250 --> 00:04:52,410 entusiasmo e emoção em outras formas. 95 00:04:52,410 --> 00:04:56,550 Mas havia outro adicional feedbacks substantivas, 96 00:04:56,550 --> 00:04:57,600 ambos os prós e delta. 97 00:04:57,600 --> 00:05:00,480 Então, por favor, eu dou a vocês um feedback em seus conjuntos de problemas. 98 00:05:00,480 --> 00:05:01,790 Sinta-se livre para me dar feedback no meu ensino. 99 00:05:01,790 --> 00:05:04,010 Estou aqui para vocês. 100 00:05:04,010 --> 00:05:05,270 >> Grande. 101 00:05:05,270 --> 00:05:07,020 Isso é tudo o que eu tenho para a primeira seção. 102 00:05:07,020 --> 00:05:08,565 Alguém tem alguma perguntas até agora? 103 00:05:08,565 --> 00:05:12,370 104 00:05:12,370 --> 00:05:14,640 E eu tenho uma nota para o centro de controle. 105 00:05:14,640 --> 00:05:21,200 Os alunos têm me enviado mensagens de Extensão dizendo que não está recebendo qualquer áudio, 106 00:05:21,200 --> 00:05:23,870 mas que está fora do meu alcance para corrigir. 107 00:05:23,870 --> 00:05:25,280 Portanto, esperamos, que recebe resolvido em breve. 108 00:05:25,280 --> 00:05:28,850 Se você está assistindo on-line, oi, mas você não pode me ouvir. 109 00:05:28,850 --> 00:05:33,860 >> Então, primeiro, vamos passar por GDB. 110 00:05:33,860 --> 00:05:37,100 GDB, como sugerido anteriormente, é uma ferramenta de depuração 111 00:05:37,100 --> 00:05:39,040 muito melhor do que printf. 112 00:05:39,040 --> 00:05:44,700 Então, para começar com o GDB, gente, se você quiser abrir o seu aparelho 113 00:05:44,700 --> 00:05:49,070 e levar o arquivo que eu enviado para você anteriormente - este arquivo também será 114 00:05:49,070 --> 00:05:51,940 disponível on-line em um pouco - 115 00:05:51,940 --> 00:05:55,700 e executar GDB. / o nome do arquivo. 116 00:05:55,700 --> 00:05:58,580 Primeiro, é claro, você tem que compilar arquivo porque GDB só funciona em 117 00:05:58,580 --> 00:05:59,890 arquivos executáveis. 118 00:05:59,890 --> 00:06:02,300 >> Mas se você quer começar GDB, a primeira coisa que você faz, 119 00:06:02,300 --> 00:06:04,550 você executar GDB. / César. 120 00:06:04,550 --> 00:06:08,340 Então esse é o nome do programa que estamos indo para ir com ele agora. 121 00:06:08,340 --> 00:06:12,810 Então eu vou escrever fazer César, que vai me dar um arquivo executável 122 00:06:12,810 --> 00:06:14,100 aqui destacadas em verde. 123 00:06:14,100 --> 00:06:19,250 E então eu vou correr GDB. / Cesar. 124 00:06:19,250 --> 00:06:19,810 >> E lá vai você. 125 00:06:19,810 --> 00:06:24,540 Você vê que temos um texto a dizer-me sobre a versão do GDB, dando-me 126 00:06:24,540 --> 00:06:27,570 algumas informações sobre a garantia, e então nós ter o prompt do PIB, o que parece tipo 127 00:06:27,570 --> 00:06:29,350 de como a nossa linha de comandos, mas você vê que é aberto 128 00:06:29,350 --> 00:06:32,510 paren, GDB, paren próximos. 129 00:06:32,510 --> 00:06:36,520 Antes de continuarmos e depurar este arquivo que enviei a todos vocês, vamos olhar para 130 00:06:36,520 --> 00:06:40,220 alguns comandos úteis para que ter um sentido de que estamos indo para cobrir. 131 00:06:40,220 --> 00:06:45,060 >> Estes comandos estão listados aqui no ordem em que eu geralmente uso deles. 132 00:06:45,060 --> 00:06:50,230 Então eu começo o meu programa, executando GBD. / Nome do programa, 133 00:06:50,230 --> 00:06:51,360 neste caso, César. 134 00:06:51,360 --> 00:06:57,430 E então a primeira coisa que faço de 99,9% do tempo é dizer tipo de quebra. 135 00:06:57,430 --> 00:06:59,070 Isso define um ponto de ruptura na principal. 136 00:06:59,070 --> 00:07:03,260 Essencialmente, o que você está fazendo lá é o programa que vai parar em 137 00:07:03,260 --> 00:07:06,100 principal para que você possa começar a examiná-lo linha por linha, em vez de correr tudo 138 00:07:06,100 --> 00:07:07,040 o caminho. 139 00:07:07,040 --> 00:07:09,730 Você pode quebrar em diferentes pontos o seu código, mas principal é geralmente uma 140 00:07:09,730 --> 00:07:11,870 bom lugar para começar. 141 00:07:11,870 --> 00:07:14,840 >> O próximo comando eu corro é executado. 142 00:07:14,840 --> 00:07:17,400 Isso inicia o programa em execução, e se você precisa digitar linha de comando 143 00:07:17,400 --> 00:07:19,090 argumentos, você executá-lo o comando. 144 00:07:19,090 --> 00:07:20,500 Correr com os argumentos. 145 00:07:20,500 --> 00:07:25,000 Então, já que estamos passando por cima de uma versão de C, que é o programa que vocês 146 00:07:25,000 --> 00:07:26,160 escreveu para pset dois - 147 00:07:26,160 --> 00:07:29,880 este, é claro, tem alguns bugs nele que espero que nós vamos encontrar - 148 00:07:29,880 --> 00:07:32,810 vamos correr correr com algum comando argumentos de linha porque César, 149 00:07:32,810 --> 00:07:34,860 como vocês sabem por o problema definir especificações, leva algum 150 00:07:34,860 --> 00:07:36,380 Argumentos da linha de comando. 151 00:07:36,380 --> 00:07:40,000 >> O próximo par de comandos, o próximo um é realmente chamado em seguida. 152 00:07:40,000 --> 00:07:42,470 Aquela leva linha por linha através de seu programa. 153 00:07:42,470 --> 00:07:45,800 Então bater n depois Enter leva você para a próxima linha, a execução de 154 00:07:45,800 --> 00:07:46,880 a linha anterior. 155 00:07:46,880 --> 00:07:49,440 Passo não só leva você para a próxima linha, mas 156 00:07:49,440 --> 00:07:51,070 leva-funções dentro. 157 00:07:51,070 --> 00:07:54,310 Portanto, se você escreveu uma função em o seu código ou se você quiser explorar um 158 00:07:54,310 --> 00:07:57,820 para i, por exemplo, você pode bater s, e ao invés de ir para a próxima linha de 159 00:07:57,820 --> 00:08:02,390 o arquivo que você está passando agora, você vai realmente entrar 160 00:08:02,390 --> 00:08:04,670 esta função e ver o seu código. 161 00:08:04,670 --> 00:08:12,300 >> Lista mostra, em muito amigável formato, os 10 ou mais linhas ao redor 162 00:08:12,300 --> 00:08:14,940 onde você está atualmente em seu código assim você pode realmente ver o arquivo 163 00:08:14,940 --> 00:08:17,810 ao invés de ter de trocar de volta e outro entre diferentes pontos de vista. 164 00:08:17,810 --> 00:08:21,890 Imprimir é como printf, como o próprio nome indica. 165 00:08:21,890 --> 00:08:24,020 Isso mostra o que uma variável é igual. 166 00:08:24,020 --> 00:08:25,870 >> Informações locais é realmente útil. 167 00:08:25,870 --> 00:08:27,740 Esta é uma versão especial de impressão. 168 00:08:27,740 --> 00:08:31,770 Informações locais mostra todo o local, variáveis, imprime todos eles para você para fora 169 00:08:31,770 --> 00:08:33,380 que estão atualmente disponíveis. 170 00:08:33,380 --> 00:08:36,360 Então, eu geralmente, ao invés de ter que imprimir as quatro variáveis ​​que eu sou 171 00:08:36,360 --> 00:08:39,929 curioso sobre se eu estou em um loop, por exemplo, eu só escrevo informações locais, 172 00:08:39,929 --> 00:08:43,470 e ele vai me que o meu contador eu mostro é igual a, bem como a matriz que eu sou 173 00:08:43,470 --> 00:08:45,130 trabalhando em pares. 174 00:08:45,130 --> 00:08:47,530 >> Finalmente, continue. 175 00:08:47,530 --> 00:08:49,300 Digitando pausa você pára no ponto de quebra. 176 00:08:49,300 --> 00:08:51,380 Você pode andar através da linha por linha com o próximo e passo. 177 00:08:51,380 --> 00:08:55,640 Continuar executa o programa para o seu próximo ponto de quebrar ou até a conclusão se 178 00:08:55,640 --> 00:08:57,180 não há mais pontos de quebra. 179 00:08:57,180 --> 00:09:00,060 Desativar remove pontos de quebra, se você decidiu que a pausa no principal era 180 00:09:00,060 --> 00:09:01,890 impróprio, você quer defini-lo em outro lugar. 181 00:09:01,890 --> 00:09:05,090 E, finalmente, q, sair, sai do GDB. 182 00:09:05,090 --> 00:09:10,784 >> Portanto, este programa,. / César, vamos a olhar através de agora e nós 183 00:09:10,784 --> 00:09:13,490 vai usar GDB para encontrar os erros neste programa. 184 00:09:13,490 --> 00:09:18,110 Corri este programa anterior com Confira 50, e eu tenho uma carranca. 185 00:09:18,110 --> 00:09:22,310 Tudo o que existia, compilado, passaram muitos dos testes, mas para 186 00:09:22,310 --> 00:09:27,950 alguma razão, ele não passou da quinta teste, transformando BARFOO, todas as letras maiúsculas, em 187 00:09:27,950 --> 00:09:33,350 E-D-U-I-R-R, todas as tampas, usando três como uma chave. 188 00:09:33,350 --> 00:09:34,090 Eu tenho muito perto. 189 00:09:34,090 --> 00:09:35,410 Desci por uma letra. 190 00:09:35,410 --> 00:09:37,340 Portanto, há um pequeno erro aqui. 191 00:09:37,340 --> 00:09:38,070 Eu olhei através do meu código. 192 00:09:38,070 --> 00:09:38,850 Eu não conseguia entender. 193 00:09:38,850 --> 00:09:41,740 Espero que vocês possam me ajudar descobrir o que é esse bug. 194 00:09:41,740 --> 00:09:44,610 >> Então esse é o erro que estamos procurando. 195 00:09:44,610 --> 00:09:46,090 Vamos passar em GDB. 196 00:09:46,090 --> 00:09:51,100 Mais uma vez, eu correr GDB. / César, então agora estamos em GDB. 197 00:09:51,100 --> 00:09:54,290 E o que é a primeira coisa que eu devo fazer? 198 00:09:54,290 --> 00:09:56,680 Acabei entrou GDB. 199 00:09:56,680 --> 00:10:00,316 Alguém me dê uma boa comando para entrar. 200 00:10:00,316 --> 00:10:01,140 >> ALUNO: Quebre principal. 201 00:10:01,140 --> 00:10:01,800 >> JASON HIRSCHHORN: Quebre principal. 202 00:10:01,800 --> 00:10:02,900 Fantástico. 203 00:10:02,900 --> 00:10:03,560 Vamos digitar que dentro 204 00:10:03,560 --> 00:10:06,390 Vocês podem ver aqui em cima ou seguir ao longo de seus computadores. 205 00:10:06,390 --> 00:10:09,410 Quebre principal, e você verá uma ponto de ruptura foi fixado em - 206 00:10:09,410 --> 00:10:12,340 dá-me algum endereço de memória estranho, e também me dá o número da linha. 207 00:10:12,340 --> 00:10:15,310 Se eu olhar para trás, este arquivo, Eu iria perceber que o principal 208 00:10:15,310 --> 00:10:17,700 aconteceu na linha 21. 209 00:10:17,700 --> 00:10:18,950 O que devo executar o próximo? 210 00:10:18,950 --> 00:10:22,970 211 00:10:22,970 --> 00:10:25,060 É o meu programa em execução? 212 00:10:25,060 --> 00:10:25,650 Não. 213 00:10:25,650 --> 00:10:27,175 Então, o que eu deveria executar o próximo? 214 00:10:27,175 --> 00:10:27,520 >> ALUNO: Correr. 215 00:10:27,520 --> 00:10:28,050 >> JASON HIRSCHHORN: Executar. 216 00:10:28,050 --> 00:10:30,760 Devo apenas correr correr, ou deveria Eu adicionar algumas outras coisas em? 217 00:10:30,760 --> 00:10:31,960 >> ALUNO: Correr com o argumento. 218 00:10:31,960 --> 00:10:33,320 >> JASON HIRSCHHORN: Corra com os argumentos do comando. 219 00:10:33,320 --> 00:10:36,420 E já que estou a depuração de um bem específico caso, eu deveria entrar nesse 220 00:10:36,420 --> 00:10:37,120 argumento de linha de comando. 221 00:10:37,120 --> 00:10:42,290 Então, eu vou fazer correr três, o que é, novamente, a saída que eu tenho de check 50. 222 00:10:42,290 --> 00:10:44,240 Começando programa. 223 00:10:44,240 --> 00:10:45,420 Passamos por um par de linhas. 224 00:10:45,420 --> 00:10:47,700 Você vai ver agora que estamos na linha 21. 225 00:10:47,700 --> 00:10:49,200 Como eu sei que estamos na linha 21? 226 00:10:49,200 --> 00:10:52,170 Porque se você olhar para a esquerda da minha janela do terminal, não 227 00:10:52,170 --> 00:10:53,120 ele diz que linha 21. 228 00:10:53,120 --> 00:10:57,010 E isso me dá, na verdade, a código que está na linha 21. 229 00:10:57,010 --> 00:10:58,440 Então eu misspoke antes. 230 00:10:58,440 --> 00:10:59,770 Principal não é realmente na linha 21. 231 00:10:59,770 --> 00:11:02,000 Principal é um par de linhas acima de 21. 232 00:11:02,000 --> 00:11:04,300 Mas na linha 21, que é onde nós estamos quebrando. 233 00:11:04,300 --> 00:11:06,280 Esta linha de código tem ainda não executados. 234 00:11:06,280 --> 00:11:06,890 Isso é importante. 235 00:11:06,890 --> 00:11:09,120 A linha que você vê não tem foi executado ainda. 236 00:11:09,120 --> 00:11:12,650 Essa é a próxima linha de código você está prestes a executar. 237 00:11:12,650 --> 00:11:15,860 >> Portanto, a próxima linha, como vocês são provavelmente está familiarizado com, isso é 238 00:11:15,860 --> 00:11:20,070 condição verificando para ver se eu tenho entrou em um argumento de linha de comando. 239 00:11:20,070 --> 00:11:22,140 E a até i, que é o segundo parte do que está fazendo? 240 00:11:22,140 --> 00:11:23,457 O que é um ai? 241 00:11:23,457 --> 00:11:24,950 >> ALUNO: alterá-lo para um número inteiro. 242 00:11:24,950 --> 00:11:25,450 >> JASON HIRSCHHORN: Desculpe? 243 00:11:25,450 --> 00:11:27,400 >> ALUNO: Está mudando o argumento para um número inteiro. 244 00:11:27,400 --> 00:11:30,890 >> JASON HIRSCHHORN: Então ao i muda arg v1 de uma string para um inteiro. 245 00:11:30,890 --> 00:11:32,140 E então o que é que a verificação? 246 00:11:32,140 --> 00:11:35,414 247 00:11:35,414 --> 00:11:37,112 >> ALUNO: Se houver uma segunda argumento de linha de comando, além 248 00:11:37,112 --> 00:11:38,100 com a execução do programa. 249 00:11:38,100 --> 00:11:39,460 >> JASON HIRSCHHORN: E o que é o segundo semestre deste 250 00:11:39,460 --> 00:11:41,220 Expressão booleana corrente? 251 00:11:41,220 --> 00:11:42,540 Esta parte aqui, ao i? 252 00:11:42,540 --> 00:11:44,080 >> ESTUDANTE: Se é negativo. 253 00:11:44,080 --> 00:11:45,380 >> JASON HIRSCHHORN: Certificar-se de que? 254 00:11:45,380 --> 00:11:47,120 >> ALUNO: Certificar-se de que É, de facto, positiva. 255 00:11:47,120 --> 00:11:47,650 >> JASON HIRSCHHORN: Exatamente. 256 00:11:47,650 --> 00:11:50,600 Esta é a verificação para ver se é negativo e se for negativo, eu 257 00:11:50,600 --> 00:11:53,220 tenho um sentimento a linha seguinte força ser-me gritar com o usuário. 258 00:11:53,220 --> 00:11:55,930 Então, vamos bater final para executar esta linha. 259 00:11:55,930 --> 00:11:59,925 Nós não vemos que a linha que vocês talvez esperava ver a gritar com o 260 00:11:59,925 --> 00:12:03,030 usuário e, em seguida, retornar, porque esta linha não foi executada. 261 00:12:03,030 --> 00:12:03,840 Entrei 3. 262 00:12:03,840 --> 00:12:06,860 Então eu tinha, de fato, entrar dois comando argumentos de linha, e 3 é 263 00:12:06,860 --> 00:12:07,610 maior do que zero. 264 00:12:07,610 --> 00:12:09,950 Então vimos que a linha, assinamos, mas não passo 265 00:12:09,950 --> 00:12:11,300 se dentro do estado. 266 00:12:11,300 --> 00:12:17,060 >> Então, agora, ao lado, eu vejo que eu estou definindo chave int é igual ao i arg v1. 267 00:12:17,060 --> 00:12:18,840 Então esse é me criando uma chave variável. 268 00:12:18,840 --> 00:12:22,450 Então, se eu imprimir chave agora, porque que permite que você veja o 269 00:12:22,450 --> 00:12:26,040 valor dentro da variável, chave é igual a 47. 270 00:12:26,040 --> 00:12:28,810 Isso é estranho, mas é claro, isso é porque eu não tenho 271 00:12:28,810 --> 00:12:30,490 executada essa linha ainda. 272 00:12:30,490 --> 00:12:35,880 Portanto, agora se eu bater n, executar essa linha, e fazer tecla de impressão, a chave será igual a 3, 273 00:12:35,880 --> 00:12:37,740 que é o que nós esperamos que seja igual. 274 00:12:37,740 --> 00:12:41,170 >> Então, novamente, em GDB, a linha que ver que você não tenha executado ainda. 275 00:12:41,170 --> 00:12:44,850 Você tem que bater N ou S ou um número de outros comandos para realmente 276 00:12:44,850 --> 00:12:46,610 executar essa linha. 277 00:12:46,610 --> 00:12:47,380 Chave de impressão. 278 00:12:47,380 --> 00:12:48,280 Da chave em 3. 279 00:12:48,280 --> 00:12:49,750 Tão longe, tão bom. 280 00:12:49,750 --> 00:12:51,000 String é texto simples. 281 00:12:51,000 --> 00:12:52,270 Vamos executar essa linha. 282 00:12:52,270 --> 00:12:53,970 Estou recebendo uma seqüência de usuário. 283 00:12:53,970 --> 00:12:58,690 >> Vamos ver no meu check 50, I entrar BARFOO todas as tampas, de modo 284 00:12:58,690 --> 00:13:01,330 isso é o que eu vou entrar. 285 00:13:01,330 --> 00:13:07,300 Se eu agora imprimir texto puro. 286 00:13:07,300 --> 00:13:08,610 Você verá que é igual a uma string. 287 00:13:08,610 --> 00:13:11,100 Dá-me algum outro hexadecimal estranho número, mas não em 288 00:13:11,100 --> 00:13:13,620 fato de dizer que a minha string é BARFOO. 289 00:13:13,620 --> 00:13:19,308 Se eu quisesse ver o que equivalia a chave Neste ponto, como eu poderia verificar-chave? 290 00:13:19,308 --> 00:13:20,710 >> ALUNO: chave de impressão. 291 00:13:20,710 --> 00:13:22,010 >> JASON HIRSCHHORN: chave de impressão, exatamente. 292 00:13:22,010 --> 00:13:23,260 E, na verdade, há um atalho. 293 00:13:23,260 --> 00:13:25,910 Se você ficar cansado de digitar impressão, você pode apenas digitar p. 294 00:13:25,910 --> 00:13:28,340 Assim chave p faz a mesma coisa exata. 295 00:13:28,340 --> 00:13:29,730 E mais uma vez, eu vejo isso é igual a 3. 296 00:13:29,730 --> 00:13:34,760 >> Se eu quisesse descobrir o que tanto chave e BARFOO igualado ao mesmo tempo 297 00:13:34,760 --> 00:13:37,215 mas eu estava cansado de escrever cada um individualmente, eu 298 00:13:37,215 --> 00:13:38,590 pode digitar informações locais. 299 00:13:38,590 --> 00:13:41,170 Isso me dá iguais chave 3. 300 00:13:41,170 --> 00:13:42,500 Texto simples é igual BARFOO. 301 00:13:42,500 --> 00:13:45,265 Ele também me dá essas duas coisas estranhas no topo, esta variável i e 302 00:13:45,265 --> 00:13:46,590 isso n variável. 303 00:13:46,590 --> 00:13:48,460 >> Essas são realmente existente no meu programa principal. 304 00:13:48,460 --> 00:13:51,280 Nós não os encontrou ainda, mas como um preview, aqueles 305 00:13:51,280 --> 00:13:52,880 existe no meu loop for. 306 00:13:52,880 --> 00:13:55,360 Então, agora, eles igual algum estranho números, porque eles não têm sido 307 00:13:55,360 --> 00:13:58,300 inicializado ainda, mas eles ainda existem na memória, por isso eles são apenas definir 308 00:13:58,300 --> 00:14:00,220 para um valor de lixo. 309 00:14:00,220 --> 00:14:02,890 Mas nós vemos chave na planície texto ali mesmo. 310 00:14:02,890 --> 00:14:06,390 >> Então, eu estou indo para executar esta linha, linha 34, o loop para. 311 00:14:06,390 --> 00:14:08,220 Vamos saltar para o loop for por bater n. 312 00:14:08,220 --> 00:14:10,050 E nós estamos dentro do loop for. 313 00:14:10,050 --> 00:14:11,360 Estamos em nosso primeiro cheque. 314 00:14:11,360 --> 00:14:14,300 E, novamente, estes devem tipo de olhar familiar para você, porque esta era uma 315 00:14:14,300 --> 00:14:18,080 Programa César que foi escrito, mas mais uma vez, tem algum tipo de bug. 316 00:14:18,080 --> 00:14:21,940 >> E agora, se eu fizer informações locais, porque eu sou dentro daquele loop for, você verá 317 00:14:21,940 --> 00:14:23,900 que i é igual a zero, como esperamos. 318 00:14:23,900 --> 00:14:26,820 Isso é o que defini-lo como e inicializado ele no loop for. 319 00:14:26,820 --> 00:14:27,560 n é igual a 6. 320 00:14:27,560 --> 00:14:30,700 Isso também faz sentido, porque partimos lo para o strlen de texto simples. 321 00:14:30,700 --> 00:14:34,270 Então, eu gostaria de fazer Informações moradores ou impressão a variável muitas vezes para se certificar de que 322 00:14:34,270 --> 00:14:36,370 tudo é sempre o que Espero que seja igual. 323 00:14:36,370 --> 00:14:39,800 Neste caso, tudo está o que eu espero que seja igual. 324 00:14:39,800 --> 00:14:41,850 >> Então, vamos começar a se mover através de isso por loop. 325 00:14:41,850 --> 00:14:45,715 A linha que eu estou é a linha 36, ​​se simples i texto é maior do que uma simples e 326 00:14:45,715 --> 00:14:48,540 i texto é inferior ou igual a z. 327 00:14:48,540 --> 00:14:51,880 Eu sei que meu problema não é com o meu primeiro carta, é com a segunda carta. 328 00:14:51,880 --> 00:14:56,290 Se olharmos para trás no Check 50, B vai para E bem. 329 00:14:56,290 --> 00:14:59,010 Estou levando a A e deixá-lo como um A, não alterá-lo para D. Assim, 330 00:14:59,010 --> 00:15:00,200 algo está errado com a segunda letra. 331 00:15:00,200 --> 00:15:01,640 Então, eu estou indo para mover lá em um segundo. 332 00:15:01,640 --> 00:15:06,030 >> Mas se eu queria verificar o que simples texto que igualou nesse particular 333 00:15:06,030 --> 00:15:07,760 caso, eu acho que deveria ser o quê? 334 00:15:07,760 --> 00:15:10,980 O que deve texto simples eu igualar neste primeira rodada através do loop for? 335 00:15:10,980 --> 00:15:14,046 336 00:15:14,046 --> 00:15:15,110 >> ALUNO: Zero? 337 00:15:15,110 --> 00:15:16,510 >> JASON HIRSCHHORN: Texto simples de I? 338 00:15:16,510 --> 00:15:21,180 Por isso, deve ser de capital B. I, é claro, é igual a zero, mas de texto simples 339 00:15:21,180 --> 00:15:25,600 suporte de zero suporte fechado é igual a B porque cordas, como vimos na semana passada, 340 00:15:25,600 --> 00:15:28,650 são array, por isso estamos recebendo o primeiro caractere a partir daí. 341 00:15:28,650 --> 00:15:34,960 Então, novamente, se eu impressos texto simples Eu, eu, de fato, obter o caractere 342 00:15:34,960 --> 00:15:36,560 B. E isso é puro, certo? 343 00:15:36,560 --> 00:15:40,380 Eu realmente não tiver texto simples I. Isso não é uma das variáveis ​​que estabeleci 344 00:15:40,380 --> 00:15:42,950 ou inicializado, mas você pode imprimir toda uma série de coisas 345 00:15:42,950 --> 00:15:45,640 se você gostaria. 346 00:15:45,640 --> 00:15:47,340 >> Mas vamos percorrer. 347 00:15:47,340 --> 00:15:50,050 Se o texto simples que é maior do que um e texto simples que é inferior ou igual a 348 00:15:50,050 --> 00:15:53,290 Z, que claramente é verdade, porque nós temos um capital B. Eu vou correr 349 00:15:53,290 --> 00:15:54,230 algum comando sobre ele. 350 00:15:54,230 --> 00:15:58,530 Vimos que a matemática, na semana passada, por isso vamos é um dado adquirido que ele funciona 351 00:15:58,530 --> 00:16:00,900 direito de acordo com Confira 50. 352 00:16:00,900 --> 00:16:03,720 >> Estas chaves, o primeiro mostrou que eu estava saindo do caso 353 00:16:03,720 --> 00:16:07,030 condição, o segundo mostrou que eu estou saindo do loop for. 354 00:16:07,030 --> 00:16:10,400 E agora quando eu bati A seguir, vamos ver estamos de volta no loop novamente. 355 00:16:10,400 --> 00:16:11,970 Estamos atravessando o loop novamente. 356 00:16:11,970 --> 00:16:18,110 Vamos realmente entrar na segunda iteração do loop e tipo 357 00:16:18,110 --> 00:16:20,520 Informações locais. 358 00:16:20,520 --> 00:16:22,190 >> Então, nós estamos na segunda iteração do nosso loop for. 359 00:16:22,190 --> 00:16:24,530 I é igual a 1, o que esperamos. 360 00:16:24,530 --> 00:16:26,650 N é igual a 6, o que esperamos. 361 00:16:26,650 --> 00:16:28,810 Chave é igual a 3, o que esperamos. 362 00:16:28,810 --> 00:16:32,625 E de texto simples, você vai ver, é igual a EARFOO agora, não mais porque BARFOO 363 00:16:32,625 --> 00:16:37,930 no nosso iteração anterior, o B foi alterado para um capital E. Então, nós estamos sobre 364 00:16:37,930 --> 00:16:40,040 para encontrar o problema, de modo que este é o lugar onde nós estamos indo 365 00:16:40,040 --> 00:16:41,130 mergulhar na depuração. 366 00:16:41,130 --> 00:16:43,365 Mas alguém tem alguma dúvida sobre o que temos feito até agora? 367 00:16:43,365 --> 00:16:46,770 368 00:16:46,770 --> 00:16:47,910 Fantástico. 369 00:16:47,910 --> 00:16:52,710 >> Então, nós estamos prestes a executar este se condição, suporte de texto simples Fechei 370 00:16:52,710 --> 00:16:57,500 suporte maior do que A e texto simples I inferior ou igual a Z. Mas antes 371 00:16:57,500 --> 00:17:00,450 Eu vou entrar nisso, porque é onde Eu sei que meu erro é que eu quero apontar 372 00:17:00,450 --> 00:17:06,859 fora de texto simples de I. Assim, vamos colocar impressão. 373 00:17:06,859 --> 00:17:12,020 Ele faz igual a um personagem, de modo que parece até agora, tudo está bem e bom. 374 00:17:12,020 --> 00:17:14,740 >> Então, eu espero que esta linha por minha lógica, esta linha deve ser verdadeira. 375 00:17:14,740 --> 00:17:16,099 É uma letra maiúscula. 376 00:17:16,099 --> 00:17:20,599 Mas se eu acertar n, nós percebemos que este linha, de fato, não foi executada. 377 00:17:20,599 --> 00:17:22,609 Eu pulei até o else if. 378 00:17:22,609 --> 00:17:25,460 Por que isso aconteceu? 379 00:17:25,460 --> 00:17:27,480 >> ALUNO: Porque você tem a sua condição de texto simples é maior 380 00:17:27,480 --> 00:17:29,130 do que A, não é igual ou maior do que. 381 00:17:29,130 --> 00:17:32,260 >> JASON HIRSCHHORN: Então, eu tinha o meu texto simples I é maior do que A, não maior 382 00:17:32,260 --> 00:17:32,850 que ou igual a. 383 00:17:32,850 --> 00:17:38,130 Então, claramente, a capital A não desencadear esta condição se, e nós fizemos 384 00:17:38,130 --> 00:17:40,520 não entrar nele, e nós fizemos não fazer a mudança necessária. 385 00:17:40,520 --> 00:17:41,360 Então é isso, na verdade. 386 00:17:41,360 --> 00:17:42,920 Eu descobri o meu erro. 387 00:17:42,920 --> 00:17:46,775 Eu pudesse voltar no meu arquivo de origem, mudá-lo, e atualizá-lo e 388 00:17:46,775 --> 00:17:47,855 executar Confira 50 novamente. 389 00:17:47,855 --> 00:17:52,590 >> Mas vamos ver, apenas por pedagogia de bem, se eu continuar. 390 00:17:52,590 --> 00:17:59,580 O outro se não executar qualquer um, mas o que equivale a vez é o comando 391 00:17:59,580 --> 00:18:00,500 que não muda. 392 00:18:00,500 --> 00:18:04,840 Por isso, não mudou em tudo, e se eu imprimir texto puro aqui, vamos ver indo 393 00:18:04,840 --> 00:18:08,250 através desse laço for não, na verdade, mudar esse segundo personagem em tudo. 394 00:18:08,250 --> 00:18:09,600 É ainda um capital A. 395 00:18:09,600 --> 00:18:12,690 >> Então, novamente, nós depurado nosso erro. 396 00:18:12,690 --> 00:18:17,380 Percebemos que não havia alguma lógica em falta. 397 00:18:17,380 --> 00:18:20,590 E nós depurado-lo antes do tempo antes realmente executar essa linha, 398 00:18:20,590 --> 00:18:24,320 mas você teria notado se tivéssemos apenas Em seguida bater e saltar para que else if, 399 00:18:24,320 --> 00:18:26,710 isso significa que que se a condição não era verdade. 400 00:18:26,710 --> 00:18:29,550 Nós não, na verdade, obter o resultado que esperávamos. 401 00:18:29,550 --> 00:18:33,240 Então nós poderia ter sido solicitado, teve não foram tão astuto, a olhar para 402 00:18:33,240 --> 00:18:38,510 que se a condição e verificar se, de fato, nossa condição deve avaliar a 403 00:18:38,510 --> 00:18:41,150 verdade no contexto atual. 404 00:18:41,150 --> 00:18:42,880 >> Isso é tudo para a depuração deste programa. 405 00:18:42,880 --> 00:18:45,340 Alguém tem alguma dúvida? 406 00:18:45,340 --> 00:18:50,486 O comando que eu poderia bater para sair GDB? 407 00:18:50,486 --> 00:18:53,900 Q. E então eu vou ser solicitado, sair de qualquer maneira? 408 00:18:53,900 --> 00:18:54,390 Sim ou não. 409 00:18:54,390 --> 00:18:58,440 Eu vou bater sim, e eu vou ter desistido GDB. 410 00:18:58,440 --> 00:19:00,860 >> Então isso foi um primer rápido para GDB. 411 00:19:00,860 --> 00:19:03,430 Na verdade, em um cenário real, Eu fiz isso em horário de expediente. 412 00:19:03,430 --> 00:19:06,710 Eu GDBed este programa exato em horário de expediente com um estudante. 413 00:19:06,710 --> 00:19:12,410 E se voltar para os comandos que vimos antes, usamos ruptura principal, em primeiro lugar 414 00:19:12,410 --> 00:19:13,190 coisa que fizemos. 415 00:19:13,190 --> 00:19:16,060 Nós costumávamos correr com argumentos de linha de comando, segunda coisa que fizemos. 416 00:19:16,060 --> 00:19:18,520 Usamos muito próximo de se mover nós através de linhas. 417 00:19:18,520 --> 00:19:20,310 E, novamente, a versão curta de seguida é n. 418 00:19:20,310 --> 00:19:22,920 Isso é entre parênteses em cinza no slide. 419 00:19:22,920 --> 00:19:28,590 >> Nós não utilizar o passo, mas não o fizemos necessariamente precisa para este caso. 420 00:19:28,590 --> 00:19:32,150 Mas podemos usá-lo em um pouco mais tarde hoje se está depurando, por 421 00:19:32,150 --> 00:19:36,500 exemplo, busca binária quando binário pesquisa é chamado em um separado 422 00:19:36,500 --> 00:19:38,200 função, mas não há algum erro com ele. 423 00:19:38,200 --> 00:19:40,440 Nós vamos querer entrar a chamada para busca binária e 424 00:19:40,440 --> 00:19:41,840 realmente depurá-lo. 425 00:19:41,840 --> 00:19:45,130 Lista que não use, porque tivemos um bom senso de nosso código, mas se eu 426 00:19:45,130 --> 00:19:48,420 queria ter uma noção do código que eu estava por perto, eu poderia apenas lista usar. 427 00:19:48,420 --> 00:19:50,310 >> Imprimir usamos, informações locais que usamos. 428 00:19:50,310 --> 00:19:53,260 Continuar nós não precisamos usar neste caso, também não é preciso usar 429 00:19:53,260 --> 00:19:55,060 desativar, mas fizemos uso desistir. 430 00:19:55,060 --> 00:19:57,850 Mais uma vez, estes 10 mandamentos, praticá-los. 431 00:19:57,850 --> 00:20:00,770 Se você entender esses 10 mandamentos, você deve ser definido para a depuração de qualquer 432 00:20:00,770 --> 00:20:02,525 Problema com GDB. 433 00:20:02,525 --> 00:20:05,230 434 00:20:05,230 --> 00:20:08,420 >> Então, nós estamos prestes a ir, de novo, para o cerne da seção de hoje, passando por cima 435 00:20:08,420 --> 00:20:09,720 estes classificação e pesquisa algoritmos. 436 00:20:09,720 --> 00:20:14,075 Antes de fazê-lo, mais uma vez, todas as perguntas, comentários, preocupações para GDB? 437 00:20:14,075 --> 00:20:16,750 438 00:20:16,750 --> 00:20:20,960 Então está todo mundo vai usar GDB em vez de printf? 439 00:20:20,960 --> 00:20:24,550 Então todo mundo, pelo amor de perpetuidade, todo mundo está balançando a cabeça direita 440 00:20:24,550 --> 00:20:27,400 agora, então eu vou te ver no horário de expediente e todos os TFs vai vê-lo e 441 00:20:27,400 --> 00:20:29,460 eles vão dizer, me mostrar como usar GDB, e você vai ser capaz 442 00:20:29,460 --> 00:20:31,240 para mostrá-los, certo? 443 00:20:31,240 --> 00:20:31,760 Mais ou menos? 444 00:20:31,760 --> 00:20:32,640 Talvez eu espero. 445 00:20:32,640 --> 00:20:33,670 Legal. 446 00:20:33,670 --> 00:20:35,790 >> Então vamos passar para classificação e pesquisa. 447 00:20:35,790 --> 00:20:40,710 Você vai ver que eu tenho uma lista já classificadas para nós, mas que não vai 448 00:20:40,710 --> 00:20:42,220 ser o caso sempre. 449 00:20:42,220 --> 00:20:49,170 Assim, no problema de especificação definida para conjunto de problemas de três, você tem calções 450 00:20:49,170 --> 00:20:51,410 que você pode assistir, e ele realmente pede-lhe para ver os calções. 451 00:20:51,410 --> 00:20:55,090 Também em palestra na semana passada, fomos muitos desses algoritmos, por isso estou 452 00:20:55,090 --> 00:20:59,150 não vai passar o tempo na sala de aula vai sobre estes algoritmos novamente ou desenho 453 00:20:59,150 --> 00:21:01,130 fotos de como estes algoritmos funcionam. 454 00:21:01,130 --> 00:21:04,030 Mais uma vez, essa informação você pode re-relógio palestra, ou que as informações 455 00:21:04,030 --> 00:21:08,570 é capturado excepcionalmente nos calções para essas pesquisas, todas 456 00:21:08,570 --> 00:21:10,920 que estão disponíveis em cs50.net. 457 00:21:10,920 --> 00:21:14,200 >> Então, em vez disso, o que nós vamos fazer é escrever esses programas. 458 00:21:14,200 --> 00:21:18,190 Nós temos um sentido, um modelo mental, de como eles trabalham, e assim o que vamos 459 00:21:18,190 --> 00:21:20,210 fazer é codificá-las de verdade. 460 00:21:20,210 --> 00:21:23,430 Vamos transformar esse modelo mental, essa imagem, se quiser, para o 461 00:21:23,430 --> 00:21:24,960 código real. 462 00:21:24,960 --> 00:21:28,460 E se você fosse um pouco confuso ou nebuloso sobre o modelo mental, eu totalmente 463 00:21:28,460 --> 00:21:28,770 entender. 464 00:21:28,770 --> 00:21:30,540 >> Nós não estamos indo realmente para saltar para o código imediatamente. 465 00:21:30,540 --> 00:21:36,030 Assim, enquanto este pedido neste slide pergunta você codificar busca binária, e 466 00:21:36,030 --> 00:21:39,470 na verdade, uma versão interativa de busca binária, a primeira coisa que eu 467 00:21:39,470 --> 00:21:42,370 realmente quero que você faça é escrever um pseudocódigo. 468 00:21:42,370 --> 00:21:47,020 Então, você tem esse modelo mental de como funciona a busca binária. 469 00:21:47,020 --> 00:21:50,060 Pegue uma folha de papel se você tiver um prontamente disponível, ou abrir uma 470 00:21:50,060 --> 00:21:52,520 editor de texto, e eu gostaria todo mundo para escrever. 471 00:21:52,520 --> 00:21:57,470 Tomar quatro minutos para escrever a pseudocódigo para a busca binária. 472 00:21:57,470 --> 00:21:58,990 >> Mais uma vez, pensar sobre esse modelo mental. 473 00:21:58,990 --> 00:22:01,980 Eu virei ao redor se você tiver dúvidas e nós podemos desenhar a imagem para fora. 474 00:22:01,980 --> 00:22:06,220 Mas em primeiro lugar, antes de começar a programação, Eu gostaria de escrever a 475 00:22:06,220 --> 00:22:09,920 pseudocódigo para busca binária então quando nós mergulhar, temos alguma direção que 476 00:22:09,920 --> 00:22:12,110 para onde devemos ir. 477 00:22:12,110 --> 00:22:15,330 >> ESTUDANTE: Podemos assumir a matriz de valores que recebemos já estão classificados? 478 00:22:15,330 --> 00:22:17,960 >> JASON HIRSCHHORN: Então por busca binária para o trabalho - excelente pergunta - você 479 00:22:17,960 --> 00:22:20,970 tem que levar em um ordenado matriz de valores. 480 00:22:20,970 --> 00:22:22,290 Então suponho que vai funcionar. 481 00:22:22,290 --> 00:22:23,480 Nós vamos voltar a este slide. 482 00:22:23,480 --> 00:22:27,220 Você verá em roxo a função declaração é bool binary_search int 483 00:22:27,220 --> 00:22:29,230 valor, valores int, int n. 484 00:22:29,230 --> 00:22:32,910 Este deve ser familiar se você tiver já se aproximou ou obtido o seu 485 00:22:32,910 --> 00:22:34,580 as mãos sujas com o conjunto de problemas. 486 00:22:34,580 --> 00:22:35,910 >> Mas essa é a sua declaração da função. 487 00:22:35,910 --> 00:22:39,080 Mais uma vez, não precisa se preocupar com tanto neste momento. 488 00:22:39,080 --> 00:22:43,660 O que eu realmente quero que você a fazer é tomar quatro minutos para binário pseudocódigo 489 00:22:43,660 --> 00:22:46,380 pesquisar, e depois vamos mais de que, como um grupo. 490 00:22:46,380 --> 00:22:47,500 E eu vou chegar perto. 491 00:22:47,500 --> 00:22:49,590 Se você tem perguntas, sinta livre para levantar sua mão. 492 00:22:49,590 --> 00:25:07,110 493 00:25:07,110 --> 00:25:09,680 >> Por que você não tomar mais de dois minutos para terminar o pseudocódigo? 494 00:25:09,680 --> 00:25:13,690 495 00:25:13,690 --> 00:25:15,820 Eu sei que isto pode parecer ridículo que estamos gastando tanto tempo com 496 00:25:15,820 --> 00:25:20,350 algo que não é verdade, mesmo em C, mas especialmente para estes mais 497 00:25:20,350 --> 00:25:24,030 algoritmos desafiadoras e problema conjuntos que temos de descobrir, 498 00:25:24,030 --> 00:25:27,210 começando em pseudocódigo não se preocupando sobre a sintaxe, apenas se preocupar com 499 00:25:27,210 --> 00:25:29,150 a lógica, é incrivelmente útil. 500 00:25:29,150 --> 00:25:32,720 E dessa forma, você não está resolvendo dois problemas extremamente difíceis ao mesmo tempo. 501 00:25:32,720 --> 00:25:35,390 Você está apenas se concentrar na lógica, e então você se move para a sintaxe. 502 00:25:35,390 --> 00:25:59,960 503 00:25:59,960 --> 00:26:01,385 >> OK. 504 00:26:01,385 --> 00:26:03,680 Vamos começar passando o pseudocódigo. 505 00:26:03,680 --> 00:26:05,380 Já escrevi aqui em cima, binário Pesquisa pseudocódigo. 506 00:26:05,380 --> 00:26:07,360 Vamos escrever isso na embarcar juntos. 507 00:26:07,360 --> 00:26:10,040 Ou eu vou escrevê-lo e você vai dar me as instruções que eu preciso. 508 00:26:10,040 --> 00:26:15,010 Então, alguém pode me dar o primeiro linha do pseudocódigo você 509 00:26:15,010 --> 00:26:18,350 escreveu para busca binária? 510 00:26:18,350 --> 00:26:20,258 Sim, Annie? 511 00:26:20,258 --> 00:26:22,698 >> ALUNO: Enquanto o comprimento do lista é maior do que zero. 512 00:26:22,698 --> 00:26:26,114 513 00:26:26,114 --> 00:26:34,880 >> JASON HIRSCHHORN: Enquanto comprimento de uma lista maior do que zero. 514 00:26:34,880 --> 00:26:38,810 E mais uma vez, vemos alguns C-looking sintáticas coisas aqui. 515 00:26:38,810 --> 00:26:41,550 Mas a maior parte desta está em Inglês. 516 00:26:41,550 --> 00:26:43,980 Alguém tem alguma linha puseram antes disso em sua pseudo-código? 517 00:26:43,980 --> 00:26:47,280 518 00:26:47,280 --> 00:26:50,210 >> ESTUDANTE: Obter uma matriz classificados de números. 519 00:26:50,210 --> 00:26:53,600 >> JASON HIRSCHHORN: Você escreveu: "ter uma matriz de números ordenados. "Per o 520 00:26:53,600 --> 00:26:56,140 declaração da função, estaremos passando uma matriz de números ordenados. 521 00:26:56,140 --> 00:26:57,280 >> Estudante: [inaudível]. 522 00:26:57,280 --> 00:26:59,030 >> JASON HIRSCHHORN: Então teremos isso. 523 00:26:59,030 --> 00:27:01,820 Mas sim, se nós não temos isso, nós seria necessário para ordenar a nossa gama de 524 00:27:01,820 --> 00:27:04,850 números, porque de busca binária só funciona em matrizes ordenada. 525 00:27:04,850 --> 00:27:11,300 Assim, enquanto o comprimento da lista é igual a zero, eu sou indo para colocar em algumas chaves 526 00:27:11,300 --> 00:27:15,420 para torná-la um pouco mais como C. Mas enquanto, parece ser mapeado para uma 527 00:27:15,420 --> 00:27:19,550 while, para que dentro deste tempo loop de que precisamos para 528 00:27:19,550 --> 00:27:22,000 fazer por busca binária? 529 00:27:22,000 --> 00:27:25,530 >> Alguém que não tenha me dado um responder ainda, mas quem escreveu isso? 530 00:27:25,530 --> 00:27:31,750 531 00:27:31,750 --> 00:27:33,320 >> ESTUDANTE: Vá para o meio da lista. 532 00:27:33,320 --> 00:27:33,980 >> JASON HIRSCHHORN: Tom. 533 00:27:33,980 --> 00:27:35,230 Ir para o meio da lista. 534 00:27:35,230 --> 00:27:43,290 535 00:27:43,290 --> 00:27:45,530 E a pergunta follow-up, o que fazemos uma vez que estamos no 536 00:27:45,530 --> 00:27:46,870 meio da lista? 537 00:27:46,870 --> 00:27:49,310 >> ALUNO: Faça uma verificação se isso é o número que você está procurando. 538 00:27:49,310 --> 00:27:50,120 >> JASON HIRSCHHORN: Excelente. 539 00:27:50,120 --> 00:28:05,500 Vá a meio da lista e verifique se o nosso valor está lá - 540 00:28:05,500 --> 00:28:06,515 fantástico. 541 00:28:06,515 --> 00:28:10,460 Alguém tem mais alguma coisa que era diferente do que isso? 542 00:28:10,460 --> 00:28:11,210 Isto é exatamente correto. 543 00:28:11,210 --> 00:28:13,800 >> A primeira coisa que fazemos em busca binária é ir para o meio da lista e 544 00:28:13,800 --> 00:28:15,870 verificar para ver se o nosso valor está lá. 545 00:28:15,870 --> 00:28:19,682 Então eu suponho que se nosso valor é lá, o que vamos fazer? 546 00:28:19,682 --> 00:28:21,610 >> ALUNO: Nós retornar zero [inaudível]. 547 00:28:21,610 --> 00:28:23,400 >> JASON HIRSCHHORN: Sim, se a nossa valor está lá, nós a encontramos. 548 00:28:23,400 --> 00:28:27,950 Assim, podemos dizer alguma forma, no entanto, este função é definida, nós dizemos que o usuário 549 00:28:27,950 --> 00:28:28,520 que encontraram. 550 00:28:28,520 --> 00:28:30,950 Se ele não estiver lá, porém, que é onde isso fica complicado. 551 00:28:30,950 --> 00:28:35,120 Então, se ele não estiver lá, alguém que estava trabalhando em busca binária ou 552 00:28:35,120 --> 00:28:36,830 tem uma idéia, agora, o que vamos fazer? 553 00:28:36,830 --> 00:28:37,830 >> ALUNO: Pergunta. 554 00:28:37,830 --> 00:28:38,100 >> JASON HIRSCHHORN: Sim? 555 00:28:38,100 --> 00:28:39,920 >> ALUNO: É a matriz já classificadas? 556 00:28:39,920 --> 00:28:42,200 >> JASON HIRSCHHORN: Sim, nós estamos assumindo a matriz já está classificada. 557 00:28:42,200 --> 00:28:46,480 >> ALUNO: Então você tem que verificar se o valor que você vê é maior do que 558 00:28:46,480 --> 00:28:51,745 o valor que você quiser, você pode mover-se para o meio da outra metade. 559 00:28:51,745 --> 00:28:54,110 >> JASON HIRSCHHORN: Então, se o meio de a lista é maior do que o que estamos 560 00:28:54,110 --> 00:28:57,440 procurando, então nós fazemos o que? 561 00:28:57,440 --> 00:28:58,320 Nós nos movemos para onde? 562 00:28:58,320 --> 00:29:01,400 >> ALUNO: Você quer se mudar para a metade da lista com 563 00:29:01,400 --> 00:29:02,780 Números mais baixos do que a. 564 00:29:02,780 --> 00:29:04,460 >> JASON HIRSCHHORN: Então nós vamos chama isso de esquerda. 565 00:29:04,460 --> 00:29:15,435 Então, se meio é maior, podemos pesquisar a metade esquerda da lista. 566 00:29:15,435 --> 00:29:20,620 567 00:29:20,620 --> 00:29:22,980 E, em seguida, por meio de busca, o que quero dizer com pesquisa? 568 00:29:22,980 --> 00:29:24,010 >> Estudante: [inaudível]. 569 00:29:24,010 --> 00:29:24,410 >> JASON HIRSCHHORN: Vamos para o meio. 570 00:29:24,410 --> 00:29:25,740 Nós realmente repetir isso. 571 00:29:25,740 --> 00:29:29,210 Voltamos através do nosso loop while. 572 00:29:29,210 --> 00:29:31,480 Eu vou dar-lhe o último - 573 00:29:31,480 --> 00:29:39,047 então, se, meio é menos do que o que o que fazemos, o que fazemos aqui? 574 00:29:39,047 --> 00:29:40,360 >> ALUNO: Vá para a direita. 575 00:29:40,360 --> 00:29:41,610 >> JASON HIRSCHHORN: Busca à direita. 576 00:29:41,610 --> 00:29:47,440 577 00:29:47,440 --> 00:29:51,710 Este parece ser bom, mas alguém tem qualquer coisa que pode estar faltando ou 578 00:29:51,710 --> 00:29:53,200 qualquer outra coisa que você colocar no seu pseudo-código? 579 00:29:53,200 --> 00:29:57,080 580 00:29:57,080 --> 00:29:58,410 Então, isso é o que temos até agora. 581 00:29:58,410 --> 00:30:00,960 Enquanto que o comprimento da lista é maior que zero, nós estamos indo para ir 582 00:30:00,960 --> 00:30:03,220 para o meio da lista e verificar se o nosso valor está lá. 583 00:30:03,220 --> 00:30:06,970 >> Se o meio é maior, nós vamos procurar à esquerda, mais se o meio é 584 00:30:06,970 --> 00:30:09,230 menos, vamos pesquisar a direita. 585 00:30:09,230 --> 00:30:14,430 Então, todos nós tivemos alguma familiaridade com os termos que usamos em ciência da computação 586 00:30:14,430 --> 00:30:15,550 e as ferramentas que temos. 587 00:30:15,550 --> 00:30:18,300 Mas você já vai notar que estávamos falar em Inglês, mas encontramos um 588 00:30:18,300 --> 00:30:24,790 monte de coisas que pareciam mapear para ferramentas que temos em nosso kit de ferramentas de codificação. 589 00:30:24,790 --> 00:30:27,210 Então, logo de cara, não estamos vai realmente codificar ainda. 590 00:30:27,210 --> 00:30:33,300 >> O que vemos aqui em Inglês que os mapas para coisas que podemos escrever em C? 591 00:30:33,300 --> 00:30:34,560 >> ALUNO: While. 592 00:30:34,560 --> 00:30:35,320 >> JASON HIRSCHHORN: While. 593 00:30:35,320 --> 00:30:40,610 Portanto, este tempo aqui mapas sobre o que? 594 00:30:40,610 --> 00:30:42,630 >> ESTUDANTE: Um loop while. 595 00:30:42,630 --> 00:30:43,200 >> JASON HIRSCHHORN: Um loop while? 596 00:30:43,200 --> 00:30:44,540 Ou, provavelmente, mais geralmente, um ciclo. 597 00:30:44,540 --> 00:30:46,260 Queremos fazer algo mais e mais. 598 00:30:46,260 --> 00:30:49,050 Então, nós estamos indo para codificar um loop. 599 00:30:49,050 --> 00:30:51,640 E já sabemos, porque nós fizemos isso um par de vezes e nós 600 00:30:51,640 --> 00:30:54,180 temos muitos exemplos por aí, como realmente de escrever 601 00:30:54,180 --> 00:30:55,310 este índice para um loop. 602 00:30:55,310 --> 00:30:56,160 Então isso deve ser muito fácil. 603 00:30:56,160 --> 00:30:58,070 Devemos ser capazes de obter essa começou muito rapidamente. 604 00:30:58,070 --> 00:31:01,830 >> O que mais vemos aqui? 605 00:31:01,830 --> 00:31:06,820 Que outras estruturas sintaxes, as coisas que estamos familiarizados com a C, que nós 606 00:31:06,820 --> 00:31:09,790 já tem um sentido de com base fora das palavras que usamos? 607 00:31:09,790 --> 00:31:10,830 Sim, Anna? 608 00:31:10,830 --> 00:31:11,360 [Inaudível] 609 00:31:11,360 --> 00:31:12,990 apenas brincando. 610 00:31:12,990 --> 00:31:13,540 Anna, vá em frente. 611 00:31:13,540 --> 00:31:14,530 >> ALUNO: Se e mais. 612 00:31:14,530 --> 00:31:16,260 >> JASON HIRSCHHORN: Se e mais - bem aqui. 613 00:31:16,260 --> 00:31:18,840 Então, o que aqueles se parece? 614 00:31:18,840 --> 00:31:20,420 >> ALUNO: Uma instrução if else. 615 00:31:20,420 --> 00:31:21,560 >> JASON HIRSCHHORN: Sim, condições, certo? 616 00:31:21,560 --> 00:31:24,650 Por isso, provavelmente vai precisar escrever algumas condições. 617 00:31:24,650 --> 00:31:31,185 E, novamente, embora talvez confuso no em primeiro lugar, nós geralmente têm um sentido agora 618 00:31:31,185 --> 00:31:34,010 de como escrever as condições e a sintaxe para as condições. 619 00:31:34,010 --> 00:31:36,850 E se não o fizermos, nós só procurar o sintaxe para condições, cortar e colar 620 00:31:36,850 --> 00:31:39,950 isso, porque sabemos que precisamos aqui uma condição. 621 00:31:39,950 --> 00:31:44,910 Quaisquer outras coisas que vemos que o mapa em coisas que talvez você precise fazer em C? 622 00:31:44,910 --> 00:31:48,312 623 00:31:48,312 --> 00:31:48,960 Sim, Aleha? 624 00:31:48,960 --> 00:31:50,370 >> ALUNO: Isso pode ser óbvio, apenas verificar se um 625 00:31:50,370 --> 00:31:51,990 valor é igual a alguma coisa. 626 00:31:51,990 --> 00:31:54,578 >> JASON HIRSCHHORN: Então, como vamos verificar e - por isso, ir para o meio da lista 627 00:31:54,578 --> 00:31:55,610 e verifique se o nosso valor não é? 628 00:31:55,610 --> 00:31:56,570 Como é que vamos fazer isso em C? 629 00:31:56,570 --> 00:31:58,450 Qual é a sintaxe para isso? 630 00:31:58,450 --> 00:31:59,235 >> ALUNO: Igual, é igual. 631 00:31:59,235 --> 00:32:00,650 >> JASON HIRSCHHORN: Igual, é igual. 632 00:32:00,650 --> 00:32:03,540 Então, esta verificação é provavelmente vai para ser um igual, é igual. 633 00:32:03,540 --> 00:32:04,510 Então, vamos saber que precisamos que em algum lugar. 634 00:32:04,510 --> 00:32:07,510 E, na verdade, apenas a escrevê-lo, vemos essas outras coisas. 635 00:32:07,510 --> 00:32:11,400 Nós vamos ter que fazer alguma operadores de comparação em lá - 636 00:32:11,400 --> 00:32:12,010 fantástico. 637 00:32:12,010 --> 00:32:14,980 Então, ele realmente se parece, por e um grande, não ter escrito 638 00:32:14,980 --> 00:32:16,390 palavra de código C ainda. 639 00:32:16,390 --> 00:32:20,610 Mas nós temos o modelo mental para baixo através de palestras e os shorts. 640 00:32:20,610 --> 00:32:22,350 >> Nós escrevemos pseudo-código como um grupo. 641 00:32:22,350 --> 00:32:27,110 E já temos 80% se não 90% do que precisamos fazer. 642 00:32:27,110 --> 00:32:28,550 Agora, só precisamos de codificar , o que mais uma vez, é um 643 00:32:28,550 --> 00:32:30,110 problema não-trivial para resolver. 644 00:32:30,110 --> 00:32:31,890 Mas pelo menos nós estamos presos na lógica. 645 00:32:31,890 --> 00:32:38,040 Pelo menos agora quando vamos para o horário de expediente, Eu posso dizer, eu sei o que eu preciso 646 00:32:38,040 --> 00:32:40,160 de fazer, mas você pode lembrar me da sintaxe? 647 00:32:40,160 --> 00:32:42,940 Ou mesmo se o horário de expediente estão lotados, você pode Google para a sintaxe, em vez 648 00:32:42,940 --> 00:32:45,040 do que ficar preso na lógica. 649 00:32:45,040 --> 00:32:48,570 >> E, novamente, ao invés de tentar resolver a lógica e os problemas de sintaxe todos 650 00:32:48,570 --> 00:32:51,900 ao mesmo tempo, muitas vezes é muito melhor quebrar esses dois problemas difíceis fora em 651 00:32:51,900 --> 00:32:58,280 dois os mais gerenciáveis ​​e fazer o pseudo-código e, em seguida, primeiro código em C. 652 00:32:58,280 --> 00:33:00,620 Então vamos ver o que eu fiz para o pseudo-código antes do tempo. 653 00:33:00,620 --> 00:33:04,060 >> Enquanto que o comprimento da lista é maior que zero, olhe para o meio 654 00:33:04,060 --> 00:33:05,090 da lista. 655 00:33:05,090 --> 00:33:09,610 Se o número encontrado retorna verdadeiro, caso contrário se o número mais elevado, busca esquerdo. 656 00:33:09,610 --> 00:33:13,200 Else if menor número, pesquisa direita, retornará false. 657 00:33:13,200 --> 00:33:18,710 De modo que parece quase idêntico, se não quase idêntico ao que escreveu. 658 00:33:18,710 --> 00:33:23,030 Na verdade, Tom, o que você disse em primeiro lugar, quebrar no meio da lista, e se 659 00:33:23,030 --> 00:33:24,880 número encontrado em duas instruções é realmente o que eu fiz. 660 00:33:24,880 --> 00:33:25,507 >> Eu combinei-los lá. 661 00:33:25,507 --> 00:33:27,100 Eu deveria ter escutado você pela primeira vez. 662 00:33:27,100 --> 00:33:30,640 Então esse é o pseudo-código que temos. 663 00:33:30,640 --> 00:33:35,060 Se você quiser agora, desculpe, vá De volta ao nosso problema inicial. 664 00:33:35,060 --> 00:33:37,780 Código binary.c Vamos. 665 00:33:37,780 --> 00:33:40,870 Então implementar uma versão interativa de pesquisa binária com a seguinte 666 00:33:40,870 --> 00:33:42,420 declaração da função. 667 00:33:42,420 --> 00:33:44,550 >> E você não precisa copiar -lo ainda. 668 00:33:44,550 --> 00:33:49,470 Na verdade, estou indo para abrir até aqui binary.c. 669 00:33:49,470 --> 00:33:52,880 Portanto, há a declaração da função no meio do ecrã. 670 00:33:52,880 --> 00:33:57,570 E você vai ver que eu tomou o pseudo-código de em meus lados, mas quase idêntico 671 00:33:57,570 --> 00:33:59,740 com o que escreveu, e colocar isso para você. 672 00:33:59,740 --> 00:34:06,010 Então, agora, vamos levar cinco minutos para codificar esta função. 673 00:34:06,010 --> 00:34:08,199 >> E, novamente, se você tiver quaisquer perguntas, levantar a mão, me avise, eu vou 674 00:34:08,199 --> 00:34:08,710 vêm por aí. 675 00:34:08,710 --> 00:34:09,800 >> Estudante: [inaudível]. 676 00:34:09,800 --> 00:34:12,380 >> JASON HIRSCHHORN: Então eu peguei o binário definição de pesquisa no 677 00:34:12,380 --> 00:34:14,429 topo, na linha 12. 678 00:34:14,429 --> 00:34:16,429 Isso é o que eu tenho para o meu slide. 679 00:34:16,429 --> 00:34:20,940 E depois de tudo isso pseudo-código que apenas copie e colei do slide, 680 00:34:20,940 --> 00:34:22,190 slides pseudo-código. 681 00:34:22,190 --> 00:35:22,830 682 00:35:22,830 --> 00:35:26,786 Eu ainda não estou ouvindo [inaudível]. 683 00:35:26,786 --> 00:37:13,010 684 00:37:13,010 --> 00:37:15,820 >> Então, se você tiver terminado o seu implementação, eu quero verificar. 685 00:37:15,820 --> 00:37:19,410 Eu lhe enviou o arquivo Helpers.h anteriormente nesta classe. 686 00:37:19,410 --> 00:37:22,360 E vai estar disponível on-line também para download para as pessoas assistindo 687 00:37:22,360 --> 00:37:24,750 Neste momento secção retardada. 688 00:37:24,750 --> 00:37:29,350 E eu usei apenas a distribuição genérico código de pset3. 689 00:37:29,350 --> 00:37:34,590 Então eu peguei find.C, use meu arquivo Helpers.h em vez do arquivo Helpers.h 690 00:37:34,590 --> 00:37:36,280 que é dada no código de distribuição. 691 00:37:36,280 --> 00:37:39,310 >> E eu tive que fazer uma outra mudança no find.C ao invés de chamar simplesmente 692 00:37:39,310 --> 00:37:42,770 pesquisa, chamada binary_search. 693 00:37:42,770 --> 00:37:49,080 Então, se você quiser testar seu código, sei que isso é como fazê-lo. 694 00:37:49,080 --> 00:37:52,530 Na verdade, quando nós estaremos executando este código agora, eu fiz apenas uma cópia do 695 00:37:52,530 --> 00:37:59,820 meu diretório pset3, mais uma vez, trocados os arquivos de ajudantes e depois fez que 696 00:37:59,820 --> 00:38:04,695 alterar em find.C chamar binary_search , em vez de simplesmente procurar. 697 00:38:04,695 --> 00:40:08,620 698 00:40:08,620 --> 00:40:09,120 >> JASON HIRSCHHORN: sim. 699 00:40:09,120 --> 00:40:11,258 Você tem uma pergunta? 700 00:40:11,258 --> 00:40:12,150 >> ALUNO: de Nevermind. 701 00:40:12,150 --> 00:40:12,600 >> JASON HIRSCHHORN: Não se preocupe. 702 00:40:12,600 --> 00:40:13,370 Bem, vamos começar. 703 00:40:13,370 --> 00:40:15,090 Vamos codificar este como um grupo. 704 00:40:15,090 --> 00:40:16,050 Uma outra nota. 705 00:40:16,050 --> 00:40:20,600 Novamente, isto é, podem ser facilmente trocados no Conjunto de Problemas para três. 706 00:40:20,600 --> 00:40:25,530 Eu tenho o meu arquivo Helpers.h que, em vez que o Helpers.h estamos dado, 707 00:40:25,530 --> 00:40:28,560 declara busca binária, bolha classificar e seleção tipo. 708 00:40:28,560 --> 00:40:37,400 E em find.c você notará on line, o que é isso, a linha 68, que chamamos de binário 709 00:40:37,400 --> 00:40:39,160 pesquisar em vez de pesquisa. 710 00:40:39,160 --> 00:40:42,930 Então, novamente, o código que está disponível on-line ou o código que você está 711 00:40:42,930 --> 00:40:46,590 criando agora podem ser facilmente trocados in para p set 3 para verificá-lo. 712 00:40:46,590 --> 00:40:50,620 >> Mas, primeiro, vamos codificar busca binária. 713 00:40:50,620 --> 00:40:53,690 Nossa declaração de função, retornamos um booleano. 714 00:40:53,690 --> 00:40:55,810 Tomamos um inteiro chamado valor. 715 00:40:55,810 --> 00:40:59,285 Tomamos um array de inteiros chamado valores, e tomamos n ser 716 00:40:59,285 --> 00:41:00,850 o tamanho da matriz. 717 00:41:00,850 --> 00:41:05,640 Na linha 10, aqui, eu tenho afiada incluem stdbool.h. 718 00:41:05,640 --> 00:41:07,360 Alguém sabe por que está lá? 719 00:41:07,360 --> 00:41:12,180 720 00:41:12,180 --> 00:41:16,600 Então, o que essa linha de código faz? 721 00:41:16,600 --> 00:41:19,880 >> ALUNO: Ele permite que você usar um tipo de retorno booleano. 722 00:41:19,880 --> 00:41:20,350 >> JASON HIRSCHHORN: Exatamente. 723 00:41:20,350 --> 00:41:22,300 >> ALUNO: Ou é uma biblioteca que permite a utilização de um tipo de retorno booleano. 724 00:41:22,300 --> 00:41:27,590 >> JASON HIRSCHHORN: Então o forte incluir linha stdbool.h me dá alguma 725 00:41:27,590 --> 00:41:31,340 definições e declarações para coisas que eu estou autorizado a usar em 726 00:41:31,340 --> 00:41:32,400 esta biblioteca. 727 00:41:32,400 --> 00:41:36,570 Assim, entre os que está dizendo que não há este tipo chamado booleano, e que pode ser 728 00:41:36,570 --> 00:41:37,750 verdadeira ou falsa. 729 00:41:37,750 --> 00:41:39,010 Então é isso que essa linha faz. 730 00:41:39,010 --> 00:41:41,680 E se eu não tiver essa linha, eu o faria ficar em apuros para escrever este 731 00:41:41,680 --> 00:41:43,520 palavra certa aqui, bool, ali mesmo. 732 00:41:43,520 --> 00:41:44,140 Exatamente. 733 00:41:44,140 --> 00:41:46,430 Então eu preciso que neste código. 734 00:41:46,430 --> 00:41:47,690 OK. 735 00:41:47,690 --> 00:41:51,860 Portanto, este, de novo, é um iterativo versão, e não uma recursiva. 736 00:41:51,860 --> 00:41:53,820 Por isso, vamos começar. 737 00:41:53,820 --> 00:41:56,200 >> Vamos começar com este primeiro linha de código pseudo. 738 00:41:56,200 --> 00:41:58,770 E espero que, nós - ou não espero. 739 00:41:58,770 --> 00:42:00,530 Nós estamos indo para ir ao redor da sala. 740 00:42:00,530 --> 00:42:05,110 Vamos linha por linha, e eu vou ajudar você descobrir a linha que precisamos 741 00:42:05,110 --> 00:42:06,310 para gravar em primeiro lugar. 742 00:42:06,310 --> 00:42:10,550 Assim, enquanto o comprimento da lista é maior do que zero. 743 00:42:10,550 --> 00:42:12,680 Vamos começar na frente. 744 00:42:12,680 --> 00:42:15,190 Que linha devo escrever aqui, em código? 745 00:42:15,190 --> 00:42:19,470 >> ALUNO: Enquanto parêntese n é maior do que 0. 746 00:42:19,470 --> 00:42:21,900 >> JASON HIRSCHHORN: Enquanto n é grande a 0. 747 00:42:21,900 --> 00:42:26,550 Assim, n é o tamanho de uma lista, e estamos verificando se - 748 00:42:26,550 --> 00:42:26,800 >> [VOZES interpondo] 749 00:42:26,800 --> 00:42:27,660 >> JASON HIRSCHHORN: - Perdão? 750 00:42:27,660 --> 00:42:29,360 >> ESTUDANTE: Como sabemos que n é o tamanho da lista de? 751 00:42:29,360 --> 00:42:29,690 >> JASON HIRSCHHORN: Desculpe. 752 00:42:29,690 --> 00:42:34,690 Por especificação pset, a pesquisa e classificar as funções que você precisa para escrever, 753 00:42:34,690 --> 00:42:36,230 n é o tamanho da lista. 754 00:42:36,230 --> 00:42:37,710 Eu esqueci de explicar isso aqui. 755 00:42:37,710 --> 00:42:41,310 Mas sim. n é o tamanho de lista, neste caso. 756 00:42:41,310 --> 00:42:44,740 Assim, enquanto que n é maior do que 0. 757 00:42:44,740 --> 00:42:45,580 OK. 758 00:42:45,580 --> 00:42:50,090 Isso pode revelar-se um pouco problemático porém, se as coisas continuarem. 759 00:42:50,090 --> 00:42:54,510 Porque vamos continuar a conhecer a Tamanho da lista ao longo deste 760 00:42:54,510 --> 00:43:06,640 função, mas dizer que começar com uma matriz de 5 inteiros. 761 00:43:06,640 --> 00:43:08,950 E nós passamos e temos agora reduzi-lo a 762 00:43:08,950 --> 00:43:10,310 uma matriz de dois inteiros. 763 00:43:10,310 --> 00:43:12,160 Que dois inteiros que é isso? 764 00:43:12,160 --> 00:43:15,895 O tamanho é de 2 agora que queremos olhar, mas que 2 é isso? 765 00:43:15,895 --> 00:43:17,720 Isso faz sentido, essa pergunta? 766 00:43:17,720 --> 00:43:18,020 >> OK. 767 00:43:18,020 --> 00:43:19,120 Vou perguntar de novo. 768 00:43:19,120 --> 00:43:26,640 Então começamos com esse conjunto de 5 inteiros, e n é igual a 5, certo? 769 00:43:26,640 --> 00:43:28,050 Nós vamos passar por aqui. 770 00:43:28,050 --> 00:43:31,560 provavelmente vamos mudar o tamanho, direita, como as coisas continuarem. 771 00:43:31,560 --> 00:43:32,700 Que é o que dizemos que queremos fazer. 772 00:43:32,700 --> 00:43:34,150 Nós não deseja pesquisar a coisa completa novamente. 773 00:43:34,150 --> 00:43:35,480 Então, dizer que mudá-lo para 2. 774 00:43:35,480 --> 00:43:36,970 Levamos metade da lista que é estranho. 775 00:43:36,970 --> 00:43:38,800 Então, basta escolher 2. 776 00:43:38,800 --> 00:43:40,590 Então agora n é igual a 2. 777 00:43:40,590 --> 00:43:42,780 Peço desculpas para os pobres marcadores de apagar a seco. 778 00:43:42,780 --> 00:43:43,080 Certo? 779 00:43:43,080 --> 00:43:45,670 E nós estamos procurando através da lista novamente com uma lista de tamanho 2. 780 00:43:45,670 --> 00:43:48,580 Bem, a nossa disposição ainda é de tamanho 5. 781 00:43:48,580 --> 00:43:51,920 Dizemos que só querem pesquisar 2 pontos na mesma. 782 00:43:51,920 --> 00:43:53,590 Assim que dois pontos são esses? 783 00:43:53,590 --> 00:43:57,640 784 00:43:57,640 --> 00:43:58,815 >> Será que isso faz sentido? 785 00:43:58,815 --> 00:44:00,290 São eles os deixaram dois pontos? 786 00:44:00,290 --> 00:44:01,940 Eles são o direito 2 pontos? 787 00:44:01,940 --> 00:44:03,540 Eles são o Oriente 2 pontos? 788 00:44:03,540 --> 00:44:06,350 Nós quebramos o problema para baixo, mas realmente não sei que parte do 789 00:44:06,350 --> 00:44:11,600 o problema ainda estamos olhando, apenas por ter essas duas variáveis. 790 00:44:11,600 --> 00:44:16,450 Então precisamos de um pouco mais então, enquanto que n é maior do que 0. 791 00:44:16,450 --> 00:44:21,410 Precisamos saber onde esse n está na nossa disposição real. 792 00:44:21,410 --> 00:44:26,660 >> Então, alguém tem um mudar para essa linha? 793 00:44:26,660 --> 00:44:27,970 A maior parte desta linha é perfeitamente correta. 794 00:44:27,970 --> 00:44:29,170 Existe uma outra adição? 795 00:44:29,170 --> 00:44:32,510 Podemos trocar alguma coisa para a n fazer esta linha um pouco melhor? 796 00:44:32,510 --> 00:44:32,865 Mm-hm? 797 00:44:32,865 --> 00:44:38,040 >> ALUNO: Você pode inicializar uma variável como o comprimento de n que vai ser usado 798 00:44:38,040 --> 00:44:39,600 posteriormente a função? 799 00:44:39,600 --> 00:44:42,060 >> JASON HIRSCHHORN: Então inicializar um comprimento variável para n, 800 00:44:42,060 --> 00:44:42,900 e nós usamos isso mais tarde? 801 00:44:42,900 --> 00:44:47,070 Mas, então, apenas atualizar comprimento e nós ainda executar para esse problema em que 802 00:44:47,070 --> 00:44:51,180 reduzir o comprimento do nosso problema, mas nunca se sabe onde, na verdade, 803 00:44:51,180 --> 00:44:52,510 que o comprimento mapeia para. 804 00:44:52,510 --> 00:44:54,790 >> ALUNO: Não é que vai acontecer mais tarde, quando você está dizendo, procure à esquerda, 805 00:44:54,790 --> 00:44:55,746 pesquisar certo? 806 00:44:55,746 --> 00:44:57,640 Você está indo para ir para um diferente área de sua - 807 00:44:57,640 --> 00:44:59,110 >> JASON HIRSCHHORN: Nós estamos indo para ir para uma área, mas como nós sabemos 808 00:44:59,110 --> 00:45:01,150 que devem ir? 809 00:45:01,150 --> 00:45:03,800 Se só temos a matriz e este n, como é que vamos saber onde 810 00:45:03,800 --> 00:45:05,050 ir para a matriz. 811 00:45:05,050 --> 00:45:05,900 Na parte de trás, não é? 812 00:45:05,900 --> 00:45:07,507 >> ALUNO: Você tem, assim, um menor amarrado e uma variável de limite superior ou 813 00:45:07,507 --> 00:45:08,586 uma coisa dessas? 814 00:45:08,586 --> 00:45:09,060 >> JASON HIRSCHHORN: OK. 815 00:45:09,060 --> 00:45:10,780 Portanto, esta é uma outra idéia. 816 00:45:10,780 --> 00:45:13,490 Ao invés de apenas manter o controle da tamanho, nós manter o controle do mais baixo e 817 00:45:13,490 --> 00:45:14,770 variável limite superior. 818 00:45:14,770 --> 00:45:17,840 Então, como podemos calcular o tamanho da um limite superior e limite inferior? 819 00:45:17,840 --> 00:45:18,520 >> [VOZES interpondo] 820 00:45:18,520 --> 00:45:19,710 >> JASON HIRSCHHORN: Subtração. 821 00:45:19,710 --> 00:45:23,650 E também manter o controle de quanto menor amarrado e limite superior para que possamos saber, 822 00:45:23,650 --> 00:45:26,215 estamos buscando esses dois? 823 00:45:26,215 --> 00:45:28,220 Estamos buscando esses dois aqui? 824 00:45:28,220 --> 00:45:29,540 Estamos procurando os dois meio? 825 00:45:29,540 --> 00:45:32,810 Provavelmente não os dois do meio, porque isto, na verdade, é de pesquisa binária. 826 00:45:32,810 --> 00:45:37,320 Mas agora nós vamos ser capazes de obter o tamanho, mas também os limites da matriz. 827 00:45:37,320 --> 00:45:40,020 Em essência, se temos o nosso gigante livro de telefone, nós rasgá-lo ao meio. 828 00:45:40,020 --> 00:45:42,990 Agora sabemos onde esse menor livro de telefone é. 829 00:45:42,990 --> 00:45:45,260 Mas nós não estamos realmente rasgando o livro de telefone pela metade. 830 00:45:45,260 --> 00:45:48,570 Nós ainda precisamos de saber onde o novos limites de nosso problema. 831 00:45:48,570 --> 00:45:51,645 Alguém tem alguma dúvida sobre isso? 832 00:45:51,645 --> 00:45:52,440 Sim? 833 00:45:52,440 --> 00:45:56,020 >> ALUNO: Será que funciona através da criação de um variável, i, que depois é só mudar 834 00:45:56,020 --> 00:46:00,770 a posição da i em relação ao seu posição actual, e o comprimento, n? 835 00:46:00,770 --> 00:46:01,710 >> JASON HIRSCHHORN: E o que é que eu? 836 00:46:01,710 --> 00:46:04,110 >> ESTUDANTE: Como eu ser como uma espécie de - 837 00:46:04,110 --> 00:46:08,040 Como você inicializar i para ser o posição central da matriz. 838 00:46:08,040 --> 00:46:12,540 E então, se o valor na posição i em no meio da matriz in encontrado para 839 00:46:12,540 --> 00:46:17,870 ser menor que o valor que você precisa, eu agora torna-se o comprimento da matriz, além 840 00:46:17,870 --> 00:46:19,215 o valor de i dividido por 2. 841 00:46:19,215 --> 00:46:20,270 Como, veja, você muda i - 842 00:46:20,270 --> 00:46:20,770 >> JASON HIRSCHHORN: Certo. 843 00:46:20,770 --> 00:46:21,165 >> ALUNO: - até o - 844 00:46:21,165 --> 00:46:24,010 >> JASON HIRSCHHORN: Então, eu estou quase positivo que vai funcionar. 845 00:46:24,010 --> 00:46:26,800 Mas o ponto é, você precisa de dois pedaços de informação aqui. 846 00:46:26,800 --> 00:46:30,050 Você pode fazê-lo com início e fim, ou você pode fazê-lo com tamanho e, em seguida, 847 00:46:30,050 --> 00:46:31,060 algum marcador. 848 00:46:31,060 --> 00:46:32,630 Mas você precisa de duas peças de informações aqui. 849 00:46:32,630 --> 00:46:34,160 Você não pode ficar com apenas um. 850 00:46:34,160 --> 00:46:35,830 Será que isso faz sentido? 851 00:46:35,830 --> 00:46:39,560 >> Então, vamos passar, e vamos fazer [inaudível] 852 00:46:39,560 --> 00:46:41,330 e criar alguns marcadores. 853 00:46:41,330 --> 00:46:42,690 Então o que você escreve no seu código? 854 00:46:42,690 --> 00:46:46,190 >> ALUNO: Eu só disse int limite é igual a 0. 855 00:46:46,190 --> 00:46:47,790 >> JASON HIRSCHHORN: Vamos chamar que int, começando. 856 00:46:47,790 --> 00:46:49,140 >> ALUNO: OK. 857 00:46:49,140 --> 00:46:50,590 >> JASON HIRSCHHORN: Isso faz mais sentido para mim. 858 00:46:50,590 --> 00:46:51,670 E? 859 00:46:51,670 --> 00:46:54,340 >> ALUNO: Eu disse, eu acho, int fim. 860 00:46:54,340 --> 00:46:55,870 >> JASON HIRSCHHORN: int fim. 861 00:46:55,870 --> 00:46:57,640 >> ALUNO: Eu acho, n menos 1, ou algo parecido. 862 00:46:57,640 --> 00:46:59,100 Como, o último elemento. 863 00:46:59,100 --> 00:47:02,310 >> JASON HIRSCHHORN: Então você escreveu, int começando igual a 0, ponto e vírgula, e int 864 00:47:02,310 --> 00:47:04,320 final é igual a n menos 1, ponto e vírgula. 865 00:47:04,320 --> 00:47:06,850 Então, basicamente, o que estamos fazendo aqui, 0 a primeira posição. 866 00:47:06,850 --> 00:47:09,570 E como sabemos em matrizes, eles não vão até n, eles vão até n menos 1. 867 00:47:09,570 --> 00:47:11,110 Portanto, temos alguns limites da nossa matriz. 868 00:47:11,110 --> 00:47:15,730 E esses limites iniciais que ser os limites iniciais de nosso problema. 869 00:47:15,730 --> 00:47:16,640 OK. 870 00:47:16,640 --> 00:47:19,200 Então, isso parece bom. 871 00:47:19,200 --> 00:47:22,380 Então, se voltarmos a essa linha, enquanto comprimento da lista é maior do que 0, 872 00:47:22,380 --> 00:47:24,752 o que, em vez de n, deve vamos colocar aqui? 873 00:47:24,752 --> 00:47:28,820 >> ALUNO: Escrever terminando menos começo. 874 00:47:28,820 --> 00:47:34,780 >> JASON HIRSCHHORN: Ao término menos começando é maior do que 0? 875 00:47:34,780 --> 00:47:35,480 OK. 876 00:47:35,480 --> 00:47:37,730 E nós poderíamos, se quiséssemos fazer isso um pouco mais agradável, o que 877 00:47:37,730 --> 00:47:38,980 mais poderíamos fazer? 878 00:47:38,980 --> 00:47:41,650 879 00:47:41,650 --> 00:47:43,412 Se quiséssemos limpar este código um pouco? 880 00:47:43,412 --> 00:47:46,716 881 00:47:46,716 --> 00:47:48,180 Como podemos nos livrar do 0? 882 00:47:48,180 --> 00:47:51,560 883 00:47:51,560 --> 00:47:52,690 Esta é apenas uma questão de estilo. 884 00:47:52,690 --> 00:47:53,690 É correto agora. 885 00:47:53,690 --> 00:47:54,870 >> ALUNO: Final não igual começo? 886 00:47:54,870 --> 00:47:55,740 >> JASON HIRSCHHORN: Nós podemos fazer o que? 887 00:47:55,740 --> 00:47:56,730 >> [VOZES interpondo] 888 00:47:56,730 --> 00:47:57,330 >> ALUNO: Terminar é maior? 889 00:47:57,330 --> 00:47:57,720 >> JASON HIRSCHHORN: Yeah. 890 00:47:57,720 --> 00:48:01,110 Podemos apenas fazer ao terminar é maior do que o início. 891 00:48:01,110 --> 00:48:03,580 Certo. 892 00:48:03,580 --> 00:48:06,240 Nós adicionamos começando para o outro lado disso, e nos livramos do 0. 893 00:48:06,240 --> 00:48:08,000 Então, isso só parece um pouco mais limpo. 894 00:48:08,000 --> 00:48:08,990 OK. 895 00:48:08,990 --> 00:48:11,460 Assim, enquanto o comprimento da lista é 0, escrevemos que, ao terminar é maior 896 00:48:11,460 --> 00:48:12,240 do que no início. 897 00:48:12,240 --> 00:48:19,840 Vamos colocar em nosso necessário chaves, e em seguida, a primeira coisa 898 00:48:19,840 --> 00:48:22,090 nós queremos fazer é olhar para los em uma pequena lista. 899 00:48:22,090 --> 00:48:22,510 Você? 900 00:48:22,510 --> 00:48:23,320 Você pode me dar o - 901 00:48:23,320 --> 00:48:26,460 >> ALUNO: Se parêntese valor colchete - 902 00:48:26,460 --> 00:48:30,450 >> JASON HIRSCHHORN: Se parênteses colchete valor. 903 00:48:30,450 --> 00:48:33,210 >> ESTUDANTE: acabar dividido por 2. 904 00:48:33,210 --> 00:48:33,952 >> JASON HIRSCHHORN: Ending? 905 00:48:33,952 --> 00:48:35,280 >> ALUNO: Eu vejo um problema com o seu - 906 00:48:35,280 --> 00:48:35,750 >> JASON HIRSCHHORN: OK. 907 00:48:35,750 --> 00:48:39,150 Bem, olhe para o meio. 908 00:48:39,150 --> 00:48:41,226 Como é que sabemos o que o meio é? 909 00:48:41,226 --> 00:48:42,450 É. 910 00:48:42,450 --> 00:48:43,070 Então deixe-me apagar esse código. 911 00:48:43,070 --> 00:48:46,360 Como é que sabemos o que o meio é? 912 00:48:46,360 --> 00:48:48,003 Em qualquer coisa, quando você tem o começo eo fim, como você encontra 913 00:48:48,003 --> 00:48:48,876 no meio? 914 00:48:48,876 --> 00:48:49,590 >> ALUNO: Você média. 915 00:48:49,590 --> 00:48:51,820 >> ALUNO: Você adiciona-los em conjunto e, em seguida, - 916 00:48:51,820 --> 00:48:53,150 >> JASON HIRSCHHORN: Adicione- juntos e depois? 917 00:48:53,150 --> 00:48:54,090 >> ALUNO: E você média. 918 00:48:54,090 --> 00:48:55,050 Divida-o por 2. 919 00:48:55,050 --> 00:48:56,500 >> JASON HIRSCHHORN: Adicione- juntos e dividir por 2. 920 00:48:56,500 --> 00:48:59,400 Assim, int meio é igual? 921 00:48:59,400 --> 00:49:01,120 Tom, você pode dar isso para mim? 922 00:49:01,120 --> 00:49:03,550 >> ALUNO: Começando mais fim - 923 00:49:03,550 --> 00:49:04,950 >> JASON HIRSCHHORN: Início mais fim. 924 00:49:04,950 --> 00:49:06,880 >> ALUNO: All, suporte, dividido por 2. 925 00:49:06,880 --> 00:49:10,940 >> JASON HIRSCHHORN: Todos, entre parênteses, dividido por dois. 926 00:49:10,940 --> 00:49:16,300 Então isso me dá a média de qualquer coisa, certo? 927 00:49:16,300 --> 00:49:18,980 >> ALUNO: Você também precisa arredondar. 928 00:49:18,980 --> 00:49:19,990 >> JASON HIRSCHHORN: O que você faz Quer dizer, eu preciso arredondar? 929 00:49:19,990 --> 00:49:20,400 >> [VOZES interpondo] 930 00:49:20,400 --> 00:49:24,520 >> ALUNO: Porque se é um estranho número, então é como - 931 00:49:24,520 --> 00:49:25,440 >> JASON HIRSCHHORN: Bem, OK. 932 00:49:25,440 --> 00:49:26,360 Assim eu poderia arredondar. 933 00:49:26,360 --> 00:49:33,350 Mas se for um número ímpar, a 5, eu posso tomar um fora do meio. 934 00:49:33,350 --> 00:49:35,665 Ou se é um número par, ao contrário, isso é um caso melhor. 935 00:49:35,665 --> 00:49:39,600 Se for 4, só temos 4, eu posso tomar o primeiro "meio", citações, fecha aspas ou 936 00:49:39,600 --> 00:49:41,760 o segundo "meio". 937 00:49:41,760 --> 00:49:46,390 Ou iria trabalhar para uma busca binária, então eu realmente não precisa arredondar. 938 00:49:46,390 --> 00:49:48,640 Mas há uma outra coisa que eu precisa olhar para esta linha. 939 00:49:48,640 --> 00:49:50,530 Podemos não perceber, ainda, mas vamos voltar a ele. 940 00:49:50,530 --> 00:49:53,200 Porque esta linha, na verdade ainda precisa de uma outra coisa. 941 00:49:53,200 --> 00:49:55,990 >> Mas até agora, nós escrevemos quatro linhas de código. 942 00:49:55,990 --> 00:49:58,120 Nós temos o nosso começo e terminando marcadores. 943 00:49:58,120 --> 00:50:01,320 Temos o nosso loop while, que mapeia em diretamente para o nosso pseudocódigo. 944 00:50:01,320 --> 00:50:05,790 Nós estamos olhando para o meio que mapeia diretamente em nosso pseudocódigo. 945 00:50:05,790 --> 00:50:09,070 Eu diria que este vai para o meio da lista, esta linha de código. 946 00:50:09,070 --> 00:50:11,560 E então, quando vamos para o meio da Na lista, a próxima coisa que precisamos fazer 947 00:50:11,560 --> 00:50:14,880 é verificar se o nosso valor está lá para o pseudocódigo que escrevemos anteriormente. 948 00:50:14,880 --> 00:50:17,100 >> Então, como vamos verificar se o nosso valor está no meio da lista? 949 00:50:17,100 --> 00:50:17,300 Você. 950 00:50:17,300 --> 00:50:18,511 Por que você não faz isso? 951 00:50:18,511 --> 00:50:23,070 >> ALUNO: Se o nosso valor de é no meio é igual 952 00:50:23,070 --> 00:50:24,592 tudo o que definir o - 953 00:50:24,592 --> 00:50:26,190 Quero dizer igual igual a - 954 00:50:26,190 --> 00:50:26,690 >> JASON HIRSCHHORN: It - 955 00:50:26,690 --> 00:50:27,940 OK. 956 00:50:27,940 --> 00:50:30,080 957 00:50:30,080 --> 00:50:32,170 >> ALUNO: Eu não tenho certeza o que o variável que estamos procurando 958 00:50:32,170 --> 00:50:32,850 pois, embora, é porque - 959 00:50:32,850 --> 00:50:33,330 >> [VOZES interpondo] 960 00:50:33,330 --> 00:50:34,520 >> Estudante: [inaudível]. 961 00:50:34,520 --> 00:50:35,060 >> JASON HIRSCHHORN: Exatamente. 962 00:50:35,060 --> 00:50:37,260 Por a declaração da função, estamos à procura de um valor. 963 00:50:37,260 --> 00:50:39,760 Então, nós estamos procurando por um valor em uma matriz de valores. 964 00:50:39,760 --> 00:50:41,080 Então você está exatamente certo. 965 00:50:41,080 --> 00:50:45,040 Você vai fazer, se faixa de valor parêntese aberto meio fechado iguais suporte 966 00:50:45,040 --> 00:50:49,930 igual valor, e lá dentro o que precisamos fazer? 967 00:50:49,930 --> 00:50:51,230 Se o nosso valor está lá, o que que precisamos fazer? 968 00:50:51,230 --> 00:50:51,420 >> [VOZES interpondo] 969 00:50:51,420 --> 00:50:52,160 >> ESTUDANTE: Return zero. 970 00:50:52,160 --> 00:50:53,070 >> JASON HIRSCHHORN: Return verdade. 971 00:50:53,070 --> 00:50:54,790 >> ALUNO: Retorna true. 972 00:50:54,790 --> 00:50:57,856 >> JASON HIRSCHHORN: Michael, o que é que esta linha faz? 973 00:50:57,856 --> 00:51:01,105 >> Estudante: [inaudível] o programa foi executado o seu curso, e que é mais, e 974 00:51:01,105 --> 00:51:01,920 você tem o que você precisa fazer? 975 00:51:01,920 --> 00:51:03,030 >> JASON HIRSCHHORN: O programa ou o quê? 976 00:51:03,030 --> 00:51:03,700 Neste caso? 977 00:51:03,700 --> 00:51:04,210 >> ALUNO: A função. 978 00:51:04,210 --> 00:51:05,170 >> JASON HIRSCHHORN: A função. 979 00:51:05,170 --> 00:51:08,420 E assim, para voltar para o que chamou lo e dar-lhe o valor, é verdade. 980 00:51:08,420 --> 00:51:09,890 Exatamente. 981 00:51:09,890 --> 00:51:10,170 Main. 982 00:51:10,170 --> 00:51:12,035 Qual é o tipo de retorno de principal, Michael? 983 00:51:12,035 --> 00:51:16,480 984 00:51:16,480 --> 00:51:17,150 >> ESTUDANTE: int, integer? 985 00:51:17,150 --> 00:51:18,080 >> JASON HIRSCHHORN: int, exatamente. 986 00:51:18,080 --> 00:51:18,680 Um inteiro. 987 00:51:18,680 --> 00:51:20,980 Isso foi apenas uma pergunta para se certificar Vocês têm estado em cima dela. 988 00:51:20,980 --> 00:51:24,250 O que geralmente retornam, se todas as coisas estão funcionando bem? 989 00:51:24,250 --> 00:51:24,520 >> ALUNO: Zero. 990 00:51:24,520 --> 00:51:24,820 >> JASON HIRSCHHORN: Zero. 991 00:51:24,820 --> 00:51:25,430 Exatamente. 992 00:51:25,430 --> 00:51:28,790 >> ESTUDANTE: Se este apenas retorna true, não há nenhuma informação a ser dada 993 00:51:28,790 --> 00:51:30,675 sobre o que o - 994 00:51:30,675 --> 00:51:34,040 Oh, este é apenas dizer que esse valor está dentro da matriz. 995 00:51:34,040 --> 00:51:35,350 >> JASON HIRSCHHORN: Exatamente. 996 00:51:35,350 --> 00:51:38,080 Este programa não está dando informações de onde exatamente é o valor. 997 00:51:38,080 --> 00:51:41,850 Ele só está dizendo, sim, encontramos -lo, ou não, nós não encontrá-lo. 998 00:51:41,850 --> 00:51:42,990 Assim, se o número encontrado, retorna true. 999 00:51:42,990 --> 00:51:45,500 Bem, na verdade nós fizemos que realmente rapidamente com que uma linha de código. 1000 00:51:45,500 --> 00:51:47,500 Então eu vou passar essa linha de pseudocódigo. 1001 00:51:47,500 --> 00:51:50,045 >> ALUNO: Não precisamos para alterar a matriz? 1002 00:51:50,045 --> 00:51:52,830 Deve ser valores, não o valor, certo? 1003 00:51:52,830 --> 00:51:53,430 >> JASON HIRSCHHORN: Desculpe. 1004 00:51:53,430 --> 00:51:54,010 Obrigado. 1005 00:51:54,010 --> 00:51:54,800 >> ESTUDANTE: Yeah. 1006 00:51:54,800 --> 00:51:55,850 >> JASON HIRSCHHORN: Esta linha devem ser valores. 1007 00:51:55,850 --> 00:51:57,150 Exatamente. 1008 00:51:57,150 --> 00:51:57,920 OK. 1009 00:51:57,920 --> 00:51:59,170 Então, nós olhamos a lista meio. 1010 00:51:59,170 --> 00:52:00,790 Se o número encontrado return true. 1011 00:52:00,790 --> 00:52:04,470 Continuando com nosso pseudocódigo, se média é maior, a busca para a esquerda. 1012 00:52:04,470 --> 00:52:09,640 Então eu tive aqui, se o número de superior, de pesquisa à esquerda. 1013 00:52:09,640 --> 00:52:12,700 1014 00:52:12,700 --> 00:52:14,462 Constantino, você pode dar me esta linha de código? 1015 00:52:14,462 --> 00:52:17,240 1016 00:52:17,240 --> 00:52:23,520 >> ESTUDANTE: Se o valor de meia - 1017 00:52:23,520 --> 00:52:24,890 >> JASON HIRSCHHORN: Então, se o valor - 1018 00:52:24,890 --> 00:52:28,890 se parêntese aberto valoriza suporte próximo suporte do meio - 1019 00:52:28,890 --> 00:52:31,500 >> ALUNO: É menor do que valor? 1020 00:52:31,500 --> 00:52:32,760 >> JASON HIRSCHHORN: É menos do que. 1021 00:52:32,760 --> 00:52:33,800 >> ALUNO: Menos de valor. 1022 00:52:33,800 --> 00:52:34,060 >> JASON HIRSCHHORN: Valor. 1023 00:52:34,060 --> 00:52:35,310 Bem, na verdade, você quer verificar se o número - 1024 00:52:35,310 --> 00:52:38,310 1025 00:52:38,310 --> 00:52:38,490 Desculpe. 1026 00:52:38,490 --> 00:52:39,140 Isso é um pouco confuso. 1027 00:52:39,140 --> 00:52:43,920 Mas o resto, se o número do meio da lista é maior. 1028 00:52:43,920 --> 00:52:45,170 >> ALUNO: Oh, OK. 1029 00:52:45,170 --> 00:52:49,800 1030 00:52:49,800 --> 00:52:50,410 >> JASON HIRSCHHORN: Eu vou mudar isso. 1031 00:52:50,410 --> 00:52:55,060 Else if média é mais elevada, deseja pesquisar esquerda, OK? 1032 00:52:55,060 --> 00:52:57,310 E o que fazemos dentro isso se condição? 1033 00:52:57,310 --> 00:53:03,660 1034 00:53:03,660 --> 00:53:07,510 >> ALUNO: Posso fazer uma pequena alteração a condição, alterá-lo para outra pessoa se? 1035 00:53:07,510 --> 00:53:08,380 >> JASON HIRSCHHORN: Else if? 1036 00:53:08,380 --> 00:53:09,270 OK. 1037 00:53:09,270 --> 00:53:12,840 Portanto, este código será executado sobre o mesmo. 1038 00:53:12,840 --> 00:53:18,620 Mas a coisa boa sobre o uso de if, else if, else if ou if, else if, else 1039 00:53:18,620 --> 00:53:22,320 significa que somente um desses vai ser verificado, não todos os três, 1040 00:53:22,320 --> 00:53:23,290 potencialmente. 1041 00:53:23,290 --> 00:53:25,530 E isso faz com que seja um pouco mais agradável no computador que está 1042 00:53:25,530 --> 00:53:26,670 executar o seu programa. 1043 00:53:26,670 --> 00:53:27,620 >> Assim, [? Constantino,?] 1044 00:53:27,620 --> 00:53:31,330 estamos dentro desta linha, mais se os valores, próximo suporte do meio suporte 1045 00:53:31,330 --> 00:53:32,260 é maior do que o valor. 1046 00:53:32,260 --> 00:53:33,150 O que precisamos fazer? 1047 00:53:33,150 --> 00:53:33,970 Precisamos pesquisar a esquerda. 1048 00:53:33,970 --> 00:53:35,220 Como fazemos isso? 1049 00:53:35,220 --> 00:53:46,960 1050 00:53:46,960 --> 00:53:48,720 Vou dar-lhe um começo. 1051 00:53:48,720 --> 00:53:52,210 >> Temos essas duas coisas chamadas começando e terminando. 1052 00:53:52,210 --> 00:53:57,340 Então, o que precisa acontecer para o começo? 1053 00:53:57,340 --> 00:53:59,640 Se você quiser pesquisar a esquerda do lista, temos nosso começo atual. 1054 00:53:59,640 --> 00:54:01,080 O que precisamos fazer isso? 1055 00:54:01,080 --> 00:54:04,220 >> ALUNO: Nós ajustamos o início a média mais 1. 1056 00:54:04,220 --> 00:54:05,120 >> JASON HIRSCHHORN: Então, se estamos buscando a esquerda? 1057 00:54:05,120 --> 00:54:06,250 >> ESTUDANTE: Desculpe, meio menos - 1058 00:54:06,250 --> 00:54:11,310 de modo que o meio final seria menos 1 e no início - 1059 00:54:11,310 --> 00:54:12,450 >> JASON HIRSCHHORN: E o acontece com o início? 1060 00:54:12,450 --> 00:54:13,210 >> ALUNO: Ele permanece o mesmo. 1061 00:54:13,210 --> 00:54:14,120 >> JASON HIRSCHHORN: Então, a significado permanece o mesmo. 1062 00:54:14,120 --> 00:54:16,040 Se estamos buscando a esquerda, estamos usando o mesmo princípio - 1063 00:54:16,040 --> 00:54:16,860 exatamente correto. 1064 00:54:16,860 --> 00:54:17,870 E o final? 1065 00:54:17,870 --> 00:54:19,390 Desculpe, o que faz o terminando igual de novo? 1066 00:54:19,390 --> 00:54:20,750 >> ALUNO: menos Oriente 1. 1067 00:54:20,750 --> 00:54:21,620 >> JASON HIRSCHHORN: menos Oriente 1. 1068 00:54:21,620 --> 00:54:23,470 Agora, por menos 1, e não apenas do meio? 1069 00:54:23,470 --> 00:54:32,870 1070 00:54:32,870 --> 00:54:35,570 >> ALUNO: O meio está fora de já imaginar, porque tivemos 1071 00:54:35,570 --> 00:54:36,700 verificado que ele está fora? 1072 00:54:36,700 --> 00:54:37,630 >> JASON HIRSCHHORN: Isso é exatamente correto. 1073 00:54:37,630 --> 00:54:38,580 O meio é fora de cogitação. 1074 00:54:38,580 --> 00:54:39,800 Já verifiquei o meio. 1075 00:54:39,800 --> 00:54:44,730 Então, nós não queremos "meio", citação fecha aspas, para continuar a estar no 1076 00:54:44,730 --> 00:54:46,110 matriz que estamos à procura. 1077 00:54:46,110 --> 00:54:47,670 Então, isso é fantástico. 1078 00:54:47,670 --> 00:54:50,670 >> Else if meio suporte de valores é maior do valor final iguais 1079 00:54:50,670 --> 00:54:51,920 meio menos 1. 1080 00:54:51,920 --> 00:54:55,060 1081 00:54:55,060 --> 00:54:57,340 Jeff, que sobre esta última linha? 1082 00:54:57,340 --> 00:54:58,590 >> ALUNO: Else. 1083 00:54:58,590 --> 00:55:02,486 1084 00:55:02,486 --> 00:55:06,000 Valores médio é menor que o valor? 1085 00:55:06,000 --> 00:55:07,570 >> JASON HIRSCHHORN: Nós vamos você está me dando mais. 1086 00:55:07,570 --> 00:55:09,310 Então, se você não me der - 1087 00:55:09,310 --> 00:55:12,270 >> ALUNO: Então começando seria mais um meio. 1088 00:55:12,270 --> 00:55:16,100 1089 00:55:16,100 --> 00:55:19,070 >> JASON Hirschhorn: iguais Começando além de um meio, de novo, para a mesma 1090 00:55:19,070 --> 00:55:20,820 razão que Constantino deu-nos mais cedo. 1091 00:55:20,820 --> 00:55:24,280 E, no final, que não tenha dado me uma linha de código ainda? 1092 00:55:24,280 --> 00:55:26,600 Return false, Aleha, o que podemos escrever aqui? 1093 00:55:26,600 --> 00:55:28,590 >> ALUNO: Return false. 1094 00:55:28,590 --> 00:55:29,320 >> JASON HIRSCHHORN: Return false. 1095 00:55:29,320 --> 00:55:33,340 E precisamos fazer isso, porque se nós não encontrá-lo, é preciso dizer que 1096 00:55:33,340 --> 00:55:34,080 não encontrá-lo. 1097 00:55:34,080 --> 00:55:36,270 E nós dissemos que vamos retornar um bool, então nós definitivamente tem que voltar 1098 00:55:36,270 --> 00:55:38,150 um em algum lugar bool. 1099 00:55:38,150 --> 00:55:42,590 >> Então, vamos executar este código. 1100 00:55:42,590 --> 00:55:44,520 Na verdade, estou indo para - 1101 00:55:44,520 --> 00:55:45,930 então estamos no terminal. 1102 00:55:45,930 --> 00:55:47,230 Nós vamos limpar nossa janela. 1103 00:55:47,230 --> 00:55:49,270 Vamos fazer toda. 1104 00:55:49,270 --> 00:55:50,340 Descobrimos que há um erro. 1105 00:55:50,340 --> 00:55:54,280 Há um erro na linha 15, que deverá vírgula no final do 1106 00:55:54,280 --> 00:55:54,890 declaração. 1107 00:55:54,890 --> 00:55:56,454 Então, o que eu esqueci? 1108 00:55:56,454 --> 00:55:57,230 >> ALUNO: Ponto e vírgula. 1109 00:55:57,230 --> 00:56:00,200 >> JASON HIRSCHHORN: Ponto e vírgula até aqui. 1110 00:56:00,200 --> 00:56:00,950 Acho que foi o código do Tom. 1111 00:56:00,950 --> 00:56:01,870 Então, Tom, [inaudível]. 1112 00:56:01,870 --> 00:56:03,120 Brincadeirinha. 1113 00:56:03,120 --> 00:56:05,010 1114 00:56:05,010 --> 00:56:07,310 Vamos fazem tudo de novo. 1115 00:56:07,310 --> 00:56:10,180 >> ALUNO: O diretório Dropbox devemos estar em para isso? 1116 00:56:10,180 --> 00:56:11,345 >> JASON HIRSCHHORN: Então você pode apenas assistir para este bit. 1117 00:56:11,345 --> 00:56:16,380 Mas, novamente, se você queria mudar isso código em seu diretório pset3 para tentar 1118 00:56:16,380 --> 00:56:17,050 com isso, isso é o que eu fiz. 1119 00:56:17,050 --> 00:56:18,600 Se você observar aqui - desculpe, boa pergunta. 1120 00:56:18,600 --> 00:56:19,460 >> [? LS,?] 1121 00:56:19,460 --> 00:56:24,700 Eu tenho aqui o código find.c a partir do código distro desta semana. 1122 00:56:24,700 --> 00:56:26,300 Tenho Helpers.h. 1123 00:56:26,300 --> 00:56:30,010 Eu tenho um arquivo Marca que eu realmente editado um pouco para incluir esses novos 1124 00:56:30,010 --> 00:56:30,710 arquivos que estamos escrevendo. 1125 00:56:30,710 --> 00:56:34,120 Tudo que o código estará disponível, não o código de distribuição, mas a nova 1126 00:56:34,120 --> 00:56:39,510 Faça arquivo, o novo arquivo será Helpers.h estar disponível on-line para download. 1127 00:56:39,510 --> 00:56:41,800 Mais uma vez, então esses são os códigos extras que temos. 1128 00:56:41,800 --> 00:56:46,130 >> Então, faça de tudo, por esta linha, faz encontrar, binária, a seleção bolha - marcas 1129 00:56:46,130 --> 00:56:50,930 todos os três e compila este achado código executável. 1130 00:56:50,930 --> 00:56:54,090 Então, geralmente, nós não queremos para direto para check50. 1131 00:56:54,090 --> 00:56:57,580 Nós queremos fazer alguns exames por conta própria. 1132 00:56:57,580 --> 00:57:11,750 Mas apenas para que possamos agilizar isso um pouco, check50 2013 pset3.find passará 1133 00:57:11,750 --> 00:57:14,630 em helpers.c-- o meu mal. 1134 00:57:14,630 --> 00:57:16,050 >> Eu não tenho esse direito agora. 1135 00:57:16,050 --> 00:57:20,670 Então, nós estamos indo realmente para executar o código de verdade. 1136 00:57:20,670 --> 00:57:23,570 Usage.find /, você sabe o que isso significa? 1137 00:57:23,570 --> 00:57:25,970 >> ALUNO: Você precisa de um segundo linha de comando sobre ele. 1138 00:57:25,970 --> 00:57:26,980 >> JASON HIRSCHHORN: Eu preciso uma segunda linha de comando. 1139 00:57:26,980 --> 00:57:30,640 E por a especificação, o que eu preciso para entrar o que estamos procurando. 1140 00:57:30,640 --> 00:57:33,750 Então, vamos olhar para 42. 1141 00:57:33,750 --> 00:57:37,030 Vamos mantê-lo em ordenada, porque nós não ter escrito uma função de classificação ainda - 1142 00:57:37,030 --> 00:57:41,830 42, 43, 44. 1143 00:57:41,830 --> 00:57:46,240 >> E Controle D não encontrou o agulha no palheiro. 1144 00:57:46,240 --> 00:57:46,505 Isso é ruim. 1145 00:57:46,505 --> 00:57:47,200 É definitivamente lá. 1146 00:57:47,200 --> 00:57:48,090 Vamos tentar outra coisa. 1147 00:57:48,090 --> 00:57:49,860 Talvez seja porque eu coloquei -lo no início. 1148 00:57:49,860 --> 00:57:54,490 >> Vamos fazer 41, 42, 43. 1149 00:57:54,490 --> 00:57:55,012 Lá vamos nós. 1150 00:57:55,012 --> 00:57:56,400 Ele encontrou. 1151 00:57:56,400 --> 00:58:00,040 Vamos colocá-lo no final agora, só para que possamos ser completo - 1152 00:58:00,040 --> 00:58:03,580 40, 41, 42. 1153 00:58:03,580 --> 00:58:05,760 Não encontrou a agulha. 1154 00:58:05,760 --> 00:58:07,550 Então, eu mencionei isso antes. 1155 00:58:07,550 --> 00:58:08,980 Infelizmente, eu sabia que isso ia acontecer. 1156 00:58:08,980 --> 00:58:11,490 >> Mas, para fins pedagógicos, é bom para explorar isso. 1157 00:58:11,490 --> 00:58:12,990 Não funciona. 1158 00:58:12,990 --> 00:58:16,020 Por alguma razão, ele não pode encontrá-lo. 1159 00:58:16,020 --> 00:58:18,970 Nós sabemos o que está lá dentro, mas não estamos encontrando. 1160 00:58:18,970 --> 00:58:24,140 Então, uma coisa que podemos fazer é passar por GDB para encontrá-lo, mas não qualquer um, 1161 00:58:24,140 --> 00:58:27,850 sem passar por GDB, ter um noção de onde nós asneira? 1162 00:58:27,850 --> 00:58:28,480 [? Madu? ?] 1163 00:58:28,480 --> 00:58:30,960 >> ALUNO: Eu acho que pode ser quando terminar é igual ao início, e é 1164 00:58:30,960 --> 00:58:33,090 apenas uma lista de um único elemento. 1165 00:58:33,090 --> 00:58:35,560 Em seguida, ele simplesmente ignora-lo em vez de realmente verificar. 1166 00:58:35,560 --> 00:58:36,940 >> JASON HIRSCHHORN: Isso é exatamente correto. 1167 00:58:36,940 --> 00:58:41,110 Ao final é igual a princípio, nós ainda tem um elemento em nossa lista? 1168 00:58:41,110 --> 00:58:42,480 >> ESTUDANTE: sim. 1169 00:58:42,480 --> 00:58:45,450 >> JASON HIRSCHHORN: Sim, na verdade, nós tem um e somente um elemento. 1170 00:58:45,450 --> 00:58:50,500 E isso provavelmente vai acontecer quando, acordo com o código que testamos, estamos no 1171 00:58:50,500 --> 00:58:54,640 frente do palheiro ou pelo No final do palheiro. 1172 00:58:54,640 --> 00:58:56,000 É aí que começo e final vai igual 1173 00:58:56,000 --> 00:58:57,820 um, com busca binária. 1174 00:58:57,820 --> 00:59:01,440 Então, nesses dois casos, não funcionou, porque terminando foi igual ao início. 1175 00:59:01,440 --> 00:59:06,030 >> Mas se acabar é igual a princípio, que isso loop while executar? 1176 00:59:06,030 --> 00:59:06,390 Isso não acontece. 1177 00:59:06,390 --> 00:59:08,660 E nós poderíamos ter verificado que mais uma vez através GDB. 1178 00:59:08,660 --> 00:59:14,000 Então, como podemos corrigir esse código, porque quando ao terminar é igual a 1179 00:59:14,000 --> 00:59:16,070 começando, nós também queremos isso while para executar. 1180 00:59:16,070 --> 00:59:18,620 >> Então, o que podemos fazer correção para a linha 18? 1181 00:59:18,620 --> 00:59:21,060 >> Estudante: [inaudível] é maior que ou igual a. 1182 00:59:21,060 --> 00:59:21,700 >> JASON HIRSCHHORN: Exatamente. 1183 00:59:21,700 --> 00:59:24,600 Enquanto final é maior do que ou igual ao início. 1184 00:59:24,600 --> 00:59:27,300 Então, agora, temos a certeza de conseguir que caso esquina no final. 1185 00:59:27,300 --> 00:59:27,870 E vamos ver. 1186 00:59:27,870 --> 00:59:29,560 Vamos correr isso mais uma vez. 1187 00:59:29,560 --> 00:59:31,266 >> Vamos fazer tudo. 1188 00:59:31,266 --> 00:59:33,910 Mais uma vez, você vai ter que apenas acompanhar aqui. 1189 00:59:33,910 --> 00:59:36,280 Encontre 41 desta vez. 1190 00:59:36,280 --> 00:59:37,360 Basta mantê-lo consistente. 1191 00:59:37,360 --> 00:59:38,210 >> Encontre 42. 1192 00:59:38,210 --> 00:59:38,930 Vamos colocá-lo no início - 1193 00:59:38,930 --> 00:59:41,630 42, 43, 44. 1194 00:59:41,630 --> 00:59:42,860 Encontrámo-lo. 1195 00:59:42,860 --> 00:59:47,710 Assim que foi de fato a mudança precisávamos fazer. 1196 00:59:47,710 --> 00:59:51,090 >> Isso foi um monte de codificação que fez, busca binária. 1197 00:59:51,090 --> 00:59:55,760 Alguém tem alguma dúvida antes Eu passo em linhas que escrevemos em 1198 00:59:55,760 --> 00:59:58,750 busca binária ou como achamos o que nós fizemos descobrir? 1199 00:59:58,750 --> 01:00:01,900 1200 01:00:01,900 --> 01:00:06,270 Antes de seguir em frente, eu também quero apontar que, em geral, mapeamos 1201 01:00:06,270 --> 01:00:09,300 nossa pseudo-código de um para uma para o nosso código. 1202 01:00:09,300 --> 01:00:11,550 >> Tivemos que coisa complicada descobrir com o 1203 01:00:11,550 --> 01:00:12,890 começando e terminando. 1204 01:00:12,890 --> 01:00:17,380 Mas se você não tivesse percebido isso, você teria escrito praticamente o 1205 01:00:17,380 --> 01:00:20,740 código idêntico, exceto por essas duas linhas principais. 1206 01:00:20,740 --> 01:00:23,380 E então você teria percebido quando você fez isso em cheques e casos que 1207 01:00:23,380 --> 01:00:24,840 você precisa de algo mais. 1208 01:00:24,840 --> 01:00:28,510 Assim, mesmo se você tivesse seguido o nosso linha pseudo-código para a linha, você teria 1209 01:00:28,510 --> 01:00:31,130 conseguido tudo, mas duas linhas de código que você precisava para escrever. 1210 01:00:31,130 --> 01:00:33,900 >> E eu estaria disposto a apostar que vocês teria descoberto isso tudo 1211 01:00:33,900 --> 01:00:37,940 muito rapidamente, o que você precisava para colocar algum tipo de marcador lá para descobrir 1212 01:00:37,940 --> 01:00:39,190 de onde você estava. 1213 01:00:39,190 --> 01:00:41,540 1214 01:00:41,540 --> 01:00:44,550 Isso, novamente, é o poder de fazer pseudo-código antes do tempo. 1215 01:00:44,550 --> 01:00:47,310 Assim, podemos fazer a lógica primeiro, e depois podemos preocupar com a sintaxe. 1216 01:00:47,310 --> 01:00:51,470 >> Se tivéssemos sido confundido sobre a lógica ao tentar escrever esse código em C, 1217 01:00:51,470 --> 01:00:53,110 teríamos conseguido toda desarrumada. 1218 01:00:53,110 --> 01:00:56,340 E então nós estaríamos fazendo perguntas sobre a lógica ea sintaxe e entrosamento 1219 01:00:56,340 --> 01:00:57,320 todos eles juntos. 1220 01:00:57,320 --> 01:01:02,170 E nós teria se perdido no que pode rapidamente tornar-se um 1221 01:01:02,170 --> 01:01:04,000 problema muito difícil. 1222 01:01:04,000 --> 01:01:08,680 Então, vamos seguir em frente agora para a seleção de tipo. 1223 01:01:08,680 --> 01:01:10,760 >> Temos 20 minutos. 1224 01:01:10,760 --> 01:01:14,130 Então, eu tenho a sensação de que não será capaz de passar por todos seleção tipo 1225 01:01:14,130 --> 01:01:15,940 e bubble sort. 1226 01:01:15,940 --> 01:01:20,670 Mas vamos pelo menos tentar para concluir a seleção tipo. 1227 01:01:20,670 --> 01:01:23,540 Então implementar seleção tipo usando o seguinte declaração da função. 1228 01:01:23,540 --> 01:01:27,530 >> Mais uma vez, este é retirado do conjunto de problemas de especificação. 1229 01:01:27,530 --> 01:01:31,560 Valores Int é parênteses, é uma matriz de números inteiros. 1230 01:01:31,560 --> 01:01:33,490 E int.n é o tamanho da matriz que. 1231 01:01:33,490 --> 01:01:36,840 Tipo de seleção vai para classificar essa matriz. 1232 01:01:36,840 --> 01:01:43,580 >> Então, por nosso modelo mental de seleção tipo, puxamos o - 1233 01:01:43,580 --> 01:01:47,720 primeiro, percorrer a lista da primeira tempo, encontrar o menor número, 1234 01:01:47,720 --> 01:01:52,860 colocá-lo no início, encontrar a segunda menor número, coloque-o no 1235 01:01:52,860 --> 01:01:56,380 segunda posição, se quisermos Ordenar em ordem crescente. 1236 01:01:56,380 --> 01:01:58,440 Eu não estou forçando você a escrever pseudo-código no momento. 1237 01:01:58,440 --> 01:02:01,350 >> Mas antes de fazer o código como uma classe em cinco minutos, vamos escrever 1238 01:02:01,350 --> 01:02:03,550 pseudo-código por isso temos algum sentido de para onde estamos indo. 1239 01:02:03,550 --> 01:02:05,630 Então, tentar escrever pseudo-código em seu próprio país. 1240 01:02:05,630 --> 01:02:08,610 E em seguida, tentar transformar essa pseudo-código em código. 1241 01:02:08,610 --> 01:02:10,740 Nós vamos fazer isso como um grupo em cinco minutos. 1242 01:02:10,740 --> 01:02:32,560 1243 01:02:32,560 --> 01:02:33,895 >> E, claro, deixe-me saber se você tem alguma dúvida. 1244 01:02:33,895 --> 01:03:56,738 1245 01:03:56,738 --> 01:03:58,230 >> ALUNO: É isso? 1246 01:03:58,230 --> 01:04:00,280 >> JASON HIRSCHHORN: Veja quão longe você pode entrar em mais de dois minutos. 1247 01:04:00,280 --> 01:04:01,790 Eu entendo que você não vai ser capaz de terminar. 1248 01:04:01,790 --> 01:04:03,050 Mas vamos falar sobre isso como um grupo. 1249 01:04:03,050 --> 01:04:57,830 1250 01:04:57,830 --> 01:05:00,630 >> Você é tudo de codificação para que [inaudível], por isso estou desculpe interromper o que está fazendo. 1251 01:05:00,630 --> 01:05:02,530 Mas vamos passar por isso como um grupo. 1252 01:05:02,530 --> 01:05:07,590 E, novamente, busca binária, todos dão me um, se não mais linhas de código. 1253 01:05:07,590 --> 01:05:08,530 Obrigado por isso. 1254 01:05:08,530 --> 01:05:11,730 Nós vamos fazer a mesma coisa aqui, o código em conjunto, como um grupo. 1255 01:05:11,730 --> 01:05:15,170 >> Assim, a seleção tipo - vamos escrever algumas rápidas pseudo-código. 1256 01:05:15,170 --> 01:05:20,380 Por modelo mental, alguém pode me dar a primeira linha de pseudo-código, por favor? 1257 01:05:20,380 --> 01:05:23,000 1258 01:05:23,000 --> 01:05:24,270 O que eu quero fazer? 1259 01:05:24,270 --> 01:05:27,070 >> ALUNO: Enquanto a lista está fora de ordem. 1260 01:05:27,070 --> 01:05:30,630 >> JASON HIRSCHHORN: OK, enquanto a lista está fora de ordem. 1261 01:05:30,630 --> 01:05:33,540 E o que você quer dizer "fora da ordem?" 1262 01:05:33,540 --> 01:05:34,960 >> ALUNO: Enquanto [inaudível] 1263 01:05:34,960 --> 01:05:36,210 não foi classificada. 1264 01:05:36,210 --> 01:05:38,460 1265 01:05:38,460 --> 01:05:40,290 >> JASON HIRSCHHORN: Enquanto a lista está fora de ordem, o que vamos fazer? 1266 01:05:40,290 --> 01:05:44,200 Dá-me a segunda linha, por favor, Marcus. 1267 01:05:44,200 --> 01:05:47,186 >> Estudante: Então, encontrar o próximo menor número. 1268 01:05:47,186 --> 01:05:49,000 Isto será recuado. 1269 01:05:49,000 --> 01:05:55,140 >> JASON HIRSCHHORN: Então, encontrar o próximo menor número. 1270 01:05:55,140 --> 01:05:56,460 E então outra pessoa? 1271 01:05:56,460 --> 01:06:01,030 Assim que encontrar o próximo menor número, o que vamos fazer? 1272 01:06:01,030 --> 01:06:03,010 Eu vou dizer encontrar o menor número. 1273 01:06:03,010 --> 01:06:04,820 Isso é o que nós queremos fazer. 1274 01:06:04,820 --> 01:06:06,210 >> Então, encontrar o menor número. 1275 01:06:06,210 --> 01:06:08,061 Então, o que vamos fazer? 1276 01:06:08,061 --> 01:06:09,480 >> Estudante: [inaudível] para início. 1277 01:06:09,480 --> 01:06:10,680 >> JASON HIRSCHHORN: Desculpe? 1278 01:06:10,680 --> 01:06:12,700 >> ALUNO: Coloque-o no no início da lista. 1279 01:06:12,700 --> 01:06:18,540 >> JASON HIRSCHHORN: Então, coloque-o no o início da lista. 1280 01:06:18,540 --> 01:06:20,140 E o que podemos fazer para a coisa que era no princípio 1281 01:06:20,140 --> 01:06:20,830 da lista, certo? 1282 01:06:20,830 --> 01:06:21,910 Estamos substituindo alguma coisa. 1283 01:06:21,910 --> 01:06:23,130 Então, onde é que vamos colocar isso? 1284 01:06:23,130 --> 01:06:24,120 Sim, Anna? 1285 01:06:24,120 --> 01:06:25,520 >> ALUNO: Onde o menor número era? 1286 01:06:25,520 --> 01:06:32,530 >> JASON Hirshhorn: Então coloque o início da lista, onde o 1287 01:06:32,530 --> 01:06:35,180 menor número era. 1288 01:06:35,180 --> 01:06:38,510 Assim, enquanto a lista está fora de ordem, encontrar o menor número, coloque-o em 1289 01:06:38,510 --> 01:06:40,630 o início da lista, coloque o início da lista, onde o 1290 01:06:40,630 --> 01:06:42,900 menor número era. 1291 01:06:42,900 --> 01:06:45,780 Marcus, você pode reformular esta linha enquanto a lista está fora de ordem? 1292 01:06:45,780 --> 01:06:51,160 1293 01:06:51,160 --> 01:06:53,900 >> ALUNO: Embora os números não foram classificadas? 1294 01:06:53,900 --> 01:06:55,920 >> JASON Hirshhorn: OK, então, a fim de sabe que os números não foram 1295 01:06:55,920 --> 01:06:58,670 classificadas, o que precisamos fazer? 1296 01:06:58,670 --> 01:07:00,640 Quanto precisamos passar por essa lista? 1297 01:07:00,640 --> 01:07:09,650 >> ALUNO: Então eu acho que um loop, ou tempo, enquanto os números verificados é menor 1298 01:07:09,650 --> 01:07:11,900 do que o comprimento da lista de? 1299 01:07:11,900 --> 01:07:13,160 >> JASON Hirshhorn: OK, isso é bom. 1300 01:07:13,160 --> 01:07:15,000 Acho que misphrased minha pergunta mal. 1301 01:07:15,000 --> 01:07:15,990 Eu só estava tentando chegar nós vamos ter que ir 1302 01:07:15,990 --> 01:07:17,580 toda a lista. 1303 01:07:17,580 --> 01:07:20,490 Assim, enquanto a lista está fora de ordem, para mim, é difícil mapear diante. 1304 01:07:20,490 --> 01:07:24,940 Mas, basicamente, é assim que Eu penso sobre isso. 1305 01:07:24,940 --> 01:07:28,880 Vá até a lista inteira, encontrar o menor número, coloque-o no 1306 01:07:28,880 --> 01:07:30,130 começando - na verdade, você está certo. 1307 01:07:30,130 --> 01:07:31,380 Vamos colocá-los ambos. 1308 01:07:31,380 --> 01:07:33,470 1309 01:07:33,470 --> 01:07:39,050 >> Assim, enquanto a lista está fora de ordem, nós precisa passar por toda a lista 1310 01:07:39,050 --> 01:07:42,250 uma vez, encontrar o menor número, lugar que no início da lista, colocar 1311 01:07:42,250 --> 01:07:45,430 o início da lista onde o menor número era, e em seguida, se o 1312 01:07:45,430 --> 01:07:47,460 lista ainda está fora de ordem, nós temos tem que passar por isso 1313 01:07:47,460 --> 01:07:48,620 processo novo, certo? 1314 01:07:48,620 --> 01:07:51,610 É por isso que a seleção tipo, Big-O tempo de execução de seleção tipo, alguém? 1315 01:07:51,610 --> 01:07:52,830 >> ESTUDANTE: n ao quadrado. 1316 01:07:52,830 --> 01:07:53,590 >> JASON Hirshhorn: n ao quadrado. 1317 01:07:53,590 --> 01:07:57,040 Porque como Marcus e eu só percebi aqui, nós vamos ter que 1318 01:07:57,040 --> 01:08:00,310 percorrer a lista lista número de vezes. 1319 01:08:00,310 --> 01:08:03,420 Então passando por algo de comprimento n n número de vezes 1320 01:08:03,420 --> 01:08:04,990 é, de fato, n ao quadrado. 1321 01:08:04,990 --> 01:08:08,100 >> Então, este é o nosso pseudocódigo. 1322 01:08:08,100 --> 01:08:09,360 Isso parece muito bom. 1323 01:08:09,360 --> 01:08:11,870 Alguém tem alguma dúvida sobre o pseudocódigo? 1324 01:08:11,870 --> 01:08:14,440 Porque na verdade a seleção tipo deve provavelmente vir um para um, o código de 1325 01:08:14,440 --> 01:08:14,980 pseudocódigo. 1326 01:08:14,980 --> 01:08:17,569 Assim, qualquer dúvida sobre a lógica do pseudocódigo? 1327 01:08:17,569 --> 01:08:18,819 Por favor, pergunte-lo agora. 1328 01:08:18,819 --> 01:08:22,609 1329 01:08:22,609 --> 01:08:25,379 >> Tipo de seleção - enquanto a lista está fora de ordem, nós vamos passar por isso 1330 01:08:25,379 --> 01:08:27,529 e encontrar o menor de cada vez e colocá-lo na frente. 1331 01:08:27,529 --> 01:08:33,470 Assim, enquanto a lista está fora de ordem, pode alguém me venha com essa linha de código que 1332 01:08:33,470 --> 01:08:39,689 não me deu uma linha de código, no entanto, por favor? 1333 01:08:39,689 --> 01:08:40,939 Parece uma coisa? 1334 01:08:40,939 --> 01:08:43,669 1335 01:08:43,669 --> 01:08:44,649 >> ALUNO: Isso é um loop for. 1336 01:08:44,649 --> 01:08:45,830 >> JASON Hirshhorn: Parece gosto de um loop for. 1337 01:08:45,830 --> 01:08:47,653 OK, você pode me dar o loop? 1338 01:08:47,653 --> 01:08:48,925 Por - 1339 01:08:48,925 --> 01:08:50,219 >> ALUNO: i é igual a 0. 1340 01:08:50,219 --> 01:08:52,705 >> JASON Hirshhorn: i ou - 1341 01:08:52,705 --> 01:08:55,111 o que é que falta? 1342 01:08:55,111 --> 01:08:56,819 O que se passa aqui? 1343 01:08:56,819 --> 01:08:57,550 >> ALUNO: Int. 1344 01:08:57,550 --> 01:08:59,270 >> JASON Hirshhorn: Exatamente. 1345 01:08:59,270 --> 01:09:02,590 (Int i = 0; - 1346 01:09:02,590 --> 01:09:07,843 >> ALUNO: i 01:09:09,319 >> JASON Hirshhorn: pregado isso, Jeff. 1348 01:09:09,319 --> 01:09:10,660 Estamos passando por uma lista, certo? 1349 01:09:10,660 --> 01:09:11,880 Já vimos que o código antes. 1350 01:09:11,880 --> 01:09:12,850 Perfeito. 1351 01:09:12,850 --> 01:09:14,790 Então, vamos colocar nossas chaves aqui. 1352 01:09:14,790 --> 01:09:17,859 Vou colocar alguns chaves aqui. 1353 01:09:17,859 --> 01:09:21,660 >> Assim, embora seja 0, é preciso ir toda a lista. 1354 01:09:21,660 --> 01:09:26,612 Assim, cada vez que vamos a lista, o que queremos para acompanhar? 1355 01:09:26,612 --> 01:09:28,260 >> ALUNO: Se algum swaps são feitas. 1356 01:09:28,260 --> 01:09:29,069 >> JASON Hirshhorn: Encontre o menor número. 1357 01:09:29,069 --> 01:09:31,479 Então, nós provavelmente deve manter o controle de o número mais pequeno de cada vez. 1358 01:09:31,479 --> 01:09:34,590 Então linha que posso fazer para manter o controle do menor número? 1359 01:09:34,590 --> 01:09:37,720 Aleha, como posso manter pista de alguma coisa? 1360 01:09:37,720 --> 01:09:38,460 >> ALUNO: Iniciar uma nova variável. 1361 01:09:38,460 --> 01:09:39,390 >> JASON Hirshhorn: Iniciar uma nova variável. 1362 01:09:39,390 --> 01:09:40,069 Então vamos criar uma variável. 1363 01:09:40,069 --> 01:09:41,830 Qual o tipo? 1364 01:09:41,830 --> 01:09:42,930 >> ALUNO: Int. 1365 01:09:42,930 --> 01:09:43,710 >> JASON Hirshhorn: Int. 1366 01:09:43,710 --> 01:09:44,939 Vamos chamá-lo o menor. 1367 01:09:44,939 --> 01:09:47,600 E o que o faz igual quando nós estamos apenas começando? 1368 01:09:47,600 --> 01:09:48,910 Nós não passaram pela lista ainda. 1369 01:09:48,910 --> 01:09:50,540 Estamos na primeira parte do listar a nossa primeira vez. 1370 01:09:50,540 --> 01:09:51,930 O que não é igual, o menor número? 1371 01:09:51,930 --> 01:09:54,140 >> ALUNO: valores que eu. 1372 01:09:54,140 --> 01:09:54,900 >> JASON Hirshhorn: valores que eu. 1373 01:09:54,900 --> 01:09:56,980 Isso soa exatamente certo, certo? 1374 01:09:56,980 --> 01:09:59,590 O menor número no início é o lugar onde estamos. 1375 01:09:59,590 --> 01:10:01,960 Portanto, agora temos nosso menor, e precisamos para percorrer a lista inteira e 1376 01:10:01,960 --> 01:10:05,080 comparar este menor para tudo o resto. 1377 01:10:05,080 --> 01:10:08,150 Assim é que vamos percorrer a lista de novo? 1378 01:10:08,150 --> 01:10:08,630 Michael? 1379 01:10:08,630 --> 01:10:10,000 >> ALUNO: Você precisa fazer outro para loop. 1380 01:10:10,000 --> 01:10:10,383 >> JASON Hirshhorn: Outra loop for. 1381 01:10:10,383 --> 01:10:11,276 Vamos fazê-lo. 1382 01:10:11,276 --> 01:10:12,540 Dê-me algum código. 1383 01:10:12,540 --> 01:10:13,790 >> ALUNO: Para loop - 1384 01:10:13,790 --> 01:10:16,750 1385 01:10:16,750 --> 01:10:19,470 para os mais pequenos - 1386 01:10:19,470 --> 01:10:23,040 1387 01:10:23,040 --> 01:10:25,770 apenas int j, você poderia dizer? 1388 01:10:25,770 --> 01:10:31,150 = 0; tal que - 1389 01:10:31,150 --> 01:10:34,014 1390 01:10:34,014 --> 01:10:35,710 >> JASON Hirshhorn: Bem, se quisermos para percorrer a lista inteira - 1391 01:10:35,710 --> 01:10:37,847 >> ALUNO: j 01:10:42,140 1393 01:10:42,140 --> 01:10:42,405 >> JASON Hirshhorn: Fantastic. 1394 01:10:42,405 --> 01:10:46,100 Nós vamos passar por o loop for mais uma vez. 1395 01:10:46,100 --> 01:10:51,380 E como é que vamos encontrar o menor número? 1396 01:10:51,380 --> 01:10:52,630 Tom? 1397 01:10:52,630 --> 01:10:54,570 1398 01:10:54,570 --> 01:11:00,520 Temos a corrente menor número, então como é que vamos encontrar o novo menor? 1399 01:11:00,520 --> 01:11:07,200 >> ALUNO: Podemos verificar se o menor número que temos é maior do que 1400 01:11:07,200 --> 01:11:09,040 valoriza suporte j. 1401 01:11:09,040 --> 01:11:14,740 >> JASON Hirshhorn: Então, se é menor maior do que os valores do suporte j. 1402 01:11:14,740 --> 01:11:19,350 Portanto, se o nosso atual menor é maior do que - 1403 01:11:19,350 --> 01:11:21,770 Vou mover estas duas linhas de código lá fora por um segundo. 1404 01:11:21,770 --> 01:11:26,010 Porque, antes de fazer qualquer troca, nós precisa passar por toda a lista. 1405 01:11:26,010 --> 01:11:28,880 Portanto, este pseudocódigo deve realmente estar fora que interna para loop. 1406 01:11:28,880 --> 01:11:30,390 Então, percorrer a lista inteira. 1407 01:11:30,390 --> 01:11:34,520 Se é maior do que o menor valores j, então o que? 1408 01:11:34,520 --> 01:11:37,830 >> ALUNO: Então menor é igual a valores j. 1409 01:11:37,830 --> 01:11:41,190 1410 01:11:41,190 --> 01:11:42,600 >> JASON Hirshhorn: Fantastic. 1411 01:11:42,600 --> 01:11:44,580 Uma pergunta rápida - 1412 01:11:44,580 --> 01:11:47,236 a primeira vez que passar por este ciclo, i vai ser igual a 0, j vai 1413 01:11:47,236 --> 01:11:50,710 para igualar 0 uma vez que temos aqui. 1414 01:11:50,710 --> 01:11:52,410 Então, nós vamos estar comparando um certo número de si. 1415 01:11:52,410 --> 01:11:53,660 Isso é eficiente? 1416 01:11:53,660 --> 01:11:57,260 1417 01:11:57,260 --> 01:11:58,390 Não, ele não é realmente eficiente. 1418 01:11:58,390 --> 01:12:02,915 O mesmo acontece com o nosso j precisa ir de 0 a N de cada vez? 1419 01:12:02,915 --> 01:12:06,310 Será que sempre precisa verificar toda a lista? 1420 01:12:06,310 --> 01:12:06,520 [Inaudível]? 1421 01:12:06,520 --> 01:12:07,564 >> ALUNO: Comece com i vez. 1422 01:12:07,564 --> 01:12:09,405 >> JASON Hirshhorn: j lata começar com o que? 1423 01:12:09,405 --> 01:12:09,990 >> ESTUDANTE: i. 1424 01:12:09,990 --> 01:12:13,040 >> JASON Hirshhorn: j pode começar com i. 1425 01:12:13,040 --> 01:12:18,840 Então, agora nós comparar começando com aquele em que estamos. 1426 01:12:18,840 --> 01:12:21,020 Mas, mesmo assim, é que, como eficiente possível? 1427 01:12:21,020 --> 01:12:22,320 >> ALUNO: i + 1. 1428 01:12:22,320 --> 01:12:25,420 >> JASON Hirshhorn: i + 1 parece ser o mais eficiente, porque nós 1429 01:12:25,420 --> 01:12:26,120 já tem i. 1430 01:12:26,120 --> 01:12:28,100 Estamos afirmando que, como o menor na linha 15. 1431 01:12:28,100 --> 01:12:29,350 Vamos começar com o próxima automaticamente. 1432 01:12:29,350 --> 01:12:34,470 1433 01:12:34,470 --> 01:12:38,540 Então, nós passamos pelo loop for. 1434 01:12:38,540 --> 01:12:39,620 Vamos passar por cada vez. 1435 01:12:39,620 --> 01:12:40,860 Nós vamos passar por um número de vezes. 1436 01:12:40,860 --> 01:12:42,860 Agora que temos obtido através este interior para loop. 1437 01:12:42,860 --> 01:12:44,350 Temos o menor valor salva. 1438 01:12:44,350 --> 01:12:46,045 Precisamos colocá-lo no no início da lista. 1439 01:12:46,045 --> 01:12:48,390 Então, como faço para colocá-lo no no início da lista? 1440 01:12:48,390 --> 01:12:51,290 1441 01:12:51,290 --> 01:12:55,926 O que é a variável que se refere para o início da lista? 1442 01:12:55,926 --> 01:13:00,500 Estamos nisso fora para o laço, então o que se refere à 1443 01:13:00,500 --> 01:13:01,280 no início da lista? 1444 01:13:01,280 --> 01:13:02,880 >> ALUNO: valores que eu. 1445 01:13:02,880 --> 01:13:03,510 >> JASON Hirshhorn: Exatamente. 1446 01:13:03,510 --> 01:13:04,650 Os valores de i é o começo da - 1447 01:13:04,650 --> 01:13:06,320 ou desculpe, não o começo. 1448 01:13:06,320 --> 01:13:07,090 Isso foi confuso. 1449 01:13:07,090 --> 01:13:11,620 É onde estamos no início de a parte indiferenciados da lista. 1450 01:13:11,620 --> 01:13:12,800 Assim, os valores i. 1451 01:13:12,800 --> 01:13:14,050 E o que faz que a igualdade? 1452 01:13:14,050 --> 01:13:15,925 1453 01:13:15,925 --> 01:13:17,326 >> ALUNO: Menor. 1454 01:13:17,326 --> 01:13:18,862 >> JASON Hirshhorn: valores i é igual a quê? 1455 01:13:18,862 --> 01:13:19,310 >> ALUNO: Menor. 1456 01:13:19,310 --> 01:13:20,030 >> JASON Hirshhorn: Menor. 1457 01:13:20,030 --> 01:13:20,980 Exatamente. 1458 01:13:20,980 --> 01:13:23,510 Então, nós estamos colocando-o no início da lista, e agora é preciso colocar 1459 01:13:23,510 --> 01:13:25,710 o início da lista quando o menor número era. 1460 01:13:25,710 --> 01:13:29,700 Então como é que eu escrevo, onde o menor número foi? 1461 01:13:29,700 --> 01:13:31,670 Valores de quê? 1462 01:13:31,670 --> 01:13:33,170 >> ESTUDANTE: 0. 1463 01:13:33,170 --> 01:13:34,090 >> JASON Hirshhorn: O pequeno número está em 0? 1464 01:13:34,090 --> 01:13:35,340 >> ESTUDANTE: Yeah. 1465 01:13:35,340 --> 01:13:38,680 1466 01:13:38,680 --> 01:13:39,910 >> JASON Hirshhorn: E se o menor número foi no final 1467 01:13:39,910 --> 01:13:40,860 esta lista não ordenada? 1468 01:13:40,860 --> 01:13:42,460 >> ESTUDANTE: Desculpe, mas o que era a pergunta? 1469 01:13:42,460 --> 01:13:44,020 >> JASON Hirshhorn: Onde está o menor número? 1470 01:13:44,020 --> 01:13:46,940 Pegamos o menor e colocá-lo no começando com essa linha aqui. 1471 01:13:46,940 --> 01:13:48,987 >> ALUNO: Ela deve ter foram armazenados em algum - 1472 01:13:48,987 --> 01:13:50,510 >> ESTUDANTE: Os valores de j. 1473 01:13:50,510 --> 01:13:51,520 >> JASON Hirshhorn: Bem, é não necessariamente os valores j. 1474 01:13:51,520 --> 01:13:54,100 Ele nem sequer existe neste momento. 1475 01:13:54,100 --> 01:13:55,960 >> ALUNO: Você tem que declarar uma variável anteriormente e 1476 01:13:55,960 --> 01:13:58,230 em seguida, atribuí-la a - 1477 01:13:58,230 --> 01:14:01,150 quando você encontrar o menor número, atribuir o índice de que o número de 1478 01:14:01,150 --> 01:14:02,480 alguma variável ou algo parecido. 1479 01:14:02,480 --> 01:14:04,790 >> JASON Hirshhorn: Então pode você dizer isso de novo? 1480 01:14:04,790 --> 01:14:08,390 >> Estudante: Então, onde você declarou int menor, você também deve declarar int 1481 01:14:08,390 --> 01:14:10,750 menor índice = i, ou algo parecido. 1482 01:14:10,750 --> 01:14:13,280 >> JASON Hirshhorn: Então, onde eu int menor, não só deve manter o controle 1483 01:14:13,280 --> 01:14:16,150 do valor mas a localização. 1484 01:14:16,150 --> 01:14:20,850 int smallest_location = neste caso, vamos apenas fazer i. 1485 01:14:20,850 --> 01:14:22,390 Precisamos saber onde ele está. 1486 01:14:22,390 --> 01:14:26,820 Chegamos ao final do código, e nós percebemos que não tinha idéia de onde estava. 1487 01:14:26,820 --> 01:14:29,810 E assim, mais uma vez, estamos mapeamento este em um para um. 1488 01:14:29,810 --> 01:14:32,890 Vocês codificação isso em sua própria vontade provavelmente chegar ao mesmo problema. 1489 01:14:32,890 --> 01:14:34,130 Como diabos eu encontrá-lo? 1490 01:14:34,130 --> 01:14:36,720 E então você percebe, espere, eu precisa manter o controle disso. 1491 01:14:36,720 --> 01:14:38,500 >> Então, se é menor maior de valores j. 1492 01:14:38,500 --> 01:14:39,740 Nós estabelecemos menor é igual aos valores j. 1493 01:14:39,740 --> 01:14:42,090 O que mais é preciso mudar? 1494 01:14:42,090 --> 01:14:43,710 Constantin, o que mais é preciso mudar? 1495 01:14:43,710 --> 01:14:44,560 >> ALUNO: A localização. 1496 01:14:44,560 --> 01:14:45,270 >> JASON Hirshhorn: Exatamente. 1497 01:14:45,270 --> 01:14:46,925 Então me dê essa linha no código. 1498 01:14:46,925 --> 01:14:53,310 >> ALUNO: smallest_location = j. 1499 01:14:53,310 --> 01:14:54,790 >> JASON Hirshhorn: Exatamente. 1500 01:14:54,790 --> 01:14:58,210 E, em seguida, para baixo, no final, se quisermos colocar o início da lista, onde 1501 01:14:58,210 --> 01:15:00,790 o menor número era, como que nos referimos, onde o 1502 01:15:00,790 --> 01:15:02,200 menor número foi? 1503 01:15:02,200 --> 01:15:03,580 Marcus? 1504 01:15:03,580 --> 01:15:08,530 >> ALUNO: O menor número foi localizado em menor local. 1505 01:15:08,530 --> 01:15:12,230 >> JASON Hirshhorn: Então, em valores smallest_location. 1506 01:15:12,230 --> 01:15:14,700 E o que é que vamos colocar lá? 1507 01:15:14,700 --> 01:15:17,600 O início da lista, o que é isso? 1508 01:15:17,600 --> 01:15:19,710 >> ESTUDANTE: Bem, nós realmente não sabemos mais porque substituiu. 1509 01:15:19,710 --> 01:15:23,250 Portanto, é um locais trocados destas duas linhas? 1510 01:15:23,250 --> 01:15:26,110 Se você alternar essas duas linhas ao redor. 1511 01:15:26,110 --> 01:15:30,740 >> JASON Hirshhorn: OK, então nós não mais, porque nós redefinir a linha 1512 01:15:30,740 --> 01:15:31,960 antes de valores i para o menor. 1513 01:15:31,960 --> 01:15:33,810 Então, nós perdemos esse valor inicial. 1514 01:15:33,810 --> 01:15:37,350 Então você disse que troca essas duas linhas. 1515 01:15:37,350 --> 01:15:41,780 Então agora coloque o início da lista onde o menor número era. 1516 01:15:41,780 --> 01:15:47,060 Então smallest_location iguala valores i. 1517 01:15:47,060 --> 01:15:51,310 Isso está se movendo no início deste indiferenciados parte da lista para o 1518 01:15:51,310 --> 01:15:52,090 menor local. 1519 01:15:52,090 --> 01:15:54,860 E, em seguida, em valores i estamos nos movendo que menor número. 1520 01:15:54,860 --> 01:15:57,450 >> Isso faz sentido porque nós tinha que fazer essa troca? 1521 01:15:57,450 --> 01:15:59,650 Gostaríamos de ter substituído o valor - outra coisa que você provavelmente teria 1522 01:15:59,650 --> 01:16:02,740 descoberto e encontrado no PIB. 1523 01:16:02,740 --> 01:16:05,310 Então, nós temos tido o cuidado de tudo o pseudocódigo. 1524 01:16:05,310 --> 01:16:10,935 Há mais alguma coisa que precisa escrever aqui? 1525 01:16:10,935 --> 01:16:14,911 Alguém pode pensar em nada? 1526 01:16:14,911 --> 01:16:16,180 >> ESTUDANTE: Como você sabe quando você é feito? 1527 01:16:16,180 --> 01:16:17,680 >> JASON Hirshhorn: Como é que nós sabe quando estamos a fazer? 1528 01:16:17,680 --> 01:16:18,890 Ótima pergunta. 1529 01:16:18,890 --> 01:16:21,684 Então, como vamos saber quando estamos a fazer. 1530 01:16:21,684 --> 01:16:24,720 >> ALUNO: Crie uma variável para manter a contagem de se há uma troca feita ou não 1531 01:16:24,720 --> 01:16:27,810 e passar por um passe. 1532 01:16:27,810 --> 01:16:30,180 >> JASON Hirshhorn: OK. 1533 01:16:30,180 --> 01:16:31,800 Isso iria trabalhar em bubble sort. 1534 01:16:31,800 --> 01:16:35,210 Mas para a seleção de tipo, se não o fizermos fazer uma troca, que pode ser apenas 1535 01:16:35,210 --> 01:16:38,670 porque o menor valor é nele a sua localização. 1536 01:16:38,670 --> 01:16:41,240 Podemos ter uma lista 1, 2, 4, 3. 1537 01:16:41,240 --> 01:16:42,830 O segundo tempo através de nós não vai fazer nenhuma swaps. 1538 01:16:42,830 --> 01:16:47,260 Estaremos no número 2, mas vamos ainda precisa continuar. 1539 01:16:47,260 --> 01:16:49,390 Portanto, é preciso manter o controle de quando estamos a fazer, ou nós só quero ir 1540 01:16:49,390 --> 01:16:50,640 até que isso seja concluído? 1541 01:16:50,640 --> 01:16:54,098 1542 01:16:54,098 --> 01:16:56,740 >> ALUNO: Nós podemos apenas ir até que esteja terminado. 1543 01:16:56,740 --> 01:16:58,090 >> JASON Hirshhorn: podemos apenas ir até que isso seja concluído. 1544 01:16:58,090 --> 01:17:01,720 Em bubble sort, você está absolutamente certo, Jeff e Aleha, com a sua solução - 1545 01:17:01,720 --> 01:17:04,990 ele é ótimo para manter o controle de quantas swaps que você fez, porque na bolha 1546 01:17:04,990 --> 01:17:07,920 tipo, se você de fato não fazem swaps, você está feito e você pode talvez cortar o 1547 01:17:07,920 --> 01:17:09,000 problema um pouco. 1548 01:17:09,000 --> 01:17:11,440 Mas para a seleção de tipo, você tem realmente tem que ir até o fim do 1549 01:17:11,440 --> 01:17:14,940 listar cada vez. 1550 01:17:14,940 --> 01:17:16,200 >> Portanto, esta é isso. 1551 01:17:16,200 --> 01:17:18,530 Temos dois minutos do fim. 1552 01:17:18,530 --> 01:17:21,560 Vamos fazer tudo. 1553 01:17:21,560 --> 01:17:24,340 Deixe-me apenas aberta Encontre aqui e faça certeza que estou, de fato, chamar-se - 1554 01:17:24,340 --> 01:17:25,610 Não estou pedindo bubble sort. 1555 01:17:25,610 --> 01:17:29,230 Vamos mudar isso para seleção tipo. 1556 01:17:29,230 --> 01:17:31,060 fazer tudo. / find. 1557 01:17:31,060 --> 01:17:32,360 Vamos encontrar 42. 1558 01:17:32,360 --> 01:17:38,110 Desta vez, vamos passar um lista não ordenada, porque ele deve classificar 1559 01:17:38,110 --> 01:17:43,790 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, 1560 01:17:43,790 --> 01:17:44,995 procurar algo. 1561 01:17:44,995 --> 01:17:46,245 Dedos cruzados todos. 1562 01:17:46,245 --> 01:17:48,530 1563 01:17:48,530 --> 01:17:49,370 >> Oh meu Deus. 1564 01:17:49,370 --> 01:17:50,800 Whoa, meu coração estava batendo. 1565 01:17:50,800 --> 01:17:52,320 Então, isso é correto. 1566 01:17:52,320 --> 01:17:57,270 Na verdade, se nós corremos este mais extensivamente, o código, tanto quanto eu puder 1567 01:17:57,270 --> 01:17:59,280 dizer, é perfeitamente correta. 1568 01:17:59,280 --> 01:18:02,150 Existem algumas sugestões Eu tenho para você. 1569 01:18:02,150 --> 01:18:06,215 Por exemplo, 15 e 16 parecem um pouco redundante. 1570 01:18:06,215 --> 01:18:09,450 Parece que você não necessariamente precisa economizar tanto aqueles. 1571 01:18:09,450 --> 01:18:12,790 Se você tem o menor local, você pode facilmente encontrar o menor valor por 1572 01:18:12,790 --> 01:18:14,750 apenas digitando valores de i. 1573 01:18:14,750 --> 01:18:18,100 >> Então, se eu fosse o seu código de classificação, que eu vou ser de fato, eu o faria 1574 01:18:18,100 --> 01:18:21,160 provavelmente tirar um ponto, se você incluído ambos, porque você 1575 01:18:21,160 --> 01:18:22,670 não precisa de ambos. 1576 01:18:22,670 --> 01:18:25,400 Se você tem a localização, você pode facilmente obter o valor. 1577 01:18:25,400 --> 01:18:27,520 E parece um pouco estranho para armazenar os dois. 1578 01:18:27,520 --> 01:18:31,070 Talvez nem mesmo tomar um ponto, mas certamente comentar que essa é talvez 1579 01:18:31,070 --> 01:18:32,670 não é uma escolha estilística você precisa fazer. 1580 01:18:32,670 --> 01:18:35,290 Claro que, o código ainda funciona perfeitamente bem. 1581 01:18:35,290 --> 01:18:36,860 >> Então, infelizmente, não fez chegar a bubble sort. 1582 01:18:36,860 --> 01:18:37,940 Eu sinto muito por isso. 1583 01:18:37,940 --> 01:18:39,135 Fizemos acabamento seleção tipo. 1584 01:18:39,135 --> 01:18:41,450 Alguém tem alguma perguntas finais sobre a seleção de tipo? 1585 01:18:41,450 --> 01:18:44,320 1586 01:18:44,320 --> 01:18:47,690 >> OK, antes de sair, quero que você para abrir o seu navegador Chrome. 1587 01:18:47,690 --> 01:18:54,340 Desculpe, isso foi apenas um plug flagrante para um tipo de navegador de internet. 1588 01:18:54,340 --> 01:18:57,770 Você pode abrir qualquer tipo de navegador, mas provavelmente vai ser Chrome. 1589 01:18:57,770 --> 01:19:01,250 E ir a este seguinte site - 1590 01:19:01,250 --> 01:19:06,410 sayat.me/cs50. 1591 01:19:06,410 --> 01:19:07,685 Se você não está digitando em seu computador agora, você está claramente 1592 01:19:07,685 --> 01:19:10,210 não fazê-lo, Tom. 1593 01:19:10,210 --> 01:19:12,870 >> E, por favor fazê-lo também direito agora ou na próxima hora - 1594 01:19:12,870 --> 01:19:14,260 dar-me algum feedback. 1595 01:19:14,260 --> 01:19:15,660 Esta é apenas a seção dois. 1596 01:19:15,660 --> 01:19:18,060 Temos muitos mais juntos, então eu tem um monte de espaço para melhorar. 1597 01:19:18,060 --> 01:19:19,620 Eu espero que também fez bem algumas coisas. 1598 01:19:19,620 --> 01:19:22,160 Então você pode me fazer sentir de todo ruim, mas se você também quiser me dar um smiley 1599 01:19:22,160 --> 01:19:24,250 cara, eu gostaria de receber isso também. 1600 01:19:24,250 --> 01:19:25,330 Encha que dentro 1601 01:19:25,330 --> 01:19:28,210 >> E com um minuto para a esquerda, que foi de três semanas. 1602 01:19:28,210 --> 01:19:30,750 Eu vou ficar fora por um tempo se você tiver quaisquer perguntas. 1603 01:19:30,750 --> 01:19:32,220 Eu vou ver vocês em palestra amanhã. 1604 01:19:32,220 --> 01:19:34,742