Antes de abordar los problemas, mira las conferencias 7-8 , lee y profundiza en los “ Materiales adicionales de la tercera semana ”. Están dedicados a algoritmos de búsqueda (lineales y binarios), clasificación (¡hay muchos!), así como al trabajo de un depurador (¡la capacidad de trabajar con un depurador para depurar programas es una habilidad extremadamente importante!). Si todo salió como debería con las clases magistrales y la teoría, podrás responder fácilmente a las preguntas del examen:
¿Por qué la búsqueda binaria requiere una matriz ordenada?
¿Por qué se estima que el tipo de burbuja es O (n2)?
¿Por qué la estimación del tipo de inserción es Ω (n)?
¿Cómo funciona la clasificación por selección? Describe en tres oraciones (o menos).
¿Cuál es el límite superior (peor de los casos) sobre cuánto tiempo puede ejecutarse la ordenación por fusión?
El depurador GDB le permite depurar un programa. Y si formulas más específicamente, ¿qué te permite hacer exactamente?
Objetivos
Aprenda a trabajar con proyectos que contienen varios archivos
Aprenda a leer el código fuente de otra persona
Comprender varios algoritmos y funciones recursivas.
La mayoría de estos objetivos son prácticamente imposibles de evaluar formalmente. Por tanto, desde el punto de vista de la verificación formal de problemas, hay pocas cosas que le parezcan difíciles. Sin embargo, te recordamos: ¡solo puedes aprender a programar a través de la práctica constante! Por lo tanto, lo alentamos no solo a resolver las tareas, sino también a dedicar tiempo y esfuerzo adicionales e implementar todos los algoritmos que se discutieron esta semana. ¡Adelante!
Comenzar
Recuerde que para los problemas de práctica de las semanas uno y dos, escribió programas desde cero y creó sus propios directorios pset1 y pset2 usando el comando mkdir . Para la tarea de práctica de la tercera semana, debe descargar la distribución (o "distro", como la llamamos) que escribimos y agregarle sus propias líneas de código. Primero, lea nuestro código e intente comprenderlo. La habilidad más importante esta semana es aprender a leer el código de otras personas. Entonces, inicie sesión en cs50.io y ejecute el comando update50 en una ventana de terminal para asegurarse de que la versión del espacio de trabajo esté actualizada. Si accidentalmente cerró la ventana de la terminal y no puede encontrarla, vaya al menú Ver y asegúrese de que la opción Consola esté marcada (márquela si no lo está). Haga clic en (+), dentro del círculo verde en el marco de la ventana de la terminal, seleccione Nueva Terminal . Después de eso, ejecute el comando cd ~/workspace y asegúrese de estar dentro del directorio del espacio de trabajo (este es su directorio). Después de eso, ejecute el comando: wget http://cdn.cs50.net/2015/fall/psets/3/pset3/pset3.zip para descargar el archivo ZIP del libro de problemas en su espacio de trabajo (wget es el comando de descarga de Linux). Si todo está bien, verá la siguiente frase en la línea: 'pset3.zip' saved Asegúrese de haber descargado realmente pset3.zip ejecutando el comando: ls y luego ejecute unzip pset3.zip para descomprimir el archivo. Si ahora ejecuta el comando ls nuevamente , también verá el directorio pset3 . Vaya a él ejecutando el comando cd pset3 y luego solicite ver el contenido del directorio nuevamente: ls verá que hay dos subdirectorios en este directorio: ¡ fifteen find Ya es intrigante!
Buscar
Profundicemos ahora en uno de estos subdirectorios. Para hacer esto, ejecutaremos el comando: cd ~/workspace/pset3/find Si muestra el contenido de esta carpeta en la pantalla (probablemente ya recuerde cómo hacerlo), esto es lo que debería ver: helpers.c helpers.h Makefile find.c generate.c Vaya, hay muchos archivos. Pero no te preocupes, nos ocuparemos de ellos ahora. El archivo generate.c contiene código para un programa que utiliza un "generador de números pseudoaleatorios" (generado por la función drand48 ) para generar una gran cantidad de números aleatorios (en realidad, pseudoaleatorios, ¡las computadoras no pueden manejar la aleatoriedad pura!) y colóquelos uno a la vez en línea. Compile el programa: make generate Ahora ejecútelo ejecutando el comando: ./generate El programa le dará el siguiente mensaje: Usage: generate n [s] Esto significa que el programa espera uno o dos argumentos de la línea de comando. Usando el primero, n, es obligatorio; este número significa cuántos números pseudoaleatorios desea crear. El parámetro s es opcional, como lo indican los corchetes. El número s puede denominarse "semilla" para el generador de números pseudoaleatorios. Por "semilla" nos referimos a los datos de entrada al generador de números pseudoaleatorios que afectan su salida. Por ejemplo, si está utilizando drand48, primero llamando a srand48 (otra función cuyo propósito es "sembrar" drand48) con un argumento de, digamos, 1, y luego, llamando a drand48 tres veces, drand48 podría devolver 2728, luego 29785, luego 54710. Si en lugar del anterior, usando drand48, primero llama a srand48 con un argumento de, digamos, 2, y luego usa drand48 nuevamente tres veces, drand48 podría devuelve 59797, luego 10425, luego 37569. Pero si vuelves a ver drand48 llamando a srand48 nuevamente con un argumento de 1, el resultado de las siguientes tres llamadas a drand48 obtendrás 2728 nuevamente, luego 29785, luego 54710. Verás, todo sucede por una razón. Ejecute el programa nuevamente, esta vez, digamos n=10, como se muestra a continuación; Verá una lista de 10 números pseudoaleatorios. ./generate 10 Ejecutemos el programa por tercera vez con el mismo valor de n; Deberías ver otra lista de 10 números. Ahora intente ejecutar el programa con dos parámetros. Tomemos s=0 como se muestra a continuación. ./generate 10 0 Ahora ejecute el mismo comando nuevamente: ./generate 10 0 ni siquiera puede discutir: volvió a ver la misma secuencia "aleatoria" de diez dígitos. Esto es lo que sucede si no cambia las semillas del generador de números pseudoaleatorios. Ahora veamos el programa generate.c en sí.(¿recuerdas cómo?). Los comentarios al principio de este archivo explican la funcionalidad general del programa. Pero parece que nos hemos olvidado de comentar sobre el código en sí. Lea el código con atención y léalo hasta que comprenda el significado de cada línea. Luego comente este código por nosotros, reemplazando cada TODO con una frase que describa el propósito o la funcionalidad de la línea o líneas de código correspondientes. (nota: unsigned int es un int "sin firmar", lo que significa que no puede ser negativo). Para obtener más información sobre rand o srand, ejecute: man drand48 o man srand48 Después de haber comentado todo lo que pueda en generate.c, vuelva a compilar el programa para asegurarse de que no haya roto nada: make generate Si generate ya no se compila, arregle lo que en bancarrota: )! Como recordatorio, el comando make automatiza la compilación del código, por lo que no es necesario ejecutar el comando clang insertando manualmente un montón de modificadores. Pero, de hecho, make simplemente simplifica nuestra entrada, pero de hecho, detrás de él se esconde el mismo sonido metálico con los parámetros que necesitamos. Sin embargo, a medida que sus programas crecen, make ya no puede descifrar a partir del contexto cómo compilar el código. En este caso, tendrás que decirle a make cómo compilar los programas, especialmente si implican el uso de diferentes archivos fuente (como .c). Para resolver este problema usaremos archivos de configuración (Makefiles) que le indican a make exactamente qué hacer. ¿Cómo supo el comando make cómo debemos compilar y generar? De hecho, el equipo utilizó un archivo de configuración que ya habíamos escrito. Este archivo se llama Makefile y se encuentra en el mismo directorio que generate.c . Makefile es una lista de reglas que especifican cómo crear el archivo generado desde generate.c. En el archivo encontrará, en particular, las líneas relevantes: generate: generate.c clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c La primera línea le dice a make que se debe crear un "objetivo" llamado generar llamando al comando desde la segunda línea. Además, la primera línea le dice a make que generate depende de generate.c, lo que significa que make solo reconstruirá generate en ejecuciones posteriores si ese archivo ha sido modificado. No es un mal truco para ahorrar tiempo, ¿verdad? De hecho, ejecute el siguiente comando nuevamente si no cambió generate.c . make generate Se le informará que generate ya se actualizó a la versión actual. Nota : La sangría al principio de la segunda línea no es una secuencia de espacios, sino un carácter de tabulación. Desafortunadamente, make requiere que los comandos vayan precedidos de tabulaciones, así que tenga cuidado de no cambiarlos a espacios o se encontrará con errores extraños. El indicador -Werror le indica al comando clangTrate las advertencias (malas) como errores (aún peores), por lo que se verá obligado (¡de una manera buena y educativa!) a corregirlas. Ahora veamos el archivo find.c. Tenga en cuenta que este programa espera un argumento de línea de comando: "iglú", que debe encontrarse en un "pajar" de valores. Después de eso, revise el código y compile el programa ejecutando el siguiente comando. make find make básicamente nos dio lo siguiente: ¡ clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Presta atención! Acaba de compilar una aplicación que consta de uno, dos archivos : helpers.c y find.c. ¿Cómo se enteró de esto? Para comprender esto, abra nuevamente el Makefile para ver qué está sucediendo realmente allí. Las líneas relevantes se encuentran a continuación. find: find.c helpers.c helpers.h clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm Lo que queremos decir con dependencia (después de los dos puntos) es que cualquier cambio en find.c , helpers.c o helpers.h obligará a make a reconstruir find la próxima vez que se llame para esos fines. Ahora ejecute este programa haciendo, por ejemplo, lo siguiente: ./find 13 Después de esto, se le pedirá que proporcione una pila determinada (es decir, números enteros) y alimente una pajita a la vez. Una vez que te canses de escribir números, presiona la combinación de teclas Ctrl-D . Esta combinación enviará al programa un carácter de fin de archivo (EOF). El símbolo obligará a la función GetInt de la biblioteca CS50 a devolver la constante INT_MAX y esto, a su vez, en find.c obligará a find a dejar de escribir "stack". El programa ahora buscará la aguja en el pajar que le proporcionó y eventualmente le dirá si la encontró. En resumen, el programa busca algún valor en una matriz. Al menos debería hacerlo, ¡pero el problema es que todavía no encontrará nada! ¡Pero aquí vienes al rescate! Hablaremos de la importancia de su papel un poco más adelante. De hecho, el proceso de proporcionar un pajar se puede automatizar, al menos "fusionando" la salida de generar con la de buscar como entrada. Por ejemplo, el siguiente comando pasa 1000 números pseudoaleatorios para buscar, que luego busca 42 entre esos valores. ./generate 1000 | ./find 42 Tenga en cuenta que cuando generar pasa los datos sin procesar para buscar, no verá el número de generación, pero verá buscar ejecutándose. . Alternativamente, puede "redirigir" la salida de generate a un archivo con un comando como este: ./generate 1000 > numbers.txt El contenido de este archivo se puede redirigir a la entrada de find con el comando: ./find 42 < numbers.txt Echemos otro vistazo al código en Makefile y observemos el siguiente línea: all: find generate Esto significa que puede generar, generar y buscar ejecutando el siguiente comando: make all Además, el comando debajo de esta línea es equivalente al comando que se encuentra arriba, ya que make genera la primera entrada en el Makefile de forma predeterminada. make ¡Si tan solo pudieras reducir todas estas tareas de práctica a un solo comando! ¡Pero Ay! Finalmente, preste atención a estas últimas líneas en el Makefile: clean: rm -f *.o a.out core find generate Esta entrada le permite eliminar todos los archivos que terminan en .o o se llaman core (¡lo explicaremos en un momento!), y también ejecutar programas de búsqueda o generación simplemente ejecutando la línea: Si desea make clean experimentar, entonces aquí hay algo con lo que debe tener cuidado: ¡no agregue, digamos, *.c a la última línea del Makefile! (¿por qué?) Todas las líneas que comienzan con el signo # son solo comentarios.
Tarea 1: Buscar
¡Es hora de algo interesante! Tenga en cuenta que find.c llama a search , una función declarada en helpers.h . Desafortunadamente, nos olvidamos de implementar esta función por completo en helpers.c . (Cabe señalar que podríamos colocar el contenido de helpers.h y helpers.c en un solo find.c. Pero a veces es mejor separar los programas en varios archivos. Especialmente si algunas funciones, o más bien funciones de utilidad, pueden ser útiles para otros programas. Como las funciones de la biblioteca CS50, por ejemplo. Eche un vistazo a helpers.c y verá que la búsqueda siempre devuelve falso, independientemente de si el valor dado está en valores. Reescriba la búsqueda para que utilice la búsqueda lineal y devuelva verdadero. , si el valor está en valores y falso si el valor no está en valores. Tenga cuidado de devolver falso inmediatamente si n no es positivo. Cuando esté listo para verificar la validez, intente llamar al siguiente comando: Dado que uno de los números ./generate 1000 50 | ./find 127 impresos con generate cuando se sembró 50 es 127, su código debería encontrar la aguja. Por el contrario, pruebe este comando: ./generate 1000 50 | ./find 128 Dado que 128 no está entre el conjunto de números generados por generate cuando se sembró 50, su código no debe encontrar la "aguja". . Ejecute otras pruebas ejecutando generate con algo de semilla, analizando el resultado y buscando la aguja que debería estar en el pajar. Tenga en cuenta que main en find.c está escrito de tal manera que find devuelve 0 si se encuentra la "aguja", de lo contrario devuelve 1. Puede verificar el llamado "código de salida" que main devuelve cuando se ejecuta después de ejecutar algún otro comandos echo $? . Por ejemplo, si su implementación de búsqueda es correcta, si ejecuta ./generate 1000 50 | ./find 127 echo $? verá 0, mientras que 127 está entre los 1000 números generados por generar con una semilla de 50, por lo que la búsqueda que escribió debería devolver verdadero. En este caso, main (escrito por nosotros) debería devolver 0 (es decir, salir). Si proporciona la siguiente entrada ./generate 1000 50 | ./find 128 echo $? , verá 1 porque 128 no está entre los 1000 números generados por generar con una semilla de 50. En este caso, la búsqueda (escrita por usted) devolverá falso y principal (escrito por nosotros). ) devolverá 1 (y luego terminará el trabajo). ¿Entiendes la lógica? Cuando todo esté listo para ser verificado usando check50, ejecute el siguiente comando: check50 2015.fall.pset3.find helpers.c Por cierto, no deberías acostumbrarte a probar tu código usando check50 antes de probarlo tú mismo. Después de todo, check50 realmente no existe, por lo que ejecutar el código con sus propias muestras de entrada, comparando el resultado real con el resultado esperado, es el mejor hábito que puede adoptar en este momento. Es verdad, ¡no te vuelvas adicto! Si está interesado en jugar con la implementación de búsqueda de los asistentes cs50, ejecute este comando: ~cs50/pset3/find
Clasificación
La búsqueda lineal no es algo realmente impresionante, pero desde las primeras lecciones (¡y en la séptima repetimos este truco nuevamente!) recuerdas que puedes encontrar una aguja en un pajar mucho más rápido. Pero primero tenemos que ordenar nuestro pajar. Tenga en cuenta que find.c llama a sort , una función declarada en helpers.h . Desafortunadamente, ¡nos “olvidamos” de implementar completamente esta función en helpers.c ! Mire helpers.c y verá que la ordenación regresa instantáneamente, aunque la función principal de búsqueda en realidad le pasa la matriz real. Ahora recuerde la sintaxis de declaración de matriz. No solo especifica el tipo de elemento de esta matriz, sino que también especifica su tamaño entre corchetes. Esto es lo que hacemos para el pajar en find.c : int haystack [MAX]; pero al atravesar una matriz, solo especifica su nombre. Y lo hacemos exactamente de la misma manera cuando revisamos el pajar para ordenar en find.c : sort (haystack, size); (¿Adivina por qué pasamos el tamaño de esa matriz por separado?) Cuando declaramos una función que toma una matriz unidimensional como argumento, No necesitamos especificar el tamaño de la matriz. Del mismo modo, no hicimos esto cuando declaramos sort en helpers.h (y helpers.c): void sort (int values [] int n); implemente sort para que la función realmente ordene la matriz de números de pequeño a grande. Necesita un tiempo de ejecución igual a O(n 2 ), donde n es el tamaño de la matriz. Es probable que desee implementar la clasificación por burbujas, la clasificación por selección o la clasificación por inserción, como aprendimos sobre ellas en la tercera semana. Sin embargo, es importante tener en cuenta: no existe una forma "correcta" de implementar estos algoritmos. Hay una gran cantidad de variaciones. De hecho, siempre puedes mejorarlos si lo crees conveniente, siempre y cuando tu implementación converja a O(n2 ) . Sin embargo, deje la experimentación al cuerpo de la función y, para simplificar las pruebas, no cambie nuestra declaración de clasificación. Debería verse así: void sort (int values [] int n); dado que la función devuelve un valor nulo, no debería devolver una matriz ordenada. En lugar de ello, debe ordenar "destructivamente" la matriz real que está "ejecutando", moviendo sus elementos. En la cuarta semana discutiremos que las matrices se pasan por referencia en lugar de por valor. Es decir, sort no recibirá copias de la matriz, sino la propia matriz original. Si bien no puede cambiar nuestra declaración de clasificación, siempre puede definir su propia función en helpers.c, a la que luego se puede llamar desde sort. Decida usted mismo cuál es la mejor manera de probar su implementación de clasificación. ¡No olvides que printf y GDB te ayudarán! Y no olvide que puede crear la misma secuencia de números pseudoaleatorios una y otra vez especificando explícitamente los valores iniciales para generar.
Búsqueda binaria, consejos
Lo primero que debes entender sobre la función de búsqueda es que ya tenemos código escrito (distribución). Simplemente estamos llenando algunos vacíos en el código existente. El programa find.c solicita la entrada de números (es decir, para llenar una "pila") y luego busca una "aguja" en ella a petición del usuario, utilizando las funciones de clasificación y búsqueda definidas en helpers.c . Entonces, buscar ya está escrito, necesitamos escribir ayudantes . Así que esto es lo que debemos hacer:
Implementar la búsqueda. Esta función debería devolver verdadero si el valor se encuentra en la pila y falso si no está allí.
Implemente sort, una función que ordena una matriz de valores.
Inicialmente la búsqueda se implementó de forma lineal. Pero puedes hacerlo mejor. El algoritmo de búsqueda lineal se ejecuta en tiempo O(n) . Tu tarea es escribir un algoritmo de búsqueda binaria. Su tiempo de ejecución es O(log n) . Sin embargo, su problema es que necesita datos ordenados como entrada; de lo contrario, no funcionará. Recuerdas el ejemplo del libro roto y probablemente sepas por qué es así. Si ha realizado una búsqueda binaria a través de los elementos y no quedan más (es decir, simplemente no hay una "aguja" en esta "pila"), necesita que la función devuelva falso. La búsqueda binaria se puede implementar de forma iterativa o recursiva (David Malan habló sobre la recursividad en la octava conferencia).
Después de eso, ejecute el comando 
GO TO FULL VERSION