>> JASON HIRSCHHORN: Bienvenido a la semana tres, todo el mundo.
Tenemos una concurrida pero apasionante sección por delante de nosotros.
Así que en primer lugar, porque hemos hecho algunos avanzar en el curso, pero todavía
tienen una gran cantidad de aprendizaje más que hacer, estoy va a aparecer ustedes algunos recursos
que debe llegar a ser increíblemente útil ya que no sólo se acerca a su
boletines de problemas, sino también a digerir todos el material que le damos chicos en
conferencias y pantalones cortos y sección.
>> A continuación vamos a pasar los primeros 20 a 25 minutos de la sección repasando
GDB, que usted puede o no puede tener utiliza en este punto, pero es una
herramienta increíblemente útil que le ayudarle a depurar sus programas.
Muchos de ustedes pueden haber utilizado printf en el medio de su programa de averiguar
lo que equivalía a una variable.
GDB es incluso mejor que printf y no arruinar su código porque
ejecutarlo en un archivo ejecutable.
Así que vamos a repasar los 10 más útiles los comandos que necesita para el IAE, y estamos
va a ir en un ejercicio juntos para en el problema de establecer tres y más allá, que
puede usar GDB para ayudar a depurar sus programas.
Y, por último, vamos a repasar algunos clasificación y búsqueda de algoritmos
que has visto en clase, y estamos ir a la realidad de código, no sólo
pseudocódigo, pero el código binario de búsqueda, ordenamiento de burbuja, y la selección de clasificación.
>> Así que en primer lugar, quiero ir sobre los recursos.
Esta es una lista extensa, y es pequeña fuente, porque tenía mucho que
encajar aquí.
Pero estos no sólo le va a ayudar, de nuevo, con los boletines de problemas y
información para digerir que aprendió, pero sin duda, llegado el momento concurso, éstos se
ser increíblemente útil.
Así que en primer lugar, la ponencia señala.
Si usted va a cs50.net/lectures y desplazarse a la semana y un día específico,
verás que hay notas para cada dar una conferencia, la cual no es más que una
transcripción, pero una versión editada de lo que fue cubierto en la conferencia con el código de
fragmentos y otras cositas útiles.
Recomiendo ir sobre aquellos.
Y entonces, así, no hay código fuente disponible de cada conferencia.
Y de nuevo, estas diapositivas también estarán disponible en línea en cs50.net/sections
esta tarde.
>> Así segundos son los cortos cada semana que temas de cobertura, por lo general de 5 a 15
minuto de longitud.
Y aquellos con suerte le dará una gran introducción a diferentes temas.
En tercer lugar -
y esto es nuevo este años - es study.cs50.net.
Si usted no ha comprobado hacia fuera, yo altamente recomendable que lo haga.
Tienes la oportunidad de elegir un tema.
Tenemos docenas de temas sobre los que hay.
Así, por ejemplo, tienes que elegir las funciones.
Le da algunas diapositivas y toma nota de las funciones.
Esas son en realidad las diapositivas que TFS se les anima a usar durante nuestra
presentaciones en la sección.
También hay consejos y trucos para hacer frente con funciones, y hay
problemas prácticos que ayudan a trabajar con funciones.
También le damos enlaces a la corta en funciones y las veces en las que las funciones
han surgido en la conferencia.
Así study.cs50.net estrenar esta año, un recurso fantástico.
>> A continuación, tengo el hombre, que es el manual de comando que se puede ejecutar en el
línea de comandos.
Así que si usted tiene alguna pregunta acerca de un comando, por ejemplo, Rand, que nos
encontrado la semana pasada durante la sección y es probable que haya encontrado en
su problema ajusta al pasar por el generar código, pero si escribe man
rand, obtendrá la página que te dice todo sobre rand.
Le da lo que se necesita, la parámetros que se necesita, así como el retorno
tipo y una breve descripción de esa función.
>> Así que echa un vistazo a rand.
Puede ser un poco prolijo y confuso, así que a veces me parece que
simplemente buscar en Google lo que quiero saber es la mejor manera de encontrar la respuesta.
Así que la práctica con Google.
Ser bueno en Google.
Se convertirá en su mejor amigo.
>> Además de Google, si usted no puede encontrarlo en Google, cs50.net/discuss, es
el foro de discusión.
Es probable que si usted tiene una pregunta, una de sus más de 700 compañeros también tiene que
cuestión y pudo haber pedido ya en el discutir
foros y haga que sea contestada.
Así que si usted tiene una pregunta común o usted tiene una pregunta que usted piensa
tal vez otras personas podrían haber quedado en, echa un vistazo a cs50.net/discuss.
>> Finalmente, los dos últimos, si quieres hablar con un ser humano real, oficina
horas de lunes a viernes.
También hay horas de oficina en línea para los estudiantes de extensión.
Y por último pero no menos importante, mí, signo de exclamación.
Todos ustedes tienen mi información de contacto.
Si necesitas algo, por favor, nunca dude en ponerse en contacto conmigo.
Siempre siéntase libre de hacerlo.
Muy pocos de ustedes me han agregado en Gchat, por lo que ha sido decepcionante,
pero espero que eso cambiará entre este y el próximo apartado.
Cualquier pregunta hasta ahora sobre los recursos?
Grande.
>> Por último, otro tapón para retroalimentación, sayat.me/cs50.
Usted me puede dar información anónima de cómo lo estoy haciendo.
Eso fue muy útil la semana pasada.
Tengo un par de comentarios de ustedes justo después de la sección, además de
otros estudiantes que lo vieron durante la semana, y
era increíblemente servicial.
Voy a tratar de limitar mi uso de la palabra "dulce", pero yo te mostraré mi
entusiasmo y emoción en otras formas.
Pero había otra adicional evaluaciones sustantivas,
ambas ventajas y delta.
Así que por favor, le doy ustedes retroalimentación en sus boletines de problemas.
Siéntase libre de dar su opinión en mi enseñanza.
Estoy aquí para ustedes.
>> Grande.
Eso es todo lo que tengo para la primera sección.
¿Alguien tiene alguna preguntas hasta ahora?
Y tengo una nota para el centro de control.
Estudiantes de extensión me han contactado a diciendo que no van a obtener cualquier archivo de audio,
pero eso está fuera de mi alcance para solucionar.
Así que espero, que obtiene resuelto en breve.
Si estás viendo en línea, hi, pero usted no me puede oír.
>> Así que primero, vamos que pasar por el BGF.
GDB, como ya he insinuado antes, es una herramienta de depuración
mucho mejor que printf.
Así que para empezar con GDB, chicos, si quiere abrir su aparato
y tomar el archivo que envié a usted antes - este archivo también será
disponible en línea en un poco -
y ejecutar BGF. / el nombre del archivo.
En primer lugar, por supuesto, usted tiene que compilar presentar porque BGF sólo funciona en
archivos ejecutables.
>> Pero si alguna vez desea iniciar GDB, el primero que se hace,
ejecuta GDB. / César.
Así que ese es el nombre del programa que estamos va a ir con él en estos momentos.
Así que voy a escribir hacer César, que me dará un archivo ejecutable
aquí resaltada en verde.
Y luego me voy a correr GDB. / Cesar.
>> Y ahí lo tienes.
Ya ves que tenemos un poco de texto diciéndome sobre la versión de GDB, dándome
alguna información sobre la garantía, y luego tienen el símbolo del PIB, lo que parece algo
de que nuestra petición de la línea de comandos, pero ya ves que está abierto
paren, GDB, cerca paren.
Antes de continuar y depurar el archivo que envié a todos ustedes, vamos a ver
algunos comandos útiles para que tengan un sentido de lo que vamos a cubrir.
>> Estos comandos están listados aquí, en el orden en el que por lo general los uso.
Así que empiezo mi programa ejecutando GBD. / Nombre del programa,
en este caso, César.
Y entonces lo primero que hago 99,9% de las veces es malo tipo de rotura.
Eso establece un punto de quiebre en el principal.
En esencia, lo que está haciendo allí es el programa que va a parar en
principal para que pueda empezar a examinarlo línea por línea, en lugar de correr todo
el camino a través.
Usted puede romper en diferentes puntos su código, pero principal es generalmente un
buen lugar para empezar.
>> El siguiente comando Corro es un negocio.
Esto comienza el programa en ejecución, y si usted necesita para entrar en la línea de comandos
argumentos, lo ejecuta ese comando.
Ejecutar con los argumentos.
Así que ya que vamos sobre una versión de C, que es el programa que ustedes
escribió para el conjunto de procesadores de dos -
éste, por supuesto, tiene algunos errores en lo que es de esperar que encontraremos -
vamos a correr correr con algunos comandos argumentos de la línea, porque César,
como ustedes saben por el problema establece las especificaciones, toma un poco de
argumentos de la línea de comandos.
>> El siguiente par de comandos, el siguiente uno se llama en realidad siguiente.
Este toma usted línea por línea a través de su programa.
Así golpear n luego Enter te lleva a la siguiente línea, la ejecución de
la línea anterior.
Paso no sólo le lleva a la siguiente línea, pero
te lleva al interior de funciones.
Así que si usted ha escrito una función en el código o si desea explorar un
a i, por ejemplo, usted puede golpear s, y en lugar de ir a la siguiente línea de
el archivo que estás pasando Ahora, usted realmente paso en
esta función y ver su código.
>> Lista muestra, muy fácil de usar formato, el 10 o así las líneas alrededor de
donde se encuentra actualmente en el código así que usted puede ver realmente el archivo
en lugar de tener que cambiar hacia atrás y hacia distintos puntos de vista.
Imprimir es como printf, como su nombre lo indica.
Eso demuestra lo que es igual a una variable.
>> Lugareños información es realmente útil.
Se trata de una versión especial de impresión.
Información lugareños te muestra todos los locales las variables, todas ellas imprime hacia fuera para usted
que están actualmente disponibles.
Así que en general, en lugar de tener que imprimir las cuatro variables que estoy
curiosidad sobre si estoy en un bucle, por ejemplo, acabo de escribir información locales,
y me lo que mi contador te muestro iguales, así como la matriz que soy
trabajando en iguales.
>> Finalmente, continúe.
Escribiendo pausa que se detiene en el punto de ruptura.
Se puede caminar a través de la línea de línea con la próxima y paso.
Continuar ejecuta el programa de su próxima romper punto o hasta la finalización si
no hay más puntos de quiebre.
Desactivar elimina puntos de quiebre si decidió romper en la principal era
inapropiada, quieres establecido en otro lugar.
Y, finalmente, q, abandonado, se sale de GDB.
>> Así que este programa,. / César, vamos mirar a través de este momento y
van a usar GDB para encontrar los errores en este programa.
Me encontré este programa antes con Compruebe el 50, y yo tengo uno ceño.
Todo lo que existía, lo recopiló, se pasado una gran cantidad de las pruebas, pero para
alguna razón, no pasó del quinto prueba, girando barfoo, todo en mayúsculas, en
E-D-U-I-R-R, todo en mayúsculas, usando tres como una clave.
Tengo bastante cerca.
Me bajé por una letra.
Así que hay algún pequeño error aquí.
He mirado a través de mi código.
Yo no podía entenderlo.
Con suerte, ustedes pueden ayudarme averiguar lo que este error es.
>> Así que ese es el error que estamos buscando.
Vamos a pasar a GDB.
Una vez más, me he encontrado GDB. / César, por lo que ahora estamos en el BGF.
Y lo que es lo primero Lo que debería hacer?
Yo sólo he entrado GDB.
Alguien me da una buena comando para entrar.
>> ESTUDIANTE: Romper principal.
>> JASON HIRSCHHORN: Romper principal.
Fantástico.
Escribamos que pulg
Ustedes pueden ver aquí o seguir a lo largo de sus ordenadores.
Main Break, y verás un punto de ruptura se fijó en -
me da un poco de dirección de memoria extraño, y también me da el número de línea.
Si tuviera que mirar hacia atrás en este archivo, Me daría cuenta de que la principal
ocurrido en la línea 21.
¿Qué debo ejecutar el siguiente?
¿Está mi programa en ejecución?
No.
Entonces, ¿qué debería funcionar ahora?
>> ESTUDIANTE: Run.
>> JASON HIRSCHHORN: Run.
¿Debo correr correr, o debería Añado algunas otras cosas en?
>> ESTUDIANTE: Ejecutar con el argumento.
>> JASON HIRSCHHORN: Ejecutar con los argumentos de comandos.
Y ya que estoy depuración de una muy específica caso, que debería entrar en ese
argumento de la línea de comandos.
Así que me voy a hacer correr tres, que es, de nuevo, la salida que recibí de Check 50.
Programa de inicio.
Vamos a través de un par de líneas.
Ahora verás que estamos en la línea 21.
¿Cómo sé que estamos en la línea 21?
Porque si miras a la izquierda de mi ventana de terminal, hay
que dice la línea 21.
Y eso me da, en realidad, la código que se encuentra en la línea 21.
Así que me equivoqué antes.
Principal no es en realidad en la línea 21.
Principal es un par de líneas por encima de 21.
Pero en la línea 21, que es donde estamos rompiendo.
Esta línea de código tiene aún no ejecutado.
Eso es importante.
La línea que se ve no tiene sido ejecutado todavía.
Esa es la siguiente línea de código usted está a punto de ejecutar.
>> Así que la siguiente línea, como ustedes son probablemente está familiarizado con, es este
condiciones comprobación para ver si tengo entrado en un argumento de línea de comandos.
Y una de i, lo que es el segundo parte de que va?
¿Qué es un ai?
>> ESTUDIANTE: Si lo cambia a un número entero.
>> JASON HIRSCHHORN: ¿Lo sientes?
>> ESTUDIANTE: Está cambiando la argumento en un entero.
>> JASON HIRSCHHORN: Así que una de i cambios arg v1 de una cadena a un entero.
Y entonces ¿cómo es de cheques?
>> ESTUDIANTE: Si hay una segunda argumento de línea de comandos, a un lado
de ejecutar el programa.
>> JASON HIRSCHHORN: Y lo que es la segunda mitad de este
Comprobar expresión booleana?
Esta parte de aquí, una de i?
>> ESTUDIANTE: Si es negativo.
>> JASON HIRSCHHORN: Asegurarse de que?
>> ESTUDIANTE: Asegurarse de que es, de hecho, positiva.
>> JASON HIRSCHHORN: Exactamente.
Esta es la comprobación para ver si es negativo, y si es negativo, lo
tener una sensación de la próxima línea de fuerza ser yo gritando en el usuario.
Así que vamos a golpear fin de ejecutar esta línea.
No vemos que la línea que los chicos quizás esperaba ver a gritar a la
usuario y luego volver, porque esta línea no se ha ejecutado.
Entré 3.
Así lo hice, de hecho, introducir dos comandos argumentos de la línea, y 3 es
mayor que cero.
Así que vimos esa línea, ejecutamos, pero no nos pisamos
dentro de la condición if.
>> Así que ahora, al lado, veo que estoy estableciendo clave int es igual a una i arg v1.
Así que eso es crearme una clave variable.
Así que si imprimo clave en este momento, porque que le permite ver la
valor dentro de la variable, clave es igual a 47.
Eso es raro, pero por supuesto, eso es porque no lo he hecho
ejecutado esa línea aún.
Así que ahora si le pego n, ejecutar esa línea, y hacer tecla de impresión, clave será igual a 3,
que es lo que esperamos que sea igual a.
>> Así que de nuevo, en el BGF, la línea que Veo que no has ejecutado todavía.
Usted tiene que golpear n o s o un número de otros comandos a realidad
ejecutar esa línea.
Tecla Imprimir.
La llave está en 3.
Hasta ahora, todo bien.
String es texto plano.
Vamos a ejecutar esa línea.
Me estoy poniendo una cadena de usuario.
>> Vamos a ver en mi Check 50, I introducir barfoo mayúsculas, por lo
eso es lo que voy a entrar.
Si ahora puedo imprimir texto plano.
Verás que es igual a una cadena.
Me da un poco de otra hexadecimal raro número, pero lo hace en
hecho de decir que mi cadena es barfoo.
Si yo quería ver lo que igualó clave en este punto, ¿cómo podría comprobar llave?
>> ESTUDIANTE: tecla Imprimir.
>> JASON HIRSCHHORN: tecla Print, exactamente.
Y de hecho, hay un acceso directo.
Si te cansas de escribir de impresión, que puede simplemente escribir p.
Así tecla p hace exactamente lo mismo.
Y de nuevo, yo lo veo es igual a 3.
>> Si quisiera saber lo tanto clave y barfoo igualó al mismo tiempo
pero yo estaba cansado de escribir cada uno de forma individual, que
podría escribir info lugareños.
Eso me da igual claves 3.
Texto sin formato es igual barfoo.
También me da estas dos cosas raras en la parte superior, esta variable iy
esta variable n.
>> Esos son realmente existente en mi programa principal.
No los hemos encontrado, sin embargo, sino como una vista previa, los
existir en mi bucle for.
Así que ahora mismo, que equivalen a un poco raro números porque no han sido
inicializan todavía, pero que todavía existen en la memoria, por lo que sólo están fijados
a algún valor de basura.
Pero sí vemos clave en la llanura texto allí.
>> Así que voy a ejecutar esta línea, la línea 34, el bucle para.
Vamos a saltar en el bucle pulsando n.
Y estamos dentro del bucle.
Estamos en nuestro primer cheque.
Y una vez más, este tipo de deben buscar familiar para usted, porque se trataba de un
Programa de César que fue escrito, pero de nuevo, tiene algún tipo de error.
>> Y ahora, si lo hago de información locales, porque soy dentro de ese bucle, verás
que i es igual a cero, ya que esperamos.
Eso es lo que nos propusimos a e inicializado que en el bucle for.
n es igual a 6.
Eso también hace sentido porque establecemos al strlen de texto sin formato.
Así que me gusta hacer información locales o de impresión a la variable a menudo para asegurarse de que
todo es siempre lo Espero que para igualar.
En este caso, todo está lo que espero que sea igual a.
>> Así que vamos a empezar a moverse a través de este bucle.
La línea que estoy es la línea 36, ​​si llanura texto i es mayor que una y la llanura
texto i es menor que o igual a z.
Sé que mi problema no es con mi primera carta, que es con la segunda letra.
Si miramos hacia atrás a la llegada 50, B va a E bien.
Estoy tomando la A y dejarlo como una A, no la cambia por D. Así
algo anda mal con la segunda letra.
Así que me voy a mover en un segundo.
>> Pero si yo quería comprobar lo sencillo texto que igualó en este particular,
caso, yo creo que debería ser qué?
¿Qué debería de texto plano que ser igual en esta primera ronda a través del bucle?
>> ESTUDIANTE: Zero?
>> JASON HIRSCHHORN: Texto simple de I?
Así debería ser capital B. Yo, por supuesto, es igual a cero, pero el texto sin formato
soporte de abrazadera cerrada es igual a cero B porque las cadenas, como vimos la semana pasada,
somos matriz, por lo que estamos recibiendo la primer carácter de eso.
Así que de nuevo, si Imprimí texto plano de Yo, yo, de hecho, conseguir el carácter
B. Y eso es limpio, ¿verdad?
Yo en realidad no tengo texto plano I. Eso no es una de las variables que establecí
o inicializado, pero puede imprimir a cabo toda una serie de cosas
si desea.
>> Pero vamos a pasar a través.
Si texto plano I es mayor que A y texto plano I es menor que o igual a
Z, que claramente es cierto porque tenemos una capital de B. Voy a correr
algún comando en él.
Vimos que las matemáticas la semana pasada, así que vamos a dar por sentado de que funciona
correcto según Check 50.
>> Estas llaves, el primero demostré que estaba saliendo de la si
condición, el segundo uno mostró que me estoy saliendo del bucle for.
Y ahora cuando golpeé A continuación, vamos a ver estamos de vuelta en el bucle de nuevo.
Vamos a través de la para el bucle de nuevo.
Vamos realmente paso en el segundo iteración del bucle y el tipo
info lugareños.
>> Así que estamos en la segunda iteración de nuestro bucle para.
I es igual a 1, lo que esperamos.
N es igual a 6, que esperamos.
Es igual a la tecla 3, la cual esperamos.
Y de texto sin formato, verás, es igual a EARFOO ahora, no más porque barfoo
en nuestra iteración anterior, el B fue cambiado a una capital E. Así que estamos a punto
para encontrar el problema, por lo que este es donde vamos a
sumergirse en la depuración.
Pero ¿alguien tiene alguna pregunta acerca de lo que hemos hecho hasta ahora?
Fantástico.
>> Así que estamos a punto de ejecutar esto si condición, soporte de texto plano Cerré
soporte mayor que A y texto plano I menos de o igual a la Z. Pero antes
Entro en eso, porque aquí es donde Sé que mi error es, quiero señalar
fuera de texto sin formato de I. Así vamos a poner impresión.
Lo hace igual al carácter A, de modo que parece hasta ahora, todo está bien y bueno.
>> Así que espero que esta línea por mi lógica, esta línea debe ser verdad.
Es una letra mayúscula.
Pero si le pego n, nos damos cuenta de que este línea, de hecho, no se ha ejecutado.
Salté a la otra persona si.
¿Por qué sucedió eso?
>> ESTUDIANTE: Debido a que tiene su condición de texto plano es mayor
que A, no es igual o mayor que.
>> JASON HIRSCHHORN: Así que tuve mi texto plano I es mayor que A, no mayor
que o igual a.
Así que, claramente, la capital A no hizo desencadenar esta condición si, y lo hicimos
no entrar en él, y lo hicimos no hacer el cambio necesario.
Así que es eso, en realidad.
Me di cuenta de mi error.
Pudiera volver atrás en mi archivo de origen, cambiarla y actualizarla y
Ejecute una comprobación 50 de nuevo.
>> Pero vamos a ver, sólo por la pedagogía de bien, si sigo adelante.
La otra persona si no se ejecuta bien, pero lo que en cambio es igual a es el comando
eso no cambia.
Por lo que no ha cambiado en absoluto, y si imprimir texto plano aquí, vamos a ver que va
a través de ese bucle no lo hizo, de hecho, cambiar ese segundo carácter en absoluto.
Es todavía un capital de A.
>> Así que de nuevo, estamos depurando nuestro error.
Nos dimos cuenta de que no había una lógica que falta.
Y hemos depurado antes de tiempo antes realmente ejecutar esa línea,
pero se habría dado cuenta si hubiéramos sólo Siguiente golpear y saltar a esa persona si,
eso significa que que si la condición No era cierto.
Nosotros no, de hecho, obtenemos el resultado que se esperaba.
Así que nos podría haber sido incitado, tuvimos si no hubiéramos estado tan astuto, que mirar
que si el estado y comprobar si, de hecho, nuestra condición debe evaluar a
cierto en el contexto actual.
>> Eso es todo para la depuración de este programa.
¿Alguien tiene alguna pregunta?
¿Qué comando podría golpear a dejar de GDB?
P. ¿Y entonces le pedirá, sale de todas maneras?
Sí o no.
Voy a golpear sí, y te he dejado GDB.
>> Así que fue una cartilla rápida de GDB.
En realidad, en un escenario real, Hice esto en horario de oficina.
Me GDBed este programa exacto en horas de oficina con un estudiante.
Y si nos remontamos a los comandos que vimos antes, se utilizó ruptura principal, primero
cosa que hicimos.
Utilizamos carrera con los argumentos de línea de comandos, segunda cosa que hicimos.
Utilizamos próxima mucho para mover nosotros a través de las líneas.
Y de nuevo, la versión corta de la próxima es n.
Eso está en los paréntesis en gris en la diapositiva.
>> No usamos el paso, pero no lo hicimos necesariamente tienen que para este caso.
Pero podríamos utilizarlo en un poco más tarde en la actualidad si se está depurando, por
ejemplo, la búsqueda binaria cuando binario búsqueda se llama en una separada
función, pero hay algún error con él.
Vamos a querer entrar en la llamada a la búsqueda binaria y
realidad depurarlo.
Lista que no use ya sea porque teníamos un buen sentido de nuestro código, pero si
ha querido tener una idea de lo que el código que estaba cerca, podía simplemente utilizo lista.
>> Imprimir utilizamos, los locales de información que utilizamos.
Continuar nosotros no necesitamos usar en este caso, tampoco tenemos que utilizar
desactivamos, pero hicimos uso renunció.
Una vez más, estos 10 mandamientos, practicarlas.
Si usted entiende estos 10 mandamientos, usted debe estar preparado para depurar cualquier
emitir con GDB.
>> Así que vamos a seguir, una vez más, a la quid de la sección de hoy, repasando
estos ordenación y búsqueda algoritmos.
Antes de hacerlo, una vez más, cualquier pregunta, comentarios, inquietudes para GDB?
Así es todo el mundo va a usar BGF en lugar de printf?
Así que todo el mundo, por el amor de perpetuidad, todo el mundo asiente con su cabeza a la derecha
ahora, así que voy a verte en horario de oficina y todos los TFS te verán y
que van a decir, muéstrame cómo utilizar GDB, y podrás
para mostrar, ¿no?
Un poco?
Tal vez con suerte.
Genial.
>> Así que vamos a pasar a ordenación y búsqueda.
Vas a ver que tengo una lista ya ordenada para nosotros, pero eso no va
ser el caso siempre.
Así, en el conjunto de problemas de especificaciones para problema fijó tres, tienes pantalones cortos
que se puede ver, y que en realidad le pregunta a ver esos pantalones cortos.
También en la conferencia la semana pasada, fuimos muchos de estos algoritmos, así que estoy
No va a pasar un tiempo en la clase va sobre estos algoritmos de nuevo o dibujo
fotos para ver cómo se algoritmos funcionan.
Una vez más, que la información que pueda volver a ver conferencia, o que la información
es capturado extraordinariamente en los pantalones para estas búsquedas, todos
que están disponibles en cs50.net.
>> Así que en vez, lo que vamos a hacer es escribir estos programas.
Tenemos un sentido, un modelo mental, de cómo trabajan, y así lo vamos
hacer es codificar los de verdad.
Vamos a convertir ese modelo mental, ese cuadro, si se quiere, en el
código real.
Y si fueras un poco confundido o nebuloso en el modelo mental, estoy totalmente de
entender.
>> No estamos realmente va a saltar al código inmediatamente.
Así, mientras que este indicador en esta diapositiva pregunta a código de búsqueda binaria, y
en realidad, una versión iterativo de búsqueda binaria, lo primero que
Realmente quiero que hagas es escribir algo de pseudocódigo.
Por lo que tiene este modelo mental de cómo los trabajos de búsqueda binaria.
Tome una hoja de papel si tiene uno de fácil acceso, o abrir un
editor de texto, y me gustaría a todo el mundo a escribir.
Tomar cuatro minutos para escribir la pseudocódigo para la búsqueda binaria.
>> Una vez más, pensar en ese modelo mental.
Vendré por aquí si tiene preguntas y podemos dibujar la imagen fuera.
Pero primero, antes de empezar la programación, Me gustaría escribir la
pseudocódigo para búsqueda binaria así que cuando nos bucear, tenemos una cierta dirección como
a donde debemos ir.
>> ESTUDIANTE: ¿Podemos asumir el conjunto de valores que obtenemos ya está ordenado?
>> JASON HIRSCHHORN: Así que para búsqueda binaria trabajar - excelente pregunta -
que tomar en una ordenada matriz de valores.
Así que supongamos que va a funcionar.
Volveremos a esta diapositiva.
Usted verá en púrpura de la función declaración es bool binary_search int
valor, valores int, int n.
Esto debería resultar familiar si has ya abordado o conseguido su
las manos sucias con el conjunto de problemas.
>> Pero ese es su declaración de la función.
Una vez más, no debería tener que preocuparse por que tanto en este momento.
Lo que realmente quiero hacer es tomar Cuatro minutos para binario pseudocódigo
Buscar y, a continuación, vamos a ir más que como un grupo.
Y voy a entrar en razón.
Si usted tiene preguntas, por libertad para que levante la mano.
>> ¿Por qué no te tomas dos minutos más para terminar el pseudocódigo?
Sé que esto puede parecer ridículo que estamos gastando tanto tiempo en
algo que ni siquiera es realmente en C, pero sobre todo para estos más
algoritmos difíciles y problemas conjuntos que tenemos que averiguar,
comenzando en pseudocódigo no preocuparse acerca de la sintaxis, sólo preocuparse
la lógica, es increíblemente útil.
Y de esa manera, no vas a resolver dos problemas muy difíciles a la vez.
No eres más que centrarse en la lógica, y entonces usted se mueve en la sintaxis.
>> Aceptar.
Empecemos pasar por el pseudocódigo.
He escrito aquí, binario Búsqueda pseudocódigo.
Vamos a escribir esto en el abordar juntos.
O lo escribiré y te voy a dar me las indicaciones que necesito.
Entonces, ¿puede alguien darme la primera línea del pseudocódigo que
escribió para la búsqueda binaria?
Sí, Annie?
>> ESTUDIANTE: Si bien la longitud de la lista es mayor que cero.
>> JASON HIRSCHHORN: Mientras que la longitud de la lista superior a cero.
Y una vez más, vemos algunos C-buscando cosas sintácticas de aquí.
Pero la mayor parte de esto está en Inglés.
¿Alguien tiene alguna línea que ponen antes de esto en su pseudo-código?
>> ESTUDIANTE: Obtiene un array de ordenar números.
>> JASON HIRSCHHORN: Usted escribió "obtiene una matriz de números ordenados. "Per la
declaración de la función, vamos a estar pasando una matriz de números ordenados.
>> ESTUDIANTE: [inaudible].
>> JASON HIRSCHHORN: Así vamos a tener eso.
Pero sí, si no teníamos eso, tendría que ordenar nuestra gama de
números, porque la búsqueda binaria sólo funciona en arrays ordenados.
Así, mientras que la longitud de la lista es igual a cero, estoy va a poner en algunas llaves
para que se vea un poco más como C. Pero mientras, parece en un mapa
while, por lo que dentro de este tiempo loop ¿Qué necesitamos para
hacer por búsqueda binaria?
>> Otra persona que no me ha dado una responder todavía, pero que escribió esto?
>> ESTUDIANTE: Vaya a la mitad de la lista.
>> JASON HIRSCHHORN: Tom.
Ir a la mitad de la lista.
Y la pregunta de seguimiento, lo que qué hacemos una vez que estemos en la
mitad de la lista?
>> ESTUDIANTE: Haga una revisión de si eso es el número que está buscando.
>> JASON HIRSCHHORN: Excelente.
Ve la mitad de la lista y comprobar si nuestro valor está allí -
fantástico.
¿Alguien tiene algo más que era diferente a esto?
Eso es exactamente correcto.
>> Lo primero que hacemos en la búsqueda binaria es ir a la mitad de la lista y
comprobar para ver si nuestro valor está ahí.
Así que supongo que si nuestro valor es allí, ¿qué hacemos?
>> ESTUDIANTE: Volvemos a cero [inaudible].
>> JASON HIRSCHHORN: Sí, si nuestro valor está ahí, lo encontramos.
Así que podemos decir de alguna manera, sin embargo, esto función se define, le decimos al usuario
lo encontramos.
Si no está allí, sin embargo, eso es donde esto se complica.
Así que si no está allí, alguien que estaba trabajando en la búsqueda binaria o
tiene una idea ahora, ¿qué hacemos?
>> ESTUDIANTE: Pregunta.
>> JASON HIRSCHHORN: ¿Sí?
>> ESTUDIANTE: ¿Es la matriz ya ordenada?
>> JASON HIRSCHHORN: Sí, estamos asumiendo la matriz ya está ordenado.
>> ESTUDIANTE: Entonces usted tiene que comprobar si el valor que usted ve es mayor que
el valor que usted quiere, usted puede moverse a la mitad de la otra mitad.
>> JASON HIRSCHHORN: Entonces, si el medio de la lista es mayor que lo que estamos
buscando, entonces nosotros qué?
Realizamos movimientos interiores de dónde?
>> ESTUDIANTE: ¿Quieres ir a la mitad de la lista con
números más bajos que eso.
>> JASON HIRSCHHORN: Así que vamos a llamar a que la izquierda.
Así que si en medio es mayor, podemos buscar la mitad izquierda de la lista.
Y luego por la búsqueda, lo que Qué quiero decir con la búsqueda?
>> ESTUDIANTE: [inaudible].
>> JASON HIRSCHHORN: Vamos a la media.
En realidad nos repetimos esta cosa.
Volvemos a través de nuestro bucle while.
Te voy a dar el último -
otra cosa, si, en medio es menos de lo que lo que hacemos, ¿qué hacemos aquí?
>> ESTUDIANTE: Ir a la derecha.
>> JASON HIRSCHHORN: Búsqueda de la derecha.
Esto se ve bien, pero ¿alguien tiene nada de lo que puede estar presente o
cualquier otra cosa que se pone en su pseudo-código?
Así que esto es lo que tenemos hasta ahora.
Mientras que la longitud de la lista es mayor de cero, vamos a ir
a la mitad de la lista y comprobar si nuestro valor está ahí.
>> Si el medio es mayor, vamos a buscar a la izquierda, más si el medio es
menos, vamos a buscar la derecha.
Así que todos hemos tenido alguna familiaridad con los términos que usamos en informática
y las herramientas que tienen.
Pero usted ya notará que éramos hablando en Inglés, pero encontramos un
Muchas cosas que parecían un mapa a partir de herramientas que tenemos en nuestra caja de herramientas de codificación.
Así que de buenas a primeras, no estamos va a codificar en realidad todavía.
>> ¿Qué es lo que vemos aquí en Inglés que los mapas a cosas que podemos escribir en C?
>> ESTUDIANTE: While.
>> JASON HIRSCHHORN: While.
Así que este tiempo aquí mapas sobre a qué?
>> ESTUDIANTE: Un bucle while.
>> JASON HIRSCHHORN: Un bucle while?
O probablemente, más en general, un bucle.
Queremos hacer algo una y otra vez.
Así que vamos a codificar un bucle.
Y ya sabemos, porque hemos hecho esto un par de veces y nos
tienen un montón de ejemplos por ahí, cómo en realidad para escribir
este índice para un bucle.
Así que debería ser bastante fácil.
Debemos ser capaces de conseguir que comenzado con bastante rapidez.
>> ¿Qué otra cosa es lo que vemos aquí?
¿Qué otras estructuras de sintaxis, las cosas que estamos familiarizados en C, ¿nos
ya tener un sentido del Based fuera de las palabras que utilizamos?
Sí, Anna?
[Inaudible]
es broma.
Anna, adelante.
>> ESTUDIANTE: Si y más.
>> JASON HIRSCHHORN: Si y otra cosa - aquí mismo.
Entonces, ¿qué los ve?
>> ESTUDIANTE: Un if-else.
>> JASON HIRSCHHORN: Sí, condiciones, ¿no?
Así que probablemente tendrá que escribir algunas condiciones.
Y de nuevo, aunque quizás confuso al en primer lugar, por lo general tienen un sentido ahora
de cómo escribir las condiciones y la sintaxis para las condiciones.
Y si no lo hacemos, sólo miramos el sintaxis de condiciones, cortar y pegar
que, debido a que sabemos que necesitará una condición aquí.
Cualesquiera otras cosas que vemos ese mapa en cosas que podríamos necesitar hacer en C?
Sí, Aleha?
>> ESTUDIANTE: Esto puede ser obvio, por sólo la comprobación si un
valor es igual a algo.
>> JASON HIRSCHHORN: Entonces, ¿cómo comprobamos y - a fin de ir a la mitad de la lista
y comprobar si nuestro valor está allí?
¿Cómo hacemos eso en C?
¿Cuál es la sintaxis para eso?
>> ESTUDIANTE: Es igual, es igual.
>> JASON HIRSCHHORN: igual, es igual.
Así que este cheque es, probablemente, va ser un signo de igual, es igual.
Así sabremos lo que necesitamos que en algún lugar.
Y, de hecho, sólo en escribirlo, vemos esas otras cosas.
Vamos a tener que hacer un poco de operadores de comparación en allí -
fantástico.
Así que en realidad se parece, en términos un grande, no hemos escrito
palabra de código de C todavía.
Pero tenemos el modelo mental hacia abajo a través de conferencias y los pantalones cortos.
>> Escribimos pseudo-código como un grupo.
Y ya tenemos el 80% si no se 90% de lo que necesitamos hacer.
Ahora, sólo tenemos que codificar , lo que de nuevo, es un
problema no trivial de resolver.
Pero al menos estamos atrapados en la lógica.
Por lo menos ahora, cuando vamos a las horas de oficina, Lo que puedo decir, yo sé lo que necesito
hacer, pero puede usted recordar me de la sintaxis?
O incluso si las horas de oficina están llenas, usted ¿Puede Google para la sintaxis, en lugar
que estar atrapado en la lógica.
>> Y de nuevo, en lugar de tratar de resolver la lógica y los problemas de sintaxis todos
a la vez, a menudo es mucho mejor romper esos dos problemas difíciles apagado en
dos más manejables y hacer el pseudo-código primero y luego el código en C.
Así que vamos a ver lo que hice para el pseudo-código antes de tiempo.
>> Mientras que la longitud de la lista es mayor que cero, mira la media
de la lista.
Si el número se encuentra devuelto cierto, otra cosa si el número más alto, búsqueda izquierdo.
Porque si el número más bajo, búsqueda derecho, devolver false.
Así que se ve casi idéntico, si no casi idéntica a lo que escribimos.
En realidad, Tom, lo que dijiste en primer lugar, romper el medio de la lista y si
número que se encuentra en dos estados es en realidad lo que hice.
>> Yo los he combinado allí.
Yo debería haber escuchado a que la primera vez.
Así que ese es el pseudo-código que tenemos.
Si quieres ahora, lo siento, vaya De vuelta a nuestro problema inicial.
Del código binary.c Let.
Así implementar una versión iterativa de búsqueda binaria utilizando el siguiente
declaración de la función.
>> Y no es necesario para copiar hacia abajo por el momento.
De hecho voy a abrir hasta aquí binary.c.
Así que no es la declaración de la función en el centro de la pantalla.
Y verás que tomé el pseudo-código a partir de mis lados, pero casi idéntico
a lo que escribimos, y poner eso por usted.
Así que ahora, vamos a tardar cinco minutos para codificar esta función.
>> Y de nuevo, si usted tiene cualquier pregunta, levantar la mano, que me haga saber, voy a
entrar en razón.
>> ESTUDIANTE: [inaudible].
>> JASON HIRSCHHORN: Así que tomó el binario definición de la búsqueda en la
Arriba, en la línea 12.
Eso es lo que tengo para mi diapositiva.
Y entonces todo este pseudo-código que acabo de copiar y pegar de la diapositiva,
pseudo-código de diapositivas.
Todavía no estoy oyendo [inaudible].
>> Así que si usted ha terminado su aplicación, quiero comprobarlo.
Les envié un correo electrónico el archivo helpers.h anteriormente en esta clase.
Y estará disponible en línea, así para su descarga para observar a la gente
esta vez la sección retrasado.
Y acabo de utilizar la distribución genérica código de pset3.
Así que tomé find.C, usar mi archivo helpers.h en lugar del archivo helpers.h
que es dado en el código de distribución.
>> Y tuve que hacer otro cambio en find.C en lugar de llamar simplemente
búsqueda, llamar binary_search.
Así que si quieres probar el código, saben que así es como se hace.
De hecho, cuando vamos a estar corriendo este código en estos momentos, acabo de hacer una copia de
mi directorio pset3, de nuevo, intercambia los archivos de ayudantes y luego hizo que
cambiar en find.C para llamar binary_search en lugar de simplemente buscar.
>> JASON HIRSCHHORN: Si.
¿Tienes una pregunta?
>> ESTUDIANTE: No importa.
>> JASON HIRSCHHORN: No se preocupe.
Bueno, vamos a empezar.
Vamos a codificar esto como un grupo.
Una nota aparte.
De nuevo, esto es, puede ser fácilmente intercambiado por Problemas de Tres.
Tengo mi archivo helpers.h que, en lugar que el helpers.h se nos da,
declara búsqueda binaria, burbuja ordenar y ordenación por selección.
Y en find.c te darás cuenta en línea, ¿qué es eso, la línea 68, que llamamos binario
en lugar de buscar en esta categoría.
Así que de nuevo, el código que se encuentra disponible en línea o el código que son
creando en estos momentos se puede intercambiar fácilmente por p el set 3 para comprobarlo.
>> Pero primero, vamos a código de búsqueda binaria.
Nuestra declaración de la función, volvemos un bool.
Tomamos un entero llamado valor.
Tomamos una matriz de enteros llamado valores, y tomamos n ser
el tamaño de la matriz.
En la línea 10, aquí, tengo aguda incluyen stdbool.h.
¿Alguien sabe por qué está ahí?
Entonces, ¿qué esa línea de código hace?
>> ESTUDIANTE: Le permite utilizar un tipo de retorno void.
>> JASON HIRSCHHORN: Exactamente.
>> ESTUDIANTE: ¿O es una biblioteca que permite utilizar un tipo de retorno void.
>> JASON HIRSCHHORN: Así que la aguda incluyen line stdbool.h me da un poco de
definiciones y declaraciones de las cosas que me permite utilizar en
esta biblioteca.
Así que entre los que está diciendo que no hay este tipo bool llama, y ​​puede ser
verdadero o falso.
Así que eso es lo que hace esa línea.
Y si yo no tenía esa línea, lo haría tener problemas para escribir este
palabra aquí, bool, justo ahí.
Exactamente derecha.
Así que necesito que en este código.
Aceptar.
Así que esto, de nuevo, es un proceso iterativo versión, no una recursiva.
Así que vamos a empezar.
>> Vamos a empezar con esta primera línea de código de pseudo.
Y es de esperar, lo haremos - o no es de esperar.
Vamos a ir alrededor de la habitación.
Vamos a ir línea por línea, y yo te ayudaremos a determinar la línea que necesitamos
para escribir primero.
Así, mientras que la longitud de la lista es mayor que cero.
Vamos a empezar en la parte delantera.
¿Qué línea debo escribir aquí, en el código?
>> ESTUDIANTE: Si bien el paréntesis n es mayor que 0.
>> JASON HIRSCHHORN: Mientras n es grande que 0.
Por lo tanto n es el tamaño de una lista, y estamos comprobando si -
>> [VOCES interponiendo]
>> JASON HIRSCHHORN: - ¿Cómo?
>> ESTUDIANTE: ¿Cómo sabemos que n es el tamaño de la lista?
>> JASON HIRSCHHORN: Lo siento.
Por la especificación pset, la búsqueda y ordenar las funciones que necesita para escribir,
n es el tamaño de la lista.
Me olvidé de explicar que aquí.
Pero sí. n es el tamaño de la lista, en este caso.
Así, mientras que n es mayor que 0.
Aceptar.
Esto puede resultar un poco problemático sin embargo, si las cosas siguen.
Porque vamos a seguir para conocer la tamaño de la lista lo largo de este
función, pero dicen que partimos con una serie de 5 números enteros.
Y vamos a través y no tenemos ahora reducido a
una matriz de 2 enteros.
Cuál 2 enteros es eso?
El tamaño es de 2 ahora que queremos a ver, pero que 2 es eso?
¿Eso tiene sentido, esa pregunta?
>> Aceptar.
Se lo preguntaré de nuevo.
Así que empezamos con este conjunto de 5 enteros, y n es igual a 5, ¿no?
Vamos a realizar aquí.
es probable que cambiaremos el tamaño, derecha, como las cosas siguen.
¿Qué es lo que decimos que queremos hacer.
No queremos buscar lo llena de nuevo.
Así que digamos lo cambiamos a 2.
Tomamos la mitad de la lista que es raro.
Tan apenas escoja 2.
Así que ahora n es igual a 2.
Pido disculpas por la mala marcadores de borrado en seco.
¿Cierto?
Y estamos buscando a través de la lista de nuevo con una lista de tamaño 2.
Bueno, nuestra gama es todavía de tamaño 5.
Nosotros decimos que sólo queremos buscar 2 puntos en el mismo.
Así que 2 puntos son esos?
>> ¿Eso tiene sentido?
¿Son los que quedan 2 puntos?
¿Son las correctas 2 puntos?
¿Son los medios 2 puntos?
Hemos roto el problema hacia abajo, pero En realidad no sé qué parte de
el problema que todavía estamos viendo, sólo por tener estas 2 variables.
Así que necesitamos un poco más y luego, mientras que n es mayor que 0.
Necesitamos saber dónde está ese n es en nuestra gama actual.
>> Así que ¿alguien tiene un cambiar a esta línea?
La mayor parte de esta línea es perfectamente correcto.
¿Hay otra adición?
¿Podemos cambiar algo que n que esta línea un poco mejor?
Mm-hm?
>> ESTUDIANTE: ¿Se puede inicializar una variable como la longitud de n que va a continuación, puede utilizar
más adelante en la función?
>> JASON HIRSCHHORN: Así inicializar una longitud variable a N,
y usamos esa tarde?
Pero entonces nos actualizamos longitud y aún con este problema en el que
reducir la duración de nuestro problema, pero nunca se sabe donde, en realidad,
que la longitud de los mapas en.
>> ESTUDIANTE: ¿No es el que va a pasar más tarde, cuando usted está diciendo, busca a la izquierda,
buscar ¿no?
Vas a ir a una diferente área de su -
>> JASON HIRSCHHORN: Vamos a ir a un área, pero ¿cómo sabemos
que han de ir?
Si sólo tenemos la matriz y esto n, ¿cómo sabemos dónde
ir a la de la matriz.
En el fondo, ¿no?
>> ESTUDIANTE: ¿Tiene usted, como, una menor atado y una variable de cota superior o
algo así?
>> JASON HIRSCHHORN: OK.
Así que esta es otra idea.
En lugar de simplemente hacer el seguimiento de la tamaño, hacemos un seguimiento de la menor y
variable de cota superior.
Entonces, ¿cómo se calcula el tamaño de un límite inferior y límite superior?
>> [VOCES interponiendo]
>> JASON HIRSCHHORN: Resta.
Y también hacer el seguimiento de la menor atado y límite superior de dejarnos saber,
estamos buscando estos dos?
¿Estamos buscando a estos dos aquí?
¿Estamos buscando a los dos del medio?
Probablemente no es el centro de los dos, porque esto, de hecho, es la búsqueda binaria.
Pero ahora vamos a ser capaces de obtener el tamaño, sino también de los límites de la matriz.
En esencia, si tenemos nuestro gigante guía telefónica, que rasgar por la mitad.
Ahora sabemos que cuando más pequeño libreta de teléfonos es.
Pero no estamos realmente rasga la guía telefónica por la mitad.
Todavía tenemos que saber dónde está el nuevos límites de nuestro problema es.
¿Alguien tiene alguna pregunta acerca de eso?
¿Sí?
>> ESTUDIANTE: ¿Funcionaría mediante la creación de un variable i, que entonces apenas muevo
la posición de i con respecto a su posición actual, y la longitud, n?
>> JASON HIRSCHHORN: ¿Y qué es i?
>> ESTUDIANTE: Como he de ser como una especie de -
Al igual que usted inicializa i para ser el posición media de la matriz.
Y luego, si el valor en la posición i en el medio de la matriz en encontrado que
ser menor que el valor que usted necesita, i ahora se convierte en la longitud de la matriz, más
el valor de i dividido por 2.
Al igual, ver, usted cambia de i -
>> JASON HIRSCHHORN: Así es.
>> ESTUDIANTE: - hasta el -
>> JASON HIRSCHHORN: Así que estoy casi positivo que va a funcionar.
Pero el punto es, que necesita dos piezas de información aquí.
Usted puede hacerlo con principio y fin, o puede hacerlo con el tamaño, y luego
algún marcador.
Pero usted no necesita dos piezas de la información aquí.
No se puede llegar a funcionar con sólo uno.
¿Eso tiene sentido?
>> Así que vamos a ir a través de, y vamos a hacer [inaudible]
y crear algunos marcadores.
Así que ¿qué se escribe en el código?
>> ESTUDIANTE: Me acaba de decir int límite uno es igual a 0.
>> JASON HIRSCHHORN: Llamemos que int, comenzando.
>> ESTUDIANTE: OK.
>> JASON HIRSCHHORN: Eso hace más sentido para mí.
¿Y?
>> ESTUDIANTE: Yo dije, supongo, int fin.
>> JASON HIRSCHHORN: int fin.
>> ESTUDIANTE: Supongo, n menos 1, o algo por el estilo.
Al igual que, el último elemento.
>> JASON HIRSCHHORN: Así que usted escribió, int comenzando igual a 0, y coma, y ​​int
final es igual a n menos 1, punto y coma.
Así que, esencialmente, lo que estamos haciendo aquí, 0 la primera posición.
Y como sabemos, en arreglos, ellos no van hasta n, van hasta n menos 1.
Así que tenemos algunos límites de nuestra matriz.
Y estos límites iniciales resultan ser los límites iniciales de nuestro problema.
Aceptar.
Así que eso suena bien.
Entonces, si nos remontamos a esta línea, mientras que Longitud de la lista es mayor que 0,
lo que, en lugar de n, debe ponemos aquí?
>> ESTUDIANTE: Escriba terminando minus principio.
>> JASON HIRSCHHORN: Mientras que termina menos comienzo es mayor que 0?
Aceptar.
Y podríamos, si quisiéramos hacer que un poco más bonito, lo que
otra cosa podíamos hacer?
Si quisiéramos limpiar este código un poco?
¿Cómo podemos deshacernos del 0?
Esta es sólo una cuestión de estilo.
Es correcto en estos momentos.
>> ESTUDIANTE: Ending no igualdad de principio?
>> JASON HIRSCHHORN: Podemos hacer qué?
>> [VOCES interponiendo]
>> ESTUDIANTE: Ending es mayor?
>> JASON HIRSCHHORN: Si.
Sólo podemos hacer mientras que termina es mayor que principio.
Derecha.
Añadimos principio hasta el otro lado de eso, y nos libramos de la 0.
Así que esto sólo se ve una poco más limpia.
Aceptar.
Así, mientras que la longitud de la lista es 0, escribimos que, si bien es mayor que termina
que comenzar.
Vamos a poner en nuestra necesaria llaves, y entonces lo primero que
que queremos hacer es mirar a en una pequeña lista.
Usted?
¿Me puede dar el -
>> ESTUDIANTE: Si paréntesis valor corchete -
>> JASON HIRSCHHORN: Si paréntesis corchete valor.
>> ESTUDIANTE: Ending dividido por 2.
>> JASON HIRSCHHORN: Ending?
>> ESTUDIANTE: Yo veo un problema con su -
>> JASON HIRSCHHORN: OK.
Bueno, mira el centro.
¿Cómo sabemos lo que el medio es?
Sí.
Así que permítanme borrar ese código.
¿Cómo sabemos lo que el medio es?
En cualquier cosa, cuando usted tiene el principio y al final, ¿cómo encontrar
el medio?
>> ESTUDIANTE: Promedias.
>> ESTUDIANTE: Usted agregarlos juntos y luego -
>> JASON HIRSCHHORN: Agréguelos juntos y luego?
>> ESTUDIANTE: ¿Y usted hace un promedio.
Divida por 2.
>> JASON HIRSCHHORN: Agréguelos juntos y dividir por 2.
Así int media es igual?
Tom, usted puede dar a mí?
>> ESTUDIANTE: A partir del plus de fin -
>> JASON HIRSCHHORN: Inicio además de acabar.
>> ESTUDIANTE: Todos, soporte, dividido por 2.
>> JASON HIRSCHHORN: All, entre paréntesis, dividido por 2.
Así que eso me da el medio de nada, ¿correcto?
>> ESTUDIANTE: También es necesario redondear esto.
>> JASON HIRSCHHORN: Lo que se hace significa, necesito redondear esto?
>> [VOCES interponiendo]
>> ESTUDIANTE: porque si es un extraño número, entonces es como -
>> JASON HIRSCHHORN: Bueno, está bien.
Así que podría redondear esto.
Pero si es un número impar, a 5, lo que pueda teniendo 1 lejos de la mitad.
O si es un número par, más bien, eso es un mejor caso.
Si se trata de 4, solo tenemos 4, puedo tomar la primera "media", dijeron ellos o
el segundo "medio".
Cualquiera podría trabajar para una búsqueda binaria, así que en realidad no necesito redondear.
Pero hay otra cosa que me que mirar a esta línea.
Nosotros no podríamos darnos cuenta todavía, pero vamos a volver a ella.
Debido a que esta línea en realidad todavía necesita una cosa más.
>> Pero hasta ahora, hemos escrito cuatro líneas de código.
Tenemos nuestro principio y terminando marcadores.
Tenemos nuestro bucle while, que asigna de forma directa a nuestro pseudocódigo.
Estamos pensando en el medio que se asigna directamente sobre nuestro pseudocódigo.
Yo diría que esto va a la media de la lista, esta línea de código.
Y luego, una vez que vamos a la mitad del la lista, lo siguiente que tenemos que hacer
es comprobar si nuestro valor está ahí para el pseudocódigo que escribió antes.
>> Entonces, ¿cómo comprobamos si nuestro valor está en la mitad de la lista?
Usted.
¿Por qué no haces esto?
>> ESTUDIANTE: Si nuestro valor es en el medio es igual a
lo ponemos el -
Quiero decir igual igual a -
>> JASON HIRSCHHORN: It -
Aceptar.
>> ESTUDIANTE: No estoy seguro de lo que el variables que estamos buscando
pues aunque, se debe a que -
>> [VOCES interponiendo]
>> ESTUDIANTE: [inaudible].
>> JASON HIRSCHHORN: Exactamente.
Por la declaración de la función, estamos buscando a un valor.
Así que estamos en busca de un valor en una matriz de valores.
Así que estás en lo cierto.
Que va a hacer, si el soporte de valor paren abierta centro cerrado iguales soporte
igual valor, y en su interior ¿Qué necesitamos hacer?
Si nuestro valor está ahí, lo que Qué tenemos que hacer?
>> [VOCES interponiendo]
>> ESTUDIANTE: Regreso cero.
>> JASON HIRSCHHORN: Devuelve true.
>> ESTUDIANTE: Devuelve true.
>> JASON HIRSCHHORN: Michael, ¿qué hace esta línea?
>> ESTUDIANTE: [inaudible] el programa se ha ejecutado su curso, y que ha terminado, y
tienes lo que hay que hacer?
>> JASON HIRSCHHORN: El programa o qué?
En este caso?
>> ESTUDIANTE: la función.
>> JASON HIRSCHHORN: la función.
Y así, para volver a lo que se llama y darle el valor, es cierto.
Exactamente derecha.
Principal.
¿Cuál es el tipo de retorno de principal, Michael?
>> ESTUDIANTE: int, entero?
>> JASON HIRSCHHORN: int, exactamente.
Un entero.
Eso fue sólo una pregunta para asegurarse ustedes han estado en la cima de la misma.
¿Qué se suele volver, si todas las cosas están funcionando bien?
>> ESTUDIANTE: Zero.
>> JASON HIRSCHHORN: Zero.
Exactamente derecha.
>> ESTUDIANTE: Si esto sólo devuelve true, no hay información que ofrecen
sobre lo que el -
Oh, esto es sólo decir que esa valor que está dentro de la matriz.
>> JASON HIRSCHHORN: Exactamente.
Este programa no está dando la información de dónde exactamente es el valor.
Sólo está diciendo, sí, hemos encontrado ella, o no, nosotros no lo encontramos.
Así que si se encuentra el número, devuelve true.
Bueno, en realidad que acabamos de hacer que realmente rapidez con que una sola línea de código.
Así que voy a pasar esa línea de pseudocódigo.
>> ESTUDIANTE: ¿No necesitamos para cambiar la matriz?
Debe ser valores, no de valor, ¿no?
>> JASON HIRSCHHORN: Lo siento.
Gracias.
>> ESTUDIANTE: Sí.
>> JASON HIRSCHHORN: Esta línea deben ser valores.
Exactamente derecha.
Aceptar.
Así hemos visto la lista media.
Si el número se encuentra return true.
Continuando con nuestro pseudocódigo, si media es mayor, la búsqueda se fue.
Así que tuve aquí, si el número de superior, la búsqueda se fue.
Constantino, le puede dar me esta línea de código?
>> ESTUDIANTE: Si el valor de la media -
>> JASON HIRSCHHORN: Así que si el valor -
si paren abierta valora soporte corchete de cierre media -
>> ESTUDIANTE: ¿Es más pequeño que el valor?
>> JASON HIRSCHHORN: ¿Es menor que.
>> ESTUDIANTE: Inferior al valor.
>> JASON HIRSCHHORN: Valor.
Bueno, en realidad, desea comprobar si el número -
Lo siento.
Esto es un poco confuso.
Pero lo demás, si el número de la medio de la lista es mayor.
>> ESTUDIANTE: Oh, está bien.
>> JASON HIRSCHHORN: voy a cambiar eso.
Porque si en medio es más alto, desee buscar izquierdo, OK?
Y ¿qué hacemos en el interior esto si condición?
>> ESTUDIANTE: ¿Puedo hacer un pequeño cambio en la condición, el cambio a otra persona si?
>> JASON HIRSCHHORN: Else if?
Aceptar.
Así que este código se ejecutará sobre el mismo.
Pero lo bueno de usar if, else if, else if o if, else if, else
significa que sólo uno de los que va a comprobar, no los tres de ellos,
potencialmente.
Y eso lo hace un poco mejor en el equipo que está
funcionamiento de su programa.
>> Así [? Constantino,?]
estamos dentro de esta línea, de lo contrario, si los valores, corchete de cierre medio soporte
es mayor que el valor.
¿Qué necesitamos hacer?
Tenemos que buscar la izquierda.
¿Cómo hacemos eso?
Voy a darle un nuevo comienzo.
>> Tenemos estas dos cosas llamadas comenzando y terminando.
Entonces, ¿qué tiene que suceder al principio?
Si desea buscar en el lado izquierdo de la lista, conseguimos nuestro inicio de corriente.
¿Qué necesitamos para hacerlo?
>> ESTUDIANTE: Fijamos el inicio a mitad más 1.
>> JASON HIRSCHHORN: Entonces, si estamos la búsqueda de la izquierda?
>> ESTUDIANTE: Lo sentimos, menos media -
por lo que el final sería medio menos 1 e inicio -
>> JASON HIRSCHHORN: ¿Y qué que sucede al principio?
>> ESTUDIANTE: Se mantiene igual.
>> JASON HIRSCHHORN: Así que el significado sigue siendo el mismo.
Si estamos buscando la izquierda, estamos utilizando el mismo principio -
exactamente correcto.
Y el final?
Lo sentimos, lo que hace el terminando igual otra vez?
>> ESTUDIANTE: minus Medio 1.
>> JASON HIRSCHHORN: minus Medio 1.
Ahora, ¿por qué menos 1, no sólo del medio?
>> ESTUDIANTE: El intermediario se queda fuera de la imaginarse ya, porque teníamos
comprueba que está fuera?
>> JASON HIRSCHHORN: Eso es exactamente correcto.
El medio está fuera de la imagen.
Ya hemos comprobado la media.
Así que no queremos "el medio", cita Lo dijeron ellos, para seguir siendo en el
matriz que estamos buscando.
Así que esto es fantástico.
>> Porque si media abrazadera valores es mayor de valor final iguales
menos la mitad 1.
Jeff, ¿qué pasa con esta última línea?
>> ESTUDIANTE: Else.
Valores medio es menor que el valor?
>> JASON HIRSCHHORN: Vamos a que me estás dando más.
Así que si no me das -
>> ESTUDIANTE: Entonces comenzando sería más medio 1.
>> JASON Hirschhorn: iguales Empezando más medio 1, de nuevo, para el mismo
razón por la que Constantino nos dio antes.
Y al final, que no ha dado me una línea de código todavía?
Return false, Aleha, lo qué escribimos aquí?
>> ESTUDIANTE: Regreso falsa.
>> JASON HIRSCHHORN: Regresa falso.
Y tenemos que hacerlo, porque si no lo encuentra, tenemos que decir que
no lo encontré.
Y dijimos que vamos a volver a bool, por lo que definitivamente tenemos que volver
una en alguna parte bool.
>> Así que vamos a ejecutar este código.
De hecho voy a -
así que estamos en el terminal.
Limpiaremos nuestra ventana.
Vamos a hacer todo.
Encontramos que hay un error.
Hay un error en la línea 15, que se espera punto y coma al final de la
declaración.
Entonces, ¿qué se me olvida?
>> ESTUDIANTE: Punto y coma.
>> JASON HIRSCHHORN: Punto y coma hasta aquí.
Creo que fue el código de Tom.
Así que Tom, [inaudible].
Es broma.
Hagámoslo Marca Todas las de nuevo.
>> ESTUDIANTE: ¿Qué directorio de Dropbox debemos estar en esto?
>> JASON HIRSCHHORN: Así que usted puede simplemente ver para este bit.
Pero, de nuevo, si se quería mover esta codificar en su directorio pset3 intentar
a cabo, eso es lo que hice.
Si te fijas aquí - lo siento, buena pregunta.
>> [? LS,?]
Tengo aquí el código find.c a partir del código distro de esta semana.
Tengo helpers.h.
Tengo un archivo Make que en realidad editado un poco para incluir estos nuevos
archivos que estamos escribiendo.
Todo ese código estarán disponibles, no el código de distribución, pero el nuevo
Hacer de archivos, el nuevo archivo se helpers.h estará disponible en línea para su descarga.
Una vez más, por lo que esos son los códigos extra que tienen.
>> Así que hacen de todo, por esta línea, hace que encontrar, binario, la selección de la burbuja - marcas
los tres de ellos y compila en este código hallazgo ejecutable.
Así que en general, no queremos a directamente a check50.
Queremos hacer algunas pruebas por nuestra cuenta.
Pero sólo para que podamos agilizar esto un poco, check50 2013 pset3.find pasará
en helpers.c-- mi mal.
>> Yo no tengo eso en este momento.
Así que estamos realmente va a ejecutar el código de verdad.
Usage.find /, ya sabes lo que eso significa?
>> ESTUDIANTE: Se necesita un segundo línea de comandos en ella.
>> JASON HIRSCHHORN: Necesito una segunda línea de comandos.
Y por la especificación, necesito para entrar en lo que estamos buscando.
Así que vamos a ver el 42.
Lo mantendremos en ordenada, porque no han escrito una función de clasificación con todo -
42, 43, 44.
>> Y Control D No se encontró la la aguja en el pajar.
Eso es malo.
Es, sin duda existe.
Vamos a intentar algo más.
Tal vez sea porque me pongo que al principio.
>> Vamos a hacer 41, 42, 43.
Eso es.
Se encontró.
Vamos a ponerlo al final ahora, sólo para que podamos ser a fondo -
40, 41, 42.
¿No has encontrado la aguja.
Así que he mencionado esto antes.
Por desgracia, yo sabía que esto que iba a suceder.
>> Sin embargo, para fines pedagógicos, es bueno para explorarlo.
No trabaja.
Por alguna razón, no lo puede encontrar.
Sabemos lo que hay allí, pero no está resultando.
Así que una cosa que podemos hacer es ir a través GDB para encontrarlo, pero no hace a nadie,
sin pasar por el BGF, tienen una sentido de donde metimos la pata?
[? Madu? ?]
>> ESTUDIANTE: Yo creo que puede ser cuando se termina es igual al principio, y es
sólo una lista de un solo elemento.
Entonces, sólo hace caso omiso de que en lugar de hecho revisando.
>> JASON HIRSCHHORN: Eso es exactamente correcto.
Al final es igual principio, ¿verdad todavía tienen un elemento en nuestra lista?
>> ESTUDIANTE: Sí.
>> JASON HIRSCHHORN: Sí, de hecho, tener uno y sólo un elemento.
Y que lo más probable ocurrir cuando, por el código que probamos, nos encontramos en el
delante de un pajar o en el final de la pajar.
Ahí es donde comienzo y final va a la igualdad de
uno, con búsqueda binaria.
Así que en estos dos casos no funcionó, porque termina fue igual al principio.
>> Pero si termina es igual al principio, no ejecutar este bucle while?
No lo hace.
Y podríamos haber comprobado que de nuevo a través de BGF.
Entonces, ¿cómo podemos solucionar este código, porque cuando, al poner fin es igual a
empezando, también queremos esta while se ejecute.
>> Entonces, ¿qué solución podemos hacer a la línea 18?
>> ESTUDIANTE: [inaudible] es mayor que o igual a.
>> JASON HIRSCHHORN: Exactamente.
Mientras final es mayor que o igual al principio.
Así que ahora, nos aseguramos de conseguir que caso esquina al final.
Y vamos a ver.
Vamos a ejecutar esto una vez más.
>> Vamos a hacer todo.
Una vez más, usted tiene que apenas siga por aquí.
Encuentra 41 esta vez.
Si prefieres algo más consistente.
>> Encuentra 42.
Vamos a ponerlo en el comienzo -
42, 43, 44.
Lo encontramos.
Así que fue realmente el cambio teníamos que hacer.
>> Eso fue un montón de que la codificación acaba de hacer, la búsqueda binaria.
¿Alguien tiene alguna pregunta antes de Sigo adelante en las líneas que escribimos en
búsqueda binaria o cómo nos imaginamos lo que hicimos averiguar?
Antes de seguir adelante, también quiero señalar que por lo general, estudiamos
nuestra pseudo-código de uno a uno en nuestro código.
>> Tuvimos que cosa difícil averiguar con el
comenzando y terminando.
Pero había que no imaginé que fuera, usted habría escrito más o menos la
Código idénticos, salvo por esas dos líneas superiores.
Y entonces se habría dado cuenta cuando que lo hizo en los controles y los casos que
necesita algo más.
Así que incluso si se hubiera seguido nuestro línea de pseudo-código de línea, lo hubieras hecho
conseguido, salvo en dos líneas de código que necesita para escribir.
>> Y yo estaría dispuesto a apostar que ustedes todo habría averiguado
bastante rápido, que necesitaba para poner algún tipo de marcador en allí para averiguar
dónde estabas.
Que de nuevo, es el poder de hacer pseudo-código antes de tiempo.
Así que podemos hacer de la lógica, y luego podemos preocuparse por la sintaxis.
>> Si lo hubiéramos confundido acerca de la lógica al intentar escribir el código en C,
nos habría conseguido todo en mal estado.
Y entonces estaríamos haciendo preguntas sobre la lógica y la sintaxis y mallado
todos ellos juntos.
Y nosotros habríamos entrado perdida en lo que puede convertirse rápidamente en un
problema muy difícil.
Así que vamos a pasar ahora a la selección de clasificación.
>> Tenemos 20 minutos para el final.
Así que tengo la sensación de que no vamos a ser capaces de conseguir a través de todos ordenación por selección
y la ordenación de burbuja.
Pero vamos a lo menos intento para terminar la selección de clasificación.
Así implementar ordenación por selección utilizando el siguiente declaración de la función.
>> De nuevo, esto se toma de la problema establece especificaciones.
Valores int se corchetes, es una matriz de enteros.
Y int.n es el tamaño de la matriz.
Selección especie va para ordenar esta matriz.
>> Así que por nuestro modelo mental de la selección Ordena, tiramos del -
en primer lugar, vamos a través de la lista de la primera tiempo, encontrar el número más pequeño,
ponerlo al principio, encontrar la segunda número más pequeño, lo puso en el
segunda posición si queremos ordenar en orden ascendente.
No estoy obligando a escribir pseudo-código en estos momentos.
>> Pero antes de hacer el código como una clase en cinco minutos, vamos a escribir
pseudo-código, así que tenemos un poco de sentido de donde vamos.
Así que intentará escribir pseudo-código por su cuenta.
Y luego tratar de convertir esa pseudo-código en el código.
Haremos todo lo que como grupo en cinco minutos.
>> Y, por supuesto, que me haga saber si tiene alguna pregunta.
>> ESTUDIANTE: ¿Es todo?
>> JASON HIRSCHHORN: Ver hasta dónde puede llegar en dos minutos más.
Entiendo que no lo harás ser capaz de terminar.
Pero vamos a ir sobre esto como un grupo.
>> Todos están de codificación por lo que [inaudible], así que estoy lo siento para hacer una pausa lo que estás haciendo.
Pero vamos a ir a través de este grupo.
Y de nuevo, la búsqueda binaria, todos ustedes dan me uno si no más líneas de código.
Gracias por eso.
Vamos a hacer lo mismo aquí, código juntos como un grupo.
>> Así ordenación por selección - vamos a escribir algunos pseudo-código rápido.
Según el modelo mental, alguien puede darme la primera línea de pseudo-código, por favor?
¿Qué quiero hacer?
>> ESTUDIANTE: Si bien la lista está fuera de orden.
>> JASON HIRSCHHORN: OK, mientras que la lista está fuera de servicio.
Y ¿qué quiere decir "fuera de servicio?"
>> ESTUDIANTE: Mientras [inaudible]
no se ha solucionado.
>> JASON HIRSCHHORN: Si bien la lista está fuera de servicio, ¿qué hacemos?
Dame la segunda línea, por favor, Marcus.
>> ESTUDIANTE: Entonces encontrar la siguiente número más pequeño.
Esta será una sangría.
>> JASON HIRSCHHORN: Así que encontrar la siguiente número más pequeño.
Y entonces alguien más?
Una vez que encontramos la inmediata inferior número, ¿qué hacemos?
Voy a decir encontrar el número más pequeño.
Eso es lo que queremos hacer.
>> Así que encontrar el número más pequeño.
Entonces, ¿qué hacemos?
>> ESTUDIANTE: [inaudible] a principio.
>> JASON HIRSCHHORN: ¿Lo sientes?
>> ESTUDIANTE: Colóquelo en el principio de la lista.
>> JASON HIRSCHHORN: Así que lo coloca en el principio de la lista.
Y lo hacemos a lo que era en el principio
de la lista, ¿no?
Estamos sobrescribir algo.
Entonces, ¿dónde ponemos eso?
Sí, Anna?
>> ESTUDIANTE: ¿Dónde los más pequeños número era?
>> JASON Hirshhorn: Así que ponga el inicio de la lista donde la
número más pequeño era.
Así, mientras que la lista está fuera de orden, encontrar el número más pequeño, colóquelo en
el principio de la lista, poner el principio de la lista, donde el
número más pequeño era.
Marcus, puede reformular esta línea mientras que la lista está fuera de servicio?
>> ESTUDIANTE: Si bien las cifras no han sido ordenados?
>> JASON Hirshhorn: OK, por lo que con el fin de saben que los números no han sido
ordenados, ¿qué tenemos que hacer?
¿Cuánto tenemos que ir a través de esta lista?
>> ESTUDIANTE: Así que supongo que un bucle for, o mientras que, mientras que los números revisados ​​es menos
que la longitud de la lista?
>> JASON Hirshhorn: OK, eso es bueno.
Creo que misphrased mi pregunta mal.
Yo sólo estaba tratando de llegar a vamos a tener que ir
a través de toda la lista.
Así, mientras que la lista está fuera de servicio, para mí, es difícil asignar sucesivamente.
Pero, básicamente, eso es lo Pienso en esto.
Ir a través de toda la lista, busque el número más pequeño, colóquelo en el
comenzando - en realidad, tienes razón.
Vamos a poner a los dos.
>> Así, mientras que la lista está fuera de orden, que pasar por toda la lista
una vez, encontrar el menor número, el lugar en el principio de la lista, poner
el principio de la lista, donde el número más pequeño era, y entonces, si la
lista es aún fuera de orden, no tenemos tiene que ir a través de este
proceso de nuevo, ¿verdad?
Es por eso que la selección de género, tiempo de ejecución de Big-O de ordenación por selección, cualquier persona?
>> ESTUDIANTE: n al cuadrado.
>> JASON Hirshhorn: n al cuadrado.
Porque al igual que Marcus y yo acabo de dar cuenta aquí, vamos a tener que
pasar por la lista de la lista número de veces.
Así que pasando por algo de longitud n n número de veces
es, de hecho, n al cuadrado.
>> Así que este es nuestro pseudocódigo.
Esto se ve muy bien.
¿Alguien tiene alguna pregunta sobre el pseudocódigo?
Porque en realidad ordenación por selección debe Probablemente venga uno a uno, el código de
pseudocódigo.
Así que cualquier pregunta acerca de la lógica del pseudocódigo?
Por favor, pregunte ahora.
>> Selección clase - mientras que la lista está fuera de orden, vamos a ir a través de él
y encontrar el más pequeño cada vez y lo puso en la parte delantera.
Así, mientras que la lista está fuera de servicio, puede alguien me dé esa línea de código que
No me ha dado una línea de código, sin embargo, por favor?
Suena como un qué?
>> ESTUDIANTE: Es un bucle for.
>> JASON Hirshhorn: Suena Quieres un bucle for.
Bien, ¿me puede dar el bucle?
For -
>> ESTUDIANTE: i es igual a 0.
>> JASON Hirshhorn: io -
lo que nos estamos perdiendo?
¿Qué pasa aquí?
>> ESTUDIANTE: Int.
>> JASON Hirshhorn: Exactamente.
(Int i = 0; -
>> ESTUDIANTE: i <n, i + +).
>> JASON Hirshhorn: Clavado él, Jeff.
Vamos por la lista, ¿no?
Hemos visto que el código anterior.
Perfect.
Así que vamos a poner nuestras llaves aquí.
Voy a poner un poco de llaves aquí.
>> Así, mientras que es 0, tenemos que ir a través de toda la lista.
Así que cada vez que vaya a través de la lista, ¿qué es lo que queremos perder de vista?
>> ESTUDIANTE: Si se realiza algún swaps.
>> JASON Hirshhorn: Buscar el número más pequeño.
Así que probablemente debería mantener un registro de el número más pequeño cada vez.
Así line puedo hacer para realizar un seguimiento del número más pequeño?
Aleha, ¿cómo puedo evitar que pista de algo?
>> ESTUDIANTE: Iniciar una nueva variable.
>> JASON Hirshhorn: Iniciar una nueva variable.
Así que vamos a crear una variable.
¿Qué tipo?
>> ESTUDIANTE: Int.
>> JASON Hirshhorn: Int.
Digamos que es el más pequeño.
Y lo que lo hace igual cuando sólo estamos empezando?
No hemos ido a través de la lista todavía.
Estamos en la primera parte de la listar nuestra primera vez.
Lo que lo hace igual, la menor número?
>> ESTUDIANTE: Valores i.
>> JASON Hirshhorn: Valores i.
Eso suena exactamente a la derecha, ¿no?
El número más pequeño al principio es donde estamos.
Así que ahora tenemos nuestro pequeño y necesitamos ir a través de toda la lista y
comparar este pequeño para todo lo demás.
Entonces, ¿vamos a través de la lista de nuevo?
Michael?
>> ESTUDIANTE: Es necesario hacer otro bucle.
>> JASON Hirshhorn: Otro bucle for.
Vamos a hacerlo.
Dame un poco de código.
>> ESTUDIANTE: Para loop -
para los más pequeños -
sólo int j, se podía decir?
= 0, de tal manera que -
>> JASON Hirshhorn: Bueno, si queremos que pasar por toda la lista -
>> ESTUDIANTE: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Vamos a ir a través de el bucle de nuevo.
Y, ¿cómo encontrar el menor número?
Tom?
Tenemos el número más pequeño de corriente, así que, ¿cómo encontrar el nuevo pequeño?
>> ESTUDIANTE: Podemos comprobar si la menor número que tenemos es mayor que
valores de soporte de j.
>> JASON Hirshhorn: Así que si el menor es mayor que los valores de soporte de j.
Así que si nuestro actual más pequeño es mayor que -
Voy a mover estas dos líneas de código por ahí por un segundo.
Porque antes de hacer cualquier intercambio, nos que pasar por toda la lista.
Así que este pseudocódigo debe en realidad ser que fuera interior para el bucle.
Así que ir a través de toda la lista.
Si el menor es mayor que valores de j ¿entonces qué?
>> ESTUDIANTE: Entonces más pequeño es igual a los valores j.
>> JASON Hirshhorn: Fantastic.
Una pregunta rápida -
la primera vez que vamos a través de este lazo, i va a ser igual a 0, j va
a ser igual a 0 una vez que tengamos aquí.
Así que vamos a comparar un número a sí mismo.
¿Es eficiente?
No, en realidad no es eficiente.
Entonces, ¿nuestra j necesita ir de 0 a n cada vez?
¿Siempre hay que comprobar a través de toda la lista?
[Inaudible]?
>> ESTUDIANTE: Comience con i en vez.
>> JASON Hirshhorn: j lata comenzar con lo que?
>> ESTUDIANTE: i.
>> JASON Hirshhorn: j puede comenzar con i.
Así que ahora nos comparamos a partir con el que nos encontramos.
Pero incluso entonces, es que a medida más eficiente posible?
>> ESTUDIANTE: i + 1.
>> JASON Hirshhorn: i + 1 parece ser el más eficiente, ya que
Ya tengo i.
Estamos indicando que a medida que el más pequeño en la línea 15.
Vamos a comenzar con el siguiente automáticamente.
Así que vamos a través del bucle.
Vamos a ir a través de cada momento.
Vamos a ir a través de un número de veces.
Ahora que hemos conseguido a través de Este interior de bucle.
Tenemos el valor más pequeño salva.
Tenemos que ponerla al principio de la lista.
Entonces, ¿cómo lo pongo en el principio de la lista?
¿Cuál es la variable que hace referencia al principio de la lista?
Estamos en esto fuera de bucle, así que lo que se refiere a la
principio de la lista?
>> ESTUDIANTE: Valores i.
>> JASON Hirshhorn: Exactamente.
Valores i es el comienzo de la -
o lo siento, no al principio.
Eso era confuso.
Es el lugar donde nos encontramos en el inicio de la parte no seleccionada de la lista.
Así los valores i.
Y lo que hace que la igualdad?
>> ESTUDIANTE: Muy pequeña.
>> JASON Hirshhorn: Valores i es igual a qué?
>> ESTUDIANTE: Muy pequeña.
>> JASON Hirshhorn: Muy pequeña.
Exactamente derecha.
Así que estamos colocándolo al principio de la lista, y ahora tenemos que poner
el principio de la lista donde el número más pequeño era.
Entonces, ¿cómo puedo escribir cuando la número más pequeño era?
Valores de qué?
>> ESTUDIANTE: 0.
>> JASON Hirshhorn: La pequeña número está en 0?
>> ESTUDIANTE: Sí.
>> JASON Hirshhorn: ¿Qué pasa si el más pequeño número era al final de
esta lista sin ordenar?
>> ESTUDIANTE: Lo siento, ¿cuál era la pregunta?
>> JASON Hirshhorn: ¿Dónde está el número más pequeño?
Tomamos el más pequeño y lo ponemos en el principio, con esta línea aquí.
>> ESTUDIANTE: Debe tener ha almacenado en algún -
>> ESTUDIANTE: Valores j.
>> JASON Hirshhorn: Bueno, es Los valores no necesariamente j.
Incluso no existe en este momento.
>> ESTUDIANTE: Usted tiene que declarar una variable antes y
asignarlo a -
cuando usted encuentra el número más pequeño, asignar el índice de ese número de
alguna variable o algo así.
>> JASON Hirshhorn: Entonces, ¿puede vuelves a decir eso?
>> ESTUDIANTE: Entonces, ¿dónde usted declaró int más pequeño, también debe declarar int
menor índice = i, o algo así.
>> JASON Hirshhorn: Entonces, ¿dónde me int más pequeño, que no sólo debería realizar un seguimiento
del valor pero la ubicación.
int smallest_location = en este caso, sólo tendremos que hacer yo.
Necesitamos saber dónde está.
Llegamos al final del código, y se dio cuenta de que no tenía idea de dónde estaba.
Y así, una vez más, somos la cartografía esto en uno a uno.
Ustedes codificación esto en su propia voluntad probablemente llegar a un mismo problema.
¿Cómo diablos lo encuentro?
Y entonces te das cuenta, espera, que hacer un seguimiento de ello.
>> Así que si el menor es mayor que los valores j.
Hemos establecido más pequeño es igual a los valores de j.
¿Qué más tenemos que cambiar?
Constantin, ¿qué otra cosa hacer tenemos que cambiar?
>> ESTUDIANTE: La ubicación.
>> JASON Hirshhorn: Exactamente.
Así que me dan esa línea en el código.
>> ESTUDIANTE: smallest_location = J.
>> JASON Hirshhorn: Exactamente.
Y luego hacia abajo al final, si queremos poner el principio de la lista donde
el número más pequeño era, ¿cómo nos referimos a que el
número más pequeño era?
Marcus?
>> ESTUDIANTE: El número más pequeño era situado en la ubicación más pequeño.
>> JASON Hirshhorn: Así que en valores smallest_location.
Y ¿qué es lo que ponemos allí?
El comienzo de la lista, ¿qué es eso?
>> ESTUDIANTE: Bueno, no se sabe muy bien más porque sobrescrito.
Así que es una ubicación intercambiadas de esas dos líneas?
Si cambia de esas dos líneas alrededor.
>> JASON Hirshhorn: OK, así que no hacemos nunca más, porque hemos reiniciamos la línea
antes que los valores i al más pequeño.
Así que hemos perdido ese valor inicial.
Así que usted ha dicho canje de estas dos líneas.
Así que ahora poner el principio de la lista donde fue el número más pequeño.
Así smallest_location iguala los valores i.
Que se está moviendo el principio de este parte sin ordenar de la lista a la
ubicación más pequeño.
Y luego en valores i nos estamos moviendo que el número más pequeño.
>> ¿Tiene sentido eso que tuvo que hacer esa permuta?
Nos habría sobrescrito ese valor - otra cosa que usted probablemente tendría
descubierto y hallado en el PIB.
Así que nos hemos encargado de todo el pseudocódigo.
¿Hay algo más que que tenga que escribir aquí?
¿Alguien puede pensar en otra cosa?
>> ESTUDIANTE: ¿Cómo sabes cuando haya terminado?
>> JASON Hirshhorn: ¿Cómo saber cuándo hemos terminado?
Muy buena pregunta.
Entonces, ¿cómo sabemos cuándo hemos terminado.
>> ESTUDIANTE: Crear una variable para llevar la cuenta de si hay un canje realizado o no
y pasar por un pase.
>> JASON Hirshhorn: OK.
Eso funcionaría en especie de burbuja.
Sin embargo, para la selección de género, si no lo hacemos hacer un intercambio, que sólo podría ser
debido a que el valor más pequeño es en ella su lugar correcto.
Puede ser que tengamos una lista 1, 2, 4, 3.
La segunda vez que nos no hará ningún swaps.
Estaremos en el número 2, pero vamos a todavía tienen que seguir adelante.
Entonces qué tenemos que perder de vista cuando nos hacen, o sólo queremos ir
hasta que esto se termine?
>> ESTUDIANTE: Podemos ir hasta que esté terminado.
>> JASON Hirshhorn: Podemos simplemente ir hasta que esto termine.
En la ordenación de burbuja, estás en lo cierto, Jeff y Aleha, con su solución -
que es grande para llevar un registro de la cantidad de swaps que ha realizado, ya que en la burbuja
ordenar, si lo hace, de hecho, no hacer swaps, haya terminado y usted puede tal vez reducir su
problema un poco.
Sin embargo, para la selección de tipo, que haya realmente tengo que ir hasta el final de la
la lista de cada vez.
>> Así que esto es eso.
Tenemos dos minutos para el final.
Vamos a hacer todo.
Permítanme abierta encontramos aquí y hago seguro de que estoy hecho llamar -
No voy a llamar especie de burbuja.
Vamos a cambiar esto a ordenación por selección.
hacer toda. / find.
Vamos a ver 42.
Esta vez vamos a pasar una lista de clasificar, ya que debe resolver
primero, por el código de descubrimiento - debe ordenar primero utilizando nuestra función de clasificación y luego
buscar algo.
Crucemos los dedos cada uno.
>> ¡Oh Dios mío.
Vaya, mi corazón latía.
Así que eso es correcto.
De hecho, si nos encontramos con esto más ampliamente, el código, por lo que yo puedo
contar, es perfectamente correcto.
Hay algunas sugerencias Me gustaría tener para usted.
Por ejemplo, 15 y 16 parecen un poco redundante.
Parece que usted no lo hace necesariamente deberá guardar tanto los.
Si usted tiene la ubicación más pequeña, que puede encontrar fácilmente el valor más pequeño de
solo teclear valores de i.
>> Así que si yo fuera a ser ley de su código, que voy a ser, de hecho, lo haría
probablemente despegar un punto si incluye ambos, porque
no necesitan tanto de éstos.
Si usted tiene la ubicación, se puede conseguir muy fácilmente el valor.
Y es que parece un poco raro para almacenar tanto de ellos.
Tal vez ni siquiera tomar un punto, pero Ciertamente comentan que esto es lo mejor
no una elección estilística usted necesita hacer.
Por supuesto, el código todavía funciona perfectamente bien.
>> Así que por desgracia no lo hicimos llegar a la ordenación de burbuja.
Lo siento por eso.
Hicimos acabado ordenación por selección.
¿Alguien tiene alguna pregunta final sobre la selección de una especie?
>> Bien, antes de que nos dirigimos, quiero que para abrir su navegador Chrome.
Lo sentimos, pero eso fue sólo un enchufe descarado para un tipo de navegador de Internet.
Usted puede abrir cualquier tipo de navegador, pero probablemente será Chrome.
Y voy a este sitio web siguiente -
sayat.me/cs50.
Si usted no está escribiendo en su computadora en este momento, usted está claramente
no hacerlo, Tom.
>> Y por favor, ya sea a la derecha ahora o en la próxima hora -
dame un poco de retroalimentación.
Esta es sólo la segunda sección.
Tenemos muchos más tenemos juntos, así que tienen un montón de espacio para mejorar.
Yo espero que también hice algunas cosas bien.
Así que usted puede hacer que me sienta del todo malo, pero si usted también quiere darme un emoticono
cara, le agradecería que también.
Rellene que pulg
>> Y con un solo minuto en el reloj, eso fue la semana tres.
Voy a estar fuera por un poco si tiene alguna pregunta.
Voy a ver ustedes en dar una conferencia mañana.