Un algoritmo simple para calcular xn es la siguiente:
y = 1; for(j=n; j > 0; j--) { y = y*x; }El invariante de este algoritmo se puede escribir como y*xj == xn, y el tiempo que demora el algoritmo es O(n). Implemente un algoritmo que realice el cálculo de manera más eficiente, es decir, que su complejidad temporal sea menor que O(n).
Solución:
Para encontrar un algortimo más eficiente hay que desligar las dos x's del invariante de la siguiente manera:
y = 1; z = x; for(j=n; j>0; j--) { y = y * z; }En este caso, el invariante se puede escribir como: y*zj == xn.
¿Para que sirve esto? Esto nos permite modificar z si lo hacemos sin modificar el invariante. En particular, si j es par, podemos hacer:
z = z*z; j = j/2;El invariante no cambia, pero ahora j disminuye mucho más rápido. Más aún, si j sigue siendo par, se puede repetir lo anterior tantas veces como sea posible. El algoritmo queda como sigue:
y = 1; z = x; for(j=n; j>0; j--) { while(j es par) { z = z*z; j = j/2; } y = y*z; }La complejidad temporal del nuevo algoritmo es O(log(n)).
Problema 2: Diagramas de estado
Escriba un algoritmo que cuente las palabras de una frase, y dibuje el diagrama de estados respectivo. Para simplificar suponga que la frase se encuentra en un string s, por ejemplo:
String s = "Hoy no se fia mañana si.";Una palabra se define como una secuencia de caracteres consecutivos distintos de ' ' (espacio en blanco). Suponga que las frases terminan en '.' (punto).
Solución:
Se examinan los caracteres de izquierda a derecha, y el proceso depende si se está dentro o fuera de una palabra.
El diagrama de estados del algoritmo es:
Primera versión del algoritmo:
np = 0; estado = FUERA; k=0; c = s.charAt(k); for(k=1; c != '.'; k++) { if(estado == FUERA) { if(c != ' ') { np++; estado = DENTRO; } } else { if(c == ' ') { estado = FUERA; } } c = s.charAt(k); }Segunda versión del algoritmo:
k = 0; np = 0; while(s.charAt(k) != '.') { // estado == FUERA while(s.charAt(k) == ' ') { k++; } if(s.charAt(k) == '.') { break; } np++; k++; // estado == DENTRO while(s.charAt(k) != ' ' && s.charAt(k) != '.') { k++; } }
Problema 3: Más diagramas de estado
Suponga que existe un arreglo a con n casilleros, en donde se almacenan números enteros. Escriba un algoritmo, y su correspondiente diagrama de estados, que reordene los elementos del arreglo dejando a la izquierda los números menores que 0 y a la derecha los números mayores o iguales a 0.
Solución:
El diagrama de estados del algoritmo es:
i = 0; j = n-1; //ultima posicion de arreglo de n elementos tiene indice (n-1) while(i < j) { if(a[i] < 0) { i++; } else if(a[j] >= 0) { j--; } else { a[i] <--> a[j]; //swap entre a[i] y a[j] i++; j--; } }Segunda versión del algoritmo:
i = 0; j = n-1; //ultima posicion de arreglo de n elementos tiene indice (n-1) while(i < j) { while(i < j && a[i] < 0) { i++; } while(i < j && a[j] >= 0) { j--; } if(i < j) { a[i] <--> a[j]; i++; j--; } }Solución alternativa:
i = 0; for(j = 0; j < n; j++) { if(a[j] < 0) { a[i] <--> a[j]; i++; } }