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

1/oct/09

1

Notas:

UNIVERSIDAD
DE CANTABRIA

1. Introducción

2. Datos y expresiones. Especificación de algoritmos

• Tipos primitivos. Variables y constantes. Operadores y expresiones. Noción de especificación. Noción
de predicado. Reglas de consecuencia de una especificación. Encapsulamiento: Concepto de clase
y objeto. Métodos y paso de parámetros. Especificación de clases y objetos

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

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

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

1/oct/09

2

UNIVERSIDAD
DE CANTABRIA

Tipos primitivos
Entero
• conjunto de los números enteros
• en la práctica limitado a un rango
• dispone de aritmética exacta en ese rango
Real
• conjunto de los números reales
• en la práctica limitado a un subconjunto de números racionales
• aritmética de punto flotante (no exacta)

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

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

1/oct/09

3

Tipos primitivos (cont.)
Carácter
• un único carácter alfanumérico, incluyendo

UNIVERSIDAD
DE CANTABRIA

letras y cifras de 0-9

-
- signos de puntuación
- espacios en blanco y tabuladores
- otros caracteres sin representación gráfica (ej., salto de línea)

Booleano
• valor lógico (verdad o falso)
Texto:
• secuencia de caracteres

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

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

1/oct/09

4

UNIVERSIDAD
DE CANTABRIA

Variables y constantes
Las variables definen una zona de memoria donde cabe un dato de
un tipo determinado, cuyo valor podemos cambiar
Se identifican mediante un nombre
Existen diversos tipos
• atributos (variables de clase y objeto)
• variables locales (variables de método)
• argumentos o parámetros (datos que pasamos a métodos al

invocarlos)

Las constantes son iguales, pero el valor no puede cambiar

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

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

1/oct/09

5

UNIVERSIDAD
DE CANTABRIA

Sintaxis para describir variables y
constantes
La notación habitual en lenguajes de la familia del C/Java es:
tipo nombre;
tipo nombre:=valorInicial;
tipo nombre1, nombre2, nombre3;
En otros lenguajes (Pascal/Ada) se define al revés:
nombre: tipo;
nombre: tipo:= valorInicial;
nombre1,nombre2,nombre3 : tipo;
Para la especificación pueden usarse indistintamente
Para definir constantes pondremos delante la palabra const

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

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

1/oct/09

6

UNIVERSIDAD
DE CANTABRIA

Ejemplos de definición de variables y
constantes
entero i,j;
entero k:=3;
real tempDeseada:=22.0;
real tempAmbiente;
caracter c1=’a’;
booleano estaEncendido:=verdad;
texto miNombre:="Pedro González";
texto miDireccion;
const real tempMaxima:=100.0;

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

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

1/oct/09

7

Operadores y expresiones
Los cálculos y operaciones de transformación de datos se llaman
expresiones
Una expresión permite obtener un resultado y se compone de
• uno o más operandos: datos que vamos a usar
• cero o más operadores: indican las operaciones que vamos a

UNIVERSIDAD
DE CANTABRIA

realizar
- unarios: operan con un solo dato
- binarios: operan con dos datos
-
ternarios: operan con tres datos

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

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

1/oct/09

8

Reglas de precedencia
Los operandos tienen reglas de precedencia, para saber en qué
orden se aplican
a+b/c-d
La precedencia puede modificarse mediante paréntesis
(a+b)/(c-d)

UNIVERSIDAD
DE CANTABRIA

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

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

1/oct/09

9

Operaciones con enteros

UNIVERSIDAD
DE CANTABRIA

Operador

+
-
- (unario)
*
div
/
mod
%

Ejemplo

a+b
a-b
-a
a*b
a div b
a/b
a mod b
a%b

Operación

suma
resta
cambio de signo
multiplicación
división entera de a entre b

resto de la división entera de a entre b

Precedencia:
• los multiplicativos mayor predecencia que los aditivos

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

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

1/oct/09

10

Operaciones con reales

UNIVERSIDAD
DE CANTABRIA

Operador

+
-
- (unario)
a*b
a/b
a mod b
a%b

Ejemplo

a+b
a-b
-a
a*b
a/b
a mod b
a%b

Operación

suma
resta
cambio de signo
multiplicación
division real de a entre b
parte fraccionaria de la división de a
entre b

Precedencia:
• los multiplicativos mayor predecencia que los aditivos

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

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

1/oct/09

11

UNIVERSIDAD
DE CANTABRIA

Ejemplos de expresiones
Enteras
entero i,j,k;

i
-25
(i*25+3) mod 2
(i-j)*k+(35 div i)
Reales
real x,y,z;
x*1.0e-6
x-z/y
-y

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

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

1/oct/09

12

UNIVERSIDAD
DE CANTABRIA

Conversiones de tipo
Generalmente intentaremos no mezclar datos de tipos distintos en
las expresiones
Cuando sea imprescindible, usaremos el operador de cambio de
tipo (cast)
(tipo) expresion
Ejemplos
• convertir la expresión real a entera
(entero) (5.0*x+y)
• Usar un número entero en una expresión real
5.0*(y+(real)i)

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

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

1/oct/09

13

Operaciones relacionales
Permiten comparar dos valores del mismo tipo para obtener un
resultado booleano

UNIVERSIDAD
DE CANTABRIA

Operador

==
!=
>
>=
<
<=

Ejemplo

a==b
a!=b
a>b
a>=b
a<b
a<=b

Operación

igual a
distinto de
mayor que
mayor o igual a
menor que
menor o igual que

Tienen menos precedencia que los operadores aritméticos

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

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

1/oct/09

14

Operaciones lógicas
Permiten operar con valores booleanos para obtener un resultado
también booleano

UNIVERSIDAD
DE CANTABRIA

Operador

&
|
!
&&

||

Ejemplo

a & b
a | b
! a
a && b

a || b

Operación

y (a veces se pone ∧)
o (a veces se pone ∨)
no (a veces se pone ¬)
y entonces
(b sólo se evalúa si es necesario)
o si no
(b sólo se evalúa si es necesario)

Precedencia
!, &, |

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

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

1/oct/09

15

UNIVERSIDAD
DE CANTABRIA

Ejemplos de expresiones relacionales y
lógicas
Expresiones simples
x>5.0
i==j
Comprobación: x en el intervalo [-5,3)
x>=-5 && x<3
Comprobación: x fuera del intervalo (-2,2)
x<=-2 || x>=2
Observar que los operadores relacionales no pueden
concatenarse
-5<x<3 //¡incorrecto!

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

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

1/oct/09

16

Noción de especificación
Para desarrollar un algoritmo seguiremos dos pasos
• especificación: describe lo que hace el algoritmo, sin detallar

UNIVERSIDAD
DE CANTABRIA

cómo lo hace

• diseño: describe con detalles lo que hace el algoritmo, es decir,

su secuencia de instrucciones
Elementos de una especificación

- declaración de variables
- precondición: condiciones sobre el estado inicial de las variables
- nombre del algoritmo
- postcondición: condiciones sobre el estado final de las variables

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

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

1/oct/09

17

Noción de predicado
Un predicado es una relación entre objetos con un resultado
booleano
• La precondición y postcondición son predicados
Pueden describirse de modo informal o formal

UNIVERSIDAD
DE CANTABRIA

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

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

1/oct/09

18

Ejemplos de predicados

UNIVERSIDAD
DE CANTABRIA

+

+

z2

y

0>

}

∧

x

∧

z

∧

z

y≥

y2

z∧

x≥

0>

0=

R2=

x2
∧
Un arco de 90º de radio R en el plano x-y
z
z es el máximo de x e y
z=max(x,y)
n N: m
∈∃
m es múltiplo de k

x y,{

k n⋅

∈

=

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

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

1/oct/09

19

Ejemplo de una especificación
Algoritmo que calcula la superficie de un
triángulo, dados sus lados
var
real a,b,c
real s, area
fvar
{Pre: a=A,b=B,c=C contienen los lados
del triángulo}
Cálculo del área
{Post: a=A, b=B, c=C, s=(A+B+C)/2,

}

s s A–(

) s C–(

) s B–(

area

=

)

A

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

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

1/oct/09

c

B

b

UNIVERSIDAD
DE CANTABRIA

a

C

20

Ejemplo de una especificación
resumida

UNIVERSIDAD
DE CANTABRIA

var
real a,b,c
real s, area
fvar
{Pre: a=A,b=B,c=C contienen los lados del triángulo}
Cálculo del área
{Post: s= semiperímetro del triángulo,

Si no se dice nada del valor de una variable, se sobreentiende que
no cambia

s s A–(

area

}

=

) s B–(

)s

cC–

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

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

1/oct/09

21

UNIVERSIDAD
DE CANTABRIA

Ejercicios de especificación
Especificar un algoritmo que no haga nada sobre dos variables
enteras
Especificar un algoritmo que intercambie el valor de dos variables
Especificar un algoritmo que ordene tres variables enteras en
orden creciente
Especificar un algoritmo que convierta una cantida