>> [REPRODUCCIÓN DE MÚSICA]
>> ANDI Peng: Bienvenidos a la semana 3 de la sección.
Gracias, chicos, para todos viene a esta hora de inicio el día de hoy.
Tenemos un bonito y pequeño grupo íntimo hoy.
Así que espero que vamos a llegar a acabado, tal vez, temprano,
un poco temprano hoy.
Así que rápidamente, sólo algunas anuncios para el orden del día de hoy.
Antes de empezar, estamos va a ir sobre
algunos problemas logísticos breves, pset preguntas, interrogar, cosas así.
Y luego vamos a bucear en derecho.
Vamos a utilizar un depurador GDB de llamada comenzar desacreditando nuestro código, que David
explicó en conferencia el otro día.
Vamos a repasar los cuatro tipos de clases.
Vamos a ir sobre ellos con bastante rapidez ya que son muy intensivos.
Pero saber que todas las diapositivas y código fuente son siempre en línea.
Así que no dude, en su lectura, a volver atrás y echar un vistazo a eso.
>> Iremos a través notación asintótica, que
es sólo una forma elegante de decir "los tiempos de ejecución"
donde tenemos la gran O, lo que David explicó en conferencia.
Y también tenemos Omega, que es el tiempo de ejecución de límite inferior.
Y hablaremos un poco más en profundidad con respecto a cómo los trabajos.
Y por último, vamos a repasar búsqueda binaria, porque muchos de ustedes que ya tienen
miró a sus conjuntos de procesadores probablemente saber que esa es una pregunta que está en su conjunto de procesadores.
Así que todos estaremos felices que cubrimos esto hoy.
>> Y por último, por su sección de comentarios, en realidad
la izquierda a unos 15 minutos a Al final sólo repasar
logística de pset3, cualquier pregunta, tal vez un poco de orientación, si se quiere,
antes de empezar la programación.
Así que vamos a tratar de conseguir a través de el material con bastante rapidez.
Y luego podemos pasar algún tiempo teniendo más preguntas para el conjunto de procesadores.
OK.
>> Rápidamente, por lo que sólo unos pocos anuncios antes de empezar hoy.
En primer lugar, recepción para hacer a través de dos de sus conjuntos de procesadores.
Eché un vistazo al tu-- Sí, vamos a conseguir un aplauso para ese.
En realidad, yo estaba muy, realmente impresionados.
Yo califiqué el primer conjunto de procesadores para ustedes semana y últimos chicos hicieron increíble.
>> Estilo estaba en punto además de algunos comentarios.
Asegúrese de que está siempre comentando su código.
Pero sus conjuntos de procesadores estaban a punto.
Y sigue así.
Y es bueno para el grado de veo que ustedes están poniendo
en tanto esfuerzo en su estilo y su diseño en su código
que nos gustaría para que usted vea.
Así que estoy pasando por mi gratitud para el resto de las AATT.
>> Sin embargo, hay una algunas preguntas Debrief
Sólo quiero ir más que haría que tanto mi vida
y un montón de la otra TA 'vive un poco más fácil.
En primer lugar, me he dado cuenta de esto pasado week-- ¿cuántos de ustedes
han estado funcionando en check50 su código antes de enviar?
OK.
Así que todo el mundo debería estar haciendo check50, porque-- un secreto-- realidad
ejecutar check50 como parte de nuestra corrección guiones para probar el código.
Así que si su código está fallando check50, con toda probabilidad,
que probablemente va a fracasar el proceso de registro también.
A veces los chicos tener las respuestas correctas.
Al igual que, en codiciosos, algunos de usted tiene los números correctos,
que acaba de imprimir algunas cosas extra.
Y ese material extra en realidad no pasa la verificación,
porque el equipo no realmente sabe lo que está buscando.
Y así se acaba de ejecutar a través de, ver que su salida no
igualaremos lo que esperamos la respuesta ser, y marcar que es un error.
>> Y sé que sucedió en algunos de sus casos de esta semana.
Así que volví y manual clasificado de nuevo código de todos.
En el futuro, sin embargo, por favor, por favor, asegúrese
que se está ejecutando comprobar 50 en tu código.
Debido a que es una especie de dolor para la TA a tener que volver atrás y manualmente reclasificar
cada conjunto de procesadores única para cada único, ejemplo poco perdido.
Así que no me quito ningún punto.
Creo que me quité quizá uno o dos para el diseño.
En el futuro, aunque, si usted está fallando check50,
se tomarán puntos apagado para la corrección.
>> Además, son conjuntos de procesadores debido viernes a mediodía.
Creo que hay un niño de siete minutos período de gracia finales que le demos.
Por tiempo de Harvard, que se les permita siete minutos tarde a todo.
Así que aquí en Yale, vamos a adherirse a eso también.
Pero más o menos, a las 12:07, si su conjunto de procesadores no se encuentra en,
que va a ser marcado como tarde.
Y así, mientras se marca lo más tarde, el TA-- estoy
todavía va a ser la clasificación de sus conjuntos de procesadores.
Así que usted todavía ve aparecer un grado.
Sin embargo, saber que en Al final del semestre,
todos los conjuntos de procesadores finales serán sólo puesto a cero automáticamente por el ordenador.
>> Hacemos esto por dos razones.
Uno, a veces obtenemos excusado, como excusas de Dean,
más adelante que yo no sé nada todavía.
Así que nos gusta asegurarnos de que estamos clasificación todo por si acaso, como, estoy
falta la excusa de un decano.
Y en segundo lugar, tener en mente, usted puede todavía
excluir a un conjunto de procesadores que tiene puntos de alcance completo.
Y así nos gusta grado todos los conjuntos de procesadores solo
para asegurarse de que su ámbito de aplicación allí y usted los está tratando.
Así que incluso si es tarde, se le sigue obtener crédito para los puntos de alcance, creo.
>> Así moraleja de la historia es, hacer Asegúrese de que sus conjuntos de procesadores están en el tiempo.
Y si no están en el tiempo, Sabe que no es grande.
Sí, antes de pasar, ¿alguien tiene cualquier pregunta con respecto retroalimentación pset?
Sí.
>> AUDIENCIA: ¿Has dicho que puede caer uno de los conjuntos de procesadores?
>> ANDI Peng: Sí.
Así que hay nueve conjuntos de procesadores general en el transcurso del semestre.
Y si usted tiene alcance points-- lo alcance es justo,
más o menos, se le intenta la problema, estás poniendo en el tiempo,
se le muestra que usted tiene demostrado que hayas leído la especificación.
Eso es más o menos alcance.
Y si usted está cumpliendo puntos de alcance, que
puede caer más bajo uno fuera de alcance completo.
Así que eso es en su ventaja para completar y probar cada conjunto de procesadores.
>> Incluso upload-- si ninguno de ellos trabajan, subirlos todos.
Y luego vamos a ojalá seamos capaces de le dará algunos de esos puntos atrás.
Guay.
¿Alguna otra pregunta?
Excelente.
>> En segundo lugar, la oficina horas-- unos pocos notas rápidas sobre las horas de oficina.
Así que primero, llegar temprano en la semana.
Nadie está nunca en horario de oficina los lunes.
Christabel vino a las horas de oficina de la noche anterior.
Sí, Christabel.
¿Y qué nos tenemos en la oficina horas de anoche, Christabel?
>> AUDIENCIA: Teníamos helado.
>> ANDI Peng: Así que está bien, tuvimos helado en horario de oficina anoche.
Aunque no puedo prometer que tendremos helado en horario de oficina
cada semana, lo que puedo prometerte es que habrá una significativamente
mejor proporción de estudiantes por TA.
Al igual que fiar, es como tres a uno.
Considerando que, contrastar eso con Jueves, tienes alrededor de 150
muy estresada niños y no helado.
Y no es sólo productiva para cualquier persona.
Así moraleja de la historia es, llegar temprano a las horas de oficina y las cosas buenas
pasará.
>> También, venga preparado para hacer preguntas.
¿Sabes?
Independientemente de lo que los TA, me pensar, he estado diciendo,
hemos estado recibiendo un par de estudiantes que vienen en el jueves en, como, 10:50
no haber leído la especificación siendo así que me ayude, que me ayude.
Desafortunadamente en ese punto, no hay no hay mucho que podamos hacer para ayudarle.
Así que por favor venga a principios de la semana.
Venga temprano para las horas de oficina.
Venga preparado para hacer preguntas.
Asegúrese de que usted, como un estudiante, son donde
tiene que ser para que el TA puede guiarlo a lo largo,
que es lo que las horas de oficina debe ser asignado para.
>> En segundo lugar, por lo que sé profesores gustaría sorprendernos con pruebas.
Tuve un profesor de los como, yo, por cierto,
recordar que de mitad de período usted tiene el próximo lunes.
Sí, yo no sé nada de eso de mitad de período.
Así que voy a ser que TA que recuerda todo lo que prueba
0-- porque, ya sabes, estamos CS.
Ahora que hemos matrices done, se obtiene por qué es prueba 0, no interrogar a 1, ¿eh?
OK.
Oh, tengo algunas risas en esa.
OK.
>> Así concurso 0 será el 14 de octubre, si usted está en la sección de lunes a miércoles
y 15 de octubre, si usted está en la sección de martes a jueves.
Esto no se aplica para los aquellos de ustedes en Harvard
que-- Creo que todos podrás tomar sus exámenes en la 14a.
>> Así que sí, la próxima semana, si David, en la conferencia, se va,
sí, así que en eso prueba la próxima semana, a todos
no será sorprendido porque usted vino a la sección
y usted sabe que su concurso 0 es en dos semanas.
Y tendremos opinión sesiones y todo.
Así que no te preocupes por tener miedo por eso.
Cualquier pregunta antes-- alguna pregunta en todas las cuestiones logísticas relativas,
clasificación, las horas de oficina, secciones?
Sí.
>> AUDIENCIA: Así que la prueba es va a ser durante la conferencia?
>> ANDI Peng: Sí.
Así que la prueba, creo, es 60 minutos asignados en ese intervalo de tiempo
que usted acaba de tomar en la sala de conferencias.
Así que usted no tiene que venir en en, como, un azar 19:00.
Está todo bien.
Sí.
Guay.
>> Correcto.
Así que vamos a introducir un concepto para usted
esta semana que David ya tiene clase del tocado en la conferencia de la semana pasada.
Se llama GDB.
¿Y cuántos de ustedes, mientras que en el curso de la escritura de sus conjuntos de procesadores,
han notado un gran botón que dice "Depuración" en la parte superior de su IDE?
OK.
Así que ahora vamos a realmente lleguemos a descubrir el misterio de lo que en realidad botón
hace.
Y te garantizo que, se trata de un , hermosa cosa hermosa.
>> Así que, hasta ahora, creo que ha habido dos cosas
los estudiantes han sido típicamente haciendo al depurar conjuntos de procesadores.
Uno de ellos, o bien añadir en printf () - por lo que cada pocas líneas,
agregan en un printf () - oh, ¿qué es esta variable?
Oh, ¿qué es esta variable ahora-- y que tipo de ver la progresión
de su código ya que se ejecuta.
O el segundo método que hacen los niños es que acaba de escribir todo el asunto
y luego ir así al final.
Esperemos que funciona.
Te garantizo que, GDB es mejor que ambos de estos métodos.
Sí.
Así que este será su nuevo mejor amigo.
Porque es una cosa hermosa visualmente que muestra tanto
lo que su código está haciendo en un punto específico
así como lo que la totalidad de su variables que están llevando,
como cuáles son sus valores, en ese punto específico.
Y de esta manera, usted puede realmente establecer puntos de interrupción en el código.
Usted puede ejecutar a través de línea por línea.
Y BGF sólo tendrá para usted, muestran para que usted,
lo que todas sus variables están, qué están haciendo,
lo que está pasando en el código.
Y de tal manera, que es mucho más fácil de ver
lo que está sucediendo en lugar de-ción printf o escribir sus declaraciones.
>> Así que vamos a hacer un ejemplo de esto más adelante.
Así que esto parece un poco abstracto.
No se preocupe, nosotros haremos ejemplos.
Y así, en esencia, los tres más grandes, funciones más utilizadas que necesitará en el BGF
son la continuación, pasar por encima, y Paso en botones.
Voy a dirigirse hay, en realidad, en este momento.
>> Así se puede ver que todos los chicos o debería acercar un poco?
En la parte posterior, se puede ver eso?
¿Debo hacer un zoom?
¿Solo un poco?
Vale, guay.
Allá vamos.
OK.
>> Así que tengo, aquí, mi aplicación de codiciosos.
Y mientras muchos de ustedes escribió codiciosos en bucle while form-- que
es una manera perfectamente aceptable hacer it-- otra manera de hacerlo es simplemente
dividir en el módulo.
Porque entonces usted puede tener su valor y luego tienen el resto.
Y entonces usted puede simplemente añadir todo junto.
¿La lógica de lo que estoy haciendo aquí tiene sentido para todos,
antes de empezar?
¿Mas o menos?
Guay.
Excelente.
Es una pieza muy sexy del código, diría yo.
Como he dicho, David, en dar una conferencia, después de un tiempo,
todos ustedes comenzará a ver código como algo que es hermoso.
Y a veces, cuando ves hermosa código, es una sensación maravillosa.
>> Así que sin embargo, mientras que este código es muy hermoso, que no funciona correctamente.
Así que vamos a correr check50 en esto.
Compruebe 50 20-- oop.
2?
¿Es que PSet2?
Sí.
Oh, pset1.
OK.
Así corremos check50.
>> Y como ustedes pueden ver aquí, está fallando un par de casos.
Y para algunos de ustedes, en el curso de hacer sus boletines de problemas,
usted es como, ah, ¿por qué no está funcionando.
¿Por qué es trabajando desde hace valores, pero no para otros?
Bueno, GDB se va a ayudar a la figura por qué esas entradas no estaban funcionando.
>> OK.
Así que vamos a ver, uno de los cheques que estaba fallando en check50
era el valor de entrada de 0,41.
Así que la respuesta correcta que que debería estar recibiendo es un 4.
Pero en lugar de lo que estoy imprimiendo es el 3-n, que es incorrecto.
Así que vamos a ejecutar esto manualmente, simplemente asegurarse de que check50 está trabajando.
Hagamos ./greedy.
Vaya, tengo que hacer codicioso.
Allá vamos.
Ahora ./greedy.
>> ¿Cuánto se le debe?
Hagamos 0.41.
Y sí, nos vemos aquí que está la salida 3
cuando la respuesta correcta, De hecho, debería ser 4.
Así que vamos a entrar en el BGF y veamos cómo nos puede ir sobre la fijación de este problema.
>> Así que el primer paso en Siempre depurar su código
es establecer un punto de interrupción, o de un punto en el que
desea que el ordenador o la depurador para iniciar mirando.
Así que si usted realmente no sé cuál es tu problema,
por lo general, lo típico queremos hacer es configurar nuestro punto de interrupción en el principal.
Así que si ustedes pueden ver esto botón rojo allí,
sí, ese era yo el establecimiento de un punto de ruptura para la función principal.
Hago clic en eso.
>> Y entonces me puedo ir a mi botón de depuración.
Golpeé ese botón.
Permítanme amplía la imagen si puedo.
Allá vamos.
Así que tenemos, aquí, un panel de la derecha.
Lo siento, chicos en la parte posterior, que en realidad no puede ver muy bien.
Pero, en esencia, todo este panel de la derecha está haciendo
es no perder de vista tanto del puesto de relieve línea, que es la línea de código
que el equipo está ejecutando actualmente, así como todas sus variables
aquí abajo.
>> Así que tienes centavos, monedas, n, todas declarado a cosas diferentes
en este punto.
No se preocupe, porque en realidad no tienen ellos inicializado a cualquier variable todavía.
Así que en su computadora, su equipo acaba de ver,
oh, 32767 fue la última función utilizada de ese espacio de memoria en mi equipo.
Así que ahí es donde actualmente centavos es.
Pero nadie que una vez que se ejecuta el código, debería convertirse inicializado.
>> Así que vamos a ir a través, línea por line, lo que está pasando aquí.
OK.
Así que aquí están los tres botones que acabo de explicar.
Usted tiene el juego, o la función Ejecutar, botón, usted tiene el paso sobre el botón,
y también tiene el Paso en botón.
Y, esencialmente, los tres ellos sólo van a través de su código
y hacer cosas diferentes.
>> Así que por lo general, cuando usted está de depuración, nosotros no queremos simplemente pulse Play,
porque Play basta con ejecutar su código al final de la misma.
Y entonces no lo hará realidad saber cuál es su problema
es menos que establezca múltiples puntos de interrupción.
Si establece varios puntos de interrupción, se acaba de forma automática
correr de un punto de ruptura, a la siguiente, a la siguiente.
Pero en este caso que hemos sólo que uno, porque
quieren trabajar nuestro camino de arriba hacia abajo a abajo.
Así que vamos a ignorar ese botón en este momento para los propósitos de este programa.
>> Así que el paso sobre la función solo pasos sobre cada línea
y te dice lo que el equipo está haciendo.
El Paso en función va en la función real
eso es en su línea de código.
Así, por ejemplo, como printf (), que es una función, ¿no?
Si quisiera paso físicamente en la función printf (),
Yo realmente entrar en el pedazo de código donde printf () fue escrito y ver
que esta pasando ahí.
>> Pero por lo general, se supone que el código que te damos funciona.
Asumimos el printf () está trabajando.
Suponemos que getInt () está trabajando.
Así que no hay necesidad de entrar en esas funciones.
Pero si hay funciones que escriba usted mismo
que desea comprobar lo que está pasando,
usted quiere dar un paso en esa función.
>> Así que ahora sólo vamos al pasar por encima de este trozo de código.
Así que vamos a ver.
Oh, imprimir, "Oh hai, cómo se debió en gran cambio? "
No nos importa.
Sabemos que está funcionando, así que pasar por encima de ella.
>> Así que n, que es nuestra carroza que que hemos initialized-- o declared--
en la parte superior, ahora estamos igualando que a GetFloat ().
Así que vamos a pasar por encima de eso.
Y vemos en la fondo aquí, el programa
me está incitando a la entrada de un valor.
Así de entrada de dejar que el valor que queremos para probar aquí, que es 0,41.
Excelente.
>> Así que ahora n-- ¿Ustedes Ver aquí, en el bottom-- es
stored-- porque no han redondeado sin embargo, es
almacenada en este gigante como flotante que es 0,4099999996,
que es lo suficientemente cerca de nuestro propósitos, ahora mismo, a 0,41.
Y luego ya veremos más adelante, a medida que continuar pasando por encima del programa,
después aquí, n se ha convertido en redondeada y centavos se ha convertido en 41.
Excelente.
Así que sabemos que el trabajo de nuestra redondeo.
Sabemos que tenemos la número correcto de centavos,
así que sabemos que eso es no es realmente el problema.
>> Así que seguimos paso a paso en este programa.
Vamos aquí.
Y así, después de esta línea de código, debe saber cuántos cuartos que tenemos.
Damos un paso más.
Y usted ver lo que hacemos, de hecho, tenemos un solo trimestre porque hemos restamos 25
de nuestro valor inicial de 41.
Y tenemos 16 izquierda para nuestros centavos.
>> ¿Todo el mundo entiende cómo el programa está intensificando a través
y por qué centavos ahora se ha convertido en 16 y por qué, ahora, las monedas se ha convertido en 1?
Está todo el mundo siguiendo esa lógica?
Guay.
Así que a partir de este punto, el de trabajo del programa, ¿no?
Sabemos que está haciendo exactamente lo que queremos que lo haga.
Y no lo hicimos realidad tienen que imprimir, oh, qué
es céntimos en este punto, lo que es las monedas en este punto.
>> Seguimos pasando por el programa.
Paso terminado.
Guay.
Repasamos monedas de diez centavos.
Excelente.
Vemos que se toma de $ 0.10 para un centavo.
Y ahora tenemos dos monedas.
Eso es correcto.
>> Repasamos peniques y vemos que que nos queda más centavos.
Hmm, eso es extraño.
Hasta aquí, en el programa, que se suponía haber restado mis peniques.
Tal vez yo no estaba haciendo que la línea derecha.
Y por desgracia, se puede ver aquí, porque sabemos
que estamos pisando a través de líneas 32 y 33,
ahí es donde nuestro programa inapropiadamente tuvieron las variables corren.
Así que podemos mirar y ver, oh, Estoy restando centavos aquí,
pero no estoy realmente añadir a mi valor de la moneda.
Estoy añadiendo a centavos.
Y yo no quiero añadir a centavos, quiero añadir a monedas.
Así que si cambiamos eso a monedas, tenemos un programa de trabajo.
Puedo correr check50.
Usted sólo puede salir del BGF derecho aquí y luego ejecutar check50 nuevo.
Yo sólo podía hacer esto.
Tengo que hacer codicioso.
0.41.
Y aquí, es la impresión la respuesta correcta.
>> Así como ustedes pueden ver, el BGF es una herramienta muy potente
para cuando tenemos tanto código pasando y tantas variables
que es difícil para nosotros, como un ser humano, no perder de vista.
El equipo, en el BGF depurador, tiene la capacidad
hacer un seguimiento de todo.
Lo sé, en Visionaire, ustedes probablemente podría haber afectado a algunos fallos de segmentación
debido a que se estaba ejecutando fuera de los límites de la matriz.
En el ejemplo de César, eso es exactamente lo que he implementado aquí.
>> Así que me olvidé de comprobar ¿qué pasaría si yo
no tener dos argumentos de la línea de comandos.
Simplemente no me pongo en el registro de entrada.
Y así, si me quedo Debug-- configuro mi punto de ruptura a la derecha allí.
Corro de depuración.
>> OK.
Sí.
Así que en realidad, el BGF se suponía me han dicho que hay
Fue un fallo de segmentación allí.
No sé lo que estaba pasando allí mismo, pero cuando me encontré con él,
que estaba trabajando.
Cuando se ejecuta a través de líneas de código y BGF podría dejar de repente sobre ti,
sube y mira lo que es el error rojo.
Se lo diré, bueno, tenido un fallo de segmentación,
lo que significa que intentó acceder espacio en una matriz que no existía.
Sí.
>> Así que en el siguiente problema establezca esta semana, chicos
probablemente tendrá una gran cantidad de Variables flotando alrededor.
Usted no va a estar seguro de lo que todos ellos significan en un momento determinado.
Así GDB realmente le ayudará a averiguar lo que todos ellos están igualando
y ser capaz de ver que visualmente.
¿Hay alguien confundido sobre cómo nada de eso estaba trabajando?
Guay.
Correcto.
Así que después de eso, estamos ir a bucear en derecho
en son cuatro diferentes tipos de clases para esta semana.
¿Cuántos de ustedes, primero sobre todo, antes de empezar,
han leído toda la especificación para pset3?
OK.
Estoy orgulloso de ustedes.
Eso es como la mitad de la clase, que es significativamente más que la última vez.
>> Así que eso es genial, porque cuando hablamos sobre el contenido
en lecture-- o lo siento, en sección- me gusta
relacionar mucho de eso de nuevo a lo que el conjunto de procesadores es
y cómo desea implementar eso en su conjunto de procesadores.
Así que si usted viene teniendo leer la especificación, que va a
ser mucho más fácil para que usted entienda lo que estoy hablando cuando digo,
oh bueno, esto podría ser una realidad buen lugar para poner en práctica este tipo.
Así que aquellos de ustedes que han leído el spec saber que, como parte de su conjunto de procesadores,
usted va a tener que escribir un tipo de especie.
Así que esto puede ser muy útil para muchos de ustedes hoy.
>> Así que vamos a empezar con, en esencia, el tipo más sencillo
de género, la ordenación por selección.
El algoritmo típico para cómo nos gustaría ir sobre esto
es-- David pasó por estos todos en conferencia, así que voy a pasar rápidamente a lo largo
aquí-- es esencialmente, que tener una matriz de valores.
Y luego encontrar el menor valor sin clasificar
y cambias ese valor con el primer valor sin clasificar.
Y luego te quedas con la repetición con el resto de su lista.
>> Y aquí está una explicación visual de la forma en que iba a funcionar.
Así, por ejemplo, si tuviéramos que empezar con una serie de cinco elementos, el índice
0 a 4, con 3, 5, 2, 6, y 4 valores colocado en el array-- así que ahora,
sólo vamos a asumir que todos están sin clasificar
porque no hemos probado lo contrario.
>> Entonces, ¿cómo una selección tipo haría el trabajo es que lo haría primero
ejecutar a través de la totalidad de la matriz sin clasificar.
Sería seleccionar el valor más pequeño.
En este caso, 3, a la derecha Ahora, es el más pequeño.
Se pone a 5.
No, 5 no es mayor no sea: o lo siento, no es inferior a: 3.
Por lo tanto el valor mínimo es todavía 3.
Y entonces se llega a 2.
El equipo considera que, oh, 2 es inferior a 3.
2 debe ser ahora el valor mínimo.
Y así 2 swaps con ese primer valor.
>> Así que después de una pasada, nosotros de hecho vemos que el 2 y el 3 se intercambian.
Y sólo vamos a seguir haciendo esto de nuevo con el resto de la matriz.
Así que vamos a simplemente ejecutar a través de los últimos cuatro índices de la matriz.
Veremos que 3 es el siguiente valor mínimo.
Así que vamos a cambiar eso con 4.
Y entonces sólo vamos a mantener que atraviesa hasta que, finalmente, se
llegar a un arreglo ordenado en el que 2, 3, 4, 5, y 6 se todo Tipo.
¿Todos entienden la lógica de cómo funciona una selección especie?
>> Sólo tienes algún tipo de un valor mínimo.
Estás hacer el seguimiento de lo que es.
Y cada vez que lo encuentras, cambias lo con el primer valor en el array--
o bien, no es la primera value-- el siguiente valor en la matriz.
Guay.
>> Así como ustedes clase de vio desde un breve vistazo,
vamos a Pseudocódigo esto.
Así que si ustedes en la parte posterior queréis formar un grupo, todo el mundo en una mesa
pueden formar un pequeño compañero, voy para darle tipos como tres minutos
simplemente hablar a través de la lógica, en Inglés,
de cómo podríamos ser capaces de implementar pseudocódigo para escribir una ordenación por selección.
Y hay dulces.
Por favor venga y conseguir caramelos.
Si estás en la parte de atrás y desea dulces, puedo tirar caramelos a usted.
En realidad, hacer fresco usted--.
Oh, lo siento.
OK.
>> Así que si nos gustaría, ya que una clase, escribir pseudocódigo
para cómo se podría acercarse este problema, apenas siente libre.
Iré a su alrededor y, con el fin, pida grupos
para la siguiente línea de lo que deberíamos estar haciendo.
Así que si ustedes quieren empezar fuera, ¿qué es lo primero
Qué hacer cuando usted está tratando de poner en práctica una forma de resolver este programa
para ordenar selectivamente una lista?
Vamos a suponer que tener una matriz, ¿de acuerdo?
>> AUDIENCIA: ¿Quieres crear algunos especie de [inaudible] que eres
corriendo a través de toda su gama.
>> ANDI Peng: Correcto.
Así que vas a querer repetir a través de cada espacio, ¿no?
Tan estupendo.
Si ustedes quieren que me diera el junto line-- sí, en la parte posterior.
>> AUDIENCIA: Échales todo para los más pequeños.
>> ANDI Peng: No vamos.
Así que queremos ir a través y verifique ver lo que el valor mínimo es, ¿verdad?
Voy a abreviar que a "min".
¿Qué es lo que ustedes quieren hacer después has encontrado el valor mínimo?
>> AUDIENCIA: [inaudible]
ANDI Peng: ¿Así que vas a querer cambiar con el primero de esa serie,
¿derecho?
Ese es el principio, que voy a decir.
Correcto.
Así que ahora que ha cambiado el primero uno, ¿qué es lo que quieres hacer después de eso?
Así que ahora sabemos que este de aquí debe ser el valor más pequeño, ¿no?
Entonces usted tiene un descanso adicional de la matriz que está sin clasificar.
Así que lo que quiero hacer aquí, si chicos quieren darme la siguiente línea?
AUDIENCIA: Entonces quiere iterar a través del resto de la matriz.
ANDI Peng: Sí.
Y así lo hace a través de la iteración tipo de implicamos que probablemente necesitaremos?
Que tipo de--
>> AUDIENCIA: Oh, una variable adicional?
ANDI Peng: Probablemente otra para el bucle, ¿verdad?
Así que probablemente vamos a querer iterar through-- grande.
Y luego vas a volver y Probablemente comprobar el mínimo de nuevo,
¿derecho?
Y usted va a seguir repitiendo esto, porque los bucles sólo va
para seguir funcionando, ¿no?
>> Así como ustedes pueden ver, sólo tienen un pseudocódigo en general
de cómo queremos que este programa se vea.
Este reiterar aquí, ¿qué hacemos normalmente necesitará escribir en nuestro código
si queremos recorrer un matriz, qué tipo de estructura?
Creo que Christabel ya se ha dicho antes.
>> AUDIENCIA: Un bucle for.
>> ANDI Peng: Un bucle for?
Exactamente.
Así que este es probablemente Va a ser un bucle for.
¿Qué es un cheque aquí va a entender?
Normalmente, si desea comprobar si algo es algo else--
>> AUDIENCIA: Si.
>> ANDI Peng: Un caso, ¿no?
Y entonces el canje Aquí, vamos a ir más tarde, porque David
pasó por que en la conferencia también.
Y entonces la segunda iteración implies--
>> AUDIENCIA: Otra de bucle.
>> ANDI Peng: --another bucle for, exactamente.
Así que si estamos buscando en este correctamente,
puede ver que estamos probablemente va a necesitar un anidado bucle for
con una sentencia condicional allí y luego una verdadera pieza de código que es
va a cambiar los valores.
Así que en general, que he escrito un código de pseudocódigo aquí.
Y entonces estamos realmente va físicamente, como una clase,
tratar de aplicar esto hoy.
Volvamos a este IDE.
>> UH oh.
¿Por qué es que no-- ahí está.
OK.
Lo sentimos, pero voy a tratar de acercar un poco más.
Allá vamos.
Todo lo que estoy haciendo aquí es que he creado un programa llamado "selección / sort.c."
He creado una serie de nueve años valores, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Actualmente, como pueda ver, son desordenados.
n va a ser el número que le dice la cantidad de valores
que tiene en su arsenal.
En este caso, tenemos nueve valores.
Y sólo tengo un bucle for aquí que imprime la matriz sin clasificar.
>> Y al final, yo también tengo una para bucle que sólo imprime hacia fuera otra vez.
Así que en teoría, si este programa funciona correctamente, al final,
debería ver un imprimen bucle for en el que 1, 2, 3, 4, 5, 6, 7, 8,
9 son todo correctamente en orden.
>> Así que tenemos nuestro pseudocódigo aquí.
¿Alguien quiere a-- Sólo soy va a ir pedir volunteers--
dime exactamente qué escribir si queremos, en primer lugar, simplemente iterar
a través del principio de esta matriz?
¿Cuál es la línea de código que soy Probablemente va a necesitar aquí?
>> AUDIENCIA: [inaudible]
>> ANDI Peng: Sí, se siente a-- siento libre, usted
no tienen que soportar up-- sensación libertad para levantar la voz un poco.
>> AUDIENCIA: Para int i es igual 0--
>> ANDI Peng: Sí, bueno.
>> AUDIENCIA: i es menor que la longitud de la matriz.
>> ANDI Peng: Así que tenga en la mente aquí, porque nosotros
no tienen una función que nos dice la longitud de una matriz,
ya tenemos una valor que almacena eso.
¿Correcto?
Otra cosa a tener en mente-- en una matriz
de nueve valores, ¿cuáles son los índices?
Digamos que esta matriz fue 0-3.
Usted ve que el último índice es en realidad 3.
No es 4, a pesar de que hay cuatro valores en la matriz.
>> Así que aquí, tenemos que tener mucho cuidado de lo que nuestra condición para la longitud
va a ser.
>> AUDIENCIA: ¿No sería n menos 1?
ANDI Peng: Va n menos 1, exactamente.
¿Tiene sentido, ¿por qué es n menos 1, todo el mundo?
Es porque las matrices son indexados de cero.
Empiezan a 0 y se ejecutan hasta n menos 1.
Sí, es un poco complicado.
OK.
Y entonces--
AUDIENCIA: Isnt'1 que ya atendidos, sin embargo,
por no decir "inferior o igual a "y decir" menos? "
>> ANDI Peng: Esa es una muy buena pregunta.
Entonces sí.
Pero también, la forma en que estamos hacer efectivo el derecho de comprobar,
es necesario comparar dos valores.
Así que usted realmente quiere salir de la "a" vacío.
Porque si se compara éste, no vas
tener nada después comparar, ¿no?
Sí.
Así que i ++.
Vamos a añadir nuestros soportes en.
¡Vaya.
Excelente.
Así que tenemos el comienzo de nuestro bucle exterior.
Así que ahora que probablemente queremos crear una variable para mantener
pista del valor más pequeño, ¿no?
¿Alguien quiere darme la línea de código que haría eso?
¿Qué necesitamos si vamos querer almacenar algo?
>> Correcto.
Tal vez un mejor nombre para que sería ser-- "temp" totalmente works--
tal vez una más bien llamado sería, si queremos que el value-- más pequeño
>> AUDIENCIA: Min.
ANDI Peng: min, ahí vamos.
min sería bueno.
Y aquí, ¿qué hacemos que inicializar a?
Esto es un poco complicado.
Debido a que en este momento en el a partir de esta matriz,
usted no ha mirado nada, ¿verdad?
Entonces, ¿qué, de forma automática, si estamos sólo en i es igual a 0,
¿qué queremos para inicializar nuestro primer valor mínimo de?
AUDIENCIA: i.
ANDI Peng: i, exactamente.
Christabel, ¿por qué queremos para inicializar a i?
>> AUDIENCIA: Porque, bueno, estamos empezando con 0.
Así que porque no tenemos nada para comparar a, el mínimo va a terminar siendo 0.
>> ANDI Peng: Exactamente.
Así que ella es exactamente correcto.
Debido a que tenemos en realidad no mirado nada todavía,
no sabemos cuál es nuestro valor mínimo es.
Queremos simplemente inicializar a i, que, actualmente, es aquí.
Y a medida que continuamos bajar esta matriz,
veremos que, con cada pase adicional, i incrementos.
Y así, en ese punto, i probablemente va
a querer ser el mínimo, porque va a ser lo que sea
es el principio de la matriz sin clasificar.
Guay.
>> Así que ahora queremos añadir un bucle for aquí eso es
va a recorrer el sin clasificar, o el resto de esta serie.
¿Alguien quiere darme un línea de código que haría eso?
Hint-- ¿Qué necesitamos aquí abajo?
¿Qué va a pasar en este bucle for?
Sí.
AUDIENCIA: Así que nos gustaría tener un número entero diferente,
porque nos estamos quedando por el resto de la matriz en lugar de la i, así que tal vez
j.
>> ANDI Peng: Sí, j suena bien para mí.
Es igual?
>> AUDIENCIA: Entonces sería i + 1, porque estás empezando en el siguiente valor.
Y luego a la end-- así que de nuevo, j es menos de n menos 1, y luego j ++.
ANDI Peng: Grande.
>> Y luego aquí, vamos a querer para comprobar si se cumple nuestra condición,
¿derecho?
Porque quieres cambiar el valor mínimo
si en realidad es más pequeño que lo que usted está comparando a, ¿verdad?
Entonces, ¿qué vamos a querer en esta lista?
Compruebe.
¿Qué tipo de declaración estamos probablemente vamos
ti desea utilizar si que desee comprobar algo?
>> AUDIENCIA: Una sentencia if.
>> ANDI Peng: Una sentencia if.
Así que si: y lo que va a ser la condición que queremos en el interior
de nuestra sentencia if?
>> AUDIENCIA: Si el valor de j es menor que el valor de i--
>> ANDI Peng: Exactamente.
Así que si: por lo que esta serie se llama "matriz".
Excelente.
Así que si array-- ¿qué fue eso?
Repitelo.
>> AUDIENCIA: Si array-j es menor que matriz-i, entonces cambiaría el min.
Así que el mínimo sería j.
>> ANDI Peng: ¿Tiene sentido?
OK.
Y ahora aquí, en realidad desee implementar el canje, ¿verdad?
Así que recuerda, en la conferencia, que David, cuando él estaba tratando de cambiar el-- lo que era
jugo de naranja it-- y milk--
>> AUDIENCIA: Eso era asqueroso.
>> ANDI Peng: Sí, eso era un poco bruto.
Pero fue una buena bonita concepto de tiempo demostrando.
Así que piensa en sus valores aquí.
Tienes un array de minutos, una gran variedad de i,
o lo que estábamos tratando de cambiar aquí.
Y es probable que no se puede verter en entre sí, al mismo tiempo, ¿verdad?
Así que, ¿qué vamos a tener que crear aquí
con el fin de intercambiar correctamente los valores?
>> AUDIENCIA: Una variable temporal.
>> ANDI Peng: Una variable temporal.
Así que vamos a hacer int temp.
Mira, esto sería una mejor tiempo a-- Whoa, ¿qué fue eso?
OK.
Así que esto habría sido una mejor tiempo para nombrar el "temp." variables
Así que vamos a hacer int temp.
¿Qué vamos a set temp igual a aquí?
AUDIENCIA: Min?
ANDI Peng: Es un poco complicado.
En realidad, no importa al final.
No importa lo que para que usted elija de cambiar de
siempre y cuando usted está haciendo seguro de que eres hacer el seguimiento de lo que estás intercambiando.
>> AUDIENCIA: Podría ser array-i.
>> ANDI Peng: Sí, vamos a hacer array-i.
Y entonces ¿cuál es la siguiente línea de código que queremos tener aquí?
AUDIENCIA: array-i es igual array-j.
ANDI Peng: Y por último?
AUDIENCIA: array-j es igual array-i.
AUDIENCIA: O array-j iguales -array temp-- o, temp.
>> ANDI Peng: OK.
Así que vamos a ejecutar esto y ver si se va a trabajar.
¿Dónde está eso suceda?
Oh, eso es un problema.
Mira, en la línea 40, que estamos tratando de usar matriz de j?
Pero ¿de dónde j sólo existen en?
>> AUDIENCIA: En el bucle for.
ANDI Peng: Correcto.
Entonces, ¿qué vamos a tener que hacer?
>> AUDIENCIA: Definir fuera el--
AUDIENCIA: Sí, supongo que tienes utilizar otra sentencia if, ¿verdad?
Así como, si el minimum-- bien, déjame pensar.
>> ANDI Peng: Chicos, tratar para echar un vistazo de Let
vemos, lo que es algo que podemos hacer aquí?
>> AUDIENCIA: OK.
Así que si el mínimo no es igual a j-- por lo que si el mínimo es todavía yo--
entonces no tendríamos que cambiar.
>> ANDI Peng: ¿Eso igual i?
¿Qué quiere decir aquí?
>> AUDIENCIA: O sí, si el mínimo no es igual a i, sí.
ANDI Peng: OK.
Bueno, eso resuelve, algo así, nuestros problemas.
Pero eso todavía no resuelve el problema de lo que sucede si j-- desde j
no existe fuera de ella, lo que Cómo se nos quiere hacer con él?
Declarar fuera?
Vamos a tratar de ejecutar este.
UH oh.
Nuestra especie no está funcionando.
>> Como se puede ver, nuestra inicial matriz tenía esos valores.
Y después que debería tener estado en 1, 2, 3, 4, 5, 6, 7, 8, 9.
No está funcionando.
Ahh.
¿Qué hacemos?
AUDIENCIA: Depuración.
ANDI Peng: Muy bien, podemos probar eso.
Podemos depurar.
Reducir un poco.
Vamos a poner nuestro punto de interrupción.
Vamos como-- Aceptar.
>> Así pues ya sabemos que estas líneas, 15 a 22,
se working-- porque todo lo que estoy haciendo es simplemente iterar a través y printing--
Puedo seguir adelante y saltar eso.
Vamos a empezar en la línea 25.
Oop, déjame deshacerme de eso.
>> AUDIENCIA: Entonces el punto de interrupción donde comienza la depuración?
ANDI Peng: O paradas.
AUDIENCIA: O paradas.
ANDI Peng: Sí.
Puede configurar varios puntos de interrupción y sólo puede saltar de una a otra.
Pero en este caso no sabemos donde el error está sucediendo.
Así que sólo queremos empezar desde arriba hacia abajo.
Sí.
OK.
>> Así que esta línea de aquí, podemos intervenir.
Se puede ver aquí abajo, tenemos una matriz.
Esos son los valores que se encuentran en la matriz.
¿Ves eso, ¿cómo el índice 0, se corresponde a la value-- oh,
Voy a tratar de hacer un zoom.
Lo sentimos, pero es muy difícil a ver-- al índice de matriz 0,
tenemos un valor de 4 y a continuación, así sucesivamente y así sucesivamente.
Tenemos nuestras variables locales.
Ahora mismo i es igual a 0, lo que queremos que sea.
>> Y así vamos a seguir paso a paso a través.
Nuestra mínimo es igual a 0, que también queremos que sea.
Y entonces entramos en nuestro segundo para lazo, si array-j es menor de gama-i,
que no lo era.
Así que ¿viste cómo que omiten sobre eso?
>> AUDIENCIA: Entonces, si el caso mínimo, todo eso-- no debería que
estar dentro de la primera bucle for?
ANDI Peng: No, porque usted todavía desea probar.
¿Quieres hacer una comparación cada tiempo, incluso después de ejecutar a través de él.
Usted no sólo quiere hacerlo en el primer paso.
¿Quieres hacerlo con cada pasada adicional de nuevo.
¿Así que quieres comprobar su condición interior.
Así que sólo vamos a seguir corriendo por aquí.
Te voy a dar una pista chicos.
Tiene que ver con el hecho de que cuando usted está comprobando su condicional,
usted no está comprobando para el índice correcto.
Así que ahora usted está comprobando índice de matriz de j es menos de matriz
Índice de i.
Pero, ¿qué estás haciendo para arriba en el principio del bucle for?
¿No estás configurando j igual a i?
>> Sí, por lo que puede en realidad salir del depurador aquí.
Así que echemos un vistazo a nuestra pseudocódigo.
Para-- vamos a comenzará a las i es igual a 0.
Vamos a ir hasta n menos 1.
Vamos a ver, qué tenemos ese derecho?
Sí, eso era correcto.
>> Así que aquí dentro, estamos va a crear un valor mínimo
y establecer que igual a i.
¿Hicimos eso?
Sí, lo hizo.
Ahora en nuestro interior para bucle, estamos va a hacer j es igual a i n menos 1.
¿Hicimos eso?
De hecho, lo hicimos.
>> Así que, sin embargo, ¿qué estamos comparando aquí?
>> AUDIENCIA: j más 1.
ANDI Peng: Exactamente.
Y entonces usted va a querer establecer su mínima igual a j plus 1 también.
Así que me fui a través de esa realidad rápidamente.
¿Entienden ustedes por qué es j más 1?
OK.
>> Así que en su conjunto, en el primer paso a través,
el bucle for, por int i es igual a 0, vamos a
asume esto no se ha cambiado todavía.
Tenemos una gran variedad de, por completo, sólo cuatro elementos no ordenados, ¿verdad?
Así que queremos inicializar i igual a 0.
Y me va a acaba ejecutar este bucle.
Y así, en la primera pasada, vamos para inicializar una variable llamada "min"
que también es igual a i, porque no tenemos un valor mínimo.
Así que esa es actualmente igual a 0 también.
Y luego vamos a pasar.
Y queremos repetir otra vez.
Ahora que hemos encontrado lo que nuestro mínima Es decir, queremos recorrer
de nuevo para ver si se trata de comparar, ¿verdad?
Así j, aquí, se va a la igualdad de i, que es 0.
Y luego, si arsenal j plus i, que es el que está al lado otra vez, como menos
de lo que su mínimo actual valor es, que desea intercambiar.
>> Así que vamos a decir que hemos tiene, como, 2, 5, 1, 8.
En este momento, i es igual a 0 y j es igual a 0.
Y ese es nuestro valor mínimo.
Si variedad j-plus yo-- por lo que si el eso es después de la que estamos viendo
es mayor que la anterior, que va a convertirse en el mínimo.
>> Así que aquí vemos que 5 no es menos que eso.
Así que va a estar 5.
Vemos que 1 es menor que 2, ¿verdad?
Así que ahora que sabemos que nuestro mínimo es va a ser el valor del índice en 0, 1, 2.
¿Sí?
Y luego cuando llegas aquí, usted puede cambiar los valores correctos.
>> Así que cuando ustedes simplemente tuvieron la j antes, no estaban buscando en el
después de.
Estabas mirando el mismo valor, el cual
es por eso que no estaba haciendo nada.
¿Eso tiene sentido para todos, por eso necesitamos que más 1 allí?
OK.
Ahora vamos a ejecutar a través de él para hacer Asegúrese de que el resto del código es correcto.
¿Por qué es que eso suceda?
Ah, es el mínimo aquí.
Estábamos comparando el valor incorrecto.
Oh no.
>> Ah, sí, aquí estábamos el canje de los valores erróneos también.
Debido a que estábamos buscando en i y j.
Esos son los que nos marchábamos.
En realidad, queremos cambiar la mínimo, el mínimo actual,
con lo que el exterior es.
Y como ustedes pueden ver abajo aquí, tenemos un arreglo ordenado.
Simplemente tenía que ver con el hecho de que cuando
nos íbamos el valores que estábamos comparando,
que no estábamos buscando en los valores correctos.
Estábamos buscando en el mismo aquí, en realidad no es el canje.
Usted tiene que mirar el uno al lado a él y luego se puede cambiar.
Así que eso es lo que era una especie de molestando nuestro código antes.
Y lo que hice aquí lo es todo el depurador podría haber hecho para ti
Yo sólo lo hizo en el tablero, porque es más fácil
para ver en lugar de tratar para acercar el depurador.
¿Eso tiene sentido para todo el mundo?
Guay.
>> Correcto.
Podemos pasar a hablar de notación asintótica, que
es sólo una forma elegante de decir la tiempos de ejecución de todos estos tipos.
Así que sé David, en la conferencia, referido a los tiempos de ejecución.
Y se fue por toda la fórmula de cómo calcular los tiempos de ejecución.
No te preocupes por eso.
Si usted es realmente curioso sobre cómo funciona,
no dude en hablar conmigo después de la sección.
Podemos caminar a través de las fórmulas juntos.
Pero todos ustedes tienen para realmente saber es que n al cuadrado más de 2
es lo mismo que n al cuadrado.
Debido a que el número más grande, el exponente, más crece.
Y así, para nuestros propósitos, todos nos preocupamos por
es ese número gigante que está creciendo.
>> Entonces, ¿cuál es el mejor de los casos tiempo de ejecución de la ordenación por selección?
Si usted va a tener para recorrer una lista
y luego recorrer el resto de la lista,
¿cuántas veces se usted va a probablemente,
en el peor de caso-- en el mejor de los casos, sorry-- ejecutar a través de?
Tal vez la mejor pregunta es preguntar, ¿cuál es el peor de los casos
tiempo de ejecución de la ordenación por selección.
AUDIENCIA: n al cuadrado.
ANDI Peng: Ha n al cuadrado, derecha.
Así que una manera fácil de pensar en esto es como, cualquier momento tienes dos anidado para los bucles,
que va a ser n al cuadrado.
Porque no sólo es usted corriendo a través una vez más,
usted tiene que volver vuelta y correr a través de él
una vez en el interior de cada valor.
Así que en ese caso, se está ejecutando n tiempos n al cuadrado, que éstos: lo siento,
n veces n, que es igual a n al cuadrado.
>> Y especie es también un poco único en el sentido
que no importa si éstos valores ya están en orden.
Todavía va a ejecutar a través de todos modos.
Digamos que este fue de 1, 2, 3, 4.
Independientemente de si era o no en fin, todavía habría corrió a través de
y todavía comprobado el valor mínimo.
Habría hecho el mismo número de cheques
cada vez, incluso si en realidad no tocar nada.
>> Así pues, en tal caso, el mejor y el peor tiempos de ejecución son en realidad equivalentes.
Así que el tiempo de ejecución esperado de ordenación por selección,
que designamos por el símbolo de theta, theta, en este caso,
también sería n al cuadrado.
Los tres de ellos serían n al cuadrado.
Está claro por qué todo el mundo la duración es n al cuadrado?
>> Correcto.
Así que sólo voy a correr rápidamente por el resto de los géneros.
El algoritmo para burbuja sort-- recuerde,
esta fue la primera David se acercó en la conferencia.
Esencialmente, usted camina a través de la lista entera
y que acaba de swap-- comparar los dos a la vez.
Y si uno es mayor, lo que sólo les intercambiar.
Así que si éstos son mayores, que cambiaría.
Tengo oficial aquí.
>> Así que vamos a decir que tenía 8, 6, 4, 2.
Se podría comparar el 8 y un 6.
Usted necesitaría para intercambiarlas.
Se podría comparar el 8 y un 4.
Usted necesitaría para intercambiarlas.
Si tiene que cambiar el 8 y el 2, cambie ellos también.
Así pues, en tal sentido, se puede ver, jugado a cabo durante un largo período de tiempo,
cómo los valores de tipo de burbuja los extremos, lo cual es por eso que lo llaman
ordenamiento de burbuja.
>> Nos gustaría simplemente ejecutar a través de nuevo en nuestra segunda pasada, y nuestro tercer paso,
y nuestro cuarto pase.
Esencialmente, burbuja especie sólo se ejecuta hasta que no haga más swaps.
Así que en ese sentido, esto es sólo el pseudocódigo general para ello.
No se preocupe, éstos serán todos en línea.
No tenemos que ir realmente sobre esto.
>> Acabamos inicializamos un contador variable que comienza en 0.
Y recorrer toda la matriz.
Y si un valor es-- si esto valor es mayor que ese valor,
vas para intercambiarlas.
Y entonces no eres más que va a seguir adelante.
Y vas a contar.
Y sólo vamos a seguir haciendo esto mientras que el contador es mayor
que 0, lo que significa que cada vez que tiene que cambiar,
usted sabe que quiere ir espalda y puedes volver a intentarlo.
Usted quiere mantener la comprobación hasta que usted sepa que usted no tiene que cambiar ya.
>> Entonces, ¿qué son los mejores y peores caso los motores de ejecución de ordenamiento de burbuja?
Y hint-- esto es realmente diferente desde la selección del tipo en el sentido
que estas dos respuestas no son iguales.
Piense en lo que sucedería en un caso si ya se solucionó.
Y pensar en lo Qué pasaría si fuera
en el caso en el que no se solucionó.
Y usted puede clase de correr a través de por qué está sucediendo.
Te voy a dar los chicos, como, 30 segundo para pensar en eso.
>> OK.
¿Alguien tiene una pista sobre lo que el peor de los casos el tiempo de ejecución de la burbuja de tipo es?
Sí.
>> AUDIENCIA: ¿Sería, como, n veces n menos 1 o algo así?
Al igual que, cada vez que se ejecuta, es sólo, como, uno de intercambio menos
que todo lo que era.
>> ANDI Peng: Sí, así usted es del todo acertada.
Y este es un caso en el que el respuesta era en realidad más compleja
que el que tenemos que dar.
Así que va a run-- estoy va a borrar todo esto aquí.
¿Es bueno todo el mundo?
¿Puedo borrar esto?
OK.
Usted va a ejecutar a través de n veces la primera vez, ¿verdad?
Y ellos van a ejecutar a través de n menos 1 la segunda vez, ¿verdad?
Y luego vas a mantener va, n mina 2, etcétera.
David hizo esto en una conferencia, en el que, si se ha añadido a todos esos valores,
usted consigue algo que es como-- yeah-- más de 2, lo que reduce esencialmente sólo
hacia abajo para n al cuadrado.
Usted va a obtener una fracción raro ahí.
Y así, sólo sé que el n al cuadrado siempre
tiene prioridad sobre la fracción.
Y así, en este caso, lo peor tiempo de ejecución sería n al cuadrado.
Si fue en descenso orden, creo, que
tener que hacer un intercambio cada vez.
>> ¿Cuál sería, potencialmente, el mejor tiempo de ejecución caso?
Digamos, si la lista ya estaba con el fin, ¿cuál sería el tiempo de ejecución?
>> AUDIENCIA: n.
ANDI Peng: Es n, exactamente.
Y ¿por qué es n?
AUDIENCIA: Debido a que usted acaba de tendrá que comprobar en cada vez.
ANDI Peng: Exactamente.
Así pues, en la mejor ejecución posible, si esta lista ya estaba
sorted-- digamos 1, 2, 3, 4-- usted acaba de pasar, que le echa,
verías, oh, todos ellos resultan.
Yo no tenía que cambiar.
He terminado.
Así que en ese caso, es sólo n o el número de pasos que acaba de
tuvo que comprobar en la primera lista.
>> Y después, ahora golpeamos ordenación por inserción, donde
el algoritmo es esencialmente divide en una parte ordenada y sin clasificar.
Y entonces uno por uno, los valores no clasificados son
insertado en su apropiada posiciones en el principio de la lista.
>> Así, por ejemplo, tenemos una Lista de 3, 5, 2, 6, 4 de nuevo.
Sabemos que es actualmente sin clasificar porque acabamos de
comenzado mirarlo.
Echamos un vistazo y sabemos que el primer valor se ordena, ¿verdad?
Si sólo está buscando en una serie de tamaño de uno, usted sabe que está ordenada.
>> Así que sabemos que el otros cuatro son sin clasificar.
Vamos a través y vemos ese valor.
Volvamos.
Ver que el valor de 5?
Echamos un vistazo.
Comparamos a 3.
Sabemos que es mayor que 3, por lo que sabemos que eso está solucionado.
Así que ahora sabemos que los dos primeros se ordenan y los tres últimos no lo son.
>> Echamos un vistazo a 2.
En primer lugar, comprobamos con 5.
¿Es menor que 5?
No lo es.
Así que tenemos que seguir mirando hacia abajo.
Luego de comprobar 2 de 3.
¿Es menor que?
No.
Así que ya sabes un 2 tiene que ser insertado en la parte delantera y 3 y 5
ambos tienen que ser expulsados.
Haga esto de nuevo con 6 y 4.
Y nosotros sólo seguimos comprobando en esencia, donde acabamos de comprobar, verificar, comprobar.
Y hasta que esté en la derecha posición, tipo de solo
insertarlo en la posición correcta, que es donde el nombre del vino.
>> Así que eso es sólo el algoritmo, pseudocódigo per se, una especie de,
sobre cómo íbamos a poner en práctica un tipo de inserción.
Pseudocódigo está aquí.
Todo está en línea.
No se preocupe si ustedes son tratando de copiar esto.
Así que una vez más, lo mismo pregunta-- sería el mejor y el peor de los tiempos de ejecución
para la ordenación por inserción?
Es muy similar a la última pregunta.
Te voy a dar los chicos, como, 30 segundo para pensar en esto también.
>> OK ¿Alguien quiere dame el peor tiempo de ejecución?
Sí.
>> AUDIENCIA: n al cuadrado.
>> ANDI Peng: Ha n al cuadrado.
Y ¿por qué es n al cuadrado?
>> AUDIENCIA: Porque en orden inverso, usted tiene
que pasar por n veces n, de que éstos:
ANDI Peng: Sí, exactamente.
Así mismo que en el ordenamiento de burbuja.
Si esta lista está en orden descendente, eres
va a tener que comprobar primero una vez.
Y a continuación, con cada valor adicional, usted es
va a tener que comprobar que en contra cada valor único, ¿no?
Y así, en conjunto, que vas a hacer un momento n pasar a otro n pasan, que
está n al cuadrado.
¿Y el mejor de los casos?
Sí.
>> AUDIENCIA: n menos 1, ya que el primero ya se eleva al cuadrado.
>> ANDI Peng: Así, cerca.
La respuesta es en realidad n.
Porque si bien la primera es ordenados, puede que no se actually--
sólo tuvimos suerte, en ese ejemplo, que 2
pasó a ser el número más pequeño.
Pero eso no siempre será el caso.
Si 2 ya está ordenado en un principio pero te ves y hay un 1 aquí,
el 1 va a topar.
Y que va a terminar siendo golpeado de todos modos.
>> Así que en el mejor de los casos, en realidad es sólo va a ser n.
Si usted tiene 1, 2, 3, 4, 5, 6, 7, 8, eres
va a ejecutar a través de esa lista toda vez
comprobar para ver si todo está bien.
Están todos claro en funcionamiento tiempos de la selección así?
Sé que estoy pasando estos realmente rápido.
Pero sólo sé que si se conoce el conceptos generales, debe ser bueno.
OK.
Así que sólo te daré chicos tal vez, como, un minuto para hablar con sus vecinos
en lo que son sólo algunas de las principales diferencias
entre estos tipos de clases.
Vamos a repasar que pronto.
AUDIENCIA: ¡Oh, OK.
ANDI Peng: Sí.
OK.
Fresco, vamos nuevamente las como clase.
OK.
Así que esto era una especie de pregunta abierta en el sentido
que hay un montón de respuestas a ellos.
Y vamos a repasar algunos de ellos brevemente.
Yo sólo quería conseguir que los chicos pensando en lo diferenciado
los tres tipos de clases.
Y oí, también, una gran pregunta-- ¿qué ordenamiento por mezcla hacer?
Muy buena pregunta, porque eso es lo que estamos cubriendo siguiente.
>> Así ordenamiento por mezcla es la un tipo que funciona
muy diferente a los otros tipos.
Como ustedes pueden ver-- hizo David esa demo
donde tenía todo el fresco ruidos de ver cómo se fusionan
especie corrió, como, infinitamente más rápido que los otros dos tipos?
OK.
Así que eso es debido a la fusión clase implementa esa brecha
y conquistar el concepto que hemos hablado mucho en conferencia.
En ese sentido que nos gusta trabajar más inteligente, no más difícil, cuando se divide
y conquistar problemas, y romperlos abajo, y luego ponerlos juntos,
buenas cosas siempre suceden.
>> Así que la forma en que se fusionan trabaja especie esencialmente
es que se divide una array sin ordenar a la mitad.
Y entonces tiene dos mitades de matrices.
Y simplemente ordena esas dos mitades.
Simplemente sigue dividiendo a la mitad, en media, en medio hasta que todo se ordena
y luego recursivamente pone todo junto.
>> Así que eso es muy abstracto.
Así que esto es sólo un poco de pseudocódigo.
¿Eso tiene sentido en la forma en que se está ejecutando?
Así que digamos que usted tiene una arreglo de n elementos, ¿verdad?
Si n es menor que 2, puede volver.
Porque usted sabe que si hay sólo una cosa, debe ser ordenada.
Si no, se ordena la mitad izquierda, y luego ordenar la mitad derecha,
y luego combinar.
>> Así, mientras que se ve muy fácil, en la realidad, pensando en que es
un poco difícil. Porque usted es como, bueno, eso es algo que se ejecuta en sí mismo.
¿Correcto?
Se ejecuta en sí mismo.
Así que en ese sentido, David tocó sobre la recursividad en clase.
Y eso es un concepto hablaremos más.
Es que esto, estas dos líneas aquí, en realidad es sólo el programa
diciendo que se ejecute en sí con diferente entrada.
Así que en lugar de correr en sí con la totalidad de n elementos,
se puede descomponer en el mitad izquierda y la mitad derecha
y luego ejecutarlo nuevamente.
>> Y luego vamos a ver visualmente, porque soy un aprendiz visual.
Funciona mejor para mí.
Así que vamos a ver un ejemplo visual aquí.
>> Digamos que tenemos una matriz, de seis elementos, 3, 5, 2, 6, 4, 1, no ordenados.
Muy bien, hay mucho en esta página.
Así que si ustedes pueden mirar el primer paso aquí, 3, 5, 2, 6, 4, 1,
se puede dividir por la mitad.
Usted tiene 3, 5, 2, 6, 4, 1.
Usted sabe que estos aren't-- usted no sé si están ordenados o no,
por lo que mantener su desglose, en medio, en medio, en medio, hasta que finalmente,
sólo tiene un elemento.
Y un elemento siempre está ordenada, ¿verdad?
>> Así que sabemos que 3, 5, 2, 4, 6, 1, por sí mismos, son ordenados.
Y ahora podemos volver a ponerlos juntos.
Así sabemos que el 3, 5.
Ponemos las juntas.
Sabemos que es ordenada.
Los 2 sigue allí.
Podemos poner el 4 y el 6 juntos.
Sabemos que eso se solucionó, así que pusimos que juntos.
Y el 1 es allí.
>> Y entonces usted acaba de ver estas dos mitades aquí.
Usted tiene el 3, 5, 2, 2, 3, 5.
Sólo puede comparar la a partir de todo.
Porque usted sabe que esto está ordenada y usted sabe que eso está solucionado.
Así que usted ni siquiera tiene que comparar el 5, que acaba de comparar el 3.
Y el 2 es menor que 3, por lo sabes 2 deben ir al final.
>> Lo mismo allí.
El 1 debe ir aquí.
Y luego cuando se va a poner esos dos valores juntos,
usted sabe que esto está ordenada y usted sabe que lo que se solucionó.
Así entonces el 1 y el 2, el 1 es menor que 2.
Eso te dice que el 1 debe ir en el final de este
sin mirar siquiera a 3 o 5.
Y luego el 4, sólo puede cheque, que va a la derecha aquí.
Usted no tiene que mirar el 5.
Lo mismo con el 6.
Usted sabe que el 6-- sólo no necesita ser mirado.
>> Y así, de esa manera, usted es simplemente ahorrándose
una gran cantidad de pasos cuando usted está comparando.
Usted no tiene que comparar cada elemento contra otros elementos.
Usted acaba de comparar contra los que usted necesita para comparar contra.
Así que eso es algo de un concepto abstracto.
No se preocupe si no es bastante golpear su derecha todavía.
Pero, en general, esto es cómo una combinación de tipo funciona.
Preguntas, preguntas rápidas, antes de pasar?
Sí.
>> AUDIENCIA: Entonces usted dice que usted toma el 1, y luego el 4 y el 6
y ponerlos en.
Así que no son those-- no están que mirarlos
como elementos separados, no como el todo?
ANDI Peng: Sí.
Así que lo que está pasando es que, básicamente,
están creando una nueva gama de la marca.
Así que ya sabes que, aquí, tengo dos matrices de tamaño 3, ¿verdad?
Así que ya sabes que mi matriz ordenada necesita tener seis elementos.
Así que usted acaba de crear una nueva cantidad de memoria.
Así que usted es algo así como siendo un desperdicio de la memoria,
pero eso no importa porque es muy pequeña.
Así que nos fijamos en el 1 y nos fijamos en el 2.
Y usted sabe que el 1 es inferior a 2.
Así que ya sabes que 1 debe ir en el comienzo de todo eso.
>> Ni siquiera necesita mirar el 3 y el 5.
Así que ya sabes 1 va allí.
Entonces, básicamente, cortar el 1.
Es, como, muerto para nosotros.
Entonces sólo tenemos 2, 3, 5, y luego 4 y 6.
Y entonces usted sabe eso, comparar el 4 y el 2,
oh, el 2 debe entrar ahí.
Así que usted plop del 2 abajo, usted taja apagado.
Entonces sólo tiene el 3 y el 5 en el 4 y el 6.
Y te quedas picado fuera hasta que se los pone en la matriz.
>> AUDIENCIA: Entonces, no eres más que siempre comparando el [inaudible]?
>> ANDI Peng: Exactamente.
Así que en ese sentido, usted es simplemente comparando, en esencia,
un número contra el otro número.
Y porque sabes que ha ordenado, que
no tienen que mirar a través de todos los números.
Sólo tienes que mirar a la primera.
Y entonces usted puede simplemente plop hacia abajo, porque sabes
pertenecen donde tienen que pertenecer.
Sí.
Buena pregunta.
>> Y a continuación, si alguno de ustedes son un poco ambicioso,
no dude en mirar este código.
Esto es en realidad la implementación física
de cómo escribiríamos fusión tipo.
Y usted puede ver, es muy corto.
Pero las ideas que hay detrás que son bastante complejos.
Así que si tienes ganas de dibujar esto en su tarea esta noche, no dude en.
>> OK.
David también se acercó esto en conferencia.
¿Cuáles son el mejor caso tiempos de ejecución, peores tiempos de ejecución de casos,
y los tiempos de ejecución previstos de fusión tipo?
Un par de segundos para pensar.
Esto es bastante difícil, pero un poco intuitiva si se piensa en ello.
Correcto.
>> AUDIENCIA: Es el peor de los casos n log n?
ANDI Peng: Exactamente.
Y ¿por qué es n log n.
>> AUDIENCIA: ¿No es porque se convierte en exponencialmente más rápido,
así que es como una función de la que en lugar de simplemente ser n
cuadrado o algo así?
ANDI Peng: Exactamente.
Así que la razón por qué el tiempo de ejecución en este registro es n
n es porque-- lo estás haciendo en todos estos pasos?
No eres más que cortar por la mitad, ¿no?
Y así, cuando estamos haciendo registro, todo lo que está haciendo
se dividir un problema en un medio, en medio, en un medio, en más de mitades.
Y en ese sentido, puede especie de eliminar el modelo lineal
que hemos estado usando.
Porque cuando picar cosas de la media, que es un registro.
Eso es sólo la matemática manera de representarlo.
>> Y, finalmente, al final, eres sólo hacer un último pase a través
poner todo en orden, ¿no?
Y por lo que si usted sólo tiene que comprobar una cosa, eso es n.
Y por lo que es clase de multiplicando los dos juntos.
Así que es como si tuvieras esa final comprobar N aquí con un registro de n
aquí arriba.
Y si se multiplica ellos, eso es n log n.
>> Y así, el mejor de los casos y lo peor caso y espera que se todo n log n.
Es también como otra especie.
Es como una especie de selección en el sentido de que
no importa lo que su lista es, que sólo va
a hacer lo mismo cada vez.
OK.
Así como ustedes pueden ver, a pesar de que los géneros que nos hemos ido through-- n
cuadrado, no es muy eficiente.
E incluso este n log n es no es el más eficiente.
Si ustedes son curiosos, hay mecanismos de ordenación
que son tan eficientes que son casi esencialmente plano en tiempo de ejecución.
>> Tienes algún log n de.
Tienes algún registro de log n de.
No tocamos sobre ellos en esta clase en este momento.
Pero si ustedes son curiosos, no dude en google, lo que es
los mecanismos de clasificación más eficiente.
No sé, hay algunos realmente divertidos,
como-- hay algo de verdad los divertidos que la gente hace.
Y uno se pregunta cómo Alguna vez has pensado en eso.
Así google, si tienes algo de repuesto tiempo, en adelante, ¿cuáles son algunas maneras divertidas
que personas--, así como personas ways-- eficientes
han sido capaces de poner en práctica las clases.
OK.
Y aquí es sólo un poco de práctica tabla.
Sé que todos ustedes, antes de esa prueba 0, estará en su habitación, probablemente tratando
memorizar eso.
Así que eso es bueno ahí para ustedes.
Pero no se olvide la lógica que made-- ¿por qué esos números estaban ocurriendo.
Si siempre estás perdido, simplemente hacer Asegúrese de saber lo que los tipos son.
Y se puede ejecutar a través de en tu mente
averiguar por qué los respuestas son esas respuestas.
>> Correcto.
Así que vamos a mover en, por último, a la búsqueda.
Porque como los de usted que han leído el conjunto de procesadores,
la búsqueda es también parte de El problema de esta semana pone.
Se le pedirá a aplicar dos tipos de búsquedas.
Se trata de una búsqueda lineal y uno es una búsqueda binaria.
>> Así que la búsqueda lineal es bastante fácil.
Lo que desea es buscar elementos de una lista para ver si usted lo consigue.
Sólo tienes que recorrer.
Y si es igual a algo, usted puede devolverlo, ¿verdad?
Pero el que estamos más interesado en hablar de
es la búsqueda binaria, la derecha, que es el dividir y conquistar mecanismo que
David estaba demostrando en la conferencia.
>> Recuerde el ejemplo guía de teléfonos que sigue la educación de,
la que él luchó tipo de un poco en este último año,
donde se divide el problema en el medio, en medio, en medio, una y otra vez,
hasta encontrar lo que estás buscando?
Y tienes la tiempo de ejecución de eso también.
Y usted puede ver, es significativamente más eficiente
que cualquier otro tipo de búsqueda.
>> Así que la forma en que íbamos a ir sobre la implementación de una búsqueda binaria
Es decir, si teníamos una matriz, índice de 0 a 6, siete elementos,
podemos mirar en el medio, derecha- lo siento, si nuestra pregunta primero--
si queremos hacer la pregunta de, ¿tiene la matriz contiene el elemento de 7,
obviamente, siendo los seres humanos, y que tiene como un pequeño arsenal, es fácil para nosotros
decir sí.
Pero la manera de implementar un binario Búsqueda sería buscar en el medio.
>> Sabemos que el índice 3 es el medio, ya que
saben que hay siete elementos.
¿Cuál 7 dividido por 2?
Usted puede cortar ese extra 1.
Tienes 3 en el medio.
Así que es conjunto de 3 igual a 7?
¿No está bien?
Pero podemos hacer un par de cheques.
Es gama de 3 a menos de 7 o es gama de 3 mayor que 7?
>> Y sabemos que es menos de 7.
Así que sabemos que, oh, debe no estar en la mitad izquierda.
Sabemos que debe ser en la mitad derecha, ¿no?
Así que sólo podemos cortar la mitad de la matriz.
Ni siquiera tenemos que verlo nunca más.
Porque sabemos que la mitad de nuestro problema--
sabemos que la respuesta está en la mitad derecha de nuestro problema.
Así que sólo nos fijamos en eso ahora.
>> Así que ahora nos fijamos en el medio de lo que queda.
Ese índice 5.
Hacemos lo mismo cheque de nuevo y vemos que es más pequeño.
Así que miramos a la izquierda de eso.
Y entonces vemos que cheque.
Es el valor de la matriz en índice de 4 igual a 7?
Es.
Así que podemos devolver cierto, porque encontramos el valor en nuestra lista.
¿La manera en que yo pasé por Eso tiene sentido para todo el mundo?
OK.
Te voy a dar chicos tal vez, como, tres, cuatro minutos para averiguar
cómo esto en pseudocódigo.
>> Así que imagino que te pedí que escribir una función llamada de búsqueda () que devuelve
un valor, un valor booleano, eso era cierto o false-- como,
cierto si usted encontró el valor, false si no lo hiciste.
Y entonces eras aprobada en el valor que
estabas buscando en valores, que es la array-- oh, definitivamente puse
que en el lugar equivocado.
OK.
De todas formas, eso debería tener estado a la derecha de los valores.
Y luego int n es el número de elementos en la matriz.
¿Cómo haría usted para tratar pseudocódigo para ese problema en?
Te voy a dar a tipos como tres minutos para hacer eso.
No, creo que hay only-- sí, hay uno justo aquí.
AUDIENCIA: ¿Puedo?
ANDI Peng: Sí, lo tienes.
¿Es que el trabajo?
Vale, guay.
>> OK.
Todas las personas adecuadas, estamos va a frenar en.
OK.
Así que suponemos que tenemos esta hermosa pequeña matriz con n valores en el mismo.
Yo no dibujar las líneas.
Pero ¿cómo podemos ir sobre tratando de escribir esto?
¿Alguien quiere dame la primera línea?
Si quiere darme la primera línea de este pseudocódigo.
>> AUDIENCIA: [inaudible]
AUDIENCIA: Lo que quiere iterar through--
AUDIENCIA: Sólo otro bucle for?
AUDIENCIA: --para.
>> ANDI Peng: Así que éste es un poco complicado.
Piense sobre-- desea para seguir funcionando este bucle
una y otra vez hasta cuándo?
>> AUDIENCIA: Hasta el [inaudible] valor es igual a ese valor.
ANDI Peng: Exactamente.
Así que usted puede en realidad sólo write-- incluso podemos simplificarlo más.
Sólo podemos hacer un bucle while, ¿verdad?
Así que usted puede simplemente tener loop-- sabemos que se trata de un tiempo.
Pero por ahora, me voy decir "bucle" - a través de qué?
Loop until-- lo es nuestra condición de finalización?
Creo que lo escuché.
Oí a alguien decir que.
>> Audiencia: Los valores equivalen a medio.
ANDI Peng: Dilo otra vez.
AUDIENCIA: O bien, hasta que el valor que está buscando
por es igual al valor medio.
>> ANDI Peng: ¿Y si no está ahí?
¿Qué pasa si el valor que está buscando por no es en realidad en esta serie?
AUDIENCIA: Volverá 1.
>> ANDI Peng: Pero, ¿qué es lo que queremos bucle hasta si tenemos una condición?
Sí.
>> AUDIENCIA: Hasta que no haya un solo valor?
ANDI Peng: Usted puede recorrer until-- así que usted sabe que usted es
va a tener un valor máximo, ¿no?
Y sabes que vas tener un valor mínimo, ¿no?
Porque también, eso es algo Me olvidé de decir antes,
que algo que es crítico sobre la búsqueda binaria
es que la matriz ya está ordenado.
Porque no hay forma de hacer esto si que son valores simplemente al azar.
Usted no sabe si uno es más grande que la otra, ¿no?
>> Así que ya sabes que su máximo y sus minutos están aquí, ¿verdad?
Si usted va a ser el ajuste su máximo en sus minutos y los mid--
vamos a suponer que su mediados valor es aquí-- derecho
vas a básicamente bucle hasta su mínimo es
casi lo mismo que su máximo, a la derecha, o si su máximo no es el mismo que el min.
¿Correcto?
Porque cuando eso sucede, usted sabe que que finalmente ha golpeado el mismo valor.
¿Así que quieres bucle hasta el min es menor o igual a-- perdón,
no menos de o igual a, la otra forma es around-- max.
>> ¿Eso tiene sentido?
Tomé un par de intentos para obtener ese derecho.
Pero bucle hasta su valor máximo es esencialmente casi menos
o igual que el mínimo, ¿no?
Eso es cuando usted sabe que ha convergido.
AUDIENCIA: ¿Cuándo su máximo valor sea inferior al mínimo?
ANDI Peng: Si se mantiene ajustándolo, que
es lo que nos vamos estar haciendo en este.
¿Tiene sentido?
Mínimo y máximo son sólo enteros que somos, probablemente,
va a querer crear para mantener la pista de donde estamos buscando.
Debido a que existe la matriz independientemente de lo que estamos haciendo.
Al igual, que no somos en realidad físicamente cortando la matriz, ¿no?
Estamos ajustando donde estamos buscando.
¿Tiene sentido?
>> AUDIENCIA: Sí.
>> ANDI Peng: OK.
Así que si esa es la condición para nuestro bucle, ¿qué es lo que queremos dentro de este bucle?
¿Qué vamos a querer hacer?
Así que ahora mismo, tenemos un máximo y un mínimo, a la derecha,
probablemente creado por aquí en alguna parte.
Vamos a probable que desee encontrar un medio, ¿no?
¿Cómo vamos a ser capaz de encontrar el medio?
¿Cuál es la mathematical--
AUDIENCIA: Max plus min dividido por 2.
ANDI Peng: Exactamente.
¿Tiene sentido?
Y es lo que ustedes veo por qué no acaba de servicio- por qué hicimos esto
en lugar de hacer simplemente n dividido por 2?
Es porque n es un valor eso va a seguir igual.
¿Correcto?
Pero a medida que nos adaptamos nuestra mínimo y valores máximos, que van a cambiar.
Y como resultado, nuestra media va a cambiar también.
Así que por eso queremos para hacer esto aquí.
OK.
>> Y luego, ahora que que hemos encontrado our-- sí.
>> AUDIENCIA: Sólo un pregunta-- rápida cuando dices mínimo y máximo,
estamos asumiendo que ya está ordenada?
>> ANDI Peng: Sí, eso es en realidad un condición previa para una búsqueda binaria,
que usted tiene que saber que está ordenada.
¿Cuál es la razón por clase, usted escribe en su problema puesto delante de su búsqueda binaria.
OK.
Así que ahora que sabemos que nuestro punto medio Es decir, ¿qué es lo que quieres hacer aquí?
>> AUDIENCIA: Queremos comparar que a la otra.
ANDI Peng: Exactamente.
Así que vamos a comparar mediados de valor, ¿no?
Y ¿qué dicen nosotros cuando comparamos?
¿Qué es lo que queremos hacer después?
>> AUDIENCIA: Si el valor es mayor de los mediados, queremos cortarlo.
ANDI Peng: Exactamente.
Así que si el valor es mayor de los mediados, estamos
va a querer cambiar estos Maxes mínimo y, ¿verdad?
¿Qué es lo que queremos cambiar?
Así que si conocemos el valor está en algún lugar aquí, lo que debemos hacer para cambiar?
Queremos cambiar nuestra mínima para ser mediados, ¿verdad?
Y luego otra cosa, si es en este medio, ¿qué es lo que queremos cambiar?
>> AUDIENCIA: Su máxima.
ANDI Peng: Sí.
Y luego te vas mantener bucle, ¿verdad?
Porque ahora, después de una iteración a través, tienes un máximo aquí.
Y entonces usted puede volver a calcular una media.
Y entonces usted puede comparar.
Y vas a seguir adelante hasta que los minutos y los Maxes
esencialmente han convergido.
Y eso es cuando se sabe que has llegado a la final de la misma.
Y ya sea que lo hayas encontrado o usted no tiene en ese punto.
>> ¿Tiene esto sentido para todo el mundo?
OK.
Esto es muy importante, ya que tendrá
escribir esto en el código de esta noche.
Pero ustedes tienen una muy buena sentido de lo que debería estar haciendo,
lo cual es bueno.
OK.
Así que tenemos alrededor de siete minuto sección izquierda.
Así que vamos a hablar de este conjunto de procesadores que vamos a hacer.
Así que el conjunto de procesadores se divide en dos mitades.
La primera media implica la implementación de un hallazgo
en el que se escribe una búsqueda lineal, un búsqueda binaria, y un algoritmo de clasificación.
>> Así que esta es la primera tiempo en un conjunto de procesadores, donde
estaremos dándole chicos lo que se llama código de distribución, que es el código
que hemos pre-escrita, pero sólo dejó algunas piezas fuera
para que usted pueda terminar de escribir.
Así que ustedes, si nos fijamos en este código, es posible que se realmente asustado.
Si acaba gusta, ahh, yo no saben lo que está haciendo,
No sé, como, eso parece tan complicado, ahh, relajarse.
Esta bien.
Leer la especificación.
La especificación le explicará exactamente lo que todos estos programas están haciendo.
>> Por ejemplo, es un programa generate.c que vendrá con su conjunto de procesadores.
En realidad no hay que tocarlo, pero usted debe entender lo que está haciendo.
Y generate.c, lo único que está haciendo es ya sea generación de números aleatorios
o puede darle una semilla, como un número preestablecido que se necesita,
y genera más números.
Así que hay una forma específica de aplicar en el que generate.c
usted puede hacer un montón de números para poner a prueba tus otros métodos sucesivamente.
>> Así que si usted quería, por ejemplo, prueba de su hallazgo,
que se quiere ejecutar generate.c, generar un montón de números,
y luego ejecutar su función de ayudantes.
La función de sus ayudantes es donde estás escribir realmente físicamente código.
Y pensar ayudantes como un archivo de biblioteca que está escrito que hallazgo está llamando.
Y así dentro helpers.c, podrás hacer búsqueda y clasificación.
>> Y luego vas a esencialmente sólo hay que poner a todos juntos.
La especificación le dirá cómo puesto que en la línea de comandos.
Y podrás probar si o no es su tipo y de búsqueda están trabajando.
Guay.
Alguien ha comenzado y problemas o dudas planteadas
que tienen ahora con esto?
OK.
>> AUDIENCIA: Espere.
Tengo una pregunta.
>> ANDI Peng: Sí.
>> AUDIENCIA: Así que empecé a hacer la búsqueda lineal en helpers.c
y no fue realmente funciona.
Pero más tarde, me enteré de que sólo que eliminarlo y hacer búsqueda binaria.
Así que qué importa si no funciona?
>> ANDI Peng: Respuesta corta es no.
Pero ya que estamos no--
AUDIENCIA: Pero nadie de realidad de cheques.
ANDI Peng: Nunca estamos va a ver eso.
Pero es probable que desee hacer Asegúrese de que su búsqueda está trabajando.
Porque si su lineal búsqueda no funciona,
entonces es probable que su binario búsqueda no va a funcionar tan bien.
Debido a que tiene similares lógica en ambos.
Y no, no importa.
Así que los únicos que convertirán en son de clasificación y búsqueda binaria.
Sí.
>> Y también, una gran cantidad de niños estaban intentar compilar helpers.c.
Usted no está realmente permitido para hacer eso, porque helpers.c
no tiene una función principal.
Y por lo que sólo debe ser en realidad la compilación
generar y encontrar, porque encontrar llamadas helpers.c y las funciones que la integran.
Así que hace la depuración un dolor en el trasero.
Pero eso es lo que tenemos que hacer.
AUDIENCIA: Usted acaba de hacer de todo, ¿no?
ANDI Peng: Usted puede simplemente hacer todo así, sí.
OK.
Así que es eso en términos de lo el conjunto de procesadores está pidiendo a todos a hacer.
Si usted tiene alguna pregunta, libre de preguntarme después de la sección.
Voy a estar aquí por como 20 minutos.
>> Y sí, de el juego de parámetros no está tan mal.
Ustedes deberían estar bien.
Estos, sólo tienes que seguir las directrices.
Clase de tener un sentido de, lógicamente, lo que debería estar sucediendo y se le multa.
No sea demasiado asustada.
Hay una gran cantidad de código ya escrito allí.
No sea demasiado asustado si no lo hace entender lo que todo eso significa.
Si es mucho, es totalmente bien.
Y llegado a las horas de oficina.
Nosotros le ayudaremos a echar un vistazo.
>> AUDIENCIA: Con el extra funciones, qué buscamos los de arriba?
>> ANDI Peng: Sí, esas son en el código.
En el juego de 15, la mitad de ya está escrito para usted.
Así que esas funciones están Ya en el código.
Sí.
Correcto.
Bueno, mejor de las suertes.
Es un día asqueroso.
Así que espero que ustedes no se sienten demasiado mal por permanecer dentro y codificación.