introducción a la programación y la informática. tema 9
TRANSCRIPT
Tema 9. Estructures de control: iteració
Introducció a la Informática i a la Programació (IIP)
Curs 2011/12
Departament de Sistemes Informàtics i Computació
Índex
1. Introducció
2. La iteració 1. Elements
2. Estructura repetitiva
3. Terminació
4. Exemple: MCD
3. Instruccions iteratives en Java 1. Instrucció while
2. Instrucció for
3. Instrucció do … while
25/10/2011 IIP - Curs 2011/12 2
Introducció
• Hi ha molts problemes tals que la seua resolució mitjançant un programa, requerix que s'execute repetidament una seqüència d'instruccions.
• En ocasions, el nombre de vegades que ha de repetir-se eixa seqüència es coneix per endavant; però altres vegades no és així.
• Exemples: – Sumar tots els valors d'una llista,
– Calcular la suma dels n primers naturals,
– Determinar, si existix, una paraula en el diccionari,
– Demanar a l'usuari un valor dins d'un rang,
– Codificar un text canviant cadascuna de les seues lletres,
– ….
25/10/2011 IIP - Curs 2011/12 3
Introducció
• Els llenguatges de programació disposen d'instruccions de repetició: els bucles.
• Els bucles permeten repetir l'execució d'una seqüència d'instruccions tantes vegades com siga necessari.
• Bàsicament, es tracta de repetir un bloc d'instruccions, anomenat cos del bucle, mentre certa condició s'avalue a verdader. Aquesta condició es coneix com a guarda del bucle.
• Iteració o passada del bucle: Cada vegada que s'executa el cos del bucle.
• Bucle: Conjunt d'instruccions tals que la seua execució es repetix fins que es verifica una condició de terminació o eixida.
25/10/2011 IIP - Curs 2011/12 4
La iteració
• Independentment de la complexitat d'un problema, la seua solució ha de complir les condicions següents:
– Les instruccions que la componen deuen descriure's de manera finita, i
– la seua execució també ha de ser finita.
• Per a resoldre molts problemes senzills (com els dels temes anteriors) basta amb simples seqüències d'instruccions.
• Però en altres problemes resulta imprescindible que algunes instruccions es repetisquen per a poder resoldre’ls.
25/10/2011 IIP - Curs 2011/12 5
La iteració • Si la repetició és necessària, al resoldre el problema es deu:
– Detectar patrons de comportament que es repetisquen i
– Expressar la solució del problema, a partir de l'anterior, fent ús de les instruccions de repetició.
• Per exemple, suposem que no disposem de l'operador de multiplicació i hem d'implementar el càlcul del producte d’a per n, basant-se en sumes (sent n un valor no negatiu).
25/10/2011 IIP - Curs 2011/12 6
a*n == 0 + a + a + a + . . . + a
n
a*n == a + a + a + . . . + a si n>0 a*n == 0 si n==0
n
La iteració
• Per a la solució, es pot utilitzar una variable acumulador que,
iteració a iteració, continga successivament, els valors:
0*a, (iteració 0)
1*a, (iteració 1)
2*a, (iteració 2)
…
n*a, (iteració n-èsima)
• On, en qualsevol iteració, el valor de la variable acumulador
podrà obtindre's del de la prèvia per mitjà de l'operació:
• El patró de repetició consistix en que en la i-èsima repetició el valor de la variable acumulador és precisament i*a.
25/10/2011 IIP - Curs 2011/12 7
acumulador = acumulador + a;
La iteració: elements
• En qualsevol implementació d'un bucle cal distingir tres elements, que són els components estructurals bàsics de tota iteració:
– La guarda del bucle: Condició que mentre s’avalue a verdader implicarà la repetició de l'execució del cos del bucle (bloc d'instruccions).
– El cos del bucle: les instruccions que permeten avançar pas a pas cap a la solució del problema.
– La inicialització de variables: Abans d'entrar en el bucle s'ha d'assignar valors ben definits a totes les variables involucrades en l'execució del bucle.
25/10/2011 IIP - Curs 2011/12 8
La iteració: elements
• Estructuralment, una forma habitual d'iteració, tenint en compte els components mencionats, sol ser com seguix :
Inicialització de variables
mentre guarda del bucle
cos del bucle
• En Java aquesta forma d’iteració és de la forma:
Inicialització de variables
while (guarda del bucle) {
cos del bucle
}
25/10/2011 IIP - Curs 2011/12 9
La iteració: elements
• Si s'identifiquen els elements de l'estructura per a l'exemple anterior es té que: – Inicialització de variables:
– Cos del bucle:
– Guarda del bucle (o condició de continuació):
• Note's l'ús de la variable numIteració per a poder expressar la terminació / continuació del bucle
25/10/2011 IIP - Curs 2011/12 10
acumulador = 0; numIteració = 0;
acumulador = acumulador + a; numIteració++;
numIteració < n
La iteració: estructura repetitiva
• Els detalls més importants a tindre en compte quan es programa un bucle són: A. Definir l'estructura repetitiva a partir de la propietat que
haurà de complir-se al finalitzar cada iteració individual i que, a l'acabar el bucle, garantix que este proporciona l'efecte desitjat.
Aquesta propietat s’anomena invariant del bucle.
– En l'exemple, l'invariant és el fet que al finalitzar la iteració i-èsima es
complix que acumulador val a*numIteració.
– Per tant, quan numIteració valga n la variable acumulador valdrà a*n
(que és el valor desitjat).
25/10/2011 IIP - Curs 2011/12 11
La iteració: terminació
B. Garantir la condició de parada (que és la inversa de la de continuació o guarda).
És a dir, que alguna de les variables que s'utilitzen en la condició del bucle resulte modificada dins del cos per a assegurar que arribarà un moment en què deixarà de repetir-se.
– En l'exemple es té que:
- A l’acabar la iteració i-èsima: acumulador val a*numIteració
- S’ha d’acabar quan numIteració valga n,
- Condició de terminació: numIteració == n,
- Condició de continuació (guarda): numIteració != n.
25/10/2011 IIP - Curs 2011/12 12
La iteració: exemple MCD
• Considerem ara el problema de determinar el màxim comú divisor de dos números enters: A, B majors que 0.
• L’algorisme, degut a Euclides (300 a.C.), és un dels més antics que es coneixen:
Algorisme MCD, siguen A i B els valors originals de les variables a i b, llavors :
1- Si a i b són iguals, parar; qualsevol d’ells és el MCD.
2- Si a > b substituir a per a – b.
en cas contrari substituir b per b – a.
3- Anar a 1.
25/10/2011 IIP - Curs 2011/12 13
La iteració: exemple MCD
A. La propietat invariant ve donada per: – Al finalitzar cada iteració: MCD(A,B) = MCD(a,b) on A, B representen els valors inicials de les variables a, b – Aquesta propietat és una conseqüència de la propietat matemàtica: MCD(a,b) = MCD(a-b,b), on a i b són distints i a és el major dels dos.
B. Terminació: sempre acaba l’execució?, sempre s’arriba a que a == b?. Sí, perquè en l’algorisme es cumplix que:
– a i b són sempre diferents de 0. – El valor max(a,b) disminuïx estrictament en cada iteració i mai pot ser
menor que 1.
• En general, per a provar que un bucle acaba, s'ha de definir una funció que, conforme itera el bucle, decresca estrictament i que estiga fitada. Aquesta funció s’anomena funció limitadora.
25/10/2011 IIP - Curs 2011/12 14
Instruccions iteratives en Java: instrucció while
Sintaxi:
on:
• B, condició de continuació o guarda, és una expressió lògica,
• S, cos del bucle, és una instrucció qualsevol (fins i tot pot ser un bloc d’instruccions).
25/10/2011 IIP - Curso 2011/12 15
while (B)
S
Instruccions iteratives en Java: instrucció while
25/10/2011 IIP - Curso 2011/12 16
Execució:
• S’executen les instruccions inicials.
• Mentre que la condició B siga certa s’executen les instruccions de S, el cos del bucle.
• Quan la condició B deixa de ser certa, s'acaba l'execució del bucle i es continua en la següent instrucció posterior a la iterativa.
Pot ser les instruccions de S, cos del bucle, no s'executen.
Instruccions inicials
Instruccions següents
S
B
Verdader
Fals
Instruccions iteratives en Java: instrucció for
Sintaxi:
on: • els elements entre claudàtors [] són optatius, • B, la condició o guarda és una expressió lògica, • S, cos del bucle, és una instrucció qualsevol (pot ser un bloc
d’instruccions), • Inici i Avanç són llistes d'instruccions, i1, i2,..., in i a1, a2,...,
am, acabades per comes, que defineixen la inicialització i la progressió del bucle, respectivament.
25/10/2011 IIP - Curso 2011/12 17
for([Inici]; B; [Avanç]) S
25/10/2011 IIP - Curso 2011/12 18
Instrucciones iterativas en Java: instrucció for
Execució:
• S'executen les instruccions inicials.
• Mentre que la condició B siga certa s'executen les instruccions de S, cos del bucle, seguides de les instruccions d'avanç.
• Quan la condició B deixa de ser certa s'acaba l'execució del bucle i es continua en la següent instrucció a la iterativa.
Pot ser que les instruccions del cos, S, i les d’avanç no s'executen.
Instruccions inicials
Instruccions següents
Avanç
B
Verdader
Fals
S
Instruccions iteratives en Java: instrucció for
• És equivalent a una instrucció while:
25/10/2011 IIP - Curso 2011/12 19
[i1 i2 ... in] // Inici
while (B) {
S
[a1 a2 ... am] // Avanç
}
Instruccions iteratives en Java: instrucció do … while …
Sintaxi:
on:
• B, condició de continuació o guarda, és una expressió lògica,
• S, cos del bucle, és una instrucció qualsevol, (fins i tot, pot ser un bloc d’instruccions).
25/10/2011 IIP - Curso 2011/12 20
do
S
while (B);
Instruccions iteratives en Java: instrucció do … while …
25/10/2011 IIP - Curso 2011/12 21
Execució:
• S'executen les instruccions inicials.
• Es repeteix l'execució de les instruccions S, cos del bucle, fins que s'arriba a un estat en què la condició B és falsa.
• En acabar, es continua en la instrucció següent a la iterativa.
S, cos del bucle, s’executa almenys una vegada.
Instruccions inicials
Instruccions següents
S
B Verdader
Fals
Instruccions iteratives en Java: instrucció do … while …
• La diferència respecte al while consistix en: – atés que la guarda es comprova després d'executar cada
passada, en un bucle do … while sempre s'executa almenys la primera passada,
– La sintaxi exigix escriure el símbol ; al final. • Tot problema que es pot expressar amb un bucle do … while, es
pot expressar amb els ajustos necessaris mitjançant un bucle while, i viceversa.
25/10/2011 IIP - Curs 2011/12 22
Instruccions inicials
if (B)
do {
S
} while (B);
Instruccions següents
Instruccions inicials
while (B) {
S
}
Instruccions següents