Jason Hirschhorn: Welcome a semana tres, todos. Temos un ocupado, pero emocionante sección á fronte de nós. Entón, primeiro, porque fixemos algúns progreso co curso, pero aínda ten unha morea de aprendizaxe deixou de facer, eu son vai amosar a vostedes algunhas funcións que debe probar ser incrible útil, non só se achega do seu conxuntos de problemas, pero tamén dixerir todo o material que dar a vostedes en conferencias e shorts e sección. Entón imos pasar o primeiro 20 25 minutos de sección pasando por riba GDB, que pode ou non pode ter usado neste momento, pero iso é unha ferramenta incrible útil que vai axudar a depurar os seus programas. Moitos de vostedes poden usar printf no medio do seu programa para descubrir o que unha variable igualado. GDB é aínda mellor printf e non romper o seu código, porque executa-lo nun arquivo executable. Entón, imos pasar por riba dos 10 máis útil as ordes que precisa para o GDB, e estamos indo a ir nun exercicio conxunto para no conxunto de problemas de tres e ademais, ten pode usar GDB para axudar a depurar seus programas. E, finalmente, imos pasar por riba de algúns clasificación e busca de algoritmos que viu na aula, e nós somos vai realmente código, non só pseudocódigo, pero o código de busca binaria, bubble sort, e selección de clasificación. Entón, primeiro, quero ir sobre os recursos. Esta é unha lista extensa, e é fonte máis pequena, porque eu tiña unha morea de caber aquí. Pero estes non só ha axudar, de novo, cos conxuntos de problemas e dixerindo información que aprendeu, pero en definitiva, chegou o momento da proba, estes serán ser moi útil. Entón, primeiro, a charla observa. Se vai para cs50.net/lectures e desprácese ata a semana e día específico, vai ver que hai notas para cada charla, que non é simplemente unha transcrición, pero unha versión editada de o que foi abordado en charla con código fragmentos e outros tapas útiles. Recomendo ir sobre aqueles. E despois, ben, non hai código fonte dispoñible a partir de cada charla. E, de novo, estes diapositivas tamén será dispoñible en liña en cs50.net/sections esta noite. Así, segundo son os shorts cada semana que abranguen temas, xeralmente de 5 a 15 minutos de duración. E aqueles espero veña a darlle unha gran cartilla sobre diferentes temas. Terceiro - e iso é novo este ano - é study.cs50.net. Se aínda non verifiquei, eu recomendo que faga iso. Comeza a escoller un tema. Temos decenas de temas sobre alí. Así, por exemplo, escolle Funcións. Dálle algúns diapositivas e notas sobre funcións. Estes son realmente os diapositivas que TFS son animou a usar durante a nosa presentacións na sección. Tamén hai consellos e trucos para xestionar con funcións, e non hai problemas prácticos que axudan traballa con funcións. Tamén darlle enlaces a curto no funcións e os tempos que as funcións veñen-se na charla. Entón study.cs50.net, a nova marca presente ano, un recurso fantástico. Logo, eu teño o home, que é a guía orde que pode ser executado no liña de comandos. Entón, se ten algunha dúbida sobre a orde, por exemplo, rand, que nós atopou a semana pasada durante a sección e probablemente atopou en seu conxunto de problemas cando pasar polo xerar o código, pero se introducir home rand, terá a páxina que dille todo sobre o rand. Dálle o que fai falta, a parámetros que leva, así como o retorno tipo e unha breve descrición desta función. Entón confía Rand. Pode ser un pouco prolixo e confuso, polo que ás veces eu creo que simplemente buscando o que quero saber é o mellor xeito de atopar a resposta. Así, a práctica con Google. Obter bos en Google. Vai chegar a ser o seu mellor amigo. Así como Google, se non pode atopalo en Google, cs50.net/discuss, é o foro de discusión. Probablemente, se ten unha pregunta, unha dos seus 700 + pares tamén ten que cuestión e pode ter pedido xa na discusión foros e telo respondeu. Entón se ten unha pregunta común ou Ten unha pregunta que pensa quizais outras persoas poidan ter executado en, confía cs50.net/discuss. Finalmente, os dous últimos, se quere falar cun ser humano real, oficina horas de luns a venres. Hai tamén o horario de oficina en liña para os alumnos de extensión. E por último pero non menos importante, me, signo de admiración. Vostedes todos teñen a miña información de contacto. Se precisa de algo, por favor, nunca dubide en contactar-me. Sempre a vontade para facelo. Moi poucos de vostedes xa me engadiu no Gchat, de xeito que foi decepcionante, pero espero que isto vai cambiar entre neste e no próximo apartado. Calquera dúbida ata agora sobre os recursos? Grande. Por último, outra ficha para feedback, sayat.me/cs50. Vostede me pode dar un feedback anónimo sobre como eu estou facendo. Isto foi moi útil a semana pasada. Eu teño un par de comentarios de vostedes logo da sección, máis de outros alumnos que asistiron durante a semana, e foi incrible útil. Vou tentar limitar o meu uso de a palabra "doce", pero vou amosar o meu entusiasmo e emoción noutras formas. Mais había outro adicional feedbacks substantivas, ambos os pros e delta. Entón, por favor, eu dou a vós un feedback nos seus conxuntos de problemas. Sinto-se libre para me dar feedback no meu ensino. Estou aquí para vós. Grande. Isto é todo o que eu teño para a primeira sección. Alguén ten algunha preguntas ata agora? E eu teño unha nota para o centro de control. Os alumnos teñen me enviou mensaxes de Extensión dicindo que non está a recibir ningún son, pero que está fóra do meu alcance para corrixir. Polo tanto, agardamos, que recibe resolto pronto. Se está a asistir en liña, ola, pero non me pode escoitar. Entón, primeiro, imos pasar por GDB. GDB, como suxerido anteriormente, é unha ferramenta de depuración moito mellor que printf. Entón, para comezar co GDB, xente, se quere abrir o seu dispositivo e levar o arquivo que eu enviado a vostede anteriormente - este ficheiro tamén será dispoñible en liña en algo - e executar GDB. / nome do ficheiro. En primeiro lugar, por suposto, ten que compilar ficheiro porque GDB só funciona en arquivos executable. Pero se quere comezar GDB, o primeiro que fai, realizar GDB. / César. Entón ese é o nome do programa que estamos indo a ir con el agora. Entón eu vou escribir facer César, que me vai dar un arquivo executable aquí destacadas en verde. E entón eu vou correr GDB. / Cesar. E alí vai vostede. Vostede ve que temos un texto a dicirme sobre a versión do GDB, dándome unha información sobre a garantía, e entón nós ter o poder do PIB, o que parece tipo de como a nosa liña de comandos, pero ve que está aberto paren, GDB, paren próximos. Antes de seguir e depurar este ficheiro que enviei a todos vostedes, imos ollar para algúns comandos útiles para que ter un sentido de que estamos indo a cubrir. Estes comandos están listados aquí no orde en que eu normalmente uso deles. Entón eu comezo o meu programa, executando GBD. / Nome do programa, neste caso, César. E entón o primeiro que fago do 99,9% do tempo é dicir tipo de quebra. Isto define un punto de ruptura na principal. En esencia, o que está facendo alí é o programa que vai parar en principal para que poida comezar a examina-lo liña por liña, en vez de correr todo o camiño. Pode romper en diferentes puntos o seu código, pero principal é xeralmente unha bo lugar para comezar. O seguinte comando corro é executado. Iniciarase o programa en execución, e se ten que escribir a liña de comandos argumentos, se executa-lo comando. Correr cos argumentos. Entón, xa que estamos pasando por riba dunha versión de C, que é o programa que vostedes escribiu para pset dous - este, por suposto, ten algúns erros nel que espero que nós imos atopar - imos correr correr con algún comando argumentos de liña por César, como vostedes saben por o problema definir especificacións, leva algún Argumentos da liña de comandos. O seguinte par de comandos, o seguinte un é realmente chamado axiña. Aquela leva liña por liña a través do seu programa. Entón bater n despois Enter leva á seguinte liña, a execución de a liña anterior. Paso non só leva a a seguinte liña, pero lévao funcións dentro. Polo tanto, se escribiu unha función en o seu código ou se quere explotar un para i, por exemplo, pode bater s, e en vez de ir á seguinte liña de o ficheiro que está pasando agora, vai realmente entrar esta función e ver o seu código. Lista mostra, en moi agradable formato, os 10 ou máis liñas ao redor onde está actualmente no seu código así pode realmente ver o ficheiro ao contrario de ter que cambiar de volta e outro entre diferentes puntos de vista. Imprimir é como printf, como o propio nome indica. Iso mostra o que unha variable é igual. Información local é realmente útil. Esta é unha versión especial de impresión. Información local mostra todo o lugar, variables, imprime todos eles para vostede para fóra que están actualmente dispoñibles. Entón, eu normalmente, en vez de ter que imprimir as catro variables que eu son curioso sobre se eu estou en un loop, por exemplo, eu só escribo informacións locais, e só pode me que o meu contador eu mostro é igual a, así como a matriz que eu son traballar en parellas. Por último, continúe. Escribindo pausa vostede para no punto de quebra. Pode andar a través da liña por liña co próximo e paso. Seguir executa o programa para o seu próximo punto de romper ou ata a conclusión se non hai máis puntos de quebra. Desactivar elimina puntos de quebra, se decidiu que a pausa no principal era axeitado, quere define-lo noutro lugar. E, finalmente, q, saír, sae do GDB. Polo tanto, este programa,. / César, imos a ollar a través de agora e nós vai utilizar GDB para atopar os erros neste programa. Corre este programa anterior con Consulte o 50, e eu teño unha carranca. Todo o que existía, compilado, pasaron moitos das probas, pero a algunha razón, el non pasou da quinta proba, transformando BARFOO, as maiúsculas, en Correo-D-U-I-R-N, as tapas, mediante tres como unha chave. Teño moi preto. Descendín por unha letra. Polo tanto, hai un pequeno erro aquí. Eu olhei a través do meu código. Eu non podía entender. Espero que vós poidan me axudar descubrir o que é ese erro. Entón este é o erro que estamos procurar. Imos pasar en GDB. Unha vez máis, eu executar GDB. / César, entón agora estamos en GDB. E o que é o primeiro cousa que eu teño que facer? Acaba entrou GDB. Alguén me dea unha boa mando para entrar. ALUMNO: Rompe principal. Jason Hirschhorn: Rompe principal. Fantástico. Imos escribir que dentro Podedes ver aquí enriba ou seguir ao longo dos seus ordenadores. Rompe principal, e podes ver unha punto de ruptura foi fixado en - dáme un enderezo de memoria estraño, e tamén me dá o número da liña. Se eu ollar cara atrás, este ficheiro, Eu ía entender que o principal pasou na liña 21. ¿Que debería facer o seguinte? É o meu programa en execución? Non Entón, o que eu debería facer o seguinte? ALUMNO: Executar. Jason Hirschhorn: Executar. Debo só correr correr, ou debería Eu engadir algunhas outras cousas en? ALUMNO: Executar co argumento. Jason Hirschhorn: Corre con os argumentos do comando. E xa que estou a depuración dun ben específico caso, eu debería entrar nese argumento de liña de comandos. Entón, eu vou facer correr tres, o que é, de novo, a saída que eu teño de check 50. Comezando programa. Pasamos por un par de liñas. Vai ver agora que estamos na liña 21. Como sei que estamos na liña 21? Porque se ollar para a esquerda da miña fiestra da terminal, non el di que liña 21. E iso me dá, en realidade, a código que está na liña 21. Entón eu misspoke antes. Principal non é realmente na liña 21. Principal é un par de liñas por riba de 21. Pero na liña 21, que se onde estamos rompendo. Esta liña de código ten aínda non executados. Isto é importante. A liña que ve non ten executou aínda. Esa é a seguinte liña de código está a piques de executar. Polo tanto, a seguinte liña, como vostedes son Probablemente está familiarizado con, iso é condición comprobando a ver se eu teño entrou nun argumento de liña de comandos. E a ata i, que é o segundo parte do que está facendo? ¿Que é un ai? ALUMNO: cambia-lo para un número enteiro. Jason Hirschhorn: Sentímolo? ALUMNO: Está cambiando o argumento para un número enteiro. Jason Hirschhorn: Entón ao i cambia arg v1 dunha cadea a un enteiro. E entón o que é o que a comprobación? ALUMNO: Se hai unha segunda argumento de liña de comandos, ademais coa execución do programa. Jason Hirschhorn: E o que é a segunda metade deste Expresión booleana cadea? Esta parte aquí, ao i? ESTUDANTE: Se é negativo. Jason Hirschhorn: Asegurarse de que? ALUMNO: Asegurarse de que É, de feito, positiva. Jason Hirschhorn: Exactamente. Esta é a verificación para ver se é negativo e se é negativo, eu teño un sentimento á fila forza serme berrar co usuario. Entón, imos bater final para realizar esta liña. Nós non vemos que a liña que vostedes quizais esperaba ver a berrar co usuario e, a continuación, regresar, xa que esta liña non foi executada. Entrei 3. Así que tiña, de feito, entrar dous comandos argumentos de liña, e 3 é maior que cero. Entón vimos que a liña, asinamos, pero non paso dentro do estado. Entón, agora, ao lado, vexo que estou definindo clave int coincide co i arg v1. Entón ese é me creando unha clave variable. Entón, se eu imprimir clave agora, porque que permite que vexa o valor dentro da variable, clave é igual a 47. Isto é raro, pero por suposto, iso é porque eu non teño realizada esta liña aínda. Polo tanto, agora que eu bater n, executar esta liña, e facer tecla de impresión, a clave será igual a 3, que é o que esperamos que sexa igual. Entón, de novo, en GDB, a liña que ver que non teña executado aínda. Ten que bater N ou S ou un número doutros comandos para realmente executar esta liña. Chave de impresión. Da chave en 3. Tan lonxe, tan bo. Cadea é claro. Imos realizar esta liña. Estou recibindo unha secuencia de usuario. A ver o meu check 50, I entrar BARFOO todas as tapas, de xeito iso é o que eu vou entrar. Se eu agora imprimir texto puro. Verá que é igual a unha cadea. Dáme algún outro hexadecimal estraño número, pero non en feito de dicir que a miña cadea é BARFOO. Se eu quixese ver o que equivalía a clave Neste punto, como eu podería comprobar chave? ALUMNO: clave de impresión. Jason Hirschhorn: clave de impresión, exactamente. E, de feito, hai un acceso directo. Se queda canso de escribir impresión, pode só escribir p. Así clave p fai o mesmo exacta. E unha vez máis, eu vexo isto é igual a 3. Se eu quixese descubrir o que tanto clave e BARFOO igualado á vez pero eu estaba canso de escribir cada un individualmente, eu pode escribir información locais. Tanto me dá iguais clave 3. Texto coincide BARFOO. Tamén me dá esas dúas cousas estrañas na parte superior, esta variable i e iso n variable. Esas son realmente existente no meu programa principal. Non os atopou aínda, pero como un preview, aqueles hai no meu loop for. Entón, agora, igual algún estraño números, porque non foron iniciar aínda, pero eles aínda existen na memoria, polo que son só definir para un valor de lixo. Pero vemos clave na chaira texto alí mesmo. Entón, eu estou indo a executar esta liña, liña 34, o loop para. Imos ir ao loop for por bater n. E nós estamos dentro do loop for. Estamos no noso primeiro cheque. E, de novo, estes deben tipo de ollar familiar para ti, porque esta era unha Programa César que foi escrito, pero unha vez máis, ten algún tipo de erro. E agora se eu fai informacións locais, porque eu son dentro daquel loop for, verás que i é igual a cero, como esperamos. Iso é o que define-lo como e iniciar el no loop for. n é igual a 6. Isto tamén ten sentido, xa que partimos lo para o strlen de texto simple. Entón, gustaríame facer Información veciños ou impresión a variable moitas veces para asegurarse de que todo é sempre o que Espero que sexa igual. Neste caso, todo está o que eu espero que sexa igual. Entón, imos comezar a moverse a través de iso por loop. A liña que estou é a liña 36, ​​simple i texto é maior que unha simple e i texto é inferior ou igual a z. Sei que o meu problema non é co meu primeiro carta, é coa segunda carta. Mira cara atrás no Check 50, B vai a E ben. Estou levando a A e deixar como un A, non cambia-lo para D. Así, algo está mal con a segunda letra. Entón, eu estou indo a mover alí en un segundo. Pero se eu quería comprobar o que simple texto que igualou nese particular caso, eu creo que debería ser o que? O que debe texto simple eu igualar neste primeira rolda a través do loop for? ALUMNO: Cero? Jason Hirschhorn: Texto simple de I? Por iso, debe ser de capital B. I, por suposto, é igual a cero, pero de texto soporte de cero soporte pechado é igual a B porque cordas, como vimos a semana pasada, son array, polo que estamos a recibir o primeiro carácter a partir de aí. Entón, de novo, se eu impresos texto Eu, eu, de feito, obter o carácter B. E iso é puro, non? Realmente non ten texto simple I. Isto non é unha das variables que establece ou iniciar, pero pode imprimir toda unha serie de cousas se desexa. Pero imos percorrer. O texto simple que é maior que un e texto simple que é inferior ou igual a Z, que claramente é verdade, porque temos un capital B. Vou correr algún mando sobre el. Vimos que a matemática, a semana pasada, polo que imos é un dato adquirido que funciona dereito segundo Consulte 50. Estas claves, a primeira amosa que eu estaba saíndo do caso condición, o segundo amosa que estou saíndo do loop for. E agora cando bati Abaixo, imos ver estamos de volta no loop novo. Estamos atravesando o loop de novo. Imos realmente entrar na segunda iteración do bucle e tipo Información locais. Entón, nós estamos na segunda iteración do noso loop for. I é igual a 1, o que esperamos. N é igual a 6, o que esperamos. Clave é igual a 3, o que esperamos. E de texto simple, vai ver, é igual a EARFOO agora, non máis porque BARFOO no noso iteración anterior, o B foi cambiado un capital E. Entón, nós estamos sobre para atopar o problema, de xeito que este é o lugar onde nós estamos indo mergullo na depuración. Pero alguén ten algunha dúbida sobre o que fixemos ata agora? Fantástico. Entón, nós estamos a piques de realizar este condición, soporte de texto simple Pechei soporte maior que A e texto simple I inferior ou igual a Z. Pero antes Eu vou entrar niso, porque é onde Sei que o meu erro é que quero apuntar fóra de texto de I. Así, imos poñer impresión. Fai igual a un personaxe, de xeito que parece de momento, todo está ben e bo. Entón, eu espero que esta liña pola miña lóxica, esta liña debe ser verdadeira. É unha letra maiúscula. Pero se eu acertar n, nós entendemos que este liña, de feito, non foi executada. Eu pulei ata o else if. Por que isto aconteceu? ALUMNO: Porque ten a súa condición simple texto é maior que A, non é igual ou maior que. Jason Hirschhorn: Entón, eu tiña o meu texto I é maior que A, non maior que ou igual a. Entón, claramente, a capital A non desencadear esta condición, e nós fixemos non entrar nel, e nós fixemos non facer o cambio necesario. Entón é iso, en realidade. Eu descubrín o meu erro. Eu puidese volver o meu arquivo de orixe, mudalo, e actualiza-lo e realizar Consulte 50 de novo. Pero imos ver, só por pedagoxía de ben, se eu continuar. A outra se non realizar calquera, pero o que equivale a vez é a orde que non cambia. Por iso, non cambiou en todo, e se eu imprimir texto plano aquí, imos ver indo través dese lazo é non, en realidade, cambiar ese segundo personaxe en todo. É aínda un capital A. Entón, de novo, nós depurado noso erro. Entender que non había algunha lóxica en falta. E nós depurado-lo antes de tempo antes realmente executar esta liña, pero que tería notado se tivésemos só Axiña bater e ir para que else if, isto significa que que se a condición non era verdade. Non, en realidade, obter o resultado que esperabamos. Entón nós podería ser solicitado, tivo non foron tan astuto, a ollar para que se a condición e comprobar que, de feito, nosa condición debe avaliar a realidade no contexto actual. Isto é todo para a depuración deste programa. Alguén ten algunha dúbida? A orde que eu podería bater para saír GDB? Q. E entón eu vou ser solicitado, saír de calquera maneira? Si ou non. Vou bater si, e eu vou desistir GDB. Así, foi un primera rápido para GDB. De feito, nun escenario real, Eu fixen iso en horario de oficina. Eu GDBed este programa exacto en horario de oficina con un estudante. E se volver para os comandos que vimos antes, usan rotura principal, en primeiro lugar que fixemos. Nós acostumabamos correr con argumentos de liña de comandos, segunda cousa que fixemos. Usan moi preto de moverse nós a través de liñas. E, de novo, a versión curta de seguida é n. Isto é entre parénteses en gris no slide. Non utilizar o paso, pero non o fixemos necesariamente ten para este caso. Pero podemos usalo en un pouco máis tarde hoxe se está depurando, por exemplo, busca binaria cando binario investigación chámase nun separado función, pero non hai algún erro con el. Nós imos querer entrar a chamada a busca binaria e realmente depurá-lo. Lista que non use, xa que tivemos un bo sentido do noso código, pero se eu quería ter unha noción do código que eu estaba por preto, eu podería só lista usar. Imprimir usan, información local que usan. Continuar nós non precisamos usar neste caso, tampouco hai que empregar desactivar, pero fixemos uso desistir. Unha vez máis, estes 10 mandamentos, practicalo los. Se entender estes 10 mandamentos, ten que ser definido para a depuración de calquera Problema con GDB. Entón, nós estamos a piques de ir, de novo, ao cerne da sección de hoxe, pasando por riba estes clasificación e investigación algoritmos. Antes de facelo, unha vez máis, as preguntas, comentarios, preocupacións para GDB? Entón está todo o mundo vai usar GDB no canto de printf? Entón todo o mundo, polo amor de perpetuidade, todo o mundo está bailando a cabeza dereita agora, entón eu vou te ver no horario de oficina e todo TFS vai velo e eles van dicir, me amosar como usar GDB, e vai ser capaz para amosalos, non? Máis ou menos? Poida que eu espero. Legal. Entón imos pasar para clasificación e investigación. Vai ver que eu teño unha lista xa clasificadas para nós, pero que non vai ser o caso sempre. Así, o problema de especificación definida para conxunto de problemas de tres, ten calzóns que pode asistir, e realmente pídelle para ver os calzóns. Tamén en charla a semana pasada fomos moitos destes algoritmos, polo que estou non vai pasar o tempo na clase vai sobre estes algoritmos de novo ou deseño fotos de como estes algoritmos funcionan. Unha vez máis, esta información pode re-reloxo charla, ou que a información é capturado excepcionalmente nos calzóns para estas investigacións, todas que están dispoñibles en cs50.net. Entón, en vez diso, o que nós imos facer é escribir estes programas. Temos un sentido, un modelo mental, de como eles traballan, e así o que imos facer é codifica-las de verdade. Imos transformar ese modelo mental, esa imaxe, se quere, ao código real. E se fose un pouco confuso ou nebuloso sobre o modelo mental, eu totalmente entender. Non estamos indo realmente para ir para o código de inmediato. Así, mentres esta solicitude neste slide pregunta vostede codificar busca binária, e en realidade, unha versión interactiva de busca binaria, o primeiro que eu Realmente quero que faga é escribir un pseudocódigo. Entón, ten ese modelo mental de como funciona a procura binaria. Tome unha folla de papel se ten un pronto dispoñible, ou abrir unha editor de texto, e gustaríame todo o mundo para escribir. Tomar catro minutos para escribir a pseudocódigo para a procura binaria. Unha vez máis, pensar sobre ese modelo mental. Eu virei arredor se ten dúbidas e podemos deseñar a imaxe para fóra. Pero en primeiro lugar, antes de comezar a programación, Gustaríame escribir a pseudocódigo para busca binaria entón cando nós mergullo, temos algunha dirección que a onde hai que ir. ESTUDANTE: Podemos asumir a matriz de valores que recibimos xa están clasificados? Jason Hirschhorn: Entón por busca binaria para o traballo - excelente pregunta - vostede ten que levar nun ordenado matriz de valores. Entón supoño que vai funcionar. Nós imos voltar a este foto. Verá en vermello a función declaración é bool binary_search int valor, valores int, int n. Este debe ser familiar se ten xa se achegou ou obtido o as mans sucias co conxunto de problemas. Pero esa é a súa declaración da función. Unha vez máis, non se preocupe tanto neste momento. O que eu realmente quero que a facer é tomar catro minutos para binario pseudocódigo buscar, e despois imos máis de que, como un grupo. E eu vou chegar preto. Se ten preguntas, Sinto libre para levantar a súa man. Por que non tomar máis de dous minutos para rematar o pseudocódigo? Sei que isto pode parecer ridículo que estamos gastan tanto tempo con algo que non é certo, mesmo en C, pero sobre todo para estes máis algoritmos reto e problema conxuntos que debemos descubrir, comezando en pseudocódigo non se preocupar sobre a sintaxe, só preocuparse a lóxica, é incrible útil. E dese xeito, non está resolvendo dous problemas moi difíciles ao mesmo tempo. Está só concentrarse na lóxica, e entón se move para a sintaxe. Aceptar. Imos comezar pasando o pseudocódigo. Xa escribín aquí enriba, binario Busca pseudocódigo. Imos escribir isto na embarcarse xuntos. Ou eu vou gravala-lo e vai dar me as instrucións que eu teño. Entón, alguén me pode dar o primeiro liña do pseudocódigo ti escribiu para procura binaria? Si, Annie? ALUMNO: Mentres a lonxitude do lista é maior que cero. Jason Hirschhorn: Mentres lonxitude dunha lista maior que cero. E unha vez máis, vemos algúns C-looking sintácticas cousas aquí. Pero a maior parte desta está en inglés. Alguén ten algunha liña puxeron antes diso na súa pseudo-código? ESTUDANTE: Obter unha matriz clasificados de números. Jason Hirschhorn: Vostede escribiu: "ter unha matriz de números ordenados. "Per o declaración da función, estaremos pasando unha matriz de números ordenados. Estudante: [inaudível]. Jason Hirschhorn: Entón teremos iso. Pero si, se nós non temos iso, nós sería necesario para ordenar a nosa gama de números, porque de busca binaria só funciona en matrices ordenada. Así, mentres a lonxitude da lista é igual a cero, eu son indo a poñer nalgunhas claves para facela un pouco máis como C. Pero agora, parece ser mapeado a unha while, para que dentro deste tempo loop de que necesitamos para facer por busca binaria? Alguén que non me deu un responder aínda, pero quen escribiu isto? ESTUDANTE: Ir a través da lista. Jason Hirschhorn: Tom Ir ao medio da lista. E a pregunta follow-up, o que facemos xa que estamos no medio da lista? ALUMNO: Fai unha comprobación se isto é o número que está a procurar. Jason Hirschhorn: Excelente. Ir a través da lista e comprobe se o seu valor está alí - fantástico. Alguén ten algo que era diferente do que iso? Isto é exactamente correcto. O primeiro que facemos en busca binaria é ir para o medio da lista e comprobar a ver se o seu valor está aí. Así que supoño que se o noso valor é alí, o que imos facer? ALUMNO: Nós voltar cero [inaudível]. Jason Hirschhorn: Si, se a nosa valor está aí, nós a atopamos. Así, podemos dicir dalgún xeito, con todo, este función é definida, dicimos que o usuario que atoparon. Se non está aí, con todo, que é onde iso está complicado. Entón, se non está alí, alguén que estaba a traballar na procura binaria ou ten unha idea, agora, o que imos facer? ALUMNO: Pregunta. Jason Hirschhorn: Si? ALUMNO: É a matriz xa clasificadas? Jason Hirschhorn: Si, estamos asumindo a matriz xa está clasificada. ALUMNO: Entón tes que comprobar se o valor que se ve é maior que o valor que quere, pode mover-se para o medio da outra metade. Jason Hirschhorn: Entón, se o medio de a lista é maior que o que estamos buscar, entón nós facemos o que? Nós nos movemos cara a onde? ALUMNO: Quere pasar a a metade da lista de Números máis baixos que a. Jason Hirschhorn: Entón nós imos chama iso de esquerda. Entón, se medio é maior, podemos buscar a metade esquerda da lista. E, a continuación, a través de busca, o que quero dicir con investigación? Estudante: [inaudível]. Jason Hirschhorn: Imos para o medio. Nós realmente repetir iso. Volvemos a través do noso loop while. Vou darlle o último - entón, se, medio é menos que o que o que facemos, o que facemos aquí? ALUMNO: Vaia á dereita. Jason Hirschhorn: Procura da dereita. Este parece ser bo, pero alguén ten calquera cousa que pode estar falta ou calquera outra cousa que poñer no seu pseudo-código? Entón, iso é o que temos ata agora. Mentres que a lonxitude da lista é maior que cero, estamos indo a ir para o medio da lista e comprobar se o seu valor está aí. O medio é maior, nós imos buscar á esquerda, máis se o medio é menos, imos buscar a dereita. Entón, todos tivemos algunha familiaridade con os termos que usan en ciencia da computación e as ferramentas que temos. Pero xa vai notar que estabamos falar en inglés, pero atopamos un chea de cousas que parecían mapear a ferramentas que temos no noso kit de ferramentas de codificación. Entón, logo de cara, non estamos vai realmente codificar aínda. O que vemos aquí en inglés que os mapas para cousas que podemos escribir en C? ALUMNO: While. Jason Hirschhorn: While. Polo tanto, este tempo aquí mapas sobre o que? ESTUDANTE: Un loop while. Jason Hirschhorn: Un loop while? Ou, probablemente, máis xeralmente, un ciclo. Queremos facer algo máis e máis. Entón, nós estamos indo a codificar un loop. E xa sabemos, porque nós fixemos isto un par de veces e nós temos moitos exemplos por aí, como realmente de escribir este índice para un loop. Entón iso debe ser moi doado. Debemos ser capaces de obter esta comezou moi rapidamente. Que máis podemos ver aquí? Que outras estruturas sintaxe, as cousas que estamos familiarizados coa C, que xa ten un sentido de base fóra das palabras que usan? Si, Anna? [Inaudível] só a xogar. Anna, vai adiante. ALUMNO: Se e máis. Jason Hirschhorn: Se e máis - ben aquí. Entón, o que os se parece? ALUMNO: Unha instrución if else. Jason Hirschhorn: Si, condicións, non? Por iso, probablemente vai ter escribir algunhas condicións. E, de novo, aínda que quizais confuso en en primeiro lugar, nós normalmente teñen un sentido agora de como escribir as condicións e a sintaxe para as condicións. E se non o facemos, nós só buscar o sintaxe para condicións, cortar e pegar iso, porque sabemos que necesitamos aquí unha condición. Calquera outras cousas que vemos que o mapa en cousas que pode ter que facer en C? Si, Aleha? ALUMNO: Isto pode ser obvio, só comprobar se un valor é igual a algo. Jason Hirschhorn: Entón, como imos comprobar e - por iso, ir para o medio da lista e asegúrese de que o seu valor non é? Como é que imos facelo en C? Cal é a sintaxe para iso? ALUMNO: Igual, é igual. Jason Hirschhorn: Igual, é igual. Entón, esta verificación é probablemente vai para ser un igual, é igual. Entón, imos ver que necesitamos que en algún lugar. E, de feito, só a gravala-lo, vemos esas outras cousas. Nós imos ter que facer algunha operadores de comparación en alí - fantástico. Entón, el realmente se parece, por e un grande, non ter escrito palabra de código C aínda. Pero nós temos o modelo mental abaixo a través de conferencias e os shorts. Nós escribir pseudo-código como un grupo. E xa temos o 80% se non 90% do que necesitamos facer. Agora, só necesitamos codificar , O que unha vez máis, é un problema non trivial para resolver. Pero polo menos estamos presos na lóxica. Polo menos agora cando imos para o horario de expediente, Eu podo dicir, eu sei que eu teño de facer, pero pode lembrar me da sintaxe? Ou mesmo se o horario de oficina están fortes, ten pode Google para a sintaxe, no canto do que queda preso na lóxica. E, de novo, en vez de tratar de resolver a lóxica e os problemas de sintaxe todo á vez, moitas veces é moito mellor romper eses dous problemas difíciles fóra en dous os máis gerenciáveis ​​e facer o pseudo-código e, a continuación, primeiro código en C. Entón imos ver o que eu fixen para o pseudo-código antes de tempo. Mentres que a lonxitude da lista é maior que cero, mire para o medio da lista. O número atopado retorna certo, se non O número máis elevado, procura esquerdo. Else if menor número, procura dereita, volverá false. De xeito que parece case idéntico, se non case o mesmo que o que escribiu. De feito, Tom, o que dixo en primeiro lugar, romper no medio da lista, e se número atopado en dúas instrucións é realmente o que eu fixen. Eu combinei los alí. Eu debería ter escoitado vostede por primeira vez. Entón este é o pseudo-código que temos. Se quere agora, Sentímolo, vaia De volta ao noso problema inicial. Código binary.c Imos. Entón implementar unha versión interactiva de investigación binaria coa seguinte declaración da función. E non precisa copiar Lo aínda. En realidade, estou indo a abrir ata aquí binary.c. Polo tanto, hai a declaración da función no medio da pantalla. E vai ver que eu tomou o pseudo-código de nos meus dous lados, pero case idéntico co que escribiu, e poñer isto para vostede. Entón, agora, imos levar cinco minutos para codificar esta función. E, de novo, se ten algunha preguntas, levantar a man, me aviso, vou veñen por aí. Estudante: [inaudível]. Jason Hirschhorn: Entón eu peguei o binario definición de investigación no arriba, na liña 12. Iso é o que eu teño para o meu foto. E despois de todo isto pseudo-código que só copia e colei do slide, diapositivas pseudo-código. Eu aínda non estou escoitando [inaudível]. Entón, se ten rematado a súa implantación, quero comprobar. Eu lle enviou o ficheiro Helpers.h anteriormente nesta clase. E vai estar dispoñible en liña tamén para descargar para a xente vendo Neste momento sección retardada. E eu usei só a distribución xenérico código de pset3. Entón eu peguei find.C, usa meu arquivo Helpers.h en vez do ficheiro Helpers.h que é dada no código de distribución. E eu tiven que facer outra mudanza no find.C en vez de chamar simplemente investigación, chamada binary_search. Entón, se quere probar o seu código, sei que iso é como facelo. En realidade, cando nós estaremos executando este código agora, eu fixen só unha copia do meu directorio pset3, unha vez máis, trocados os ficheiros de axudantes e despois fixo que cambiar en find.C chamar binary_search , En vez de simplemente buscar. Jason Hirschhorn: si. Ten unha pregunta? ALUMNO: de Nevermind. Jason Hirschhorn: Non se preocupe. Ben, imos comezar. Imos codificar este como un grupo. Outra nota. De novo, isto é, poden ser facilmente trocados no conxunto de problemas para tres. Eu teño o meu arquivo Helpers.h que, no canto que o Helpers.h estamos dado, declara busca binaria, burbulla clasificar e selección tipo. E en find.c notará on line, o que é iso, a liña 68, que chamamos binario buscar en vez de investigación. Entón, de novo, o código que está dispoñible en liña ou o código que está creando agora poden ser facilmente trocados in para p set 3 para verificalo. Pero, primeiro, imos codificar busca binaria. A nosa declaración de función, retornamos un booleano. Tomamos un enteiro chamado valor. Tomamos un array de enteiros chamado valores, e tomamos n ser o tamaño da matriz. Na liña 10, aquí, eu teño afiada inclúen stdbool.h. Alguén sabe por que está aí? Entón, o que esta liña de código fai? ALUMNO: Permite que usar un tipo de retorno booleano. Jason Hirschhorn: Exactamente. ALUMNO: Ou é unha biblioteca que permite o uso dun tipo de retorno booleano. Jason Hirschhorn: Entón o forte incluír liña stdbool.h dáme algunha definicións e declaracións para cousas que estou autorizado a usar en esta biblioteca. Así, entre os que está dicindo que non hai este tipo chamado booleano, e que se pode verdadeira ou falsa. Entón é iso que esta liña fai. E se eu non ten esa liña, eu o faría estar en apuros para escribir este palabra correcta aquí, bool, alí mesmo. Exactamente. Entón eu teño que neste código. Aceptar. Polo tanto, este, de novo, é un iterativo versión, e non unha recursiva. Por iso, imos comezar. Imos comezar con este primeiro liña de código pseudo. E espero que, nós - ou non espero. Estamos indo para ir ao redor da sala. Imos liña por liña, e eu vou axudar descubrir a liña que necesitamos para gravar en primeiro lugar. Así, mentres a lonxitude da lista é maior que cero. Imos comezar na fronte. Que liña debo escribir aquí, en código? ALUMNO: Mentres paréntese n é maior que 0. Jason Hirschhorn: Mentres n é grande a 0. Así, n é o tamaño dunha lista, e estamos comprobando se - [Voces interpondo] Jason Hirschhorn: - Perdón? ESTUDANTE: Como sabemos que n é o tamaño da lista de? Jason Hirschhorn: Sentímolo. Por especificación pset, a investigación e clasificar as funcións que precisa para escribir, n é o tamaño da lista. Esquecín de explicar iso aquí. Pero si. n é o tamaño de lista, neste caso. Así, mentres que non é maior que 0. Aceptar. Isto pode revelar-se un pouco problemático porén, se as cousas seguen. Porque imos continuar a coñecer a Tamaño da lista ao longo deste función, pero dicir que comezar cunha matriz de 5 enteiros. E nós pasamos e temos agora reduci-lo a unha matriz de dous enteiros. Que dous enteiros que é isto? O tamaño é de 2 agora que queremos ollar, pero que 2 é isto? Isto ten sentido, esta pregunta? Aceptar. Vou preguntar de novo. Entón empezamos con este conxunto de 5 enteiros, e n é igual a 5, non? Nós imos pasar por aquí. probablemente imos cambiar o tamaño, dereita, como as cousas sigan. Que é o que dicimos que queremos facer. Non quere buscar a cousa completa de novo. Entón, dicir que muda-lo para 2. Levamos a metade da lista que é raro. Entón, só tes que escoller 2. Entón agora non é igual a 2. Pido desculpas para os pobres marcadores de borrar a seco. Non? E nós estamos a buscar a través da lista de novo con unha lista de tamaño 2. Ben, a nosa disposición aínda é de tamaño 5. Dicimos que só queren buscar 2 puntos na mesma. Así que dous puntos son estes? Será que isto ten sentido? Son eles os deixaron dous puntos? Son o dereito 2 puntos? Son o Medio 2 puntos? Nós quebramos o problema para abaixo, pero realmente non sei que parte do o problema aínda estamos mirando, só por ter estas dúas variables. Entón necesitamos un pouco máis entón, mentres que non é maior que 0. Necesitamos saber onde este n está na nosa disposición real. Entón, alguén ten un pasar a esa liña? A maior parte desta liña é perfectamente correcta. Existe outra adición? Podemos cambiar algo para a n facer esta liña un pouco mellor? Mm-HM? ALUMNO: Pode arrincar unha variable como a lonxitude de n que vai ser empregado posteriormente a función? Jason Hirschhorn: Entón arrincar unha lonxitude variable para n, e usamos iso máis tarde? Pero, entón, só actualizar lonxitude e nós aínda executar para este problema en que reducir a lonxitude do noso problema, pero nunca se sabe onde, de feito, que a lonxitude mapea a. ALUMNO: Non é que vai pasar máis tarde, cando está dicindo, busque á esquerda, buscar non? Está indo a ir a un diferente área da súa - Jason Hirschhorn: Estamos indo a ir a unha zona, pero como sabemos que deben ir? Se só temos a matriz e este n, como é que imos ver onde ir á matriz. Na parte de atrás, non é? ALUMNO: Ten, así, un pequeno amarre e unha variable de límite superior ou unha cousa desas? Jason Hirschhorn: Aceptar. Polo tanto, esta é outra idea. En vez de só manter o control da tamaño, nós manter o control do máis baixo e variable límite superior. Entón, como podemos calcular o tamaño da un límite superior e límite inferior? [Voces interpondo] Jason Hirschhorn: subtracción. E tamén manter o control de canto menor amarre e límite superior para que poidamos saber, estamos buscando eses dous? Estamos buscando estes dous aquí? Estamos a buscar os dous medio? Probablemente non os dous do medio, xa que isto, en realidade, é de investigación binaria. Pero agora nós imos ser capaces de obter o tamaño, pero tamén os límites da matriz. En esencia, se temos o noso xigante libro de teléfono, nós resga-lo ao medio. Agora sabemos onde ese pequeno libro de teléfono é. Pero nós non estamos realmente rasgando o libro de teléfono pola metade. Aínda necesitamos saber onde a novos límites do noso problema. Alguén ten algunha dúbida sobre iso? Si? ALUMNO: Será que funciona a través da creación dun variable, i, que despois é só cambiar a posición da i en relación ao seu posición actual, e a lonxitude, n? Jason Hirschhorn: E que é o que eu? ESTUDANTE: Cómo ser como unha especie de - Como arrincar i para ser o posición central da matriz. E entón, o valor na posición i en no medio da matriz in atopou ser menor que o valor que precisa, eu agora pasa a ser a lonxitude da matriz, ademais o valor de i dividido por 2. Como, vexa, cambia i - Jason Hirschhorn: Certo. ALUMNO: - ata o - Jason Hirschhorn: Entón, eu estou case positivo que vai funcionar. Pero o punto é, precisa dous anacos de información aquí. Podes facelo con inicio e fin, ou pode facelo con tamaño e, a continuación, algún marcador. Pero ten que de dúas pezas de información aquí. Non pode ir con só un. Será que isto ten sentido? Entón, imos pasar, e imos facer [inaudível] e crear algúns marcadores. Entón o que escribe no seu código? ALUMNO: Eu só dixo int límite é igual a 0. Jason Hirschhorn: Imos chamar que int, comezando. ALUMNO: Aceptar. Jason Hirschhorn: Isto fai máis sentido para min. E? ALUMNO: Eu dixen, eu creo, int fin. Jason Hirschhorn: int fin. ALUMNO: Coido, n menos 1, ou algo parecido. Como, o último elemento. Jason Hirschhorn: Entón escribiu, int comezando igual a 0, punto e coma, e int final é igual a n menos 1, punto e coma. Entón, basicamente, o que estamos facendo aquí, 0 a primeira posición. E como sabemos en matrices, eles non van ata n, van ata n menos 1. Polo tanto, temos uns límites da nosa matriz. E eses límites iniciais que ser os límites iniciais do noso problema. Aceptar. Entón, iso parece bo. Entón, se volvemos a esa liña, mentres lonxitude da lista é maior que 0, o que, en vez de n, debe imos poñer aquí? ALUMNO: Escribir terminando menos comezo. Jason Hirschhorn: Ao término menos comezando é maior que 0? Aceptar. E poderiamos, se quixésemos facelo un pouco máis agradable, o que máis poderiamos facer? Se quixésemos limpar este código un pouco? Como podemos librar do 0? Esta é só unha cuestión de estilo. É correcto agora. ALUMNO: Final non igual comezo? Jason Hirschhorn: Podemos facer o que? [Voces interpondo] ALUMNO: Rematar é maior? Jason Hirschhorn: Yeah. Podemos só facer ao rematar é maior que o principio. Correcto. Nós engadimos comezando a outro lado diso, e nos libramos do 0. Entón, iso só parece un pouco máis limpo. Aceptar. Así, mentres a lonxitude da lista é 0, escribimos que, ao rematar é maior que ao principio. Imos poñer na nosa necesario claves, e logo, o primeiro queremos facer é mirar para los nunha lista. Vostede? Que me pode dar o - ALUMNO: Se paréntese valor corchete - Jason Hirschhorn: Se parénteses corchete valor. ESTUDANTE: acabar dividido por 2. Jason Hirschhorn: Ending? ALUMNO: Eu vexo un problema co seu - Jason Hirschhorn: Aceptar. Ben, mire para o medio. Como é que sabemos o que o medio é? É. Entón déixeme borrar este código. Como é que sabemos o que o medio é? En calquera cousa, cando ten o comezo eo fin, como está no medio? ALUMNO: Vostede media. ALUMNO: engade-los xuntos e logo, - Jason Hirschhorn: Engadir- xuntos e despois? ALUMNO: E ti media. Débeda o por 2. Jason Hirschhorn: Engadir- xuntos e dividir por 2. Así, int medio é igual? Tom, pode dar isto para min? ALUMNO: Comezando máis fin - Jason Hirschhorn: Inicio máis fin. ALUMNO: All, soporte, dividido por 2. Jason Hirschhorn: Todos, entre parénteses, dividido por dous. Entón iso me dá a media de calquera cousa, non? ALUMNO: Tamén cómpre redondear. Jason Hirschhorn: O que fai É dicir, eu teño redondear? [Voces interpondo] ALUMNO: Porque se é un estraño número, entón é como - Jason Hirschhorn: Ben, OK. Así eu podería redondear. Pero se é un número impar, a 5, podo tomar un fóra do medio. Ou se é un número par, ao contrario, isto é un caso mellor. De ser 4, só temos 4, podo tomar o primeiro "medio", multimedia, pecha comiñas ou o segundo "medio". Ou ía traballar para unha busca binaria, entón eu realmente non precisa redondear. Pero hai outra cousa que eu que ollar para esta liña. Podemos non entender, aínda, pero imos volver a el. Por esta liña, en realidade aínda precisa outra cousa. Pero ata agora, nós escribimos catro liñas de código. Temos o noso comezo e rematando marcadores. Temos o noso loop while, que mapea en directamente ao noso pseudocódigo. Estamos mirando para o medio que mapea directamente na nosa pseudocódigo. Eu diría que este vai para o medio da lista, esta liña de código. E entón, cando imos para o medio da Na lista, a seguinte cousa que cómpre facer é comprobar que o seu valor está aí para o pseudocódigo que escribimos anteriormente. Entón, como imos comprobar se o seu valor está no medio da lista? Vostede Por que non fai iso? ALUMNO: O noso valor de é no medio coincide todo o que establecer o - Quero dicir igual igual a - Jason Hirschhorn: It - Aceptar. ALUMNO: Eu non estou seguro o que o variable que estamos a buscar pois, aínda, é porque - [Voces interpondo] Estudante: [inaudível]. Jason Hirschhorn: Exactamente. Por a declaración da función, estamos á procura dun valor. Entón, nós estamos a buscar por un valor nunha matriz de valores. Entón está exactamente certo. Vai facer, se franxa de valor paréntese aberta medio pechado iguais soporte igual valor, e dentro o que necesitamos facer? O noso valor está aí, o que que necesitamos facer? [Voces interpondo] ESTUDANTE: Return cero. Jason Hirschhorn: Return verdade. ALUMNO: Devolve true. Jason Hirschhorn: Michael, que é o que esta liña fai? Estudante: [inaudível] o programa foi executado o seu curso, e que é máis, e ten o que hai que facer? Jason Hirschhorn: O programa ou que? Neste caso? ALUMNO: A función. Jason Hirschhorn: A función. E así, para volver ao que chamou lo e darlle o valor, é certo. Exactamente. Main. Cal é o tipo de retorno de principal, Michael? ALUMNO: int, integer? Jason Hirschhorn: int, exactamente. Un enteiro. Isto foi só unha pregunta para asegurarse Vostedes estiveron enriba dela. Que xeralmente retornan, se todas as cousas están funcionando ben? ALUMNO: Cero. Jason Hirschhorn: Cero. Exactamente. ESTUDANTE: Se este só retorna true, non hai ningunha información a ser dada sobre o que - Oh, este é só dicir que este valor está dentro da matriz. Jason Hirschhorn: Exactamente. Este programa non está dando información de onde é exactamente o valor. El só está dicindo, si, atopamos Lo, ou non, nós non atopalo. Así, se o número atopado, retorna true. Ben, en realidade nós fixemos que realmente axiña que unha liña de código. Entón eu vou pasar esta liña de pseudocódigo. ALUMNO: Non necesitamos para cambiar a matriz? Debe ser valores, non o valor, non? Jason Hirschhorn: Sentímolo. Grazas. ESTUDANTE: Yeah. Jason Hirschhorn: Esta liña deben ser valores. Exactamente. Aceptar. Entón, nós miramos a lista medio. O número atopado return true. Continuando co noso pseudocódigo, se media é maior, a procura á esquerda. Así que tiven aquí, se o número de superior, de investigación á esquerda. Constantino, pode dar me esta liña de código? ESTUDANTE: O valor de media - Jason Hirschhorn: Entón, se o valor - se paréntese aberta valora soporte preto soporte do medio - ALUMNO: É menor que valor? Jason Hirschhorn: É menos que. ALUMNO: Menos de valor. Jason Hirschhorn: Valor. Ben, en realidade, quere comprobar que o número - Sentímolo. Isto é un pouco confuso. Pero o resto, se o número do medio da lista é grande. ALUMNO: Oh, Aceptar. Jason Hirschhorn: Vou cambiar isto. Else if media é máis elevada, quere buscar esquerda, OK? E o que facemos dentro iso condición? ALUMNO: Podo facer unha pequena modificación a condición, cambia-lo a outra persoa se? Jason Hirschhorn: Else if? Aceptar. Polo tanto, este código será executado sobre o mesmo. Pero a cousa boa sobre o uso de if, else if, else if ou if, else if, else quere dicir que só un destes vai ser verificado, non todos os tres, potencialmente. E iso fai que sexa un pouco máis agradable no ordenador que está realizar o seu programa. Así, [? Constantino,?] estamos dentro desta liña, máis se os valores, preto soporte do medio soporte é maior que o valor. O que necesitamos facer? Necesitamos buscar a esquerda. Como facemos iso? Vou darlle un comezo. Temos estas dúas cousas chamadas comezando e rematando. Entón, o que ten que pasar ao comezo? Se quere buscar á esquerda do lista, temos o noso comezo actual. O que necesitamos facelo? ALUMNO: Nós axustar o inicio a media máis 1. Jason Hirschhorn: Entón, se estamos buscando a esquerda? ESTUDANTE: Sentímolo, medio menos - de xeito que o medio final sería menos 1 e no inicio - Jason Hirschhorn: E o ocorre co inicio? ALUMNO: El permanece o mesmo. Jason Hirschhorn: Entón, a significado permanece o mesmo. Se estamos buscando á esquerda, estamos usando o mesmo principio - exactamente correcto. E o final? Sentímolo, o que fai o terminando igual de novo? ALUMNO: menos Oriente 1. Jason Hirschhorn: menos Oriente 1. Agora, por menos 1, e non só do medio? ALUMNO: O medio está fóra de xa imaxinar, porque tivemos Comprobarase que está fóra? Jason Hirschhorn: Isto é exactamente correcto. O medio é fóra de cogitação. Xa verifiquei o medio. Entón, nós non queremos "medio", cita pecha comiñas, para continuar a estar no matriz que estamos buscando. Entón, iso é fantástico. Else if medio soporte de valores é maior do valor final iguais medio menos 1. Jeff, que sobre esta última liña? ALUMNO: Else. Valores medio é menor que o valor? Jason Hirschhorn: Nós imos está me dando máis. Entón, se non me der - ALUMNO: Entón comezando sería máis un medio. Jason Hirschhorn: iguais Comezando ademais dun medio, de novo, para a mesma razón que Constantino deunos máis cedo. E, ao final, que non deu me unha liña de código aínda? Return false, Aleha, o que podemos escribir aquí? ALUMNO: Return false. Jason Hirschhorn: Return false. E necesitamos facer iso, porque se nós non atopalo, hai que dicir que non atopalo. E nós dixemos que imos voltar un bool, entón nós sempre ten que volver un en algún lugar bool. Entón, imos realizar este código. En realidade, estou indo a - entón estamos no terminal. Nós imos limpar a nosa fiestra. Imos facer toda. Descubrimos que hai un erro. Hai un erro na liña 15, que deberá coma ao final do declaración. Entón, o que eu esquezo? ALUMNO: Punto e coma. Jason Hirschhorn: Punto e coma ata aquí. Creo que foi o código do Tom Entón, Tom, [inaudível]. Brincadeirinha. Imos facer todo de novo. ALUMNO: O directorio Dropbox debemos estar en para iso? Jason Hirschhorn: Entón pode só asistir a este bit. Pero, de novo, se quería cambiar isto código no seu directorio pset3 para intentar con iso, iso é o que eu fixen. Se observa aquí - Sentímolo, boa pregunta. [? LS,?] Eu teño aquí o código find.c desde o código distro desta semana. Teño Helpers.h. Eu teño un arquivo Marca que realmente editado un pouco para incluir eses novos arquivos que estamos escribindo. Todo o que o código está dispoñible, non o código de distribución, pero a nova Fai arquivo, o novo ficheiro será Helpers.h estar dispoñible en liña para descargar. Unha vez máis, entón eses son os códigos extra que temos. Entón, fai de todo, por esta liña, fai atopar, binaria, a selección burbulla - marcas os tres e compila este achado código executable. Entón, xeralmente, nós non queremos para directo para check50. Queremos facer algúns exames por conta propia. Pero só para que poidamos axilizar iso un pouco, check50 2013 pset3.find pasará en helpers.c-- o meu mal. Eu non teño ese dereito agora. Entón, nós estamos indo realmente para executar o código de verdade. Usage.find /, xa sabe o que significa isto? ALUMNO: Debe dun segundo liña de comandos sobre el. Jason Hirschhorn: Necesito unha segunda liña de comandos. E por a especificación, o que eu teño para entrar o que estamos a procurar. Entón, imos ollar a 42. Imos mantelo en ordenada, porque nós non ter escrito unha función de clasificación aínda - 42, 43, 44. E Control D non atopou o agulla no palheiro. Isto é malo. É en definitiva alí. Imos tentar outra cousa. Quizais sexa porque eu coloque Lo no inicio. Imos facer 41, 42, 43. Alí imos nós. El atopou. Imos poñelas ao final agora, só para que poidamos ser completo - 40, 41, 42. Non atopou a agulla. Entón, eu mencionen iso antes. Desafortunadamente, eu sabía que iso ía pasar. Pero, para fins pedagóxicos, é bo para explorar iso. Non funciona. Por algunha razón, non pode atopalo. Sabemos o que está aí dentro, pero Non estamos atopando. Entón, unha cousa que podemos facer é pasar por GDB para atopalo, pero non calquera, sen pasar por GDB, ter un noción de onde nós asneira? [? Madu? ?] ALUMNO: Eu creo que pode ser cando rematar é igual ao principio, e é só unha lista de un único elemento. A continuación, el simplemente ignora-lo en vez de que realmente comprobar. Jason Hirschhorn: Isto é exactamente correcto. Ao final é igual a principio, nós aínda ten un elemento na nosa lista? ESTUDANTE: si. Jason Hirschhorn: Si, de feito, nós ten un e só un elemento. E iso probablemente vai ocorrer cando, Segundo o código que probamos, estamos no diante do palheiro ou polo Ao final do palheiro. É alí onde comezo e finais vai igual un, con busca binaria. Entón, neses dous casos, non funcionou, porque rematando foi igual ao principio. Pero se acabar coincide a principio, que iso loop while realizar? Isto non acontece. E poderiamos ter verificado que unha vez máis a través GDB. Entón, como podemos corrixir este código, por cando ao finalizar é igual a empezando, nós tamén queremos iso while para realizar. Entón, o que podemos facer corrección para a liña 18? Estudante: [inaudível] é maior que ou igual a. Jason Hirschhorn: Exactamente. Mentres final é maior que ou igual ao principio. Entón, agora, ten por seguro de conseguir que caso esquina ao final. E imos ver. Imos correr iso unha vez máis. Imos facer todo. Unha vez máis, vai ter que seguir aquí. Atopar 41 esta vez. Basta mantelo consistente. Atopar 42. Imos colocar-lo no inicio - 42, 43, 44. Atopámolo lo. Así que foi de feito o cambio necesitabamos facer. Iso foi unha morea de codificación que fixo, busca binaria. Alguén ten algunha dúbida antes Eu paso en liñas que escribimos en busca binaria ou como cremos o que nós fixemos descubrir? Antes de seguir adiante, eu tamén quero apuntar que, en xeral, mapeamos nosa pseudo-código dun a unha para o noso código. Tivemos que cousa complicada descubrir co comezando e rematando. Pero se non tivese percibido iso, escribiría practicamente o código idéntico, excepto por estas dúas liñas principais. E entón tería entendido cando fixo iso en cheques e casos que precisas algo máis. Así, mesmo se tivese seguido a nosa liña pseudo-código para a liña, que tería conseguir todo, pero dúas liñas de código que precisaba para escribir. E eu estaría disposto a apostar que vostedes descubriría iso todo moi rapidamente, o que precisaba para poñer algún tipo de etiqueta aí para descubrir de onde estaba. Iso, de novo, é o poder de facer pseudo-código antes de tempo. Así, podemos facer a lóxica primeiro, e despois podemos preocupe a sintaxe. Se tivésemos sido confundido sobre a lóxica ao tentar escribir este código en C, teriamos conseguido toda desarrumada. E entón nós estariamos facendo preguntas sobre a lóxica ea sintaxe e entrosamento todos eles xuntos. E nós tería perdido no que pode rapidamente tornar-se un problema moi difícil. Entón, imos seguir adiante agora para a selección de tipo. Temos 20 minutos. Entón, eu teño a sensación de que non poderá pasar por todos selección tipo e bubble sort. Pero imos polo menos tentar para completar a selección tipo. Entón aplicar selección tipo mediante o seguinte declaración da función. Unha vez máis, este é eliminado do conxunto de problemas de especificación. Os valores Int é parénteses, é unha matriz de números enteiros. E int.n é o tamaño da matriz que. Tipo de selección vai para clasificar esta matriz. Entón, por noso modelo mental de selección tipo, tiramos o - primeiro, percorrer a lista do primeiro tempo, atopar o menor número, poñelas no inicio, atopar a segunda menor número, coloque-o no segunda posición, se quere Ordenar por orde crecente. Eu non estou forzando a escribir pseudo-código no momento. Pero antes de facer o código como unha clase en cinco minutos, imos escribir pseudo-código polo que temos algún sentido de cara a onde estamos indo. Entón, tentar escribir pseudo-código no seu propio país. E a continuación, tentar transformar esa pseudo-código en código. Nós imos facelo como un grupo en cinco minutos. E, por suposto, deixe-me saber se tes algunha dúbida. ALUMNO: É iso? Jason Hirschhorn: Vexa quão lonxe pode poñerse en máis de dous minutos. Eu entendo que non vai ser capaz de rematar. Pero imos falar sobre iso como un grupo. Vostede é todo de codificación para que [inaudível], polo que estou Sentímolo interromper o que está facendo. Pero imos pasar por iso como un grupo. E, de novo, busca binaria, todos dan me un, se non máis liñas de código. Grazas por iso. Nós imos facer o mesmo aquí, o código en conxunto, como un grupo. Así, a selección tipo - imos escribir algunhas rápidas pseudo-código. Por modelo mental, alguén me pode dar a primeira liña de pseudo-código, por favor? O que quero facer? ALUMNO: Mentres a lista está fóra de orde. Jason Hirschhorn: OK, mentres a lista está fóra de orde. E o que quere dicir "fóra da orde?" ALUMNO: Mentres [inaudível] non foi clasificada. Jason Hirschhorn: Mentres a lista está fóra de orde, o que imos facer? Dáme a segunda liña, por favor, Marcus. Estudante: Entón, o seguinte menor número. Isto será recuado. Jason Hirschhorn: Entón, atopar o preto menor número. E entón outra persoa? Así que o seguinte menor número, o que imos facer? Eu vou dicir atopar menor número. Iso é o que queremos facer. Entón, atopar o menor número. Entón, o que imos facer? Estudante: [inaudível] para inicio. Jason Hirschhorn: Sentímolo? ALUMNO: Pon-o no ao comezo da lista. Jason Hirschhorn: Entón, coloque-o no o inicio da lista. E o que podemos facer para a cousa que era no principio da lista, non? Estamos substituíndo algo. Entón, onde é que imos poñer isto? Si, Anna? ALUMNO: Onde o máis pequeno número era? Jason Hirshhorn: Entón engada o inicio da lista, onde a menor número era. Así, mentres que a lista está fóra de orde, atopar menor número, coloque-o en o inicio da lista, introduza o inicio da lista, onde o menor número era. Marcus, pode reformular esta liña mentres que a lista está fóra de orde? ALUMNO: Aínda que as cifras non foron clasificadas? Jason Hirshhorn: OK, entón, a fin de sabe que as cifras non foron clasificadas, o que necesitamos facer? Canto necesitamos pasar por esta lista? ALUMNO: Entón eu creo que un loop, ou tempo, mentres que os números verificados é menor do que a lonxitude da lista de? Jason Hirshhorn: OK, iso é bo. Creo que misphrased miña pregunta mal. Eu só estaba tentando chegar nós imos ter que ir toda a lista. Así, mentres que a lista está fóra de orde, para min, é difícil localizar nun mapa diante. Pero, basicamente, é así que Eu penso sobre iso. Vai á lista enteira, atopar o menor número, coloque-o no comezando - en realidade, está certo. Imos poñer-los dous. Así, mentres que a lista está fóra de orde, nós que pasar por toda a lista xa, atopar o menor número, lugar que no inicio da lista, poñer o inicio da lista onde a menor número era, e logo, se o lista aínda está fóra de orde, temos ten que pasar por iso proceso novo, non? É por iso que a selección tipo, Big-O tempo de execución de selección tipo, alguén? ESTUDANTE: n ao cadrado. Jason Hirshhorn: n ao cadrado. Porque como Marcus e eu só entender aquí, nós imos ter que percorrer a lista lista número de veces. Entón pasando por algo de lonxitude n n número de veces é, de feito, n ao cadrado. Entón, este é o noso pseudocódigo. Isto parece moi bo. Alguén ten algunha dúbida sobre o pseudocódigo? Porque en realidade a selección tipo debe probablemente chegar un a un, o código de pseudocódigo. Así, calquera dúbida sobre a lóxica do pseudocódigo? Por favor, pregunta-lo agora. Tipo de selección - mentres que a lista está fóra de orde, nós imos pasar por iso e atopar o menor de cada vez e poñelas diante. Así, mentres que a lista está fóra de orde, pode alguén me veña con esa liña de código que non me deu unha liña de código, con todo, por favor? Parece unha cousa? ALUMNO: Isto é un loop for. Jason Hirshhorn: Parece gusto de un loop for. OK, que me pode dar o loop? Por - ALUMNO: i é igual a 0. Jason Hirshhorn: i ou - que é o que falta? O que pasa aquí? ALUMNO: Int Jason Hirshhorn: Exactamente. (Int i = 0; - ALUMNO: i