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

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

3/dic/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

6. Iteración y recursión sobre tablas

• Concepto de tabla. Sintaxis. Operaciones sobre tablas. Recorrido de tablas. Búsqueda en tablas.

Algoritmos sencillos de ordenación en tablas.

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

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

3/dic/09

2

Formas de acceso a una colección
En el capítulo anterior hablamos de la importancia de las
colecciones de datos
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

UNIVERSIDAD
DE CANTABRIA

es preciso haber accedido a los anteriores

• 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 o también
vector

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

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

3/dic/09

3

Definición de la tabla
La tabla representa una colección de cero o más objetos de un
determinado tipo, en la que se dispone de acceso directo
• cada elemento se identifica mediante un índice
El índice es un valor de un tipo discreto, en un rango determinado
• nos restringiremos a índices enteros en un rango, pues hay

lenguajes (Java, C, C++) que nos obligan a ello
- en algunos lenguajes (Java, C, C++), el rango tiene otra limitación:

UNIVERSIDAD
DE CANTABRIA

son números entre 0 y un valor positivo

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

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

3/dic/09

4

UNIVERSIDAD
DE CANTABRIA

Declaración de tablas
Para declarar una tabla es preciso indicar
• su nombre
• el rango de valores del índice
• el tipo de elemento de cada casilla de la tabla
Sintaxis
tipo [1..N] nombre;

entero [1..50] a;
Declara una tabla de 50 variables de
tipo entero
String [0..29] listaNom; Declara una tabla de 30 objetos de
tipo String
Alumno [0..19] alumno;
Declara una tabla de 20 objetos de la
clase Alumno

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

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

3/dic/09

5

UNIVERSIDAD
DE CANTABRIA

Uso de los elementos de la tabla
• tabla[i] es el nombre del elemento i-ésimo de la tabla
a[i] // elemento i de la tabla a (es un entero)
listaNom[3] // cuarto elemento de la tabla
// listaNom (es un String)
alumno[19] // ultimo elemento de la tabla
// alumno (es un objeto de Alumno)
• estos elementos se pueden usar como variables
j := j*a[3]+4*a[7];
imprimir(listaNom[2]);
a[5] := 38;
listaNom[3] := "Esto es un texto";

- y para asignarle un valor

- en expresiones

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

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

3/dic/09

6

UNIVERSIDAD
DE CANTABRIA

Operaciones sobre tablas
Las tablas suelen disponer de una forma de obtener su tamaño
Si a es una tabla
• llamaremos a.longitud al número de casillas de a
Algunas de las operaciones más comunes que haremos en las
tablas son las mismas que en la secuencia
• recorrido
• búsqueda
El acceso directo dará otras posibilidades (ordenación, ...)
En ocasiones tendremos que convertir una secuencia a una tabla,
y viceversa

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

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

3/dic/09

7

Recorrido de tablas
Esquema de recorrido: especificación
método recorrido (tipo[1..N] t)
{Pre:}
Recorrido
{Post: tratados t[1]..t[N]}
fmétodo

UNIVERSIDAD
DE CANTABRIA

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

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

3/dic/09

8

UNIVERSIDAD
DE CANTABRIA

Recorrido Iterativo (mientras)
esquema recorridoIter(tipo[1..N] t)
{Pre:}
var entero i:=1 fvar;
inicializaciones;
{Inv: tratados t[1]..t[i-1], 1<=i<=N+1}
mientras i<N+1 hacer
tratar t[i];
i:=i+1;
fmientras
{Post: tratados t[1]..t[N]}
fesquema

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

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

3/dic/09

9

Recorrido Iterativo (para)
esquema recorridoIter(tipo[1..N] t)
{Pre:}
inicializaciones;
para i:=1 hasta N hacer
{Inv: tratados t[1]..t[i-1], 1<=i<=N}
tratar t[i];
fpara
{Post: tratados t[1]..t[N]}
fesquema

UNIVERSIDAD
DE CANTABRIA

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

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

3/dic/09

10

UNIVERSIDAD
DE CANTABRIA

Recorrido Iterativo (para)
// cuando el índice empieza en cero
esquema recorridoIter(tipo[0..N-1] t)
{Pre:}
inicializaciones;
para i:=0 hasta N-1 hacer
{Inv: tratados t[0]..t[i-1], 0<=i<=N-1}
tratar t[i];
fpara
{Post: tratados t[0]..t[N-1]}
fesquema

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

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

3/dic/09

11

Recorrido recursivo
esquema recorridoRec(tipo[1..N] t, entero i)
{Pre: tratados t[1]..t[i-1]}
si i<N+1 entonces
tratar t[i];
recorridoRec(t,i+1)
fsi
{Post.- tratados t[1]..t[N]}
fesquema

UNIVERSIDAD
DE CANTABRIA

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

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

3/dic/09

12

Ejemplo de recorrido:
Suma de elementos
método sumaTabla(entero[1..N] t) retorna entero
{Pre:}
suma
{Post: valor retornado=t[1]+...+t[N]}
fmétodo

UNIVERSIDAD
DE CANTABRIA

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

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

3/dic/09

13

UNIVERSIDAD
DE CANTABRIA

Solución Iterativa
Invariante: s contiene la suma de los elementos t[1]..t[i-1],
1<=i<=N+1
Cota: N+1-i
Terminación: i==N+1
Inicializaciones:
i:=1;
s:=0;
Cuerpo del bucle:
s:=s+t[i];
i:=i+1;

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

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

3/dic/09

14

UNIVERSIDAD
DE CANTABRIA

Solución iterativa
método sumaTabla(entero[1..N] t) retorna entero
{Pre:}
var
entero i:=1;
entero s:=0;
fvar
{Inv: s es la suma de elementos t[1]..t[i-1],
0<=i<=N-1}
mientras i<N+1 hacer
s:=s+t[i];
i:=i+1;
fmientras
retorna s;
{Post: valor retornado=t[1]+...+t[N]}
fmétodo

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

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

3/dic/09

15

UNIVERSIDAD
DE CANTABRIA

Máximo de una tabla
// con bucle para
método máximo(entero[1..N] t) retorna entero
{Pre: N>=1 (la tabla tiene al menos un elemento)}
var
entero m:=t[1];
fvar
{Inv: m es el máximo de t[1]..t[i-1]}
para i:=2 hasta N hacer
si t[i]>m entonces
m:=t[i]
fsi
fpara
retorna m;
{Post: valor retornado= máximo de t[1],...,t[N]}
fmétodo

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

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

3/dic/09

16

UNIVERSIDAD
DE CANTABRIA

Búsqueda en tablas
Búsqueda de un elemento que satisface una propiedad P
esquema buscar (elem[1..N] t) retorna entero
{Pre:}
{Post:
valor retornado= primer k, 1<=k<=N, tal que
t[k] satisface P
si ningún valor satisface P, valor retornado=-1
}
fesquema

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

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

3/dic/09

17

UNIVERSIDAD
DE CANTABRIA

Solución iterativa
esquema buscar (elem[1..N] t) retorna entero
var
booleano encontrado:= falso;
entero índice:=-1;
entero i:=1;
fvar
{Inv: si encontrado, t[índice] cumple P
si no encontrado, índice=-1 y ninguno de los
elementos t[1]..t[i-1] cumple P
1<=i<=N+1}

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

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

3/dic/09

18

Solución iterativa (cont.)
mientras no encontrado y i<N+1 hacer
encontrado:= P(t[i]);
si encontrado entonces
índice:=i;
fsi
i:=i+1;
fmientras;
retorna índice;
fesquema

UNIVERSIDAD
DE CANTABRIA

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

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

3/dic/09

19

Búsqueda binaria o dicotómica
método búsquedaBinaria(elem[1..N] t, elem x)
retorna entero
{Pre: t ordenada crecientemente}
{Post: valor retornado =
-1 si x no está en la tabla
1<=i<=N si x==t[i]}
fmétodo

UNIVERSIDAD
DE CANTABRIA

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

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

3/dic/09

20

UNIVERSIDAD
DE CANTABRIA

Solución Iterativa
método búsquedaBinaria(elem[1..N] t, elem x)
retorna entero
var
entero inicio:=1;
entero fin:=N;
entero medio;
fvar
// comprobar si la tabla esta vacía
si t.longitud==0 entonces
retorna -1; // elemento no encontrado
fsi
{Inv: x > elementos anteriores a inicio,
x < elementos posteriores a fin,
1<=inicio<=fin<=N}

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

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

3/dic/09

21

UNIVERSIDAD
DE CANTABRIA

Solución Iterativa (cont.)
mientras inicio<fin hacer
medio:=