Download 3. Estructuras iterativas

3. Estructuras iterativas
Fundamentos de Informática
Dpto. Lenguajes y Sistemas Informáticos
Curso 2012 / 2013
Índice
Estructura iterativas
1.
2.
3.
4.
5.
Análisis de algoritmos iterativos
Ej11: While
Ej12: For
Ej13: Do - Loop
Resumen
2
Iterativas
Análisis
1.1 Problemas iterativos
• No pares hasta que tengas 145 pulsaciones por minuto
• Vas a dar diez vueltas al campo
• Calcula la media: suma todas las notas de la asignatura y
divide entre el número de alumnos (contar)
• Busca un número que cumpla unas condiciones
– ¿Uno? ¿Todos?
– ¿En qué dominio?
• Cuenta los votos de la urna
– Mientras queden votos
– Hasta que no quede ningún voto
• Operaciones con cadenas de caracteres
• Hasta que encuentres la cartera no sales de casa
3
Iterativas
Análisis For
1.2 Análisis: For
•
¿Puedo determinar de antemano cuántas veces se ha de
ejecutar el cuerpo (“…”)?
– Sí: entonces utilizar una estructura For
•
Utiliza un contador i. Se divide en tres cláusulas:
1. Inicialización: dar un valor inicial ini al contador i
2. Condición: se verifica si el contador i ha llegado al fin
3. Actualización: se incrementa el contador i el paso p
For i = ini To fin Step p
i ← ini
i←i+p
i ≤ fin
no
. . .
Next i
sí
…
4
Iterativas
Análisis For
For: decreciente
• En vez de contar i también puede descontar:
1. Inicialización: dar un valor inicial top al contador i, que
será el valor superior
2. Condición: se verifica si el contador i ha llegado al fin
(mientras i ≥ fin)
3. Actualización: se decrementa el contador i el paso p,
que es negativo
For i = top To fin Step -p
i ← top
i←i-p
i ≥ fin
no
. . .
Next i
sí
…
5
Iterativas
Análisis For
For: Escribir números del 1 al 10 (incremento)
i←1
i←i+1
i ≤ 10
sí
Escribe i
no
Sub Escribe_Click()
Dim i As Integer
For i = 1 To 10 Step 1
pct1.Print CStr (i)
Next i
End Sub
6
Iterativas
Análisis For
For: Escribir números del 10 al 1 (decremento)
i ← 10
i←i-1
i≥1
no
sí
Escribe i
For i = 10 To 1 Step -1
pct1.Print CStr (i)
Next i
7
Iterativas
Análisis While
1.3 Análisis: While
• Si no puedo determinar de antemano cuántas veces se ha
de ejecutar el cuerpo,
For
• ¿Puedo terminar directamente?
• ¿Quiero que se ejecute cero o más veces?
– Sí: estructura While
sí
…
While
cond
sí
…
no
no
While cond
. . .
Wend
8
Iterativas
Análisis While
Escribir números del 1 al 10 (incremento) utilizando While
i←1
i ≤ 10
Lo normal es utilizar una estructura For ya que el
propósito es más claro, pero aquí queremos
comparar las dos estructuras
no
i = 1
While i <= 10
sí
pct1.Print CStr (i)
Escribe i
i = i + 1
i←i+1
Wend
i←1
i←i+1
i ≤ 10
sí
no
For i = 1 To 10 Step 1
pct1.Print CStr (i)
Escribe i
Next i
9
Iterativas
Análisis Do-Loop
1.4 Análisis: Do-Loop
• Si no puedo determinar de antemano cuántas veces se ha
For
de ejecutar el cuerpo
• Y no puedo terminar directamente
no
• ¿Quiero que se ejecute al menos una vez?
sí
– Sí: estructura Do – Loop While / Until
…
While
Do - Loop
While/Until
Do
no
sí
…
Do
…
. . .
Loop While cond
. . .
sí
no
cond
Loop Until cond
no
sí
10
Iterativas
Análisis Do-Loop
Escribir números del 1 al 10 utilizando Do – Loop While
i←1
Escribe i
Lo normal es utilizar una estructura For ya que el
propósito es más claro, pero aquí queremos
comparar las dos estructuras
i = 1
Do
i←i+1
pct1.Print CStr (i)
i = i + 1
sí
i ≤ 10
Loop While i <= 10
no
11
Iterativas
Análisis Do-Loop
Escribir números del 1 al 10 utilizando Do – Loop Until
i←1
Escribe i
Lo normal es utilizar una estructura For ya que el
propósito es más claro, pero aquí queremos
comparar las dos estructuras
i = 1
Do
i←i+1
pct1.Print CStr (i)
i = i + 1
no
i > 10
Loop Until i > 10
sí
12
Iterativas
Ej11: While
2. Ejemplo 11
• Título:
– Iterativa While (mientras)
• Nombre
– cmd11_Click
• Descripción
– Calcular la primera potencia de 2 mayor o igual que
un número natural dado
• Observaciones
– Cero o más veces: While
– Productorio (Pi mayúscula, Π)
While
no
sí
…
13
Iterativas
Ej11: While
Ej11: Diagrama de Flujo
cmd11_Click
n, p: entero
n ← LeeEntero
Condición de
parada
Inicialización al elemento neutro
p←1
p<n
sí
p←p·2
Cuerpo simple
Iterativa While
no
Escribe p
Fin
14
Iterativas
Ej11: Codificación VB
Ej11: While
cmd11_Click
n, p: entero
Sub cmd11_Click()
n ← LeeEntero
Dim s As String
Dim n As Integer, p As Integer
p←1
s = InputBox ("Número:")
n = CInt (s)
p<n
Iterativa While
p = 1
sí
While p < n
p←p·2
p = p * 2
Wend
MsgBox "Potencia: " & p
Cuerpo indentado
End Sub
no
Escribe p
Fin
15
Iterativas
Ej12: For
Salida para n = 8
i f
- 1: 1
2: 3
3: 6
4: 10
5: 15
6: 21
7: 28
8: 36
4. Ejemplo 12
• Título:
– Iterativa For (para)

f =

• Nombre
– cmd12_Click

i

∑
i =1 
n
• Descripción
– Escribir las sumas parciales de los n primeros términos
de una progresión a1= 1 y ai=ai-1+i para todo i > 1
• Observaciones
– Número n de veces: For
– Sumatorio (Sigma mayúscula, Σ)
Do-Loop
While
no
no
sí
…
…
sí
…
For
sí
no
16
Iterativas
Ej12: For
Ej12: Diagrama de Flujo
Ej12
Inicialización
Condición
i, n: entero
f: entero
n ← LeeEntero
Actualización

f =


i
∑
i =1 
n
f←0
Iterativa For
i←1
i ← i+1
i≤n
sí
f←f+i
Escribe i, f
no
Fin
Cuerpo del For
17
Iterativas
Ej12: For
Ej12: Codificación VB
cmd12_Click
Inicialización
Condición
Sub cmd12_Click()
Actualización
Dim s As String
Dim i As Integer, n As Integer
Dim f As Integer
s = InputBox ("Número:")
n = CInt (s)
f = 0
For i = 1 To n Step 1
f = f + i
pct1.Print CStr (i) & ": " & _
CStr (f)
Next i
End Sub
i, n: entero
f: entero
n ← LeeEntero
f←0
i←1
i ← i+1
i≤n
no
sí
f←f+i
Fin
Escribe i, f
18
Iterativas
Ej13: Do-Loop
3. Ejemplo 13
• Título:
– Iterativa do-while (haz-mientras)
• Nombre
– cmd_Click13
• Descripción
– Sumar una serie de números introducidos del
teclado hasta introducir un cero.
• Observaciones
– Una o más veces: Do-Loop
– Contar
Do-Loop
While
…
no
sí
sí
…
no
19
Iterativas
Ej13: Do-Loop
Ej13: Diagrama de Flujo
cmd13_Click
t, n: entero
t←0
Cuerpo del Do-Loop
n ← LeeEntero
Iterativa Do-Loop
t←t+n
sí
n≠0
Condición de
parada Until
no
Condición de
parada While
Escribe t
no
n=0
sí
Fin
20
Iterativas
Ej13: Do-Loop
Ej13: Codificación VB
Sub cmd13_Click()
Dim s As String
Dim n As Integer, t As Integer
t = 0
Do
s = InputBox ("Número:")
n = CInt (s)
t = t + n
Loop While n <> 0
MsgBox CStr (t)
End Sub
cmd13_Click
t, n: entero
t←0
n ← LeeEntero
t←t+n
sí
n≠0
no
Escribe t
Fin
21
Iterativas
Resumen
5. Resumen
• Ejemplos básicos
– Inicializar al elemento neutro y realizar la operación iterativa
• Patrones de operaciones
–
–
–
–
–
Sumar. Elemento neutro: 0
Contar. Elemento neutro: 0
Producto. Elemento neutro: 1
Concatenación. Elemento neutro: cadena vacía
Búsqueda. Elemento neutro: False.
For
While
…
no
no
sí
…
Do-Loop
sí
…
sí
no
22