Tip:
Highlight text to annotate it
X
>> 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 > Jason Hirshhorn: cravado tanto, Jeff.
Estamos pasando por unha lista, non?
Xa vimos que o código antes.
Perfecto.
Entón, imos poñer as nosas chaves aquí.
Vou poñer algúns claves aquí.
>> Así, aínda que sexa 0, hai que ir toda a lista.
Así, cada vez que imos a lista, o que queremos para seguir?
>> ALUMNO: Se algún swaps poden facer.
>> Jason Hirshhorn: Atopar menor número.
Entón, nós probablemente debe manter o control de o número máis pequeno de cada vez.
Entón liña que podo facer para manter o control do menor número?
Aleha, como podo manter pista de algo?
>> ALUMNO: Comezar unha nova variable.
>> Jason Hirshhorn: Comezar unha nova variable.
Entón imos crear unha variable.
Cal é o tipo?
>> ALUMNO: Int
>> Jason Hirshhorn: Int
Imos chamalo menor.
E o que o fai igual cando estamos só comezando?
Non pasaron pola lista aínda.
Estamos na primeira parte do consultar a nosa primeira vez.
O que non é igual, o menor número?
>> ALUMNO: valores que eu.
>> Jason Hirshhorn: valores que eu.
Isto soa exactamente correcto, non?
O menor número ao comezo é o lugar onde estamos.
Polo tanto, agora temos o noso pequeno, e necesitamos para percorrer a lista enteira e
comparar este pequeno para o resto.
Así é que imos percorrer a lista de novo?
Michael?
>> ALUMNO: Cómpre facer outro para loop.
>> Jason Hirshhorn: Outra loop for.
Imos facelo.
Déame algún código.
>> ALUMNO: Para loop -
para os máis pequenos -
só int j, podería dicir?
= 0; tal que -
>> Jason Hirshhorn: Ben, se queremos para percorrer a lista enteira -
>> ALUMNO: j > Jason Hirshhorn: Fantastic.
Nós imos pasar por o loop for unha vez máis.
E como é que imos atopar o menor número?
Tom?
Temos a cadea menor número, entón como é que imos atopar o novo menor?
>> ALUMNO: Podemos comprobar que o menor número que temos é maior que
valora soporte j.
>> Jason Hirshhorn: Entón, se é menor maior que os valores do soporte j.
Polo tanto, se o noso actual menor é maior que -
Vou mover estas dúas liñas de código aí por un segundo.
Porque, antes de facer calquera cambio, nós que pasar por toda a lista.
Polo tanto, este pseudocódigo que realmente estar fóra que interna para loop.
Entón, percorrer a lista enteira.
Se é maior que o menor valores j, entón o que?
>> ALUMNO: Entón menor é igual a valores j.
>> Jason Hirshhorn: Fantastic.
Unha pregunta rápida -
a primeira vez que pasar por este ciclo, i será igual a 0, j vai
para igualar 0 xa que temos aquí.
Entón, nós imos estar comparando un certo número de si.
Isto é eficaz?
Non, non é realmente eficaz.
O mesmo acontece co noso j que ir de 0 a N de cada vez?
Será que sempre que comprobar toda a lista?
[Inaudível]?
>> ALUMNO: Comeza i vez.
>> Jason Hirshhorn: j lata comezar co que?
>> ESTUDANTE: i.
>> Jason Hirshhorn: j pode comezar con i.
Entón, agora nós comparar comezando con aquel no que estamos.
Pero, aínda así, é que, como eficiente posible?
>> ALUMNO: i + 1.
>> Jason Hirshhorn: i + 1 semella o máis eficiente, porque nós
xa ten i.
Estamos afirmando que, como o menor na liña 15.
Imos comezar co seguinte xeito automático.
Entón, nós pasamos polo loop for.
Imos pasar por cada vez.
Nós imos pasar por un número de veces.
Agora que temos obtido a través este interior para loop.
Temos o menor valor gardada.
Necesitamos colocar-lo no ao comezo da lista.
Entón, como fago para poñer-lo na ao principio da lista?
¿Que é a variable que se refire ao comezo da lista?
Estamos niso fóra para o lazo, entón o que se refire á
ao principio da lista?
>> ALUMNO: valores que eu.
>> Jason Hirshhorn: Exactamente.
Os valores de i é o comezo da -
ou Sentímolo, non o comezo.
Iso foi confuso.
É onde estamos a principios de a parte indiferenciados da lista.
Así, os valores i.
E o que fai que a igualdade?
>> ALUMNO: Menor.
>> Jason Hirshhorn: valores i é igual a que?
>> ALUMNO: Menor.
>> Jason Hirshhorn: Menor.
Exactamente.
Entón, nós estamos poñendo-o no inicio da lista, e agora hai que poñer
o inicio da lista cando menor número era.
Entón como é que eu escriba, onde o menor número foi?
Os valores de que?
>> ESTUDANTE: 0.
>> Jason Hirshhorn: O pequeno número está en 0?
>> ESTUDANTE: Yeah.
>> Jason Hirshhorn: E se o menor número foi ao final
esta lista non ordenada?
>> ESTUDANTE: Sentímolo, pero o que era a pregunta?
>> Jason Hirshhorn: Onde está menor número?
Pegamos o menor e poñelas no comezando con esta liña aquí.
>> ALUMNO: Debe ter foron almacenados nalgún -
>> ESTUDANTE: Os valores de j.
>> Jason Hirshhorn: Ben, é non necesariamente os valores j.
El nin sequera existe neste momento.
>> ALUMNO: Ten que declarar unha variable anteriormente e
logo atribuílo la a -
cando atopar o menor número, asignar a taxa de que o número de
algunha variable ou algo parecido.
>> Jason Hirshhorn: Entón pode vostede dicir iso de novo?
>> Estudante: Entón, onde declarou int menor, tamén debe declarar int
menor índice = i, ou algo parecido.
>> Jason Hirshhorn: Entón, onde eu int menor, non só debe manter o control
do valor pero a situación.
int smallest_location = neste caso, imos só facer i.
Necesitamos saber onde está.
Chegamos ao final do código, e nós entendemos que non tiña idea de onde estaba.
E así, unha vez máis, estamos cartografía este en un a un.
Vostedes codificación iso na súa propia vontade probabelmente chegar ao mesmo problema.
Como diaños eu atopalo?
E entón entende, espera, eu Debe manter o control diso.
>> Entón, se é menor maior de valores j.
Nós establecemos menor é igual aos valores j.
Que máis é preciso cambiar?
Constantin, o que máis hai que cambiar?
>> ALUMNO: A localización.
>> Jason Hirshhorn: Exactamente.
Entón me dea esa liña no código.
>> ALUMNO: smallest_location = j.
>> Jason Hirshhorn: Exactamente.
E, a continuación, para abaixo, ao final, se quere poñer o inicio da lista, onde
menor número era, como que nos referimos, onde o
menor número foi?
Marcus?
>> ALUMNO: O menor número foi situado en menor local.
>> Jason Hirshhorn: Entón, en valores smallest_location.
E que é o que imos poñer alí?
O inicio da lista, o que é iso?
>> ESTUDANTE: Ben, nós realmente non sabemos máis porque substituíu.
Polo tanto, é un sitios trocados destas dúas liñas?
Se cambiar estas dúas liñas ao redor.
>> Jason Hirshhorn: OK, entón nós non máis, porque redefinir a liña
antes de valores i a menor.
Entón, nós perdemos ese valor inicial.
Entón dixen que cambio estas dúas liñas.
Entón agora introduza o inicio da lista onde o menor número era.
Entón smallest_location iguala valores i.
Isto está movendo no inicio deste indiferenciados parte da lista para o
menor local.
E, a continuación, en valores i estamos movendo que menor número.
>> Isto ten sentido porque tiña que facer esa cambio?
Queremos ter substituído o valor - outra cousa que probablemente tería
descuberto e atopar no PIB.
Entón, temos tido o coidado de todo o pseudocódigo.
Hai algo máis que que escribir aquí?
Alguén pode pensar en nada?
>> ESTUDANTE: Como vostede sabe cando está feito?
>> Jason Hirshhorn: Como é que nós sabe cando estamos a facer?
Excelente pregunta.
Entón, como imos ver cando estamos a facer.
>> ALUMNO: Crea unha variable para manter a conta de se hai un intercambio feita ou non
e pasar por un pase.
>> Jason Hirshhorn: Aceptar.
Isto ía traballar en bubble sort.
Pero para a selección de tipo, se non o facemos facer un troco, que pode ser só
xa que o menor valor é nel a súa localización.
Podemos ter unha lista 1, 2, 4, 3.
O segundo tempo a través de nós Non vai facer ningunha swaps.
Estar no número 2, pero imos aínda que continuar.
Polo tanto, hai que manter o control de cando estamos a facer, ou nós só quero ir
ata que isto sexa completado?
>> ALUMNO: Podemos só ir ata que estea terminado.
>> Jason Hirshhorn: podemos só ir ata que isto sexa completado.
En bubble sort, está absolutamente correcto, Jeff e Aleha, coa súa solución -
é óptimo para manter o control de cantas swaps que fixo, porque na burbulla
tipo, se de feito non fan swaps, está feito e pode quizais cortar o
problema un pouco.
Pero para a selección de tipo, ten realmente ten que ir ata o final do
lista á vez.
>> Polo tanto, esta é iso.
Temos dous minutos do final.
Imos facer todo.
Déixeme só aberta Atope aquí e faga seguro que estou, de feito, chamar-se -
Non estou pedindo bubble sort.
Imos cambiar isto para a selección tipo.
facer todo. / find.
Atoparemos 42.
Esta vez, imos pasar un lista non ordenada, porque debe clasificar
en primeiro lugar, polo Código de busca - debe clasificar o primeiro en utilizar a nosa función de clasificación e, en seguida,
buscar algo.
Dedos cruzados todos.
>> Oh meu Deus.
Whoa, o meu corazón estaba batendo.
Entón, iso é correcto.
En realidade, se nós corremos este máis exhaustivamente, o código, tanto como eu poida
dicir, é perfectamente correcta.
Existen algunhas suxestións Eu teño para ti.
Por exemplo, 15 e 16 parece algo redundante.
Parece que non necesariamente Debe aforrar tanto aqueles.
Se ten o menor local, Pode facilmente atopar o menor valor por
só escribindo valores de i.
>> Entón, se eu fose o seu código de clasificación, que eu vou ser de feito, eu o faría
probablemente sacar un punto, se incluído ambos, porque
Non precisa de ambos.
Se tes a localización, pode facilmente obter o valor.
E parece un pouco raro para gardar os dous.
Quizais nin sequera tomar un punto, pero seguramente comentar que esta é quizais
non é unha opción estilística cómpre facer.
Claro que, o código aínda funciona perfectamente ben.
>> Entón, por desgraza, non está chegar a bubble sort.
Eu sinto moito por iso.
Fixemos acabado selección tipo.
Alguén ten algunha preguntas finais sobre a selección de tipo?
>> OK, antes de saír, quero que para abrir o seu navegador Chrome.
Sentímolo, iso foi só un plug flagrante para un tipo de navegador de internet.
Pode abrir calquera tipo de navegador, pero probablemente será Chrome.
E ir a este seguinte web -
sayat.me/cs50.
Se vostede non está escribindo no seu ordenador agora, está claramente
non facelo, Tom
>> E, por favor facelo tamén dereito agora ou no próximo hora -
darme algún feedback.
Esta é só a sección dous.
Temos moitos máis xuntos, entón eu ten unha morea de espazo para mellorar.
Espero que tamén fixo ben algunhas cousas.
Entón pode facerme sentir de todo malo, pero se tamén quere me dar un Smiley
cara, eu desexa recibir iso tamén.
Encha que dentro
>> E con un minuto para a esquerda, que foi de tres semanas.
Vou estar fóra por un tempo se tes algunha preguntas.
Vou ver vostedes en charla mañá.