PDF de programación - Tratamiento secuencial - Esquemas de recorrido y búsqueda

Tratamiento
secuencial

Esquemas de recorrido y búsqueda

Jordi Àlvarez Canal
Xavier Burgués Illa

PID_00149891

© FUOC • PID_00149891

Índice

Tratamiento secuencial

Introducción........................................................................................... 5

Objetivos .................................................................................................. 6

1. Algoritmos y secuencias .................................................................

7

2. Esquema de recorrido de una secuencia ....................................
2.1. Planteamiento del esquema ..........................................................
2.2. Refinamiento .................................................................................
2.3. Especificación ................................................................................
2.4. Metodología...................................................................................
2.5. Ejemplos ........................................................................................
2.5.1. Divisores de un número.....................................................
2.5.2. Suma de las cifras de un número .......................................

3. Esquema de búsqueda en una secuencia....................................
3.1. Planteamiento del esquema ..........................................................
3.2. Refinamiento .................................................................................
3.3. Especificación ................................................................................
3.4. Metodología...................................................................................
3.5. Ejemplos ........................................................................................
3.5.1. Números de Fibonacci........................................................
3.5.2. Números primos.................................................................

4. Esquemas aplicados a secuencias de entrada/salida ..............
4.1. Esquema de recorrido aplicado a la entrada..................................
4.1.1. Planteamiento ....................................................................
4.1.2. Especificación.....................................................................
4.1.3. Ejemplo ..............................................................................
4.2. Esquema de búsqueda aplicado a la entrada.................................
4.2.1. Planteamiento ....................................................................
4.2.2. Especificación.....................................................................
4.2.3. Ejemplo ..............................................................................
4.3. Tres ejemplos .................................................................................
4.3.1. Media aritmética ................................................................
4.3.2. ¿Aprueban todos?...............................................................
4.3.3. Número de aprobados........................................................

5. Combinación de esquemas.............................................................
5.1. Planteamiento................................................................................
5.2. Ejemplos ........................................................................................
5.2.1. Media de los suspensos ......................................................
5.2.2. Longitud de la primera palabra..........................................

12
12
13
14
15
16
16
18

21
21
22
23
24
24
24
28

30
30
30
31
31
33
33
34
35
36
36
37
38

40
40
40
40
42

© FUOC • PID_00149891

Tratamiento secuencial

Resumen................................................................................................... 44

Ejercicios de autoevaluación .............................................................. 49

Solucionario............................................................................................ 50

Glosario.................................................................................................... 52

Bibliografía ............................................................................................ 53

© FUOC • PID_00149891

Introducción

5

Tratamiento secuencial

Ved el módulo “Introducción
a la algorítmica” de este curso.

En el módulo anterior hemos aprendido a especificar un problema, hemos in-
troducido la noción de algoritmo que lo resuelve y hemos introducido el len-
guaje algorítmico, que nosotros utilizaremos para formular algoritmos. Todavía
no hemos hablado de cómo llegar desde la especificación de un problema hasta
el algoritmo que lo resuelve. En este módulo nos ocuparemos de este tema. No
introduciremos aquí ningún elemento nuevo del lenguaje algorítmico, sino
que, utilizando los elementos que ya conocemos, proporcionaremos una
metodología que nos permita diseñar algoritmos de la forma más sistemática
posible.

La parte más importante que trabajaremos en este módulo será, sobre todo, el
planteamiento de la solución, que, como hemos visto en el módulo “Introduc-
ción a la algorítmica”, es una de las etapas más dificultosas en el diseño de un
algoritmo.

Ciertamente, podríamos intentar diseñar algoritmos de un nivel de compleji-
dad similar a los ejemplos que aparecen en el módulo 1. Sin embargo, las únicas
herramientas de las que disponemos hasta el momento son nuestra capacidad
creativa para combinar adecuadamente las construcciones del lenguaje algorít-
mico y nuestra experiencia (que, por el momento, es poca), como ayuda inesti-
mable para la primera.

El estudio de un conjunto de casos concretos que incremente nuestra experien-
cia podría ser una solución, pero el aprendizaje por esta vía puede ser bastante
costoso y, a un tiempo, incompleto. Por el contrario, en este curso proponemos
una metodología lo más sistemática posible para diseñar algoritmos. A pesar de
todo, igualmente seguiremos necesitando nuestra capacidad creativa; aunque
una vez asimilada esta metodología, el agujero que debemos llenar con nues-
tra creatividad será bastante menor.

Esta metodología se basa en la aplicación de unos algoritmos genéricos que
nos permitirán solucionar problemas que se puedan modelar utilizando una
secuencia de elementos, algo que, como veremos, es bastante habitual. Estos
algoritmos genéricos los denominaremos esquemas, y funcionan como una
especie de plantillas, de forma que su aplicación (que llamaremos refinamien-
to) consistirá en sustituir alguna de sus partes por “trocitos” de algoritmo co-
rrespondientes al problema concreto que estamos intentando solucionar en
aquel momento.

© FUOC • PID_00149891

Objetivos

6

Tratamiento secuencial

Después de haber estudiado este módulo, tendréis que haber alcanzado los si-
guientes objetivos:

1. Entender la noción de secuencia como elemento básico para el diseño de

algoritmos.

2. Conocer los esquemas básicos de tratamiento secuencial y ser capaz de iden-

tificar los problemas a los que se pueden aplicar.

3. Dado un problema al que podemos aplicar los esquemas, saber averiguar la
secuencia subyacente. En ocasiones, esto resulta bastante evidente, como
veremos por ejemplo en el apartado correspondiente a las secuencias de
entrada y salida. Sin embargo, otras veces no lo es tanto.

4. Saber elegir adecuadamente el esquema que hay que aplicar para resolver

un problema concreto.

5. Obtener práctica refinando esquemas para problemas concretos. De este
modo, una vez hayáis averiguado la secuencia y decidido el esquema que
hay que aplicar, el refinamiento debe ser una tarea bastante mecánica.

6. Identificar los problemas en los que hay que hacer varios tratamientos se-
cuenciales para obtener un algoritmo que los solucione. Ser capaces de com-
binar los esquemas adecuadamente para hacerlo con éxito.

© FUOC • PID_00149891

7

Tratamiento secuencial

1. Algoritmos y secuencias

Todos tenemos en mente el concepto de secuencia: un conjunto de elementos
ordenados de una forma determinada. Por ejemplo, sabemos que la siguiente
secuencia: <1, 2, 3, 5, 7, 11, 13, 17, 19> es la secuencia de los números primos
entre 1 y 20. También podemos encontrar ejemplos de secuencia fuera del
mundo de las matemáticas y de la algorítmica: los automóviles que se encuen-
tran en una cinta mecanizada a la espera de ser pintados por un brazo robot
también suponen en realidad una secuencia.

Sin embargo, ¿por qué es importante para nosotros el concepto de secuencia?
Pues resulta que la inmensa mayoría de los algoritmos mínimamente complejos
consiste en repetir un conjunto de cálculos en una secuencia de datos. Estos algo-
ritmos pueden ser modelizados como algoritmos que tratan secuencias.

De este modo, por ejemplo, un posible algoritmo del brazo robot podría ser el
siguiente:

• Al principio de la jornada de trabajo hace falta que algún operario lo ponga
en marcha, lo cargue de pintura si no tiene la suficiente y compruebe que
el brazo funciona correctamente.

• Una vez hecho esto, el brazo robot se pone a funcionar. Su trabajo es muy
simple. Espera a que llegue un automóvil y lo pinta. Entonces se detiene y
espera a que llegue el siguiente automóvil.

• Finalmente, cuando la secuencia de automóviles se termina, el brazo robot

se para.

Fijémonos en que el brazo robot repite las mismas operaciones para cada au-
tomóvil. La cinta mecanizada se encarga de ir poniéndole los automóviles de-
lante para que el brazo robot actúe. Entonces, la dificultad del algoritmo del
brazo robot se limita a pintar un automóvil, mientras que la cinta mecanizada
se encarga de gestionar la secuencia de automóviles.

Notad que esta organización supone dos grandes ventajas: en primer lugar, el
algoritmo del brazo robot es más sencillo que si él mismo tuviese que gestionar
la secuencia de automóviles (seguro que el brazo robot tendría que ser más
complejo; por ejemplo, debería tener capacidad de movi