Harvard CS50: Asignaciones de la semana 3 (Conferencias 7 y 8), Parte 2

Conferencias sobre fundamentos de programación de Harvard CS50 Materiales adicionales: notación asintótica, algoritmos de clasificación y búsqueda Tareas de la semana 3, parte 1. Clasificación y búsqueda.

¡Comienza el juego!

¡Es hora de jugar! La mayoría de la gente está familiarizada con el juego de rompecabezas "Tag". Para formalizarlo, “Etiqueta” es un campo bidimensional de 4x4, en este campo no hay 16, sino 15 cuadrados, es decir, un espacio queda vacío. Cada uno de los cuadrados está numerado y puede moverse horizontal o verticalmente dentro del campo (si, por supuesto, hay espacio para moverse). El objetivo es colocar los números en orden, del 1 al 15, de izquierda a derecha, de arriba a abajo. Entonces el espacio vacío estará en la esquina inferior derecha. El movimiento de cualquier ficha (o varias) es un “paso” en este espacio de juego. La combinación que se muestra en la imagen de arriba ya está apilada, pero tenga en cuenta que se pueden colocar 12 o 15 fichas en el espacio vacío. Las reglas establecen que una ficha no se puede mover en diagonal ni eliminar del tablero de juego. En realidad, hay muchas configuraciones para comenzar el juego (puedes contar cuántas exactamente), pero en aras de la simplicidad, organicemos las fichas en orden de mayor a menor y dejemos un espacio vacío en la esquina inferior derecha del tablero. . Lo único es que intercambiemos 1 y 2 para que el rompecabezas se pueda resolver. Ahora vaya al directorio ~/ de su banco de trabajo , luego a /pset3/fifteen y abra quince.c . Contiene el código para el motor del juego. La tarea es agregar código al juego. Pero primero, vamos a compilar nuestro “motor” (probablemente ya sepas cómo hacerlo). A pesar de que el juego no está terminado, puedes iniciar la aplicación. Será más conveniente ejecutarlo en una ventana de terminal más grande de lo habitual, que se puede abrir haciendo clic en el signo más (+) verde al lado de una de las pestañas de código y seleccionando Nueva Terminal . O puede abrir la ventana de la terminal en pantalla completa haciendo clic en el ícono Maximizar en la esquina superior derecha de la consola. Ves que algunas cosas funcionan de alguna manera. Pero, de hecho, la mayor parte del juego aún no se ha escrito. Y aquí, prepárate, ¡está tu salida!

Estudiar

Estudie el código y los comentarios de quince.c y luego responda las siguientes preguntas:

1. Aparte de una tabla 4x4, ¿qué tamaño de campo permite nuestro motor?
2. ¿Qué estructura de datos es el campo de juego?
3. ¿A qué función se llama para saludar al jugador al inicio del juego?
4. ¿Qué características necesitas implementar?
5. Nota: Si desea que la verificación automática le indique si respondió las preguntas correctamente, junto al archivo quince.c, busque el archivo quince.txt y escriba las respuestas a estas preguntas en él.

Implementación

Bueno, comencemos a implementar el juego. Recuerde, avanzamos en pequeños pasos, no intente hacer todo a la vez. En su lugar, implementemos funciones una a la vez y asegurémonos de que funcionen antes de seguir adelante. En particular, le sugerimos que implemente las funciones del juego en el siguiente orden: init (inicialización), draw (dibujar), move (dar un paso), won (ganar). Las decisiones de diseño (como cuánto espacio insertar entre nuestros mosaicos numéricos) son suyas. El campo de juego debería verse así: 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 _ Una vez más, tenga en cuenta que en la posición inicial, 1 y 2 están ubicados en orden inverso (esto se aplica al clásico campo 4x4 si el número de fichas es impar). Si el número de fichas es par y el campo es de 3x3, no es necesario intercambiar las dos fichas "más bajas". 8 7 6 5 4 3 2 1 _ Para probar su implementación de "Etiquetas", debe intentar reproducirlos (no olvide que puede salir del programa antes de que finalice naturalmente presionando la combinación de teclas crtl+c). Asegúrese de que el programa funcione si se ingresan números incorrectos. Y recuerda que así como automatizaste la entrada en Find, puedes automatizar el “recorrido” del juego. De hecho, en la carpeta ~cs50/pset3 hay archivos 3x3.txt y 4x4.txt , que contienen todas las secuencias de pasos para ganar en los campos 3x3 y 4x4. Para probar el programa, por ejemplo, usando el primero de los archivos, ejecute el siguiente comando: ./fifteen 3 < ~cs50/pset3/3x3.txt Configure el argumento que necesita para acelerar la animación. Y en general, si quieres, siempre puedes cambiar de juego. Para divertirse con las "secuencias de escape ANSI", incluido el color. Eche un vistazo a nuestra implementación de clear y visite http://isthe.com/chongo/tech/comp/ansi_escapes.html para aprender nuevos trucos. Si lo desea, escriba sus propias funciones o cambie los prototipos de las funciones que escribimos. La única limitación es que no cambias la lógica de la función principal, de lo contrario no podremos aplicarle algunas pruebas automáticas para confirmar que tu programa está funcionando correctamente. En particular, main debe devolver 0 si y sólo si el usuario resolvió el rompecabezas. Se deben devolver valores distintos de cero para todas las opciones de error. Si ocurre algún error, escríbanos. Bueno, si quieres jugar con la implementación de la aplicación preparada por los asistentes de CS50, ejecuta el siguiente comando: ~cs50/pset3/fifteen Si estás interesado en ver una implementación más interesante, con resolución automática de acertijos, consulta la versión “Hacker” del programa: ~cs50/hacker3/fifteen En lugar de ingresar un número en la ventana del juego, escribe la palabra DIOS. Genial, ¿no? Si desea verificar oficialmente la corrección de su programa con check50, tenga en cuenta que check50 supone que el espacio vacío del campo de juego se llena con 0; si eligió un valor diferente, reemplácelo con cero para una verificación correcta. Además, check50 supone que está indexando los campos del tablero en el orden [fila] [columna], no en el tablero [columna] [fila]. check50 2015.fall.pset3.fifteen fifteen.c

Obtenga más información sobre la implementación de las funciones del juego Quince

• init (inicialización)
• dibujar
• moverse (dar un paso)
• ganó (ganó)

en eso

En esta función introducimos el campo de juego. Para hacer esto, utilizamos una matriz bidimensional de números enteros. La dimensión de la matriz es MAX x MAX, donde MAX es una constante que indica el número máximo de mosaicos que pueden caber en una fila o columna de un campo. Por lo tanto, necesitamos definir la variable int board[MAX][MAX] Sin embargo, recuerde que el tamaño del campo de juego lo determina el usuario. Por lo tanto, necesitamos definir una variable que indique el tamaño del tablero que debe ingresar el usuario. Esto es int d . donde d es la dimensión del tablero, d <= MAX. Sin embargo, en C no se puede cambiar el tamaño de una matriz, por lo que hay que conformarse con el tamaño máximo. En init necesitas poner los valores en el tablero. Lea más sobre matrices bidimensionales si aún no ha trabajado con ellas. En resumen, tienen dos índices, el primero indica el número de fila y el segundo el número de columna. Para nuestro problema, comenzamos con el número máximo y terminamos en el caso de d = 3 (“Ochos”) con uno y una esquina vacía. Si todavía tenemos "Etiqueta", intercambiamos 1 y 2. ¿Qué hacer con el espacio vacío? Nuestra matriz consta de números enteros, por lo que el vacío debe llenarse con algún número entero. Por lo tanto, debes elegir algún número entero para inicializar la ficha vacía (o, en el caso de un juego físico, la ausencia de una ficha). Se pueden utilizar bucles para inicializar el tablero de juego y llenarlo con un conjunto inicial de fichas. Recorremos los índices i y j, donde tablero[i][j] es un mosaico que se encuentra en la fila número i y la columna número j. Rellenamos el tablero en orden descendente. Si el número de fichas (sin las vacías) es impar, intercambia 1 y 2.

dibujar

Esta función debería imprimir el estado actual del campo de juego. Recuerde que podemos tener valores con uno o dos dígitos, por lo que para un formato atractivo después de los números del 1 al 9, la función debe imprimir un espacio ( #s ). Esto se puede hacer usando el marcador de posición %2d . printf (“%2d”, board[i][j]); Tampoco te olvides de la celda vacía. Seleccione el carácter que lo representará (en nuestro ejemplo, es un guión bajo). La función de dibujo debería dibujar este personaje tan pronto como llegues a una celda vacía. Entonces nuestro bucle sería algo como esto: for каждой строки for каждого elemento строки print significado и пробел print новую строку Recuerde que el orden en el que la función dibujar dibuja los mosaicos en la pantalla debe reflejar el orden en el que están en la matriz definida en la función init .

mover

Una vez que haya inicializado el campo de juego y dibujado las posiciones iniciales de las fichas, debe permitir al usuario editar la posición de las fichas, es decir, realizar movimientos. Entonces, en Fifteen.c, el programa toma la salida del usuario, construye el tablero de juego y luego llama a la función de movimiento y le dice qué ficha quiere mover. Tenga cuidado: está aplicando la función específicamente al número en la ficha y no a su posición en el tablero (en la matriz). Entonces necesitas encontrar la posición real del mosaico. Además, solo debes permitir que el usuario mueva el mosaico cuando sea posible. En la imagen de arriba, solo podemos mover las fichas número 2, 5 y 8. ¿Cómo determinar esto? Por el valor de una ficha vacía. Entonces la función de movimiento funciona de esta manera:

• Acepta el número de mosaico que el usuario desea mover.
• Busca la posición en la matriz (en el campo de juego) de este mosaico
• Recuerda la posición de un mosaico vacío.
• Si un mosaico vacío está adyacente a uno que el usuario desea mover, se intercambian en la matriz.

ganado

Esta función comprueba si el juego ha finalizado después de cada paso del usuario. Devuelve verdadero si los mosaicos están en el orden correcto (incluida la posición del mosaico vacío en la esquina inferior derecha). En este caso, se puede cancelar el programa. Si las fichas aún están dispersas, la función devuelve falso y pasa las riendas a la función mover . ¿Cómo organizar una inspección? Como en el caso de inicializar y dibujar el tablero, utilizando dos bucles for anidados. Por ejemplo, puede establecer la condición de que cada número posterior en la matriz debe ser mayor que el anterior. Observe qué valor está escrito en el mosaico vacío. O de otra manera: usa un contador para asegurarte de que todos los mosaicos estén en su lugar, si puedes manejarlo, y escribe la fórmula para obtenerlo. ¡Le deseamos mucha suerte en sus experimentos!

Cómo validar tu código y obtener notas

¡Atención! Si es importante para usted verificar solo la corrección de las tareas, utilice cs50check. Si desea obtener calificaciones en la plataforma edx, siga el procedimiento que se describe a continuación. Tenga en cuenta que este procedimiento utiliza el mismo cs50check para verificar las tareas. La única diferencia es que recuerda los resultados y calcula la puntuación global.

1. Inicie sesión en CS50 IDE
2. Cerca de la esquina superior izquierda del IDE de CS50 , donde se encuentra su explorador de archivos (no en la ventana del terminal), haga clic derecho en su directorio pset3 y haga clic en Descargar . Deberías ver que el navegador ha descargado el archivo pset3.tar.gz .
3. En una ventana o pestaña separada, inicie sesión en CS50.
4. Haga clic en el icono Enviar en la esquina superior izquierda de la pantalla.
5. En la lista de carpetas de la izquierda, haga clic en el directorio Conjunto de problemas 3 y luego haga clic en el botón Cargar nuevo envío. Está a la derecha.
6. En la pantalla que aparece, haga clic en el botón Agregar archivos .... Se abrirá una ventana para seleccionar archivos de su computadora.
7. Navegue hasta la carpeta donde guardó pset3.tar.gz. Lo más probable es que esté ubicado en su carpeta de Descargas o donde su navegador coloque los archivos de forma predeterminada. Cuando encuentre pset3.tar.gz , haga clic en él una vez para seleccionarlo y luego haga clic en Abrir .
8. Haz clic en Iniciar carga . Sus archivos se cargarán en los servidores CS50 .
9. En la pantalla que aparece, debería ver la ventana No hay ningún archivo seleccionado . Si mueve el cursor del mouse hacia la izquierda, verá una lista de archivos descargados. Para confirmar, haga clic en cada uno de ellos. Si no estás seguro de algo, puedes volver a cargar los archivos repitiendo los mismos pasos. Puedes hacer esto tantas veces como quieras hasta finales de 2016.