|
COMO GENERAR / CONSTRUIR ALGORITMOS MEDIANTE REFINAMIENTOS SUCESIVOS |
William Díaz Sepúlveda.
Resumen: Uno de los pasos que se deben realizar para iniciar el proceso de codificación de alguna operación que se debe escribir en código de un lenguaje de programación, si el algoritmo o método de solución no es fácil o no se tiene alguna idea de cómo realizar las operaciones lo primero es que debe tener una idea para el algoritmo que desea generar y obviamente construirlo en forma detallada para hacer la codificación. Este articulo les ensena una forma de lograrlo.
Palabras Claves: Algoritmos, programación, Generación de algoritmos, refinamientos sucesivos, construcción de algoritmos, requerimiento, Entrada-proceso-salida.
1 . Introducción
Hacer programas no es lo mismo que solucionar problemas ya que para solucionar un problema es necesario mucho más análisis y se requiere de una idea y un método que permita lograr el resultado final que se espera obtener Por ello es necesario, cuando no se sabe cómo hacer cada instrucción y tener claro todo el procedimiento, que se inicia el proceso para ir construyendo paso a paso el algoritmo.
Si ya se tiene claro el procedimiento es mejor que empiece a codificarlo y se salte este proceso que explico en este artículo.
Para personas que apenas están incursionando en el mundo de la programación y que han hecho algunos pequeños programas y para estudiantes de los primeros semestres de su formación profesional en programación este artículo es ideal.
Este trabajo se basa en mi experiencia y en las ideas de la generación de algoritmos que se ha dado desde el trabajo de Wirth Niklaus en 1970 y de Vaclav [85] Refinamiento paso a paso revisited y otros autores.
De igual forma pretende dar algunas respuestas a estas interrogantes: ¿Cómo generar un algoritmo para lograr un determinado resultado? Que se puede hacer para generar la idea? ¿Cómo lo puedo ir desarrollando?
1.1 Procedimiento.
Todo inicia con el Problema Veamos un ejemplo:
Hacer un programa para hallar el numero que mas se repite en un array de enteros de tamaño n. Es probable que para dar una sensación de un problema grande se diga que es n un número muy grande (millones)
El primer paso para solucionar este problema es el análisis y es muy útil tener el requerimiento claro con sus entradas y resultados
Requerimiento 01 nombre HallarElmasRepetido
Descripción: se debe hallar en numero que mas se repite en un array de enteros (desordenado porque no se dice que este ordenado)
Entrada: el array de números enteros llamado datos y el tamaño nro (entero)
Resultado: un numero entero r (el mas repetido)
Parte del análisis es que pueden ser varios los repetidos y se debe dar uno podría ser el ultimo que mas se repita, por ejemplo.
1.2 La idea de solución
Si no se TIENE UNA idea párrafo Hallar Este Número Que se Pide, se Recomienda ONU Hacer example grafico ONU de la estafa Tamaño no muy grande (15 ESTA BIEN). Hacer gráficos ayuda mucho. Viendo el grafico pensar en ideas (formas, métodos, pasos, estrategias) para lograr lo que se pide
Una primera idea podría ser esta:
Pero otra idea que se muestra a continuación
puede ser tomar este array
Las dos ideas permiten obtener el resultado pero hay que hacer una.
cual?
Un breve análisis indica que es mas fácil la primera pero si el array tuviera 100.000 números enteros haría muchas comparaciones en sus múltiples recorridos. La segunda idea aunque debe ordenar se puede aprovechar una utilidad del lenguaje que permitir ordenar. Estos ordenamientos usan algoritmos muy eficientes y luego hacer un solo recorrido. Tomaremos la de un solo recorrido y si se puede compararemos al final las dos soluciones.
La gran ventaja de tener los datos gráficamente es que es fácil concebir ideas y obvio hacer ejemplo de la solución gráficamente usando papel, una pizarra digital o cualquier otro medio grafico
1.3 Generación del algoritmo
Ya tenemos una idea: la de un solo recorrido
Ahora empezaremos el procedimiento para generar el algoritmo
Partimos del requerimiento y empecemos un proceso de ir generando el algoritmo de lo mas general a lo más detallado, en varios pasos. Se parte de la idea general y se va mejorando (refinando) la propuesta es decir que el; refinamiento siguiente será mas detallado y tendrá mas forma de algoritmo que el anterior
Refinamiento # 1
Se ordena el array (using una utilidad ya existente)
Se recorre el array ordenado y se van contando las repeticiones
de cada numero con cada cuenta (contador) se mira cual va siendo
la mayor cuenta y se guardada al igual que le numero que tuvo esa
mayor cuenta, al final del recorrido se tendrán la mayor cuenta y
el número que tuvo esa mayor cuenta
se retorna ese número de la mayor cuenta
aleta
Observen que es una idea muy general (pero es una idea)
Refinamiento # 2
Se le va dando mas forma de algoritmo a la función (método en Programación Orientada a Objetos POO)
Teniendo siempre presente el refinamiento anterior (nro 1 en este caso)
|
Entero HallarElmasRepetido (Entero [] datos, Entero nro) Inicio ordenar (datos) se declaran las variables contador, MayorCuenta y mayorValor y se inician en 0 Se hace un para (for) y se van recorriendo lo números que están ordenados lo repetidos están contiguos y se van contando Cada que cambie el número se mira cuantos Repetidos había y se guarda esa cuenta si es mayor que la anterior y le número que se contó. y sigue avanzando el recorrido aleta |
 |
Con respecto a los dos parámetros Entero [] datos, Entero nro Si se tiene una clase y estas son dos propiedades de la clase no es necesario pasarlas como parámetros y asumiremos esto en este caso.
Refinamiento # 3
Entero hallarelmasRepetido ()
Inicio
Se declaran las variables para contar (contador0, el mayor Valor, la mayor Cuenta
y se necesita ir llevando el numero que se esta contando (el actual)
se deben ordenar los números
Se hace un para desde de la posición 0 a hasta la nro- 1 de uno en uno
Se mira si se trata del mismo numero y se va contando
sino
es porque el numero cambio
y se mira si la cuenta fue mayor que las anterior
y se guaradna el mayor valor y la mayor cuenta
y luego
se cambia el numero actual que se va a procesar
y el contador es 1
por fuera del para se
retorna el mayor
aleta
Refinamiento # 4
Entero hallarelmasRepetido ()
Inicio
entero contador = 0
entero actual = datos [0] // esta variable es para ir mirando cual se esta contando
entero mayorCuenta = 0
entero mayorValor = 0;
ordenar ();
para i de 0 a nro-1 hacer
Si (datos [i] = actual)
Contador = contador + 1 // se cuentas las veces que esta un numero
// empezando desde el 0
sino
Si (contador> = mayorCuenta) // se mira si la cantidad de veces que aparece
mayorCuenta = contador // este número es mayor que el mayor actual,
mayorValor = actual // si es asi se actualiza el mayorCuenta y el
//
mayorValor
finsi
actual = datos [i] // se actualiza para el siguiente número
contador = 1 // en el arreglo que no se ha contado
finsi
finpara
retorne mayorValor
Aleta
A Este algoritmo se le puede hacer una prueba de escritorio. Algo así
Observe que por la lógica del algoritmo se espera que la respuesta sea 24 que es el numero el ultimo que mas repeticiones (2) pero como esta será 14 eso indica que algo no esta bien se hacen mas pruebas y se detecta que cuando el numero que mas se repite es uno solo y esta al final el algoritmo falla. Por tanto no esta teniendo en cuenta la ultima cuenta esto se soluciona con este nuevo refinamiento que verifica la ultima cuenta (contador) al salir del ciclo
Refinamiento # 5
Entero hallarelmasRepetido ()
Inicio
entero contador = 0
entero actual = datos [0] // esta variable es para ir mirando cual se esta contando
entero mayorCuenta = 0
entero mayorValor = 0;
ordenar ();
para i de 0 a nro-1 hacer
Si (datos [i] = actual)
Contador = contador + 1 // se cuentas las veces que esta un numero
// empezando desde el 0
sino
Si (contador> = mayorCuenta) // se mira si la cantidad de veces que aparece
mayorCuenta = contador // este número es mayor que el mayor actual,
mayorValor = actual // si es asi se actualiza el mayorCuenta y el
//
mayorValor
finsi
actual = datos [i] // se actualiza para el siguiente número
contador = 1 // en el arreglo que no se ha contado
finsi
finpara
Si (contador> = mayorCuenta) // se mira si la cantidad de veces que aparece
mayorCuenta = contador // este número es mayor que el mayor actual,
mayorValor = actual // si es asi se actualiza el mayorCuenta y el
// mayorValor
finsi
retorne mayorValor
Aleta
si se prueba con estos datos:
Se podrá comprobar que si funciona en este caso y el resultado será 23
1.3.3 Codificación
La codificación es muy sencilla Se toma el último refinamiento y se van colocando las instrucciones con su equivalente enle lenguaje
; al final de cada instrucción, int por entero, if por si, for por para, inicio es {, fin es} etc.
public int hallarelmasRepetido () {// Encuentra el más repetido
int contador = 0;
int actual = datos [0];
int mayorCuenta = 0;
int mayorValor = 0;
ordenar ();
datos [nro-2] = datos [nro-1];
para (int i = 0; i <nro; i ++)
{
si (datos [i] == actual)
{
contador ++; // se cuentas las veces que esta un numero
// empezando desde el 0
}
demás {
si (contador> = mayorCuenta)
{// se mira si la cantidad de veces que
mayorCuenta = contador; // aparece este número actual es mayor
// que la cuenta anterior que fue mayor
mayorValor = actual; // si es asi se actualiza el mayorCuenta Y el mayorValor
}
actual = datos [i]; // se actualiza al siguiente número
contador = 1; // en el arreglo que no se ha contado
}
} // cierra por
si (contador> = mayorCuenta) {// se mira si la cantidad de veces que
mayorCuenta = contador; // aparece este número es mayor que el mayor actual,
mayorValor = actual; // si es asi se actualiza el mayorCuenta Y el mayorValor
}
return mayorValor;
}
Se prueba de nuevo a corriendo el programa y se verifica que funciona.
Esa es la técnica de los refinamientos sucesivos cuya propuesta inicial fue de Wirth Niklaus en 1971 Wirt [h71].
1.4 Consideraciones finales.
Para justificar porque no se hizo la idea inicial y se eligió la de un solo recorrido
Se hizo el codigo para la primera propuesta
Este es:
public int hallarelmasRepetido2 () {
int maxValue = 0, maxCount = 0;
para (int i = 0; i <nro; ++ i) {
int count = 0;
para (int j = 0; j <nro; ++ j) {
if (datos [j] == datos [i]) ++ count;
}
if (cuenta> = maxCount) {
maxCount = recuento;
maxValue = datos [i];
}
}
return maxValue;
}
Y se incluyo una forma de medir cuanto se demoraba cada algoritmo con 100.000 números esteros y estos fueron los resultados:
El caso al cual se le hizo el algoritmo de un solo recorrido se demoró: 44 segundos
El repetido era
96119
Y el caso de un ciclo dentro de un ciclo (dos for anidados) se demoró: 15600 segundos
El repetido era 96119 (el mismo por supuesto)
O sea que el algoritmo mas simple no siempre es el mas óptimo.
Por ultimo Si Lo Que se pedia época Obtener todos los que mas se repiten (Porque pueden Ser Varios)
Se Puede (antes del salir del algoritmo Incluir y Un ArrayList yv recorrer el array y Todos Los Que Tengan mayorCuenta
se va incluyendo en el ArrayList EL valor correspondiente y se retorna el ArrayList
2. Conclusiones
Hacer programas no es lo mismo que solucionar problemas en este caso por ejemplo antes de hacer el programa (codificar) se hizo el algoritmo con la técnica de los refinamientos sucesivos.
Al iniciar el proceso, si no hay una idea para el algoritmo, una forma de solución hacer ejemplos con conjuntos de datos apropiados y usar gráficos darán el ambiente adecuado para que fluyan las ideas y alguna de ellas será la mas apropiada.
Los años de experiencia, la solución de muchos problemas y su codificación, permitirán que dado un problema, se coloque frente al computador y digite el código (de su mente al ordenador) pero si el problema tiene un algoritmo difícil esta técnica le permite inteligentemente ( sin buscar en internet la solución) que usted genere el algoritmo y haga su programa.
La cantidad de refinamientos y el tamaño del algoritmo depende de la complejidad y la cantidad de operaciones requeridas para la solución completa y funcional. Estudiar los algoritmos de varios problemas frecuentemente usados (ordenamientos, búsquedas, proceso de conjuntos de datos, etc.) ayudan mucho en el proceso de aprender a programar efectivamente.
3. REFERENCIAS
Wirt [h71]. Desarrollo de programas mediante refinamiento paso a paso. Niklaus Wirth. Comm. ACM 14, 4, mayo de 1971.
Vaclav [85] Refinamiento paso a paso revisado Rajlich, Vaclav Journal of Systems and Software 1985
archivo: /// C: /Users/Usuario/Downloads/Stepwise_refinement_revisited.pdf
Reynolds [] Refinamiento paso a paso y resolución de problemas Reynolds, Robert Porvin, Stephen Software, IEEE 1992
https://www.researchgate.net/publication/3246859_Stepwise_Refinement_and_Problem_Solving
Cormen [2009]ntroducción a los algoritmos . 3a. ed. -. Cormen, Thomas H. I Cambridge: The Mit Press, 2009.
EJERCICIOS PARA PRACTICAR
1.
Investigue como se multiplican dos matrices A y B de dimensiones mxn y nxp respectivamente y haga un programa para hallar la matriz resultado
Ayuda: haga / estudie / analice ejemplos con matrices 2x2 y 2x2 y 3x3 y 3x3
y aplique este método para generar el respectivo algoritmo
2.
Números afortunados
Dado un N ≥ 2, se llaman números afortunados a los que resultan de ejecutar el siguiente proceso: comienza generando una lista que contiene los números desde 1 hasta N en este orden; se elimina de la lista un número de cada 2 (es decir, los números 1, 3, 5, etc.); de la lista final resultante se elimina un número de cada 3, etc. son los afortunados.
Entrada
La entrada consistirá en distintos casos de prueba, cada uno en una línea. Cada caso de prueba contiene el número con el que se calcularán los números afortunados. Ese número será siempre mayor o igual que 2 y no mayor que 100.000. La entrada terminará con un 0, que marcará el final de la entrada y no generará salida.
Salida
Para cada caso de prueba se escribirá una línea que contendrá al principio el N de partida, seguido por dos puntos, un espacio y todos los números afortunados en orden decreciente.
Entrada de ejemplo
3
10
30
0
Salida de ejemplo
3: 2
10:10 6 4
30:30 22 18 12 10
3.
Investigue como se soluciona un sistema de ecuaciones por el método de la matriz inversa y haga un programa que solucione un sistema de ecuaciones con n incógnitas.
a aquí se explica un ejemplo para un caso de 3 incógnitas
htthttps: //www.youtube.com/watch? v = -YhUfG8DXwk & ab_channel = ProfeBonny
Sus comentarios seran bienvenidos o puede escribir a williamdiaszs@gmail.com
