Resolver un problema algorítmico

> Borradores

Borrador en proceso por ''Hazurl''

Este artículo le dará los conceptos básicos para lograr todo tipo de problemas algorítmicos. Está dirigido principalmente a principiantes que no saben cómo empezar, pero no solo. La primera parte explicará los diferentes métodos de resolución, es decir la teoría. Entonces tomaría por ejemplo el algoritmo de los cuadrados accesibles para concretar estos métodos. Elegí este algoritmo porque es uno de los algoritmos más útiles y porque la página que lo trata no es adecuada para principiantes; es más desde una perspectiva de optimización. Ya que estoy hablando de eso, la optimización no será parte de este artículo, ya hay algunos sobre este tema.

Teóricamente

En términos generales, un problema algorítmico es una pregunta que puede ser resuelta por una computadora. Distinguimos dos de ellos:

Problema de decisión: la respuesta es binaria, sí o no, podemos citar por ejemplo canUseWeapon o isObstacle, podemos notar que estas funciones muchas veces tienen "is" o "can" al principio de su name, esto permite leer, para saber de inmediato que la respuesta de la función será un booleano, le recomiendo encarecidamente que haga lo mismo con sus funciones.
Problema de evaluación: consiste en la creación de un objeto planteado por el problema, por ejemplo getCellsToUseWeapon que devuelve una estructura: un array

No es realmente para recordar, sino más bien para su conocimiento general.

Comprender la declaración

Nada más obvio, pero un paso que mucha gente olvida. Y no solo principiantes. Es necesario entender bien el tema y no dudar en volver a leerlo para que no quede vago. Imagínate explicándole el tema a alguien que nunca lo ha leído. Tienes que saber reformularlo en tu cabeza, sin hacer generalizaciones ni especificaciones, de lo contrario empezarás con mal pie. No empieces a pensar en resolver el programa. Es necesario explicar los datos de entrada y salida, cómo se construye, etc... Si el problema no tiene ninguna restricción en la salida, imagine cómo se manipulará para simplificar su uso. Tienes que saber responder (¡perfectamente!) a estas dos preguntas:

¿Qué tengo para empezar?
¿Qué debo conseguir?

Resolver ejemplos

La mejor manera de encontrar una implementación del algoritmo es resolverlo usted mismo. Los ejemplos a resolver no se encuentran por pura casualidad. Debemos tomar diferentes casos y límites. Tienes que averiguar cuándo la resolución es complicada, y luego crear los ejemplos al extremo. Entonces es necesario preparar un soporte para probar el algoritmo. Una simple prueba de igualdad en la buena salida puede hacer el trabajo, de lo contrario, puede convertirlo en una pantalla simple para verificarlo a mano.

Búsqueda de algoritmos

Aquí está el paso más concreto. Necesitas convertir tu problema en una solución. Lo mejor es proceder en pasos cada vez más precisos a partir de su problema inicial, además podemos ver que este proceso es un algoritmo en sí mismo 😉. Tienes que dividir el problema en subproblemas mientras revelas las estructuras de control: bucles, estructuras condicionales... Busca redefinir todos tus problemas en cada etapa. Nada mejor que un ejemplo para ilustrar este concepto: Ordenar una matriz. Tenemos una matriz en la entrada y, a cambio, una matriz ordenada (por ejemplo, en orden ascendente). ¿Cómo ordenar una matriz? hay que modificarlo obviamente, pero no es suficiente, hay que modificarlo hasta que se ordene. Vaya ! Pero... ¿no sería eso un bucle? Entonces, nuestra primera división mencionó una hebilla, así como su cuerpo y su condición. Pero modificar la matriz no es muy preciso... También debe tener en cuenta que el bucle es potencialmente igual al bucle infinito. Tenga mucho cuidado de que la condición se evalúe de manera diferente en algún momento para salir del bucle. Por lo tanto, la modificación de la matriz debería ordenarla más antes que después del ciclo, de modo que la matriz se ordene en algún punto y el ciclo finalice. Hay muchas formas de ordenar una matriz, una de las más simples es invertir el elemento más pequeño con el primer elemento y luego hacer lo mismo con el segundo elemento, es decir, de manera más general, para cada elemento de la matriz en la posición i invertirlo con el elemento más pequeño a su izquierda. Aquí hay una representación de dónde estamos:

function sort_array (tab) // tab es la variable de la matriz que se va a ordenar Mientras que is_not_sort(pestaña) Para i que va de 0 a n - 1 // n es el tamaño de la matriz pos_elem_min = pos_elem_min_droite(tab, i) // posición del elemento de matriz más pequeño a la derecha de i invert(tab, i, pos_elem_min) // Invertimos los dos elementos Terminar por Bronceado final