PDF de programación - Bloque 1. Conceptos y técnicas básicas en programación

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

28/oct/09

1

Notas:

UNIVERSIDAD
DE CANTABRIA

1. Introducción

2. Datos y expresiones. Especificación de algoritmos

3. Estructuras algorítmicas básicas

• La asignación. Composición secuencial de instrucciones. La instrucción alternativa simple y múltiple.

Alternativa exclusiva y general.

4. Iteración y recursión

5. Iteración y recursión sobre secuencias

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

28/oct/09

2

3.1. La asignación
La instrucción de asignación consiste en dar valor a una variable
Sintaxis:
Variable:=expresión
• primero se evalúa la expresión
• después el resultado se guarda en la variable
• el valor anterior de la variable se pierde

UNIVERSIDAD
DE CANTABRIA

- aunque se puede usar en la expresión

El tipo de la expresión debe ser compatible con el tipo de la
variable

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

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

28/oct/09

3

UNIVERSIDAD
DE CANTABRIA

Corrección de la asignación: Ejemplo
Podemos averiguar la corrección de un algoritmo que dispone de
una asignación, comprobando la precondición y postcondición
algoritmo ejemplo
// debemos encontrar la expresión E que hace
// correcto el algoritmo
var
entero x,y;
fvar
{Pre: x+y=X, y=Y}
x:=E;
{Post: x=X, y=Y}
falgoritmo

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

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

28/oct/09

4

UNIVERSIDAD
DE CANTABRIA

Corrección de la asignación:
solución al ejemplo
E es la expresión x+y
Explicación:
• la postcondición es {x=X, y=Y}
• si sustituimos x por x+y en la postcondición obtenemos
{x+y=X, y=Y}
- que es justamente la precondición
x X-Y

y Y

valor inicial

valor final

x:=x+y

y Y

x X

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

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

28/oct/09

5

x
RE

a la sustitución en el predicado R de toda aparición

Corrección de la asignación
Llamamos
de la variable x por la expresión E
Axioma de la asignación
• para toda variable x y toda expresión válida E del mismo tipo y
todo predicado R, la especificación siguiente es correcta

UNIVERSIDAD
DE CANTABRIA

}

{
x
RE
x:=E;
{ }
R

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

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

28/oct/09

6

Regla de inferencia de la asignación
Combinando el axioma de la asignación con la primera regla de
consecuencia de una especificación (ver capítulo 2), se obtiene
• Para que esta especificación sea correcta

UNIVERSIDAD
DE CANTABRIA

{ }
P
x:=E;
{ }
Q

• se debe cumplir que

P

x⇒
QE

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

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

28/oct/09

7

UNIVERSIDAD
DE CANTABRIA

3.2. Composición secuencial de
instrucciones
Una de las estructuras algorítmicas básicas es la composición
secuencial
• ejecutar un algoritmo a continuación de otro
• el orden en que se ejecutan influye en el resultado
Sintaxis
algoritmo 1;
algoritmo 2
o algoritmo 1; algoritmo 2

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

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

28/oct/09

8

UNIVERSIDAD
DE CANTABRIA

Composición secuencial de asignaciones
Una composición de dos asignaciones
var
tipo1 x1;
tipo2 x2;
fvar
{Pre:P}
x1:=E1;
x2:=E2;
{Post:Q}
x2 )x1
QE2
Es correcta si
E1⇒
P
Si son n expresiones,
⇒

xn )xn 1–
QEn

P

En 1– …)

x1
E1

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

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

28/oct/09

9

UNIVERSIDAD
DE CANTABRIA

Ejemplos
algoritmo intercambiar
// debemos intercambiar los valores de x y de y
var
entero x,y;
fvar
{Pre: x=X, y=Y}
var
entero temp;
fvar
temp:=x;
x:=y;
y:=temp;
{Post: x=Y, y=X}
falgoritmo

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

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

28/oct/09

10

Traza de intercambiar

UNIVERSIDAD
DE CANTABRIA

valor inicial

valor inter.

valor inter.

valor final

x X

x X

x Y

x Y

y Y

temp:=x

x:=y

y Y

y Y

y:=temp

y X

temp ?

temp X

temp X

temp X

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

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

28/oct/09

11

Corrección de intercambiar

UNIVERSIDAD
DE CANTABRIA

postcondición

x=Y, y=X

x=Y, temp=X

y=Y, temp=X

precondición

y=Y, x=X

sustituir

y por temp

x por y

temp por x

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

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

28/oct/09

12

Ejemplo: clase Circulo

UNIVERSIDAD
DE CANTABRIA

Circulo

real centroX
real centroY
real radio
Circulo(real x,
real y,
real r)
real centroX()
real centroY()
real radio()
real area()
dibuja()

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

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

28/oct/09

13

UNIVERSIDAD
DE CANTABRIA

Especificación de los métodos
método Circulo(real x, real y, real r)
{Pre: x=X, y=Y, r=R, r>=0}
constructor
{Post: centroX=X & centroY=Y & radio=R}
fmétodo
método centroX() retorna real
{Pre:}
obtener la coordenada x del centro
{Post: valor retornado=centroX}
fmétodo
// centroY y radio son similares

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

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

28/oct/09

14

UNIVERSIDAD
DE CANTABRIA

Especificación de los métodos (cont.)
método area() retorna real
{Pre:}
cálculo del área
{Post: valor retornado=π⋅radio2}
fmétodo
método dibuja(
{Pre:}
dibuja el círculo en la pantalla
{Post: el círculo se ha dibujado en la pantalla}
fmétodo

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

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

28/oct/09

15

UNIVERSIDAD
DE CANTABRIA

Diseño de los métodos
método Circulo(real x, real y, real r)
{Pre: x=X, y=Y, r=R, R>=0}
centroX:=x;
centroY:=y;
radio:=r;
{Post: centroX=X & centroY=Y & radio=R}
fmétodo
método centroX() retorna real
{Pre:}
retorna centroX;
{Post: valor retornado=centroX}
fmétodo
// centroY y radio son similares

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

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

28/oct/09

16

Diseño de los métodos (cont.)
método area() retorna real
{Pre:}
retorna π⋅radio2;
{Post: valor retornado=π⋅radio2}
fmétodo
// el método dibuja es complejo y requiere
// instrucciones que aún no conocemos

UNIVERSIDAD
DE CANTABRIA

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

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

28/oct/09

17

3.3. La instrucción alternativa
La instrucción alternativa, o condicional, nos permite ejecutar
unas instrucciones u otras en función de:
• una condición booleana: alternativa simple
• múltiples condiciones booleanas: alternativa múltiple

UNIVERSIDAD
DE CANTABRIA

- alternativa general: pueden cumplirse varias de las condiciones

- alternativa exclusiva: las condiciones son disjuntas (es decir, sólo

una puede ser cierta)

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

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

28/oct/09

18

UNIVERSIDAD
DE CANTABRIA

Sintaxis de la alternativa simple
Ejecución condicional de instrucciones
si condición entonces
instrucciones
fsi
Ejecución condicional de una de entre dos alternativas
si condición entonces
instrucciones
si no
instrucciones
fsi

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

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

28/oct/09

19

Ejemplo 1: valor absoluto
método valorAbsoluto(real x) retorna real
{Pre:}
si x>=0 entonces
retorna x;
si no
retorna -x;
fsi
{Post: valor retornado=|x|}
fmétodo

UNIVERSIDAD
DE CANTABRIA

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

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

28/oct/09

20

Ejemplo 2: máximo de dos enteros
método maximo(real x,y) retorna real
{Pre:}
si x>=y entonces
retorna x;
si no
retorna y;
fsi
{Post: valor retornado=máximo(x,y)}
fmétodo

UNIVERSIDAD
DE CANTABRIA

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

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

28/oct/09

21

UNIVERSIDAD
DE CANTABRIA

Sintaxis de la alternativa múltiple
La condición depende de múltiples predicados booleanos
si
condicion1 -> instrucciones;
condicion2 -> instrucciones;
condicion3 -> instrucciones;
fsi
Las condiciones se evalúan en el orden en que aparecen
• cuando una es cierta, se ejecutan sus instrucciones y se termina

la instrucción condicional

Cada conjunto de instrucciones debe conducir a la postcondición
Recomendación: Deben cubrirse todos los casos (al menos una de
las condiciones debe ser cierta)

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

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

28/oct/09

22

3.4. Alternativa exclusiva y general
Alternativa exclusiva
• Las condiciones son disjuntas (es decir si una es cierta, ninguna

UNIVERSIDAD
DE CANTABRIA

de las otras puede ser cierta)

Alternativa general
• Las condiciones no tienen por qué ser disjuntas
• el orden en que se escriben influye en el resultado
La alternativa simple es siempre exclusiva

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

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

28/oct/09

23

UNIVERSIDAD
DE CANTABRIA

Ejemplo: ordenación de tres números
Especificación:
va