computación i primer semestre 2006 capítulo iv ciclos y colecciones (con un sabor a algoritmos)
TRANSCRIPT
![Page 1: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/1.jpg)
Computación IPrimer Semestre 2006
Capítulo IV
Ciclos y Colecciones(con un sabor a algoritmos)
![Page 2: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/2.jpg)
El objetivo de este capítulo es que los alumnos aprendar el uso y sintáxis de los ciclos en Java.
Además aprender el uso de grupos de objetos o tipos nativos (llamese colección/lista/arreglo).
Finalmente usar los ciclos para escribir algoritmos de uso frecuente en grupos (principalmente
búsqueda y ordenamiento)
![Page 3: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/3.jpg)
Ciclos
• Un ciclo es un trozo de programa que
se repite mientras una condición sea
verdaderaNumero
Premiar!
Hay bingo?SiNo
Ej: Al jugar Bingo
![Page 4: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/4.jpg)
Ciclo while
…
while (condición) {
Instrucción;
Instrucción;
…
}
…Condición = expresión “booleana”
![Page 5: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/5.jpg)
while, ejemplo factorial
public int factWhile(int n) {
int i = 1;
int result = 1;
while (i < n) {
result = result * i;
i++;
}
return result;
}
Hay errores, cuales ?Hay errores, cuales ?
![Page 6: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/6.jpg)
while, ejemplo factorial
public int factWhile(int n) {
if (n<0) { return (-1); } // error
int i = 1;
int result = 1;
while (i <= n) {
result = result * i;
i++;
}
return result;
}
Si se define “0!=1”, porque no
Necesito evaluar si n vale 0 ?
“if (n ==0) { return (1); }”
Si se define “0!=1”, porque no
Necesito evaluar si n vale 0 ?
“if (n ==0) { return (1); }”
Que valor tiene i después del
ciclo while?
Que valor tiene i después del
ciclo while?
i?
![Page 7: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/7.jpg)
Ciclo for
…
for(iniciación; condición; instrucción de post-ciclo) {
Instrucción;
Instrucción;
…
}
…
![Page 8: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/8.jpg)
for, ejemplo factorial
public int factFor(int n) {
if (n<0) { return (-1); } // error
int result = 1;
for (int i = 1; i <= n; i++) {
result = result * i;
}
return result;
}Que sucede si uso ?
“for (int i = 0; i <= n; i++)”
Que sucede si uso ?
“for (int i = 0; i <= n; i++)”
![Page 9: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/9.jpg)
Factorial recursivo,
ejemplo avanzado
public int factRecurs(int n) {
if (n<0) { return (-1); } // error
if (n == 0) { return (1); }
return (n*factRecursv(n-1));
}
![Page 10: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/10.jpg)
Ejercicio• Dado un valor entero positivo n, calcule
con un ciclo la función de Fibonacci
para n:
• Función de Fibonacci:
f (n)
0
1
f (n 1) f (n 2)
si n 0
si n 1
si n 1
![Page 11: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/11.jpg)
Fibonacci con while (1/2)
public int fibWhile(int n) {
if ( n < 0 ) { return(-1); } //error
int fibSub1 = 0;
int fibSub2 = 1;
int i = 1;
![Page 12: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/12.jpg)
Fibonacci con while (2/2)
while (i<n) {
int aux = fibSub2;
fibSub2 = fibSub2+fibSub1;
fibSub1 = aux;
i++;
}
return (fibSub2);
}
Porqué “i < n” y no “i <= n”?Porqué “i < n” y no “i <= n”?
![Page 13: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/13.jpg)
Fibonacci con for (1/2)
public int fibFor(int n) {
if ( n < 0 ) { return(-1); } //error
int fibSub1 = 0;
int fibSub2 = 1;
![Page 14: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/14.jpg)
Fibonacci con for (2/2)
For (int i=0;i < n; i++) {
int aux = fibSub2;
fibSub2 = fibSub2+fibSub1;
fibSub1 = aux;
}
return (fibSub2);
}
Que valor tiene i después del
ciclo for?
Que valor tiene i después del
ciclo for?
![Page 15: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/15.jpg)
Fibonacci recursivo
ejemplo avanzado
public int fibRecurs(int n) {
if (n<0) { return(-1); } //error
if (n==0) { return(0); }
if (n==1) { return(1); }
return (fibRecurs(n-2)+fibRecurs(n-1));
}
![Page 16: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/16.jpg)
Ejemplo usando Fibonacci
Golden rate
• Se define el golden rate de Fibonacci
como:
limn
f (n 1)
f (n)
Implemente un método que calcule el golden rate con una
precisión dada como parámetro
* ojo: es una serie convergente, demuéstrelo si lo desea
![Page 17: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/17.jpg)
Golden rate
• Que quiere decir precisión?
– Que la diferencia entre un término de la serie y el
anterior sea menor que valor dado (la precisión)
• Como resolvemos el problema?
– Calculando sucesivamente el golden rate hasta
que la diferencia entre dos sucesiones sea menor
que la precisión dada como parámetro
![Page 18: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/18.jpg)
Golden Ratepublic double goldenRatio(double pres) {
int i = 1;
double error=1000;
double ratio=0;
while (error>pres) {
double aux = ratio;
ratio = ((double)fibFor(i+1))/((double)fibFor(i));
error = Math.abs(ratio-aux);
i++;
}
return(ratio);
}
CastingCasting
¿Porque i desde 1 y no 0?¿Porque i desde 1 y no 0?
¿Se puede implementar usando for?¿Se puede implementar usando for?
![Page 19: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/19.jpg)
Ejercicios propuestos: Implemente
métodos que resuelvan:
ii0
N
i2
i0
N
• Las sumatorias y usando while y for para ambos casos
• Calcular el máximo común divisor usando el método de Euclides (ver slide
siguiente).
• Determinar si un número es primo (un primo es un número divisible sólo por
si mismo)
• Descomponer un número en sus factores primos (hint: use el método
anterior)
![Page 20: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/20.jpg)
mcd de Euclides1071 1029 Coloque el numero más grande a la izquierda y
el otro a la derecha
1029 42 El residuo de 1071/1029 es 42. Coloque 42 en la derecha y traslade 1029 a la izquierda
42 21 Se repite el paso anterior hasta que el numero de la derecha es 0
21 0 El numero a la izquierda es el máximo común divisor
![Page 21: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/21.jpg)
Arreglos
• Un arreglo es un grupo “indexado” de
elementos del mismo tipo.N elementos
0 321 n-3 n-1n-2
elementoelemento
índiceíndice
Los arreglos siempre
Empiezan con el índice 0!
Los arreglos siempre
Empiezan con el índice 0!
![Page 22: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/22.jpg)
Declarando arreglos
int numeros[];Tipo
Variable
Indica que
Es arreglo
Inicializando arreglos
numeros = new int[55];
Tamaño
del arreglo
![Page 23: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/23.jpg)
Modificando y accediendo a
elementos del arreglonumeros[0] = 10;
numeros[5] = 18;
numeros[3] = 2;
numeros[13]=numeros[3]*numeros[0]+numeros[5];
numeros[13]++;
System.out.println(numeros[13]);
Que valor se imprime en pantalla?Que valor se imprime en pantalla?
Largo de un arreglo:
numeros.length
Largo de un arreglo:
numeros.length
En este ejemplo, cuánto vale numeros.lenght?En este ejemplo, cuánto vale numeros.lenght?
![Page 24: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/24.jpg)
Arreglos de Objetos// declarar arreglo
Factorial numeros[];
// inicializar arreglo
numeros = new Factorial[n];
// inicializar elementos
numeros[3] = new Factorial();
// acceder a funciones
int x = numeros[3].factWhile(15);
![Page 25: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/25.jpg)
Usando arreglos: Clase Pila
• Una Pila es un objeto al que se le
agregan y sacan elementos, tal que el
elemento a sacar es el último en ser
puesto (conocido como orden LIFO, last
in first out)
poner sacar
Pila
![Page 26: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/26.jpg)
Implementación Clase Pila
• Se quiere implementar una clase Pila
con los métodos poner y sacar para
enteros.
• Que necesitamos ?
• Un arreglo de enteros para guardar los elementos
• Un índice que nos indique el último elemento agregado
![Page 27: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/27.jpg)
Clase Pila(1/3)
public class Pila {
…}
this.last = -1;
this.valores = new int[n];
public Pila(int n) {
private int last;
private int valores[];
![Page 28: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/28.jpg)
…
public void poner(int elem) {
más elementos, la pila está llena");
// otra: valores[++last] = elem;
}
…}
valores[last] = elem;
last++;
} else {
System.out.println("No puede agregar
if (last >= valores.length-1) {
Clase Pila(2/3)
![Page 29: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/29.jpg)
…
public int sacar() {
más elementos, la pila está vacía");
}…
}
// otra: return valores[last--];
return aux;
last--;
int aux = valores[last];
} else {
return(-1);
System.out.println("No puede sacar
if (last < 0) {
Clase Pila(3/3)
![Page 30: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/30.jpg)
Usando arreglos: Clase Lista
• Una Lista es un objeto al que se le
agregan y sacan elementos, tal que el
elemento a sacar es el más anciano en
ser puesto (conocido como orden FIFO,
first in first out)
Fila
Poner Sacar
![Page 31: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/31.jpg)
Implementación Clase Lista
• Se quiere implementar una clase Lista
con los métodos poner y sacar para
enteros.
• Que necesitamos ?• Un arreglo de enteros para guardar los elementos
• Un índice que nos indique el elemento a sacar (cabeza)
• Un índice que nos indique el próximo espacio para
agregar (cola)
![Page 32: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/32.jpg)
Listas
cabeza cola
cabeza cola
cabeza cola
En un momento la fila está:
Poner:
Sacar:
![Page 33: Computación I Primer Semestre 2006 Capítulo IV Ciclos y Colecciones (con un sabor a algoritmos)](https://reader035.vdocumento.com/reader035/viewer/2022062520/5665b4731a28abb57c9190e7/html5/thumbnails/33.jpg)
Listas
cabeza cola
Poner?, donde apuntará cola?
?
cabezacola