1 Programación Orientada a Objetos EIF200 FUNDAMENTOS DE INFORMÁTICA Proyecto 0151-14 UNA – Mora & Coto, 2015 Compilado por: Mag. Sonia Mora. Dra. Mayela Coto.

2 Problema  Suponga que su profesor de Fundamentos desea realizar un análisis de las calificaciones obtenidas durante el I examen parcial. En particular desea: 1. Calcular el promedio de calificación obtenido 2. Encontrar la calificación más alta y la más baja. 3. Determinar cuántos estudiantes tuvieron una calificación superior a 8, cuántos una calificación entre 6 y 8, y cuántos una calificación inferior a 6.

3 Problema  ¿Cómo podemos resolverlo?  ¿Qué estructuras de programación son necesarias?  ¿Qué estructuras de datos son necesarias? ARREGLOS

4 Arreglos  Se utilizan cuando se necesita almacenar múltiples valores del mismo tipo.  Permiten agrupar muchos datos usando un mismo identificador.  El tamaño o el número de elementos de un arreglo debe ser constante y debe ser declarado con anterioridad.  La memoria utilizada por los arreglos se conoce como memoria estática.

5 Arreglos  En el POO vamos a desarrollar colecciones  Estas clases tienen como atributos estructuras o arreglos multidimensionales.  En este curso se estudiarán arreglos unidimensionales (vectores) y bidimensionales (matrices)  Hay varias formas de definirlos: Arreglos estáticos de longitud fija o de “longitud variable”.

6 Arreglos unidimensionales Un arreglo es un grupo de posiciones en memoria relacionadas entre sí, por el hecho de que todas tienen el mismo nombre y son del mismo tipo. Se utilizan cuando se necesita almacenar y procesar múltiples valores del mismo tipo. Permiten agrupar datos usando un mismo identificador. Ejemplo: int valores[5] 25414335 [0] [1] [2] [3] [4]

7 Arreglos unidimensionales Para referirse a una posición en particular o elemento dentro del arreglo, se especifica el nombre del arreglo y el número de posición del elemento particular dentro del mismo (un índice entero) El índice de los arreglos inicia en cero (0), el primer elemento de un arreglo tendrá siempre índice cero (0), mientras que el último elemento tiene como índice la longitud del arreglo menos uno. int a = valores[3]  a = 14 valores[2] = 100  254141005 [0] [1] [2] [3] [4] 25414335 [0] [1] [2] [3] [4]

8 Arreglos unidimensionales  Para crear arreglos en C++, hay que indicar: El tipo de los elementos  ejemplo: int, char, float, bool, string  o un tipo definido por el programador El nombre del arreglo El tamaño del arreglo, entre [ ] Sintaxis [tamaño];

9 Arreglos unidimensionales  Declaración char vector[4]; // forma una secuencia de cuatro elementos de tipo char  Nombre del grupo: vector  Nombre de los elementos vector[0] → primer elemento vector[1] → segundo elemento vector[2] → tercer elemento vector[3] → cuarto elemento

10 Arreglos unidimensionales  El tamaño o el número de elementos de un arreglo debe ser determinado y es declarado con anterioridad, en tiempo de compilación o en tiempo de ejecución (mediante punteros).  Para recorrer un vector es necesario usar un ciclo.  El ciclo clásicamente usado para recorrer un arreglo es un ciclo for.

11 Arreglos unidimensionales  Un arreglo unidimensional por lo general es llamado vector.  Una colección es una clase que “contiene” elementos con algún significado.  Vamos a definir colecciones que almacenan datos de un mismo tipo, de forma particular: a través de un vector.

12 Clase Colección class Coleccion { private: int vector[50]; int tamano; int cantidad;. } Atributo que indica el tamaño real del vector de acuerdo a las necesidades particulares del usuario Atributo que indica la cantidad de elementos que el vector tiene en uso en un momento dado Número máximo de elementos del vector

13 Clase Colección: métodos constructores class Coleccion { private: int vector[50]; int tamano; int cantidad; public: Coleccion() { cantidad=0; tamano= 50; for(int i=0;i< tamano;i++) vector[i]=0; } Coleccion(int n) { cantidad=0; tamano= n; for(int i=0;i< tamano;i++) vector[i]=0; } Dos tipos de constructores class Coleccion { private: int vector[50]; int tamano; int cantidad;

14 Clase Colección: métodos set y get int getCantidad() {return cantidad;} int getTamano() { return tamano; } void setCantidad(int can) { if ((can 0)) cantidad = can; } void setTamano(int ptamano) // NO se implementa { tamano = ptamano; } class Coleccion { private: int vector[50]; int tamano; int cantidad;

15 Clase Colección: creación de objetos int main() { int n; cout

16 Clase Coleccion  Para que la colección Numeros sea útil, debemos tener la capacidad de “administrarlo”.  De esta manera se requieren métodos para: imprimir el contenido realizar operaciones con sus valores insertar un elemento en el vector eliminar un elemento en el vector buscar un elemento en el vector etc…… class Coleccion { private: int vector[50]; int tamano; int cantidad;

17 Clase Colección: insertar Elemento void insertarEle(int elem ) { if (cantidad < tamano) {vector[cantidad]=elem; setCantidad(cantidad+1); } Este método agrega un elemento al vector y modifica la cantidad de elementos que el vector contiene [0] [1] [2] [3] [4] [5] [6] [7] [49] Numeros 250000000 Si n=8 cantidad=1 vector … tamano=8 En el main Numeros.insertarEle(25); class Coleccion { private: int vector[50]; int tamano; int cantidad;

18 insertar Elemento versión mejorada bool insertarEle(int elem ) { if (cantidad < tamano) {vector[cantidad]=elem; setCantidad(cantidad+1); return true; } else return false; } En el main if (! Numeros.insertarEle(25)) cout

19 Clase Coleccion  Escriba la sección del main() que permita agregar en el vector (usando el método anterior) valores digitados por el usuario. class Coleccion { private: int vector[50]; int tamano; int cantidad;

20 Clase Coleccion …… // recuerde que la colección Numeros ya fue creado int num,cont,k,elem; coutnum; cont=0; while (cont

21 Clase Colección: toString()  En la clase Coleccion escriba un método para mostrar los elementos de un vector (debe incluir ) string toString(){ stringstream s; for(int i=0;i

22 Clase Colección: eliminar elementos  En la clase Coleccion escriba un método que permita eliminar el último elemento del arreglo class Coleccion { private: int vector[50]; int tamano; int cantidad;

23 Clase Colección: eliminar último elemento void eliminarEle( ) { setCantidad(cantidad-1); } Este método modifica la cantidad de elementos que el vector contiene Numeros 258411061200 Cantidad=5 [0] [1] [2] [3] [4] [5] [6] [7] «basura» En el main Numeros.EliminarEle(); class Coleccion { private: int vector[50]; int tamano; int cantidad; vector

24 Clase Colección: suma de elementos  Haga un método que sume los elementos de la colección. int sumarEle() { int suma=0; for(int i=0; i

25 Clase Colección: media de elementos  En la clase Coleccion escriba un método para calcular la media de sus elementos float media() { int suma=0; for(int i=0; i

26 En el main cout

27 Casting necesario float media() { return sumarEle()/cantidad; } float media() { return (float) sumarEle()/cantidad; } Al ser enteros C++ retorna un valor entero casting

28 Clase Colección: valor máximo  En la clase Coleccion escriba un método que retorne el valor máximo del vector. class Coleccion { private: int vector[50]; int tamano; int cantidad;

29 int valorMax(){ int max = vector[0]; for(int i=1; imax){ max=vector[i]; } return max; } En el main cout

30 Clase Colección: posición del mayor  En la clase Coleccion escriba un método que retorne la posición del vector en el que se encuentra el valor máximo class Coleccion { private: int vector[50]; int tamano; int cantidad;

31 int posMax() { int posic=0; int max=vector[0]; for(int i=1; imax) { posic= i; max=vector[i]; } return posic; } En el main cout

32 Clase Colección: posición del menor  En la clase Coleccion escriba un método que retorne la posición del vector en el que se encuentra el valor mínimo class Coleccion { private: int vector[50]; int tamano; int cantidad;

33 int posMin() { int posic=0; int min=vector[0]; for(int i=1; i

34 Clase Colección: intercambio mínimo y máximo  En la clase Coleccion escriba un método que intercambie los valores máximo y mínimo del vector class Coleccion { private: int vector[50]; int tamano; int cantidad;

35 void intercambiaMaxMin() { int i,j, aux; i=posMax(); j=posMin(); aux= vector[i]; vector[i]=vector[j]; vector[j]=aux; } En el main cout

36 Clase Colección: invertir elementos  En la clase Coleccion escriba un método para invertir los elementos de un vector  Por ejemplo: 46982 [0] [1] [2] [3] [4] vector 29684 [0] [1] [2] [3] [4] class Coleccion { private: int vector[50]; int tamano; int cantidad; vector

38 Clase Colección: intercambiar dos posiciones Otra forma: Primero necesitamos un método que nos permita intercambiar dos posiciones determinadas void intercambiaPos( int i, int j) { int temp; temp = vector[i]; vector[i] = vector[j]; vector[j]=temp; } class Coleccion { private: int vector[50]; int tamano; int cantidad;

39 void invertirEle() { int k,i; for(i=0,k=cantidad-1; i

40 Clase Colección: encontrar un elemento  En la clase Coleccion escriba un método que retorne true si un elemento determinado se encuentra en el arreglo y false si no. class Coleccion { private: int vector[50]; int tamano; int cantidad;

41 Clase Colección: encontrar un elemento bool encuentraElemento(int elem) { for (int i=0;i

42 Clase Colección: búsqueda de la posición  En la clase Coleccion escriba un método que retorne la posición de un elemento determinado en el arreglo. Si el elemento no se encuentra retorna -1. class Coleccion { private: int vector[50]; int tamano; int cantidad;

43 int encuentraPosElemento(int elem) { for (int i=0; i

44 Clase Colección: eliminar un elemento  En la clase Coleccion escriba un método que permita eliminar el elemento en la posición x del arreglo. x=2 Numeros 258411061200 Cantidad=6 Tamano=8 [0] [1] [2] [3] [4] [5] [6] [7] Numeros 25864112000 Cantidad=5 Tamano=8 [0] [1] [2] [3] [4] [5] [6] [7] class Coleccion { private: int vector[50]; int tamano; int cantidad; vector

45 Clase Colección: eliminar un elemento void eliminarElementoPos(int pos) { for (int i=pos;i

46 Clase Colección: insertar un elemento en 1 posición  En la clase Coleccion diseñe un método que permita insertar el valor x en el lugar k-ésimo de un vector, produciendo un corrimiento hacia la derecha de los restantes elementos. Ejemplo: si el vector y el llamado es insertarElePos(15,4), el vector quedaría como: Suponga que el tamaño definido del vector permite la inserción. 258411061200 [0] [1] [2] [3] [4] [5] [6] [7] 2584110156120 [0] [1] [2] [3] [4] [5] [6] [7] Cantidad=6 Tamano=8 Cantidad=7 Tamano=8 class Coleccion { private: int vector[50]; int tamano; int cantidad;

47 Clase Colección: insertar un elemento en 1 posición void insertarElePos(int elem, int pos) { for (int i=cantidad; i>pos; i--) vector[i] = vector[i-1]; //hace un corrimiento a la derecha para abrir espacio vector[pos] = elem; cantidad++; } En el main cout >elem>>pos; Numeros.insertaElemPos(elem,pos); Numeros.toString(); class Coleccion { private: int vector[50]; int tamano; int cantidad;

48 Tarea para entregar  En la clase Coleccion Escriba un método que reciba dos elementos a y b y reemplace cada ocurrencia del elemento a por el b. Escriba un método que reciba un elemento y devuelva el número de veces que aparece el elemento en el arreglo. class Coleccion { private: int vector[50]; int tamano; int cantidad;

49 EIF200 FUNDAMENTOS DE INFORMÁTICA ORDENAMIENTO Imagen de ordenamiento por Nmnogueira en English Wikipedia (Own work by uploader using Matlab) [CC BY-SA 2.5 (http://creativecommons.org/licenses/by-sa/2.5)], via Wikimedia Commons. Imagen de Lupa de Dominio Público

50 Problema  Se requiere ordenar las notas del I examen parcial de menor a mayor, ya que de esta forma es más sencillo identificar cuántos estudiantes necesitan ayuda extra.  Hay varias formas de resolver el problema de ordenamiento

51 Clase Coleccion  En la clase Coleccion escriba un método para ordenar los elementos de un vector  Por ejemplo: 46982 [0] [1] [2] [3] [4] vector 24869 [0] [1] [2] [3] [4] class Coleccion { private: int vector[50]; int tamano; int cantidad; vector

52 Ordenamiento de burbuja (bubble sort) Algoritmo de ordenamiento más sencillo. Revisa cada elemento del arreglo que va a ser ordenado con el siguiente elemento, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda el arreglo hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas".

53 Ordenamiento burbuja Created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania. Directed by Kátai Zoltán and Tóth László. In cooperation with "Maros Művészegyüttes", Tirgu Mures (Marosvásárhely), Romania. Choreographer: Füzesi Albert. Video: Lőrinc Lajos, Körmöcki Zoltán. Supported by "Szülőföld Alap", MITIS (NGO) and evoline company. https://www.youtube.com/v/lyZQPjUT5B4?start=52&end=2 36&autoplay=1

54 Ordenamiento de burbuja (bubble sort) Imagine que el arreglo a ordenar se coloca verticalmente y que los objetos menos “pesados” suben más rápidamente hacia el tope del arreglo como las burbujas menos pesadas lo hacen a la superficie. Se hacen repetidas pasadas sobre el arreglo. Si dos objetos adyacentes están desordenados entonces se intercambian de posición. El efecto de esta operación es que en el primer pase el objeto más “pesado” es llevado hacia la última posición; en el segundo pase, el segundo objeto más pesado es llevado a la penúltima posición y así sucesivamente. De forma general en la pasada i-ésima, el i-ésimo objeto menos “pesado” es llevado a la posición i.

55 Clase Coleccion void OrdenBurVector() //ordena el vector por el método burbuja { int aux,i,j; for (i =cantidad-1; i > 0; i--) for(j = 0; j vector[j+1]) { aux = vec[j]; vector[j] = vector[j+1]; vector[j+1] = aux; } En el main A.OrdenBurVector(); cout

56 Ordenamiento por selección Created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania. Directed by Kátai Zoltán and Tóth László. In cooperation with "Maros Művészegyüttes", Tirgu Mures (Marosvásárhely), Romania. Choreographer: Füzesi Albert. Video: Lőrinc Lajos, Körmöcki Zoltán. Supported by "Szülőföld Alap", MITIS (NGO) and evoline company. https://www.youtube.com/v/Ns4TPTC8whw?start=7&end=387& autoplay=1

57 Ordenamiento por selección  Es uno de los algoritmos más intuitivos de ordenamiento.  Consiste en lo siguiente: Si el vector consta de «cantidad» elementos, encuentre el elemento de menor valor e intercámbielo con la posición 0, luego tome el menor elemento a partir de la posición 1 e intercámbielo con el de la posición 1 y así sucesivamente hasta intercambiar el menor elemento entre la posición «cantidad-1» y «cantidad» y ubicarlo en la posición «cantidad-1».

58 Ordenamiento por selección void OrdenaSeleccion() { int i, k, posMenor, temp; for(k = 0; k < cantidad-1; k++) { posMenor = k; for(i = k+1; i < cantidad; i++) if(vector[i] < vector[posMenor]) posMenor = i; if(posMenor != k) { temp = vector[posMenor]; vector[posMenor] = vector[k]; vector[k] = temp; } } class Coleccion { private: int vector[50]; int tamano; int cantidad;

59 The sound of sorting  Burbuja https://youtu.be/Cq7SMsQBEUw  Selección https://youtu.be/92BfuxHn2XE por Timo Bingmann

60 EIF200 FUNDAMENTOS DE INFORMÁTICA BÚSQUEDA

61 Problemas de búsquedas  Búsquedas en arreglos: Tiempo Eficacia Eficiencia  Posibles soluciones: Arreglos ordenados (vs costo de ordenarlos) Búsquedas especiales

62 Búsqueda de un elemento en un arreglo ordenado  Si se quiere buscar un elemento en un arreglo ordenado, NO hace falta recorrer todo el arreglo para determinar que el elemento no se encuentra Ejemplo: si el vector y se quiere buscar el valor 15, en el momento que se encuentra el valor 21 (21>15) se puede detener la búsqueda  Escriba un método que retorne true si el elemento se encuentra en el arreglo y false si no 382110365200 [0] [1] [2] [3] [4] [5] [6] [7] Cantidad=6 Tamano=8 class Coleccion { private: int vector[50]; int tamano; int cantidad;

63 Búsqueda de un elemento en un arreglo ordenado bool encuentraElemOrdenado(int elem) { if (elem vector[cantidad - 1]) return false; else { for (int i = 0; i

64 Búsqueda binaria  Se utiliza en arreglos ordenados.  Consiste en tomar el objeto que ocupa en el arreglo la posición del medio (si la cantidad de objetos es impar se toma el que ocupa la posición mitad - 1)  Se comparan los elementos: Si el objeto que se busca es mayor entonces hay que buscarlo en la mitad de la derecha. y si es menor se busca en la mitad de la izquierda. Este proceso se repite hasta encontrar el número o concluir que no está.

65 Intervalo de búsqueda vector 2481012137 INI FIN MED = ( INI + FIN) / 2 = (0 + 6 ) / 2 = 3 1023456 Elem 7 Búsqueda binaria 2481012137 1023456

66 Intervalo de búsqueda vector 2481012137 INI FIN MED = ( INI + FIN) / 2 = (0 + 2 ) / 2 = 1 1023456 Elem 7 Búsqueda binaria 2481012137 1023456

67 67 Intervalo de búsqueda vector 2481012137 INI FIN MED = ( INI + FIN) / 2 = (2 + 2 ) / 2 = 2 1023456 Elem 7 Búsqueda binaria

68 bool busquedaBinaria(int elem) { int inicio=0; int fin=cantidad-1; int mitad; while (inicio vector [mitad]) inicio = mitad+1; else fin = mitad -1; } return false; } class Coleccion { private: int vector[50]; int tamano; int cantidad;

69 EIF200 FUNDAMENTOS DE INFORMÁTICA PARÁMETROS

70 Parámetros  Recuerde…. La sintaxis que se usa para definir un método es la siguiente: ([ ]) { }

71 Parámetros  Un parámetro es un tipo de variable que es recibida por un método.  Un parámetro influye en el comportamiento o el resultado de la ejecución del método que lo recibe.  Tipos: Parámetros de Entrada: contienen datos que son pasados al método desde el código llamador. Parámetros de Salida: contienen datos que son calculados dentro del método y retornados al código llamador. Parámetros de Entrada/Salida: reciben datos desde el código llamador, se modifican los datos, y se retornan al código llamador.

72 Paso de parámetros Por valor Se utilizan como parámetros de entrada Por referencia Se utiliza como parámetros de salida o de entrada/salida

73 Parámetros por valor Se usan para proporcionar información de entrada a un método Hasta ahora en todos los métodos estudiados, los parámetros pasados a los métodos han sido pasados por valor Pasar por «valor» indica que a los métodos se han pasado copias de los valores pero nunca las variables Quiere decir que el cambio de un valor de un parámetro no actualiza el valor de la variable que se pasó al método Cuando invocamos un método pasando una variable como parámetro por valor, a pesar de que cambiemos el valor del parámetro dentro del método, la variable original no se ve afectada por ese cambio.

74 Parámetros por referencia Se usan cuando un método debe modificar el valor de la variable pasada como parámetro Está basado en pasar al método una referencia a la variable actual en lugar de su valor La referencia que un método recibe es la dirección de la variable. Las referencias sirven para definir "alias" o nombres alternativos para una misma variable. Para ello se usa el operador de referencia (dirección) (&), el cual devuelve la dirección donde se ubica una variable en la memoria Una limitación es que se pueden pasar sólo variables al método. No se pueden utilizar constantes ni expresiones en la línea de llamada al método.

75 Parámetros de entrada  Son variables locales al método que se inicializan con los valores que existen en la llamada  Ejemplo: void eliminarElePos(int pos) { for (int i=pos; i

76 Parámetros de salida  El método fija los valores de los parámetros y los devuelve al main (o al punto donde fue invocado) void raices(float &R1, float &R2 ) { R1 = (-b + sqrt (b*b-4*a*c) / (2*a); R2 = (-b - sqrt (b*b-4*a*c) / (2*a); } En el main int main() { float x1,x2; EcuCuadratica ecuacionA(2,2,-12); ecuacionA.raices(x1,x2); cout

78 Resumiendo… Cuando se utilizan parámetros por valor y por referencia se deben tener presentes los siguientes aspectos: Los parámetros por valor (declarados sin &) reciben copias de valores pasados a ellos. Las asignaciones a parámetros por valor en un método nunca cambian los valores originales pasados a los parámetros. Los parámetros referencia (declarados con &) reciben la dirección de los valores pasados a ellos. En un método, las asignaciones a parámetros por referencia cambian los valores de los parámetros originales

79 Paso de parámetros  Suponga que en la clase Coleccion se desea un método sumaColeccion() que recibe una segunda colección como parámetro y modifique la primera colección con la suma de los elementos de la segunda colección 46982 [0] [1] [2] [3] [4] vector 71017133 [0] [1] [2] [3] [4] class Coleccion { private: int vector[50]; int tamano; int cantidad; 34851 [0] [1] [2] [3] [4] vec2 vector

80 Ejemplo: Paso de parámetros void sumaColeccion(Colección obj){ // es una forma de enviar una copia del arreglo completo for(int i=0;i

81 Ejemplo: Paso de parámetros void sumaColeccion(Coleccion obj) {for(int i=0;i

82 Ejemplo: Paso de parámetros class Coleccion { private: int vector[50]; int tamano; int cantidad;

83 Ejemplo: Paso de parámetros  En la clase Coleccion escriba un método que ahora intercambie los elementos de dos colecciones. Para hacer esto debe recibir la colección a intercambiar, es decir debe recibir como parámetro una instancia de tipo Coleccion  Ejemplo: 46982 [0] [1] [2] [3] [4] A 34851 B 34851 A 46982 B class Coleccion { private: int vector[50]; int tamano; int cantidad;

84 Ejemplo: Paso de parámetros void intercambio(Colección obj) { int temp; for(int i=0; i

85 Paso de parámetros  En el ejemplo anterior el arreglo real NO se pasa al método sólo una copia de su valor. void intercambio(Contenedor vec2) {….}  Su uso es local, al terminar el método la copia se pierde y el original no es alterado

86 Ejemplo: Paso de parámetros void intercambioRef(Contenedor &vec2) { int temp; for(int i=0; i

87 Paso de arreglos como parámetros  En el ejemplo anterior al método se le pasa la dirección del arreglo void intercambioRef(Contenedor &vec2) {….}  Al terminar el método el arreglo original es alterado

88 Tarea:  Suponga que en el main() se han creado los objetos A y B de tipo Coleccion y que ambos ya tienen valores definidos:  Escriba un método que reciba una instancia tipo Coleccion como entrada y devuelva true si ambas colecciones son iguales y false, en caso contrario.  A.sonIguales(B)  Escriba un método que reciba una instancia tipo Coleccion como entrada y modifique cada uno de sus valores con el producto de los valores de la colección de A y B.  A.multiplica(B) class Coleccion { private: int vector[50]; int tamano; int cantidad;

89 EIF200 FUNDAMENTOS DE INFORMÁTICA C. Lethbridge, Timothy. (2001). Object-Oriented Software Engineering, United Kingdom. Booch, Grandy. (1996 ). “ Análisis y Diseño Orientado a Objetos con Aplicaciones”., Editorial Addison Wesley Logman, 2 da edición, México,. Martín, James. (1994). Odell, James J;“Análisis y Diseño Orientado a Objetos”, Editorial Prentice Hall, 1era edición, México, Rodríguez Rojas, Oldemar. (1997). “ C ++ para ambientes gráficos”., Editorial Tecnológica de Costa Rica, 1era edición, Costa Rica. REFERENCIAS

90 Uso didáctico curso EIF 200 Escuela de Informática Universidad Nacional Costa Rica EIF200 FUNDAMENTOS DE INFORMÁTICA Proyecto 0151-14 UNA – Mora & Coto, 2015