Soluciones Ejercicios Capítulo 4.2 Matemáticas Discretas Johnsonbaugh 6 ed

1. Haga un seguimiento del algoritmo 4.2.1 para la entrada t = “balalaika”
y p = “bala”.

2. Haga un seguimiento del algoritmo 4.2.1 para la entrada t = “balalaika”
y p = “lai”.

3. Haga un seguimiento del algoritmo 4.2.1 para la entrada
t = “000000000” y p = “001”.

4. Haga el seguimiento del algoritmo 4.2.3 para la entrada
34 20 144 55.

5. Haga el seguimiento del algoritmo 4.2.3 para la entrada
34 20 19 5.

6. Haga el seguimiento del algoritmo 4.2.3 para la entrada
34 55 144 259.

7. Haga el seguimiento del algoritmo 4.2.3 para la entrada
34 34 34 34.

8. Haga el seguimiento del algoritmo 4.2.4 para la entrada
34 57 72 101 135.
Suponga que los valores de rand son
rand(1, 5) = 5, rand(2, 5) = 4,
rand(3, 5) = 3, rand(4, 5) = 5.

9. Haga el seguimiento del algoritmo 4.2.4 para la entrada
34 57 72 101 135.
Suponga que los valores de rand son
rand(1, 5) = 2, rand(2, 5) = 5,
rand(3, 5) = 3, rand(4, 5) = 4.

10. Haga el seguimiento del algoritmo 4.2.4 para la entrada
34 57 72 101 135.
Suponga que los valores de rand son
rand(1, 5) = 5, rand(2, 5) = 5,
rand(3, 5) = 4, rand(4, 5) = 4.

11. Pruebe que el algoritmo 4.2.1 es correcto.

12. Pruebe que el algoritmo 4.2.3 es correcto.

13. Escriba un algoritmo que regrese el índice de la primera ocurrencia
del valor clave de la sucesión s1, . . . , sn. Si la clave no está
en la sucesión, el algoritmo regresa el valor 0. Ejemplo: Si la sucesión
es 12 11 12 23 y la clave es 12, el algoritmo regresa el valor 1.

14. Escriba un algoritmo que regrese el índice de la última ocurrencia
del valor clave en la sucesión s1, . . . , sn. Si la clave no está
en la sucesión, el algoritmo regresa el valor 0. Ejemplo: Si la sucesión
es 12 11 12 23 y la clave es 12, el algoritmo regresa el valor 3.

15. Escriba un algoritmo cuya entrada es la sucesión s1, . . . , sn que
está en orden no decreciente, y un valor x. (Suponga que todos los
valores son números reales). El algoritmo inserta x en la sucesión
de manera que la sucesión obtenida está en orden no decreciente.
Ejemplo: Si la sucesión de entrada es
2 6 12 14
y x = 5, la sucesión resultante es
2 5 6 12 14.

16. Modifique el algoritmo 4.2.1 para que encuentre todas las ocurrencias
de p en t.

17. Describa la entrada del mejor caso para el algoritmo 4.2.1.

18. Describa la entrada del peor caso para el algoritmo 4.2.1.

19. Modifique el algoritmo 4.2.3 de manera que ordene la sucesión
s1, . . . , sn en orden no creciente.

20. El algoritmo de selección por orden acomoda la sucesión s1, . . . , sn
en orden no decreciente, para ello encuentra primero el elemento
más pequeño, por ejemplo si, y lo coloca en el primer lugar intercambiando
s1 y si. Después encuentra el algoritmo más pequeño
en s2, . . . , sn, de nuevo digamos si, y lo coloca en el segundo lugar
intercambiando s2 y si. Continúa hasta que la sucesión esté ordenada.
Escriba selección por orden en seudocódigo.

21. Haga el seguimiento del algoritmo selección por orden (vea el
ejercicio 20) para la entrada de los ejercicios 4 al 7.

22. Muestre que el tiempo para la selección por orden (vea el ejercicio
20) es el mismo que para todas las entradas de tamaño n.