PDF de programación - Bloque 1. Conceptos y técnicas básicas en programación - 5. Iteración y recursión sobre secuencias

Bloque 1. Conceptos y técnicas básicas
en programación
1. Introducción
2. Datos y expresiones. Especificación de algoritmos
3. Estructuras algorítmicas básicas
4. Iteración y recursión
5. Iteración y recursión sobre secuencias
6. Iteración y recursión sobre tablas

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN
4

© Michael González Harbour y José Luis Montaña

25/nov/09

1

Notas:

UNIVERSIDAD
DE CANTABRIA

1. Introducción

2. Datos y expresiones. Especificación de algoritmos

3. Estructuras algorítmicas básicas

4. Iteración y recursión

5. Iteración y recursión sobre secuencias

• Descripción de la secuencia. Interfaz. Recorridos sobre secuencias. Búsquedas en secuencias.

Esquemas mixtos

6. Iteración y recursión sobre tablas

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

2

Introducción
En muchas aplicaciones informáticas es preciso guardar
colecciones o listas de datos
• habitualmente son datos del mismo tipo, o tipos similares
• por ejemplo:

lista de alumnos de una asignatura

-
- colección de datos de temperatura recogidos por un sensor a lo

UNIVERSIDAD
DE CANTABRIA

largo del tiempo

- vector de 6 dimensiones que representa la posición y orientación

de un cuerpo en el espacio

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

3

Formas de acceso a una colección
Las dos formas más comunes de acceder a una colección de datos
• acceso secuencial: para acceder a un elemento de la colección

es preciso haber accedido a los anteriores
- por ejemplo, una cinta de vídeo: para acceder a una imagen es

UNIVERSIDAD
DE CANTABRIA

preciso haber accedido a las anteriores

- acceso a los caracteres introducidos por teclado
-
lectura de los datos de un sensor de temperatura
la estructura que admite este acceso se llama secuencia
-

• acceso directo: se puede acceder a un elemento concreto de la

colección directamente, a través de su posición, o índice
- por ejemplo, acceso a las imágenes de un DVD
- acceso a un elemento de un vector
-

la estructura que admite este acceso se llama tabla

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

4

Descripción de la secuencia
La secuencia representa una colección de cero o más objetos de
un determinado tipo, en la que se dispone de acceso secuencial
Para el acceso definimos el concepto de elemento actual
• es el primero de los elementos que quedan por acceder

UNIVERSIDAD
DE CANTABRIA

- al terminar de recorrer la secuencia no hay elemento actual

Diferenciamos dos partes en la secuencia
• parte izquierda: representa los elementos ya leídos

- está vacía antes de recorrer la secuencia

• parte derecha: representa los elementos aún no leídos

- el elemento actual es el primero de la parte derecha
- está vacía cuando terminamos de recorrer la secuencia

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

5

Descripción de la secuencia (cont.)

UNIVERSIDAD
DE CANTABRIA

parte izquierda

parte derecha

a1 a2

ai-1

ai

an

actual

i

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

6

Descripción de la secuencia (cont.)
Disponemos de las siguientes operaciones
• reinicia: pone el elemento actual al principio

-

la parte izquierda queda vacía

UNIVERSIDAD
DE CANTABRIA

• actual: retorna el elemento actual
• avanza: el elemento actual pasa a ser el siguiente elemento
• fds: retorna un booleano que indica si estamos en el fin de

secuencia

En las secuencias modificables, disponemos además de
• constructor: crea la secuencia vacía
• escribe: añade un elemento a la izquierda del elemento actual

-

lo añade al final si la parte derecha está vacía

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

7

UNIVERSIDAD
DE CANTABRIA

Interfaz de la secuencia
La interfaz representa una
colección de métodos de los que
deben disponer las clases que se
deriven de ella
• las secuencias deben disponer

de los métodos que indican en la
interfaz de la figura
- Elemento representa el tipo o
clase de los elementos que se
guardan en la secuencia

Secuencia
<<interfaz>>

reinicia()
Elemento actual()
avanza()
booleano fds()
constructor()
escribe(Elemento e)

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

8

Especificación de los métodos de la
secuencia
Dada la secuencia S<Elemento> de elementos del tipo Elemento:
• pi(S): parte izquierda de S
• pd(S): parte derecha de S
Especificación de los métodos
• representaremos un elemento de la secuencia con una letra
• representaremos una parte de la secuencia, compuesta por cero

UNIVERSIDAD
DE CANTABRIA

o más elementos, con una letra griega

método reinicia()
{Pre:}
{Post:pi(S)=vacia}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

9

UNIVERSIDAD
DE CANTABRIA

Especificación de los métodos de la
secuencia
método actual() retorna Elemento
{Pre:pi(S)=α, pd(S)=bβ}
{Post:pi(S)=α, pd(S)=bβ, valor retornado=b}
fmétodo
método avanza()
{Pre:pi(S)=α, pd(S)=bβ}
{Post:pi(S)=αb, pd(S)=β}
fmétodo
método fds() retorna booleano
{Pre:}
{Post:valor retornado = pd(S)==vacio)}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

10

Especificación de los métodos de la
secuencia (cont.)
método constructor()
{Pre:}
{Post:S está vacía}
fmétodo
método escribe(Elemento e)
{Pre:pi(S)=α}
{Post:pi(S)=αe}
fmétodo

UNIVERSIDAD
DE CANTABRIA

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

11

Problemas a estudiar en las secuencias
1. Recorridos
• recorrer todos los elementos de la secuencia para hacer algo

UNIVERSIDAD
DE CANTABRIA

con cada uno de ellos

2. Búsquedas
• buscar y obtener un elemento de la secuencia que cumple una

determinada condición

3. Combinación de recorridos y búsquedas
• recorrer una secuencia buscando elementos que cumplen una

determinada condición para hacer algo con ellos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

12

Ejemplos de problemas a estudiar en
las secuencias
1. Recorridos
• contar el numero de apariciones de una letra en un texto
• calcular la media de una secuencia de enteros
• evaluación de un polinomio representado por la secuencia de

UNIVERSIDAD
DE CANTABRIA

sus coeficientes, en un punto x dado

2. Búsquedas
• determinar si en un texto aparece una letra dada
• determinar si una secuencia de enteros está formado por

números positivos solamente

• mostrar los datos de un alumno cuyo DNI se indica, dada una

lista de alumnos

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

13

Ejemplos de problemas a estudiar en
las secuencias (cont.)
3. Combinación de recorridos y búsquedas
• contar el número de palabras de un texto
• fusionar dos secuencias ordenadas
• sustituir en un texto todas las apariciones de una palabra, por

UNIVERSIDAD
DE CANTABRIA

otra

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

14

UNIVERSIDAD
DE CANTABRIA

Recorridos sobre secuencias: contar
apariciones de una letra en un texto
método contarLetra(caracter l,
Secuencia<caracter> texto) retorna entero
texto.reinicia();
var entero num:=0; fvar
{Inv: num es el número de letras l en pi(texto)}
{Cota: longitud de pd(texto)}
mientras no texto.fds() hacer
si texto.actual()==l entonces
num++;
fsi
texto.avanza();
fmientras
retorna num;
{Post: valor retornado=número de letras l del texto}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

15

UNIVERSIDAD
DE CANTABRIA

Recorrido sobre secuencias: media de
una lista de enteros
método media(Secuencia<entero> lista) retorna entero
{Pre: lista tiene al menos un elemento}
var entero suma:=0; entero num:=0; fvar
lista.reinicia();
{Inv: suma es la suma de los enteros de pi(lista),
num es la longitud de pi(lista)}
{Cota: longitud de pd(lista)}
mientras no lista.fds() hacer
suma:=suma+lista.actual();
num++;
lista.avanza();
fmientras
retorna suma/num
{Post: valor retornado=media de los enteros de lista}
fmétodo

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

16

UNIVERSIDAD
DE CANTABRIA

Recorrido sobre secuencias: esquema
para el diseño
esquema recorrido(Secuencia<Elemento> s)
{Pre:}
Inicializaciones;
s.reinicia();
{Inv: los elementos de pi(s) han sido tratados}
{Cota: longitud de pd(s)}
mientras no s.fds() hacer
tratar s.actual();
s.avanza();
fmientras
Finalización
{Post: los elementos de s han sido tratados}
fesquema

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

17

Ejemplo: evaluación de un polinomio
Un polinomio P de orden n cuyos coeficientes (de orden mayor a
menor) son an, an-1, ..., a1, a0 se evalúa para el valor x como
1– … aixi … a1x

P an … a0
(

anxn

1– xn

UNIVERSIDAD
DE CANTABRIA

] x,

)

+

a0

+

an

=

[

,

,

+

+

+

+

Que se puede expresar también como (regla de Horner)

P an … a0
(

[

,

,

] x,

)

=

(

(

(

(

anx

+

an

)x

+

an

1–

2–

)x …+

)

a1+

)x

a0+

DEPARTAMENTO DE MATEMÁTICAS,
ESTADÍSTICA Y COMPUTACIÓN

© Michael González Harbour y José Luis Montaña

25/nov/09

18

Ejemplo: evaluación de