poo
TRANSCRIPT
Universidad Central de Venezuela Facultad de Ciencias
Escuela de Computación
Lecturas en Ciencias de la Computación ISSN 1316-6239
Algoritmos y Programación
Prof. Ana Vanesa Leguizamo León
ND 2007-01
CENEAC
Caracas, Enero, 2007.
Universidad Central de Venezuela
Facultad de Ciencias
Escuela de Computación
Algoritmos y Programación
Notas de Docencia
Ana Vanessa Leguízamo León
Caracas, Enero 2007
2
CONTENIDO INTRODUCCIÓN........................................................................................................................................ 1 TEMA 1: INTRODUCCIÓN A LA PROGRAMACIÓN ............. ............................................................ 2
CONCEPTOS BÁSICOS.................................................................................................................................. 2 Hardware: ............................................................................................................................................. 2 Software:................................................................................................................................................3 El lenguaje ensamblador ....................................................................................................................... 4 Lenguaje de programación:................................................................................................................... 4 Algoritmo ............................................................................................................................................... 6 Programa............................................................................................................................................... 7
CONSTRUCCIÓN DE PROGRAMAS................................................................................................................ 7 Estructuración por acciones.................................................................................................................. 8 Estructuración por objetos .................................................................................................................... 8
CALIDAD DE UN PROGRAMA: ...................................................................................................................... 8 TEMA 2: ACCIONES ELEMENTALES ................................................................................................ 10
NOTACIÓN ALGORÍTMICA:........................................................................................................................ 10 Valores no estructurados o elementales: ............................................................................................. 10 Valores estructurados:......................................................................................................................... 10 Constantes: .......................................................................................................................................... 10 Variables: ............................................................................................................................................ 10 Expresiones: ........................................................................................................................................ 10 Tipo de Dato:....................................................................................................................................... 11
CARACTERÍSTICAS Y VENTAJAS DE LOS TIPOS DE DATOS.......................................................................... 11 CLASIFICACIÓN DE LOS TIPOS DE DATOS................................................................................................... 11 TIPOS DE DATOS NO ESTRUCTURADOS......................................................................................................12
Tipo Entero:......................................................................................................................................... 12 Tipo Real: ............................................................................................................................................ 12 Tipo Caracter: ..................................................................................................................................... 13 Tipo Lógico: ........................................................................................................................................ 13 Ejercicios Resueltos: ........................................................................................................................... 14
PRIORIDAD DE OPERADORES..................................................................................................................... 14 TEMA 3: ACCIONES ELEMENTALES ................................................................................................ 16
DECLARACIÓN DE VARIABLES .................................................................................................................. 16 ACCIONES ELEMENTALES......................................................................................................................... 16
Asignación:.......................................................................................................................................... 16 Secuenciamiento:................................................................................................................................. 17 Entrada Simple .................................................................................................................................... 18 Salida Simple ....................................................................................................................................... 18 Ejercicios Resueltos: ........................................................................................................................... 18
TEMA 4: INTRODUCCIÓN AL ENFOQUE ORIENTADO A OBJETOS ......................................... 22 PROGRAMACIÓN ORIENTADA A OBJETOS.................................................................................................. 22
Objeto: ................................................................................................................................................. 22 Identidad de un objeto ......................................................................................................................... 22 Estado de un objeto: ............................................................................................................................ 22 Comportamiento de un objeto.............................................................................................................. 23
CLASES..................................................................................................................................................... 23 Atributos: ............................................................................................................................................. 24 Métodos: .............................................................................................................................................. 24
ELEMENTOS DE LA POO. .......................................................................................................................... 25 Abstracción.......................................................................................................................................... 25 Encapsulación (Ocultamiento de información) ................................................................................... 25 Modularidad ........................................................................................................................................ 25 Polimorfismo ....................................................................................................................................... 25
DEFINICIÓN DE CLASES............................................................................................................................. 26 RELACIONES ENTRE CLASES...................................................................................................................... 27
3
Herencia: ............................................................................................................................................. 27 Agregación: ......................................................................................................................................... 28 Composición:....................................................................................................................................... 28 Asociación: .......................................................................................................................................... 28 Navegabilidad...................................................................................................................................... 29 Rol........................................................................................................................................................ 30
CLASE ABSTRACTA................................................................................................................................... 31 TEMA 5: ESTRUCTURAS DE CONTROL ........................................................................................... 32
FORMAS DE COMPOSICIÓN DE ACCIONES................................................................................................... 32 SELECCIÓN MÚLTIPLE .............................................................................................................................. 32 SELECCIÓN SIMPLE ................................................................................................................................... 33
Ejercicios Resueltos: ........................................................................................................................... 34 ESTRUCTURAS ITERATIVAS....................................................................................................................... 36
Repetir ................................................................................................................................................. 36 Mientras............................................................................................................................................... 38 Para .....................................................................................................................................................39 Ejercicios Resueltos: ........................................................................................................................... 40
TEMA 6: CLASES Y MÉTODOS............................................................................................................ 43 IMPLEMENTACIÓN DE UNA CLASE............................................................................................................. 43 CREACIÓN DE OBJETOS............................................................................................................................. 44 MÉTODOS: ................................................................................................................................................ 45
Métodos: Acciones............................................................................................................................... 45 Métodos: Función................................................................................................................................ 46
PARÁMETROS............................................................................................................................................ 46 Parámetros actuales:........................................................................................................................... 46 Parámetros formales: .......................................................................................................................... 46
TIPOS DE PASE DE PARÁMETROS............................................................................................................... 47 LLAMADA (O USO) DE UN MÉTODO........................................................................................................... 47 AMBIENTE DE REFERENCIACIÓN............................................................................................................... 48
Objetos No locales a una acción: ........................................................................................................ 48 Objetos locales a una acción:.............................................................................................................. 48
TEMA 7: TIPOS DE DATOS ESTRUCTURADOS ............................................................................... 50 ESTRUCTURA DE DATOS............................................................................................................................ 50 ARREGLOS................................................................................................................................................ 50
Acceso a los elementos de un arreglo.................................................................................................. 51 Operación Constructora:..................................................................................................................... 51 Ejercicios Resueltos: ........................................................................................................................... 52
ARREGLOS MULTIDIMENSIONALES........................................................................................................... 53 ARREGLO BIDIMENSIONAL........................................................................................................................ 54
Ejercicios Resueltos: ........................................................................................................................... 55 ALGORITMOS DE ORDENAMIENTO ............................................................................................................ 56
Selección Directa................................................................................................................................. 56 Inserción Directa ................................................................................................................................. 57 Burbujas............................................................................................................................................... 59
ALGORITMOS DE BÚSQUEDA .................................................................................................................... 59 Búsqueda Lineal .................................................................................................................................. 60 Búsqueda Lineal (Arreglo Ordenado) ................................................................................................. 60 Búsqueda Binaria ................................................................................................................................ 60
ARCHIVOS................................................................................................................................................. 61 Operaciones Básicas sobre Archivos................................................................................................... 62 Operaciones de Entrada y Salida ........................................................................................................ 63 Ejercicios Resueltos: ........................................................................................................................... 64
REGISTROS................................................................................................................................................ 64 Acceso a los elementos de un Registro ................................................................................................ 65 Ejercicios Resueltos: ........................................................................................................................... 66
REFERENCIAS ..........................................................................................................................................69
1
INTRODUCCIÓN
Las presentes Notas de Docencia han sido realizadas con el fin de unificar los
conceptos básicos de programación impartidos a los alumnos de Algoritmos y
Programación, así como la notación utilizada para escribir los algoritmos que se
produzcan. Esta información es producto de los aportes de varios profesores que han
dictado la materia, y han sido recopilados y adaptados para producir una guía completa,
con conceptos teóricos y ejercicios resueltos que sirva de referencia a los estudiantes.
Este contenido está adaptado a la última revisión hecha al pensum de la Licenciatura en
Septiembre de 2004, así incluye siete capítulos que se corresponden con los temas
establecidos para el programa de la asignatura Algoritmos y Programación, a saber:
Introducción a la Programación, Tipos de Datos Elementales, Acciones Elementales,
Introducción al Enfoque Orientado a Objetos, Estructuras de Control, Clases y Métodos
y Tipos de Datos Estructurados.
2
TEMA 1: INTRODUCCIÓN A LA PROGRAMACIÓN Organización del Computador. Conceptos de algoritmo, dato, información, lenguaje natural,
lenguaje pseudo-formal, lenguaje de programación, programa. Principio de abstracción.
Refinamiento progresivo y estrategia divide y vencerás
CONCEPTOS BÁSICOS
Computador: es un dispositivo electrónico utilizado para procesar los datos en forma
automática y obtener resultados. Los datos se pueden introducir en el computador como
entrada y se procesan para producir la información de salida.
Un Ambiente de Computación está formado por:
Hardware: se refiere a todas los componentes físicos que lo conforman. La palabra
Hardware proviene del inglés: hard que significa duro y ware que significa producto,
artículo o mercancía.
Todos los computadores con un único procesador son construidos de acuerdo al
modelo propuesto en 1944 por el matemático Estadounidense de origen húngaro John
Von Neumann. El modelo de Von Neumann consta de lo siguiente:
El computador está compuesto por:
Procesador Memoria Principal
Bus
Perifericos: monitor, teclado, etc.
Memoria secundaria: discos, floppy, CD.
Computador (Proceso)
Datos
Resultados (Información)
3
Memoria Principal: donde se almacenan la información “tratante” o instrucciones,
y la información “tratada” o datos. Esta información está representada en una
codificación binaria de 0 y 1.
La Unidad Central de Proceso (CPU o Procesador) encargada de extraer las
instrucciones y datos de la memoria principal, para realizar los tratamientos
correspondientes. Está conformada por la unidad de Control y la Unidad Lógico
Aritmética.
Bus o unidades de intercambio, ligados a los periféricos para intercambiar
información con el mundo exterior
Memoria secundaria, permiten conservar la información aún luego de apagar el
computador
Periféricos que sirven de comunicación con el hombre (monitor, teclado,
impresora, scanner, etc) o el intercambio de información sobre una red (tarjeta
de red)
Software: son los programas que permiten utilizar los recursos del computador. La
palabra software viene del inglés soft, que significa suave y ware producto.
El sistema operativo es un conjunto de programas que asegura la gestión de recursos
físicos y lógicos empleados por los usuarios. Tiene como tarea la administración y
conservación de la información y genera el ambiente necesario para la ejecución de un
programa. Actualmente se ofrecen una cantidad extra de servicios tales como
tratamiento de texto, navegadores, multimedia, que ofrecen un ambiente de trabajo
confortable y de fácil utilización.
¿Cómo se trata o procesa la información en un ambiente de computación?
El tratamiento de la información es la ejecución por el computador de una serie finita de
comandos preparados, que generalmente tienen como objetivo calcular y devolver
resultados en función de datos introducidos al comienzo o en el curso de ejecución.
4
Programas: Conjunto finito y secuencial de comandos preparados, que tienen como
objetivo ser ejecutados por un computador para realizar cálculos y reportar resultados,
generalmente en función de datos suministrados al comienzo o durante la ejecución.
Los comandos que forman un programa son descritos mediante un lenguaje especial.
¿Cómo es ese lenguaje? ¿Cómo lo entiende el computador?
El único lenguaje que comprende el computador es su lenguaje de máquina. Cada
modelo de computador posee su propio lenguaje llamado Lenguaje de Máquina, que no
es más que un conjunto de comandos elementales representados en código binario que
pueden ser ejecutados por el computador.
Ejemplo 00001110101011110000111101010101 instrucción de 32 bits
Donde: 1 bit: unidad mínima de información, representada por 1 ó 0
Byte= 8 bits
1 Kilobyte= 1024 Bytes
1Megabyte= 1024 Kilobytes
1 Gigabyte= 1024 Megabytes.
El lenguaje ensamblador es una codificación alfanumérica del lenguaje de máquina.
Es más legible, pero continua siendo particular a una familia de computadoras y difícil
de usar.
Ejemplo Load R1, 5
Lenguaje de programación: conjunto de enunciados que hacen posible al ser humano
expresarse siguiendo las reglas de una gramática dada y que están destinados a
representar los objetos y los comandos que pueden constituir un programa.
Ejemplo: if (b>0) r1=5 else r1=10
La definición de un lenguaje de programación cubre tres aspectos:
Léxico: Define los símbolos que sirven para la redacción de un programa y las reglas
para la formación de palabras en el lenguaje. Ejemplo 255 es una cifra entera.
Sintaxis: conjunto de reglas que permiten organizar las palabras en frases. Por ejemplo:
255/5 formada por dos cifras enteras y un operador de división sigue las reglas
sintácticas que definen una expresión
5
Semántica: define las reglas que dan sentido a una frase. Una frase puede ser
sintácticamente correcta pero incorrecta semánticamente: 255 / 5
¿Cómo se ejecuta un programa escrito en un lenguaje de programación en un
computador, si sólo entiende lenguaje de máquina?
Existen dos soluciones a este problema:
La primera en traducir el programa escrito en un Lenguaje de Programación (LP) a otro
programa semánticamente equivalente escrito en Lenguaje de Máquina (LM). Esta
traducción se realiza a través de un software especial llamado compilador . En general
el compilador produce código para un sólo tipo de máquina.
La segunda opción consiste en simular el funcionamiento del lenguaje de programación
sobre el computador real, interpretando las instrucciones del programa fuente. El
software que realiza esta interpretación se llama Intérprete . La interpretación directa de
instrucciones escritas en un LP de “alto nivel” es generalmente muy difícil, y por ellos e
realiza en dos fases. En la primera fase, se realiza una traducción del programa fuente
a un lenguaje intermediario, lo cual es un proceso equivalente a la compilación. Luego,
se realiza la interpretación sobre este lenguaje intermedio. Esta es la técnica que usa el
lenguaje de programación Java.
Un programa fuente en Java es traducido a un programa objeto en un lenguaje
intermedio, llamado Java pseudo-código (o byte-code). Este programa objeto es
entonces ejecutado sobre la máquina virtual Java (JVM) quien lo interpreta.
Como se ve, la compilación y la interpretación no son incompatibles. El interés de la
interpretación es asegurar la portabilidad de los programas: esto significa que un
programa elaborado en un computador puede ser ejecutado sobre otros, sin
modificaciones. Pero tiene el inconveniente que el tiempo de ejecución de programas
interpretados es notablemente mayor que el de los programas compilados.
Un Diagrama de flujo es un diagrama que ilustra el flujo de datos, información y trabajo
por medio de símbolos especializados que, cuando se conectan por líneas de flujo,
reflejan la lógica de un sistema o programa.
6
Algoritmo: Un algoritmo es una secuencia finita de pasos para la solución de un
problema. El algoritmo describe, de forma no ambigua, la secuencia de acciones a
efectuar para especificar una funcionalidad a tratar de manera automática. Está escrito
en una notación formal, independiente del lenguaje utilizado para programar. Los
algoritmos están compuestos por objetos y acciones sobre esos objetos.
Objeto: Elementos que conforman un algoritmo. En particular se distinguen los
objetos de datos, los cuales poseen atributos o valores y no son más que un
elemento de información dentro de un contexto particular, que tiene un nombre y
un valor asociado.
Un objeto tiene tres características fundamentales:
− Identificación única.
7
− Estado.
− Comportamiento (operaciones, funciones y métodos).
Estado : Es el conjunto de valores de los diferentes objetos en un momento
determinado. En un algoritmo se diferencian dos estados particulares de un
objeto, que son el estado INICIAL y el estado FINAL.
Acción: Suceso o evento que dura un tiempo finito y produce un resultado o
efecto “bien definido y previsto”. Toda acción produce cambios de estado (valor)
sobre los objetos y está perfectamente determinada por sus estados inicial y
final.
La concepción de un algoritmo requiere de un gran esfuerzo intelectual. Para un mismo
problema, existen muchos algoritmos que conducen a la solución. La elección del mejor
algoritmo casi siempre está guiada por criterios de eficacia y eficiencia, pero no son las
únicas características deseables en los programas.
Programa: es un algoritmo expresado en un lenguaje de programación.
CONSTRUCCIÓN DE PROGRAMAS
La programación es la disciplina de la computación que trata el desarrollo de
programas. Es una tarea compleja, que requiere métodos rigurosos, para alcanzar el
objetivo de todo programa que es obtener resultados válidos y confiables.
En general, la actividad de programación se realiza por etapas, contemplando al menos
las siguientes: (explicar cada una)
Análisis del Problema
Diseño de la Solución
Desarrollo del Programa
Prueba del programa
8
De manera general podemos decir que un programa efectúa acciones sobre objetos. De
allí que existan dos enfoques para estructurar los programas:
Estructuración por acciones (años 70): El problema a resolver es descompuesto
(dividido) en subproblemas aún más simples, sucesivamente hasta obtener problemas
con soluciones elementales programables directamente. Esta descomposición se
realiza utilizando una capacidad intelectual denominada abstracción.
Abstracción : Mecanismo intelectual que permite durante el análisis del problema la
separación de los aspectos relevantes de los irrelevantes en el contexto estudiado.
Ejemplo: si el problema consiste en determinar cual es la persona más alta del salón, lo
relevante es la estatura de cada persona, no el peso, el color de los ojos o del cabello.
Estructuración por objetos (años 80): la estructura del programa está basada en los
objetos que maneja y las relaciones entre ellos. El problema a resolver es visto como un
modelo del mundo real constituido por objetos. Los objetos son componentes que
contienen atributos (datos) y métodos (acciones) que describen el comportamiento del
objeto.
CALIDAD DE UN PROGRAMA:
Para garantizar que un programa es de calidad, se toman en cuenta varios aspectos
que estos deben cumplir. A continuación se presentan los más comunes:
− Eficacia: el programa debe resolver el problema para el cual fue desarrollado
− Eficiencia: esto se mide en función del uso de los recursos del computador. Un
programa es más eficiente mientras utilice menos recursos (memoria, tiempo de
uso del CPU - tiempo de respuesta -, etc.).
− Legibilidad: Un programa debe estar escrito de forma tal que pueda ser
entendido por otros programadores cuando haya necesidad de realizar
modificaciones. Para esto es conveniente intradocumentar los programas:
agregar comentarios en lenguaje natural, que ayuden a entender su lógica.
− Adaptabilidad: Un programa es adaptable, si a un bajo costo, puede ser
modificado para resolver otros problemas.
− Reusabilidad: un programa es reutilizable si sus componentes pueden ser
extraídos para ser utilizados para resolver diversos problemas.
9
− Portabilidad: un programa es portable si puede ser ejecutado sobre diversas
plataformas, con cambios mínimos.
10
TEMA 2: ACCIONES ELEMENTALES Declaraciones de variables, constantes y tipos. Instrucción de Asignación. Valor izquierdo y
derecho de una variable. Acciones predefinidas. Operación de Lectura. Operación de Escritura.
NOTACIÓN ALGORÍTMICA:
A fin de garantizar la correcta interpretación del lector de los algoritmos que escribimos,
debemos especificar una notación, la cual debe ser:
− Fácil de entender.
− Debe reflejar el análisis que produjo la solución al problema, de manera directa.
− Debe ser poderosa, es decir, que con pocos elementos se puedan expresar
muchas cosas.
Los algoritmos manejan valores y datos para procesarlos y obtener resultados. Los
conjuntos de valores que puede tomar la información pueden dividirse en dos
categorías:
Valores no estructurados o elementales: son aquellos valores que no pueden
dividirse en componentes. Ejemplo: la CI, la edad, un real, un entero.
Valores estructurados: son aquellos valores que están formados por componentes y
por tanto, pueden descomponerse en términos de los valores que lo constituyen.
Ejemplo: una persona, un carro.
Los valores que constituyen cada conjunto se pueden expresar de tres maneras:
Constantes: denotan un valor particular dentro de un conjunto. Ejemplo: (3, 5, -10, 0)
dentro del conjunto de los enteros. (verdadero, falso) lógicos. (3.5, 3.14, -10.0) reales,
(‘a’, ‘b’, ‘c’) caracteres.
Variables: denotan un valor genérico dentro del conjunto. Ej A, Int, salir
Expresiones: denotan valores a partir de operaciones entre nombres y/o constantes.
Ej: x+1, x^2, x>5 Y y<3, A div I, A mod I
11
Sobre cada uno de dichos conjuntos de valores están definidas una serie de
operaciones primitivas que permiten manipular sus valores. De aquí se origina el
concepto de tipo de dato.
Tipo de Dato: es un conjunto de valores junto a una serie de operaciones que pueden
ser aplicadas sobre dichos valores.
Por ejemplo, objetos de tipo Entero pueden tomar valores del conjunto de los enteros
(Z), y las operaciones sobre dichos valores son:
Aritméticos: +,-, -(unario), *, div, mod, ^
Relacionales: >,<, =, ≥, ≤, ≠
CARACTERÍSTICAS Y VENTAJAS DE LOS TIPOS DE DATOS
Características:
Un tipo de dato determina la clase de valores que puede asumir una variable o una
expresión. En ocasiones una variable determina el tipo de una expresión.
Cada variable pertenece a un solo tipo de dato
Cada operador actúa sobre operandos de algún tipo, y da como resultado un valor de
algún tipo
Ventajas:
La verificación de tipos es realizada por el traductor
Permite agrupar un conjunto de valores que guardan una estrecha relación.
Permite ver las operaciones sobre los valores de manera indivisible
Ocultamiento de la representación interna: se ve sólo la especificación y no la
implementación.
CLASIFICACIÓN DE LOS TIPOS DE DATOS
El criterio para clasificar los tipos de datos está dado por el número de componentes
(determina si es estructurado o no) y según el tipo de sus componentes (si es no
8 5
3 1 DIV MOD
12
estructurado equivale al tipo, y si es estructurado determina si es homogéneo o
heterogéneo).
Podemos referirnos a objetos de tipo no estructurado cuando el conjunto de valores que
pueden tomar son no estructurados, y objetos de tipo estructurado cuando el conjunto
de valores que pueden tomar son estructurados.
TIPOS DE DATOS NO ESTRUCTURADOS
Los tipos de datos no estructurados que están disponibles en la mayoría de los
lenguajes de programación son el tipo entero, caracter, real y lógico. Muchos lenguajes
permiten la definición de tipos subrango o subintervalos y enumerados. A continuación
explicaremos brevemente cada uno de estos tipos.
Tipo Entero:
Conjunto de valores: subconjunto de los enteros
Conjunto de operaciones
Aritméticos: +,-, -(unario), *, div, mod, ^
Relacionales: >,<, =, ≥, ≤, ≠
Tipo Real:
Conjunto de valores: subconjunto de los reales
Conjunto de operaciones:
Aritméticos: +,-, -(unario), *, /, ^
Relacionales: >,<, =, ≥, ≤, ≠
Tipo
Número de
Componentes Elemental
Estructurado
Entero, caracter, lógico, real
Enumerado
Subrango
Homogéneos: archivos
arreglos
Heterogéneos: registros
1
n
Tipo de
Componentes =
≠
13
Tipo Caracter:
Conjunto de valores: Tabla ASCII tiene 128 caracteres, Tabla ASCII extendida tiene 256
caracteres.
Conjunto de operaciones:
Relacionales: >,<, =, ≥, ≤, ≠
Acerca del código ASCII: La organización Internacional de Normas (ISO) define el
código estadounidense ASCII (Código Standard Americano para el Intercambio de
Información), que constituye el código más aceptado. Este código consta de 128
caracteres, de los cuales 99 son imprimibles y los 33 restantes son de control. En
muchas máquinas se usan 8 bits para representar los caracteres, y suele usarse la tabla
ASCII extendida, que consta de 256 caracteres (los mismos 128 del código ASCII y
otros 128 caracteres).
En el conjunto de caracteres se tienen las 26 letras mayúsculas latinas, las 26
minúsculas, los 10 números arábigos y otros caracteres como los signos de puntuación
y el espacio. Entre los caracteres hay un orden, que viene dado por el valor binario que
tiene asociado. Este orden depende del sistema de codificación que se use. Sin
embargo, en general los subconjuntos de letras y números son ordenados y contiguos,
cumpliéndose:
‘a’<’b’< … <’z’
‘A’<’B’< … <’Z’
‘0’<’1’< … <’9’
Esto hace que los operadores relacionales puedan aplicarse sobre los caracteres. Así
mismo, muchos lenguajes de alto nivel proveen herramientas para realizar operaciones
aritméticas sobre caracteres. En Pascal Succ(‘a’)=’b’; Chr(ORD(‘a’)+1)=’b’. En C y en
Java, sencillamente ‘a’+1=’b’. Las letras A…Z están ubicadas del 65 al 90, de la a … z
del 97 al 122. Los números de 0 … 9 del 49 al 57, el espacio en el 32.
Tipo Lógico:
Conjunto de valores: {verdadero y falso}
14
Conjunto de operaciones:
Lógicas: no, o, y
Relacionales: =, ≠
Resumiendo:
Tipo de dato Constantes Variables Expresiones
Entero 3, 0, -1 I, J, K, ini I+J*K, 5+8*3
Real 3.141, 0.1, -1.1 Pi, X, Z X^(1/2) , Pi*R^2
Lógico verdadero/falso L1, L2, L3 no L1 y L2 o no L3
Caracter ‘A’, ‘h’, ‘ ‘ C1, C2 ‘A’>’B’, C1≠C2
Ejercicios Resueltos:
Traducir a lenguaje algorítmico
1) ¬p∨q
no p o q;
2) ax2+bx+c
a * (x^2) + b * x + c;
3) a+2b
3
(a + 2 * b) / 3;
PRIORIDAD DE OPERADORES
Cuando mezclamos en una expresión operadores relacionales, booleanos y aritméticos,
tendremos la siguiente prioridad:
( )
- (unario), no, ^
*, /, mod, div
p q ¬p ¬q p∧q p∨q
V V F F V V
V F F V F V
F V V F F V
F F V V F F
Para recordar…
15
+, -
<, ≤ , >, ≥
=, ≠
y
o
16
TEMA 3: ACCIONES ELEMENTALES Declaraciones de variables, constantes y tipos. Instrucción de Asignación. Valor izquierdo y
derecho de una variable. Acciones predefinidas. Operación de Lectura. Operación de Escritura.
DECLARACIÓN DE VARIABLES
Las variables se declaran de la siguiente forma:
<nombre del tipo> <lista de 1 o más variables>; Cada variable es la concatenación de uno o más caracteres alfanuméricos,
comenzando siempre por un caracter alfabético.
Ejemplos:
Acción Principal Entero i, j, k; Real x, y; Lógico b1; Caracter y1; facción
ACCIONES ELEMENTALES
Las acciones elementales son: la asignación, la entrada simple y la salida simple. Con
estas acciones se pueden crear acciones más complejas mediante las formas de
composición de acciones.
Asignación:
Asociación de un valor a una variable. Permite modificar el estado de los objetos del
algoritmo. La notación algorítmica que usaremos para la asignación es:
<nombre de variable> <constante, variable o e xpresión>;
Por ejemplo, si I y J son variables de tipo entero, las siguientes asignaciones son
validas:
I ← 1; # asignación de una constante a una varia ble I ← J; # asignación de una variable a otra I ← I+1; # asignación del resultado de evaluar una ex presión a # una variable I ← J mod 2; # asignación del resultado de evaluar una exp resión a # una variable
17
Otro ejemplo
Caracter C1; Entero I; Lógico Enc; C1 ← ‘a’; # en este momento C1=‘a’ Enc ← (1>0); # Luego de la asignación, el valor de Enc e s # verdadero I ← 5+16 div 3 # luego de la asignación, el valor de I es 10
Secuenciamiento:
Consiste en presentar las acciones en un orden. Las acciones se efectúan en el mismo
orden en que son escritas. El símbolo punto y coma ( ; ) se utiliza para separar una
instrucción de otra.
Ejemplo:
Acción Principal Entero I; I ← 1; #en este momento I tiene el valor de 1 I ← I+1; # en este momento I tiene el valor de 2 I ← I^5; # en este momento I tiene el valor de 32 I ← I mod 2; # I = 0 facción
Otro ejemplo
Acción Principal Caracter C1; Entero I; Lógico Enc; C1 ← ‘a’; # en este momento C1=‘a’ Enc ← (1>0); # Luego de la asignación, el valor de Enc e s # verdadero I ← 5+16 div 3 # luego de la asignación, el valor de I es 10 facción
18
Entrada Simple
Almacena un valor extraído desde un dispositivo externo (del cual hacemos abstracción,
aunque generalmente es el teclado) en una variable. El efecto de esta acción es el
cambio de valor de la variable en cuestión.
La sintaxis algorítmica que adoptaremos para esta acción es:
Leer (<nombre de variable>);
Ejemplos:
Entero I; Leer (I); Real X; Leer (X); Caracter c; Leer (c);
Cabe destacar que luego de leer un valor de un dispositivo externo, el valor de la
variable cambia de igual forma que en una asignación.
Salida Simple
Transmite un valor (constante, variable o evaluación de una expresión) a un dispositivo
externo (del cual hacemos abstracción, aunque generalmente es el monitor) para ser
mostrado al usuario. Generalmente es utilizado para mostrar los resultados obtenidos.
La sintaxis algorítmica que utilizaremos para esta acción es:
Escribir (<Nombre de variable, constante o expresión>);
Ejemplos
Escribir (1); # se ha escrito el número 1 Entero I; I ← 1; Escribir (I+1); #se ha escrito el número 2
Ejercicios Resueltos:
Haga un algoritmo que dados dos números enteros devuelva el resultado de la suma de
ellos.
19
Acción Principal Entero A, B, Res; Leer (A); Leer (B); Res ← A + B; Escribir (Res); faccion
Dado un número entero N obtener el primer dígito (asociado a las unidades)
Acción Principal Entero N, Res; #se han declarado dos variables, con valo r # indefinido Leer (N); # N contiene el numero introducido por el # usuario Res ← n mod 10; # Res tiene el resultado, el primer dígito de N Escribir (Res); # Se escribió el resultado. faccion
Dado un numero entero N obtener el dígito asociado a las decenas
Acción Principal Entero N, Res; # se han declarado dos variables, con val or # indefinido Leer (N); # N contiene el numero introducido por el # usuario Res ← N div 10; # Res contiene el numero N sin el primer dígit o Res ← Res mod 10; # Res tiene el segundo dígito de N Escribir (Res); # Se escribió el resultado. faccion
En este algoritmo podemos suprimir la variable Res, ya que la escritura soporta la
evaluación de expresiones, finalmente el algoritmo puede ser escrito como:
Acción Principal Entero N; # se declaro la variable N Leer (N); # N contiene el numero introducido # por el usuario Escribir (N div 10 mod 10); # Se escribió el resultado. faccion
Dado un número entero N obtener el dígito I-esimo
En este caso el usuario debe introducir además del número, la posición del dígito a
extraer. Haciendo analogía con los ejercicios anteriores, debemos extraer los I-1
20
primeros dígitos del numero N, como I es entero, debemos asumir, por ahora, que es
mayor que 0
Acción Principal Entero N, I, Res; Leer (N); Leer (I); Res ← N div 10^(I-1); Res ← Res mod 10; Escribir (Res); faccion
Dado un círculo centrado en el origen, determine si un punto pertenece al mismo.
Análisis: para empezar hay que saber cuales don los elementos que intervienen en este
problema. Por un lado, tenemos el círculo. Un circulo centrado en el origen está definido
como todos los puntos (x,y) tal que:
x2+y2 ≤ r2
Donde r es el radio del circulo y x e y las coordenadas de un punto en el plano R2. Los
valores que necesitamos conocer entonces son el radio y el punto (x,y) que queremos
verificar. El resultado es simplemente evaluar si el punto está dentro o no del círculo con
la inecuación.
Acción Principal Real r, x, y; Lógico Res Leer ( r ); Leer (x); Leer (y); Res ← (x*x + y^2 ≤ r*r) Escribir (Res); faccion
Nótese que podemos eliminar la variable Res si escribimos Escribir(x*x + y^2 ≤ r*r)
Dado un número entero de 3 dígitos, verificar si es palindrome.
Acción Principal Entero N, D1, D3; Lógico L; Leer (N);
21
D3 ← N div 100; // D1 tiene el valor del primer dígito del // número
D1 ← N mod 10; // D3 tiene el valor del tercer dígito L ← D1 = D3; // si D1=D3 L tiene verdadero , sino tiene falso Escribir (L); faccion
22
TEMA 4: INTRODUCCIÓN AL ENFOQUE ORIENTADO A OBJETOS Objetos y Clases. Atributos de clase y de objetos. Mensajes. Encapsulamiento. Descomposición basada en objetos. Relaciones entre clases y objetos
PROGRAMACIÓN ORIENTADA A OBJETOS
Es una ampliación natural del concepto de Tipo de Datos, que incorpora los aspectos
descriptivos y funcionales de la información en bloques autónomos de programación
(clases). La mayor parte del software comercial y en uso está basado en los conceptos
de orientación a objetos.
En la POO, cada objeto puede ser considerado como un proveedor de servicios
utilizados por otros objetos que son sus clientes. Cada objeto puede ser a la vez
proveedor y cliente. De allí que un programa pueda ser visto como un conjunto de
relaciones entre proveedores y clientes.
Objeto:
Es una entidad fundamental que tiene una identidad, un estado y un comportamiento.
Identidad de un objeto
Cada objeto tiene una identidad única, aun si su estado en un momento dado, es
idéntico al de otros objetos
Profesor: “J. Pérez”
Enseña: Matemáticas
Profesor: “J. Pérez”
Enseña: Matemáticas
Estado de un objeto:
El estado de un objeto es una de las posibles condiciones en que un objeto puede
existir El estado de un objeto normalmente cambia con el tiempo
El estado de un objeto es usualmente implementado por un conjunto de propiedades
llamadas atributos
23
Ejemplo.
Nombre: Vanessa
CI: 123456
Contratación: 01/01/01
Puesto: profesora
Comportamiento de un objeto
El comportamiento determina como un objeto actúa y reacciona
El comportamiento define la manera en la que un objeto responde a las peticiones de
otros objetos
El comportamiento visible de un objeto se modela con un conjunto de mensajes a los
que el puede responder
Los mensajes se implementan como las operaciones del objeto
CLASES
Cuando se han identificado muchos objetos en un dominio, decimos que una clase es
una abstracción que describe un grupo de objetos que tienen:
propiedades en común (atributos)
comportamiento en común (operaciones)
relaciones comunes con otros objetos (asociaciones)
Una clase es una abstracción porque:
Enfatiza características relevantes al sistema
Suprime otras características
La Relación entre Clases y Objetos
Una clase es una definición abstracta de un objeto
Escuela de Computación
Profesores Asigna curso
Confirmación
24
Define la estructura y comportamiento de cada objeto en la clase
Sirve como una plantilla para crear objetos
Un objeto es una instancia concreta de una clase
Los objetos pueden agruparse en clases
Clase Asignatura
Estructura
Nombre
Código
Créditos
Secciones
Comportamiento
Añadir un Estudiante
Eliminar un Estudiante
Ver si el cupo está lleno
Los servicios ofrecidos por los objetos son de dos tipos:
Los datos, que llamamos atributos
Las acciones, que llamamos métodos .
Atributos:
Son elementos de datos utilizados para definir una ocurrencia de un objeto. Un atributo
es una característica de un objeto. Mediante los atributos se define la información de un
objeto, la cual es manipulada solamente por los métodos definidos sobre dicho objeto.
Métodos:
Son las operaciones que se aplican sobre los objetos. La implementación de los
métodos no es visible fuera del objeto.
Ejemplo: Algoritmos y programación es un objeto de la clase Asignatura y está
caracterizada por cuatro atributos que son: su Nombre: Algoritmos y programación,
25
Código: 6201, Créditos: 6, Secciones: 4, y los métodos que permiten Añadir un
estudiante, eliminar un estudiante y verificar si hay cupo.
ELEMENTOS DE LA POO.
Abstracción
Es el principio de ignorar aquellos aspectos de un fenómeno observado que no son
relevantes, con el objetivo de concentrarse en aquellos que si lo son. Una abstracción
denota las características esenciales de un objeto (datos y operaciones).
Encapsulación (Ocultamiento de información)
Plantea la integración en una entidad simple de un conjunto de datos y operaciones
sobre estos datos. La idea central de la encapsulación es esconder los detalles y
mostrar lo relevante. La encapsulación permite el ocultamiento de la información
separando el aspecto correspondiente a la especificación de la implementación; de esta
forma, distingue el "qué hacer" del "cómo hacer". La especificación es visible al usuario
y la implementación oculta al él. En la práctica, se esconde la especificación del objeto,
así como la implementación de los métodos.
Modularidad
Es la propiedad que permite tener independencia entre las diferentes partes de un
sistema. En POO las clases son módulos perfectamente definidos y estructurados, al
definir un objeto se crea una instancia de la clase que contiene sus datos y métodos
para realizar operaciones sobre él.
Polimorfismo
Es la propiedad que permite que un nombre pueda denotar instancias de distintas
clases. Existen 2 tipos de polimorfismo:
El polimorfismo por inclusión se basa en el hecho de que un objeto puede pertenecer a
más de una clase y por consiguiente puede ser manipulado por los métodos de las
clases a las cuales pertenece. La herencia entre clases es el mecanismo más conocido
26
de polimorfismo por inclusión en el EOO.
El polimorfismo operacional permite aplicar operaciones con igual nombre a diferentes
objetos que no están relacionados. En este tipo de polimorfismo, los métodos son
interpretados en el contexto del objeto particular, ya que los métodos con nombres
comunes son implementados de diferente manera dependiendo de cada objeto.
DEFINICIÓN DE CLASES
Diagrama de Clases: siguiendo la notación UML (Unified Modeling Language), cada
clase identificada en el dominio del problema planteado, es representada con un
rectángulo dividido en tres partes, de la siguiente forma:
Donde Nombre es el nombre de la clase
Atributos es la lista de atributos definidos para la clase, indicando por cada uno:
<modo de acceso><Nombre del atributo>: <tipo de dato>
<modo de acceso> indica la visibilidad del atributo, fuera del alcance de la clase,
pudiendo ser:
Privado (-): No puede accederse a el fuera del alcance de la clase
Publico (+): Puede accederse sin limitaciones fuera del alcance de la clase
Protegido (#): Puede ser accedido solo en las subclases o clases hijas dentro de la
jerarquia de clases relacionadas por la herencia.
<Nombre del atributo> denominación dada al atributo
<Tipo de dato> describe el dominio de datos dentro del que se representa el atributo.
Puede ser un tipo de dato elemental (entero, real, string, logico), un arreglo o una clase
ya definida.
Nombre
Atributos
Métodos
27
Métodos: es la lista de métodos definidos sobre los objetos de la clase, indicando para
cada método:
<modo de acceso> <Nombre>(<lista de parametros>)
Para el caso de la clase Asignatura:
RELACIONES ENTRE CLASES
Las relaciones entre clases se pueden enumerar en: asociación, herencia, agregación,
composición, instanciación y metaclase.
Herencia: Es la relación entre clases donde una clase comparte la estructura y/o
conducta de otras clases. Define una jerarquía "es un" entre clases. Una subclase se
considera una especialización de la superclase. Por ejemplo, un mosquito "es un"
insecto, y una especialización de insecto. Se representa mediante una relación de
generalización/especificación, que se denota con la flecha siguiente:
Ejemplo: profesor hereda de persona, entonces
Los diagramas con herencia se pueden presentar así:
Asignatura
- Nombre: string - Código: entero - Créditos: entero - Secciones: entero
+ Añadir_estudiante() + Eliminar_Estudiante()
+ Ver_cupo()
padre hijo
Profesor Persona
Departamento
Mercadeo Contabilidad Informática . . .
28
Agregación: La agregación es una relación "es parte de". Por ejemplo, un segmento
está delimitado por dos puntos a y b, que son parte del segmento. Es un tipo de relación
dinámica, en donde el tiempo de vida del objeto incluido es independiente del que lo
incluye. El objeto base utiliza al incluido para su funcionamiento. Esta relación se
destaca por un rombo vacío del lado base, y una flecha del lado incluido.
El en caso del computador, si no deseamos venderlo completo, podemos vender
sus partes. Así, pese a que el computador haya sido desarmado, sus partes
siguen existiendo.
En una práctica de boxeo, los guantes pueden ser pensados como una parte del
boxeador. Si el boxeador se retira, los guantes podrían ser utilizados por otro. Así, los
guantes de boxeo perduran, a pesar de que el boxeador ya no esté en el cuadrilátero
Composición: Es similar a la agregación, salvo que es un tipo de relación estática, en
donde el tiempo de vida del objeto incluido esta condicionado por el tiempo de vida del
que lo incluye. El Objeto base se contruye a partir del objeto incluido, es decir, es
"parte/todo". Esta relación se destaca por un rombo relleno del lado “todo”, y una flecha
del lado “parte”.
Otro ejemplo es Universidad y Facultad. Si la universidad deja de existir, tampoco
deben existir sus facultades, y si no hay facultades tampoco escuelas ni los salones, ni
los pupitres.
Asociación: Una asociación denota una dependencia semántica entre objetos. La
asociación entre clases tiene asociada una cardinalidad para instancias de ellas: uno a
uno, uno a muchos, muchos a muchos. Por ejemplo, entre estudiante y materia hay una
relación muchos a muchos: un estudiante tiene asociado n materias (n≥1), y una
Computador
Monitor
Teclado
Arbol Rama 1 m
29
materia tiene asociada m estudiantes (m≥1). Una asociación se representa como una
línea que une dos o más clases.
La Cardinalidad es una restricción que se pone a una asociación/agregación, que limita
el número de instancias de una clase que pueden tener esa asociación con una
instancia de la otra clase. Puede expresarse de las siguientes formas:
Con un número fijo: 1.
Con un intervalo de valores: 2..5
Con un rango en el cual uno de los extremos es un asterisco. Significa que es un
intervalo abierto. Por ejemplo, 2..* significa 2 o más.
Con una combinación de elementos como los anteriores separados por comas: 1, 3..5,
7, 15..*.
Con un asterisco: * . En este caso indica que puede tomar cualquier valor (cero o más).
Para el caso de la cuenta bancaria, a esta puede ser aplicada 0 o más operaciones..
En una relación de agregación o de asociación, se puede indicar el nombre de la
relación (por ejemplo, emplea, aplica, tiene, etc…), cardinalidad y/o rol.
Navegabilidad
En una asociación, se puede indicar la navegabilidad mediante un triángulo colocado
sobre la línea, donde la base esté colocada hacia el objeto origen. Significa que es
posible "navegar" desde el objeto de la clase origen hasta el objeto de la clase destino.
Se trata de un concepto de diseño, que indica que un objeto de la clase origen conoce
al (los) objeto(s) de la clase destino, y por tanto puede llamar a alguna de sus
operaciones.
Operación Cuenta Bancaria
Se aplican
* 1
30
Rol
Para indicar el papel que juega una clase en una asociación se puede especificar un
nombre de rol. Ejemplo: contratante y empleado para las clases empresa y Persona
Cuando una asociación tiene propiedades propias se representa como una clase unida
a la línea de la asociación por medio de una línea a trazos. Como vemos en el ejemplo,
tenemos dos clases que se asocia: empresa y trabajador, pero en la asociación nace
una nueva clase que tiene como atributo el salario, producto de emplear al trabajador.
Asociación n-arias, se unen por un rombo. Para el caso de un equipo de Béisbol que
contrata jugadores para temporadas, tendríamos lo siguiente:
El nombre de la asociación es opcional y se muestra como un texto que está próximo a
la línea. Se puede añadir un pequeño triángulo negro sólido que indique la dirección en
la cual leer el nombre de la asociación. En Figura siguiente se puede leer la asociación
como “Una Empresa emplea uno o más Persona”.
Los nombres de las asociaciones normalmente se incluyen en los modelos para
Empresa Persona Emplea 1 1…*
Contratante Empleado
Salario
Empresa Persona Emplea
1 1…*
Contratante Empleado
Temporada
Equipo Jugador
Salario
Contrata
1 11...*
1…*
31
aumentar la legibilidad. Para agregación, Combinación y de herencia no se suele poner
el nombre.
CLASE ABSTRACTA
Una clase abstracta se denota con el nombre de la clase y de los métodos con letra
"itálica". Esto indica que la clase definida no puede ser instanciada pues posee métodos
abstractos (aún no han sido definidos, es decir, sin implementación). La única forma de
utilizarla es definiendo subclases, que implementan los métodos abstractos definidos.
Un ejemplo es la clase Figura. La clase Figura no tiene implementado un método
Dibujar. Sin embargo las subclases Círculo, Triángulo y Elipse sí.
Figura
Dibujar()
Triángulo
Dibujar()
Círculo
Dibujar()
Elipse
Dibujar()
32
TEMA 5: ESTRUCTURAS DE CONTROL Secuenciación. Bloques. Selección simple, compuesta, anidada y múltiple. Estructuras de control
iterativas: Repetir, Mientras, Para.
FORMAS DE COMPOSICIÓN DE ACCIONES
Son los mecanismos mediante los cuales es posible construir nuevas acciones a partir
de otras. En este curso estudiaremos las siguientes:
Selección múltiple
Selección simple
Formas de iteración: Mientras, Repetir, Para.
SELECCIÓN MÚLTIPLE
Es una forma de composición de acciones que se utiliza en problemas donde es
necesario realizar un análisis por casos, es decir, permite tratar problemas donde las
acciones a tomar dependan de la evaluación de ciertas condiciones.
La notación que vamos a utilizar, es la siguiente:
Seleccion E1: <acción1> E2: <acción2> . . En: <acción n> fseleccion
Donde Ei debe satisfacer las siguientes condiciones:
E1 o E2 o . . . o En = verdadero
∀ Ei, Ej Ei y Ej = falso
Es decir, una y solo una de las posibilidades debe satisfacerse.
Ejemplo de un semáforo:
Si está en rojo, detenerse
Si está en verde, pasar
Si está en amarillo, detenerse si es posible, si no pasar con precaución
33
En una selección el criterio sería el color del semáforo, para el que el dominio de
definición es el conjunto formado por los tres colores del semáforo {verde, rojo, amarillo}
Selección Semaforo=verde: pasar; Semaforo = rojo: parar; Semaforo= amarillo: pasar con precaución; fselección
Ejemplo:
Hallar el máximo entre 2 números dados
Accion Principal Entero A, B, Max; Seleccion A>B: Max ← A; A=B: Max ← A; A<B: Max ← B; fselección facción
SELECCIÓN SIMPLE
Surge como una simplificación de un caso particular de la selección múltiple, es decir, si
la selección está formada por dos casos y no hay acción asociada a uno de esos casos,
entonces usamos la selección simple.
Ej:
Seleccion L1: A; L2:B fseleccion
Si L1 entonces A fsi Si L2 entonces B fsi
En el caso del mayor de dos números, podríamos escribir el algoritmo así:
Accion Principal Entero A, B, Max; Si A>B entonces Max ← A; fsi Si A=<B entonces
34
Max ← B; fsi facción
O también así:
Accion Principal Entero A, B, Max; Si A>B entonces Max ← A; sino Max ← B; fsi facción
Ejercicios Resueltos:
Como aguinaldo de fin de año, se ha decidido conceder un bono a todos los empleados
y trabajadores del país, en base a su sueldo mensual. A los empleados menores de 25
años, se les dará el 25% de su sueldo, a los trabajadores entre 25 y 45 años, se les
dará el 30% de su sueldo, y a los trabajadores con más de 45 años, se les dará el 40%
de su sueldo.
Adicionalmente, a las mujeres se les dará un bono adicional de Bs. 100.000 por cada
hijo que tenga.
En ningún caso el bono puede exceder de Bs. 3.000.000
Dados los datos de una persona (edad, sexo, sueldo, n° de hijos) determinar el monto
del bono.
Acción Principal Entero Edad, hijos; Caracter sexo; Real sueldo, bono; Leer (sueldo); Leer (Edad); Leer (sexo); Leer (hijos); Seleccion Edad < 25: bono ← sueldo * 0.25; Edad ≥ 25 y Edad ≤ 45: bono ← sueldo * 0.30; Edad > 45: bono ← sueldo * 0.40; fselección
35
Si sexo= ‘f’ entonces bono ← bono + (100.000 * hijos); fsi Si bono>3.000.000 entonces bono ← 3.000.000; fsi Escribir (bono); faccion
Dados los coeficientes de dos rectas decir si son iguales, paralelas o distintas. Si son
distintas decir en que punto se intersectan.
La ecuación de una recta viene dada por y=m1x + b1.
Si tenemos dos rectas, entonces tenemos
R1: Y = m1x+b1
R2: Y = m2x+b2
R1=R2 si m1=m2 y b1=b2
R1 || R2 si m1=m2 y b1 ≠ b2
R1 ≠ R2 si m1≠m2 y b1 ≠ b2
Accion Principal Entero m1, m2, b1, b2; Leer (m1); Leer (m2); Leer (b1); Leer (b2); Selección m1=m2 y b1=b2: Escribir (“Las rectas son iguales”); m1=m2 y b1 ≠b2: Escribir (“las rectas son paralelas”); m1 ≠m2: Escribir (“las rectas son diferentes); xi ← (b1-b2) / (m2-m1); yi ← m1*xi+b1; Escribir (“se intersectan en” +xi, xy); fseleccion faccion
36
ESTRUCTURAS ITERATIVAS
Hasta ahora, hemos visto que una acción puede ser ejecutada sólo cero o una vez. ¿Es
posible repetir más de una vez la ejecución de una acción? Si, mediante estructuras
iterativas
Repetir
Es una estructura de control que permite ejecutar un bloque de instrucciones varias
veces hasta que la expresión que controla dicha estructura sea verdadera. Debido a
que la evaluación de la expresión de control se realiza al final del bloque de
instrucciones, este conjunto de instrucciones se ejecuta al menos una vez.
Con un diagrama de flujo, podríamos ilustrarlo así:
La sintaxis algorítmica que vamos a utilizar para expresar este ciclo es:
Repetir <acción 1> . . <acción n> hasta <expresión>
Ejemplo.
En el ejercicio del cálculo del bono, realizar el cálculo e imprimir el bono
correspondiente a c/u de los empleados de la empresa. Asuma que CI=0 indica que ya
se calculó el bono de todos los empleados y que la empresa tiene al menos un
empleado.
Instrucciones
Condición F
V
37
Acción Principal Entero CI, Edad, hijos; Caracter sexo; Real sueldo, bono; Leer (CI); Repetir Leer (sueldo); Leer (Edad); Selección Edad < 25: bono ← sueldo * 0.25; Edad ≥ 25 y Edad ≤ 45: bono ← sueldo * 0.30; Edad > 45: bono ← sueldo * 0.40; fselección Leer (sexo); Leer (hijos); Si sexo=’f’ entonces Bono ← bono + (100.000 * hijos); fsi Si bono>3.000.000 entonces Bono ← 3.000.000; fsi Escribir (CI, bono); Leer (CI) Hasta (CI=0) facción
Dado un conjunto de 100 números enteros, determinar el menor, el mayor y el promedio
de ellos.
Acción Principal Entero Menor, Mayor, N, Suma, cont; Real promedio; Leer (N); Mayor ← N; Menor ← N; Suma ← N; Cont ← 1; Repetir Leer (N) Si N > Mayor entonces Mayor ← N; fsi Si N < Menor entonces Menor ← N; fsi Suma ← Suma + N; cont ← cont+1; Hasta (cont=100) Promedio ← Suma/100; Escribir (Mayor);
38
Escribir (Menor); Escribir (promedio); facción
Mientras
Es una estructura iterativa con control antes de ejecutar el bloque de instrucciones, es
decir, el bloque de instrucciones se ejecuta mientras la evaluación de la expresión sea
verdadera, lo que implica que es posible que no se ejecute dicho bloque. Con un
diagrama de flujo podríamos verlo así:
La sintaxis que vamos a utilizar es
Mientras <condición> hacer <inst1> . . <instn>
fmientras
Ejemplo:
El Banco APC necesita que usted desarrolle un algoritmo que permita cambiar una
cantidad de dinero en billetes a su equivalente en monedas de 500, 100, 50, 20 y 10.
Asuma que la cantidad de dinero es múltiplo de 10. El algoritmo debe terminar cuando
la cantidad introducida sea igual a 0.
Acción Principal Entero dinero, mon500, mon100, mon50, mon20, mon10, resto ; Leer (dinero); Mientras (dinero ≠ 0) hacer mon500 ← dinero div 500; resto ← dinero mod 500; mon100 ← resto div 100; resto ← resto mod 100; mon50 ← resto div 50; resto ← resto mod 50; mon20 ← resto div 20; resto ← resto mod 20;
Instrucciones Condición
F
V
39
mon10 ← resto div 10; Leer (dinero); fmientras Escribir (mon500); Escribir (mon100); Escribir (mon50); Escribir (mon20); Escribir (mon10); faccion
Para
Es una estructura iterativa que es controlada por una variable, la cual es modificada
desde una cantidad inicial en incrementos dados hasta que alcanza un valor final.
La sintaxis que vamos a utilizar es la siguiente:
Para <Identificador> ← <valor1> hasta <valor2> en <inc> hacer <inst 1> <inst n> fpara
En este ciclo la variable <Identificador> se inicializa en <valor1> y el ciclo continuará
hasta que <Identificador> sobrepase <valor2. <inc> es el tamaño del paso en el que se
incrementa la variable <Identificador>
Ejemplo:
Dado un número entero, hallar su factorial.
Instrucciones
Condición F
V
Var ← N1
Var←Var+N2
40
Para calcular el factorial de un número N, se debe cumplir que:
N > 0
Fact(n) = n*Fact(n-1)
Fact(1) = 1
Fact(n) = n*(n-1)*(n-2)* . . . * 2 * 1
Accion Principal Entero i, n, fact; Leer (n); Si (n>0) entonces Para (i=1) hasta n en 1 hacer fact ← fact * i; fpara Escribir (fact); sino Escribir (“el numero debe ser positivo); fsi faccion Usando un Mientras
Accion Principal Entero i, n, fact; Leer (n); i ← 1; Si (n > 0) entonces Mientras (i ≤ n+1) hacer fact ← fact * i; i ← i+1; fmientras Escribir (fact); sino Escribir (“el numero debe ser positivo); fsi faccion
Ejercicios Resueltos:
La panadería Mi Pan desea que usted desarrolle un programa que dada la cantidad de
personas le indique los ingredientes necesarios para hacer el pastel danés. La receta
con la que ellos cuentan es para 4 personas y es la siguiente:
675 gramos de manzanas
75 gramos de mantequilla
150 gramos de azúcar
100 gramos de migas de pan
41
150 mililitros de leche.
Realice un algoritmo que dado el número de personas indique la cantidad de
ingredientes a utilizar
Acción Principal Entero personas Real mantequilla, manzanas, azucar, pan, leche; Leer (personas) Si (personas>0) entonces
Mantequilla ← (75/4)*personas; Manzanas ← (675/4)*personas; azucar ← (150/4)*personas; pan ← (100/4)*personas; leche ← (150/4)*personas; Escribir (“Mantequilla” +((75/4)*personas)+ “gramos”); Escribir (“Manzanas” +((675/4)*personas)+ “gramos”); Escribir (“azucar” +((150/4)*personas)+ “gramos”); Escribir (“pan” +((100/4)*personas)+ “gramos”); Escribir (“leche” +((150/4)*personas)+ mililitros”);
Sino Escribir (“Numero invalido”); fsi faccion
Dados a y b enteros, obtener el producto de ambos por sumas sucesivas.
Accion Principal Entero a, b, i, prod; prod ← 0; Para (I=1) hasta b en 1 hacer prod ← prod + a; fpara faccion
Se tiene un listado de alumnos que consiste en cédula y 4 notas por alumno. La
condición de aprobación es un promedio mayor o igual que 10. Informar un listado en el
mismo orden de entrada con el numero de cédula, el promedio y una leyenda (aprobado
o desaprobado) por alumno. No se conoce la cantidad total de alumnos a procesar. El
listado puede estar vacío (CI=0).
Acción Principal Entero CI, nota1, nota2, nota3, nota4; Real prom; Leer (CI);
42
Mientras (CI ≠0) hacer Leer (nota1); Leer (nota2); Leer (nota3); Leer (nota4); Prom ← (nota1+nota2+nota3+nota4) / 4; Si (prom<10) entonces
Escribir (“El alumno” +CI+ “tiene promedio de” +prom+ “y está reprobado”);
Sino Escribir (“El alumno” +CI+ “tiene promedio de” +prom+ “y está aprobado”);
fsi fmientras faccion
De una prueba de nivel realizada a 100 alumnos se conoce la cantidad total de
preguntas realizadas y la cantidad de respuestas correctas por cada uno. Informar el
nivel registrado de acuerdo a la siguiente escala:
Muy Bueno si el porcentaje es mayor o igual a 90%;
Bueno entre 70% y 90% ;
Regular entre 50% y 70% ;
Malo si el porcentaje es menor que 50%.
Accion Principal Entero preguntas, respuestas, I; Real porcentaje; Leer (preguntas); Para (i=1) hasta 100 en 1 hacer Leer (CI); Leer (respuestas); Porcentaje ← respuestas/preguntas; Seleccion
Porcentaje ≥ 90: Escribir (“El alumno” +CI+ “tuvo un nivel Muy Bueno”); Porcentaje 70 y Porcentaje ≤ 90: Escribir (“El alumno” +CI+ “tuvo un nivel Bueno”); Porcentaje ≥50 y Porcentaje < 70: Escribir (“El alumno” +CI+ “tuvo un nivel Regular”); Porcentaje < 50: Escribir(“El alumno” +CI+ “tuvo un nivel Malo”);
fselección fpara faccion
43
TEMA 6: CLASES Y MÉTODOS Declaración de Clases. Atributos. Métodos. Control de acceso. Utilización de métodos. Pase de
Parámetros: valor y referencia. Métodos Predefinidos. Métodos Constructores y Destructores.
Definición de Objetos. Relaciones entre clases: dependencia, agregación, herencia. Jerarquía de
Clases. Redefiniciones de métodos y polimorfismo. Los métodos en los lenguajes
procedimentales: Acciones y Funciones, ambientes de referenciación: datos locales y no
Locales.
IMPLEMENTACIÓN DE UNA CLASE
La implementación de una clase está delimitada por:
Clase <Nombre_Clase> [hereda de <lista de superclases>] . . . fclase <Nombre_Clase>
Para declarar los atributos y métodos de una clase, usaremos la siguiente notación:
<modo de acceso><tipo de dato><Nombre del atributo>;
<modo de acceso> indica la visibilidad del atributo, fuera del alcance de la clase,
pudiendo ser:
Privado Publico Protegido
Algorítmicamente, las clases son descripciones netamente estáticas de conjuntos
posibles de objetos. Su rol es definir nuevos tipos (valores + operaciones)
Por el contrario, los objetos son instancias particulares de una clase.. Durante la
ejecución del programa sólo los objetos existen.
La declaración de una variable de una clase dada NO crea el objeto. La asociación
siguiente: <Clase> <Variable>, por ejemplo Rectángulo R, no genera automáticamente
un objeto Rectángulo. Sólo indica que R será una referencia a objetos de la clase
rectángulo. La creación de un objeto, debe ser indicada explícitamente por el
44
programador, de forma análoga a como inicializamos las variables con un valor dado,
sólo que para los objetos se hace a través de un método constructor.
CREACIÓN DE OBJETOS
Cada objeto o instancia de una clase debe ser creada explícitamente a través de un
método especial denominado Constructor . Los atributos de un objeto toman valores
iniciales dados por el constructor. Por convención el método constructor tiene el mismo
nombre de la clase y no se le asocia modo de acceso (es público) y se distingue en la
implementación de la clase con las palabras:
Constructor () . . fconstructor ;
Algunos lenguajes proveen un método constructor por defecto para cada clase y/o
permiten la definición de más de un método constructor. En la notación algorítmica,
definimos obligatoriamente un método constructor de la clase.
Si tenemos la clase Rectángulo, representada gráficamente por:
Su declaración quedaría de la siguiente manera:
Clase Rectángulo Privado Real Largo, Ancho; Constructor Rectángulo() Largo ← 10; Ancho ← 5; fconstructor; fclase Rectángulo
Rectángulo
- Altura: Entero - Base: Entero
45
Si quisiéramos calcular el área de un rectángulo, se debe definir además un acción
Principal, donde se realizarán las instrucciones necesarias para ello, ej.
Clase Rectángulo Privado Real Largo, Ancho; Constructor Rectángulo() Largo ← 10; Ancho ← 5; Fconstructor ; Acción Principal Rectángulo R; # se declara un objeto rectángulo Entero Area; R.Rectangulo(); # se crea el objeto rectángulo Area ← R.Largo * R.Ancho; # se calcula el área del rectán gulo Escribir (Area); faccion fclase Rectángulo
MÉTODOS:
Son las operaciones que se aplican sobre los objetos. La implementación de los
métodos no es visible fuera del objeto. Los métodos definen el comportamiento de los
objetos, así como las funcionalidades que ellos tienen.
Tenemos dos tipos de métodos: aquellos que devuelven un solo valor, que llamaremos
Funciones, y los que devuelven 0 o más valores, que llamaremos Acciones.
Métodos: Acciones
Es un mecanismo que permite asociarle un nombre a un conjunto de instrucciones, para
luego referirnos a esas acciones mediante ese nombre. Estos métodos pueden devolver
0 o más valores.
Definición de acciones:
<modo de acceso>Acción <Nombre> [(lista de parámetros formales)] #objetivo de la acción <definición de variables locales> <instrucciones> facción <nombre>;
46
donde:
<nombre> es el identificador de la acción
<lista de parámetros formales> son los objetos en base a los cuales se definen las
acciones, pero que no tienen valor hasta que se use la acción.
<definición de variables locales>, es el conjunto de variables que no tienen significado
fuera de esta secuencia de acciones.
<acciones> secuencia de acciones a ser ejecutadas. Está delimitada por el facción.
Métodos: Función
Es un mecanismo que permite asociarle un nombre a un conjunto de acciones, para
luego referirnos a esas acciones mediante ese nombre. A diferencia de las Acciones,
una función se utiliza cuando se desea obtener solo un valor de retorno.
La notación que vamos a utilizar es la siguiente:
<modo de acceso>Función <nombre> [(parámetros)] → <Tipo> #objetivo de la acción <definición de variables locales> <instrucciones> ← <valor> o >identificador> ffunción <nombre>;
PARÁMETROS
Los parámetros representan los datos que manipulan los métodos al momento de ser
invocados. Tenemos dos tipos de parámetros:
Parámetros actuales:
Se especifican en la llamada a la acción y son los valores sobre los cuales se desea
aplicar la acción
Parámetros formales:
Se especifican en la definición de la acción y son alcanzables solo en el cuerpo de la
acción, tal y como variables locales.
47
TIPOS DE PASE DE PARÁMETROS
Paso por Valor: el parámetro actual no es modificado si se modifica el parámetro formal
dentro de la acción. Esto se debe a que el parámetro actual (constante, variable o
expresión) se evalúa y el resultado se copia en el correspondiente parámetro formal,
que ocupa otra posición de memoria.
Paso por Referencia: el parámetro actual sufre los mismo cambios que el parámetro
formal. El parámetro actual no puede ser ni una constante ni una expresión. Ambos
parámetros comparten la misma posición de memoria.
LLAMADA (O USO) DE UN MÉTODO
objeto.<nombre>[(lista de parámetros)]; La llamada a un método es a su vez una acción elemental que permite la ejecución de
la secuencia de acciones elementales asociada a su nombre. Consiste en indicar el
nombre y los parámetros actuales que van a ser utilizados, los cuales corresponden
posicionalmente a los parámetros formales.
La cantidad de parámetros actuales debe ser igual a la cantidad de parámetros formales
y del mismo tipo de dato.
Ejemplo:
Dado un rectángulo definido por un par de puntos: esquina superior izquierda e inferior
derecha, y dado un punto p, se desea saber en cual de los rectángulos está contenido
p.
Un punto de coordenadas (x, y) esta contenido dentro de un rectángulo cuya esquina
superior izquierda tiene coordenadas (x0, y0) y la inferior derecha (x1, y1) si:
(X0 ≤ X) ∧ (X ≤ X1) ∧ (Y1 ≤ Y) ∧ (Y≤ Y0)
Clase Rectángulo Privado Real X0,Y0, X1,Y1; Constructor Rectángulo(Real XI, YI, XD, YD) X0 ← XI;
Xo, Yo X1, Yo
X0, Y1 X1, Y1
48
Y0 ← YI; X1 ← XD; Y1 ← YD; fconstructor Privado Función Pertenece (Real X, Y) → Lógico # chequea si un punto pertenece a un rectángulo ← (X0 ≤ X) y (X ≤ X1) y (Y1 ≤ Y) y (Y ≤ Y0); ffuncion Privado Función Area () → Real # retorna el área ocupada por un rectangulo ← (X1-X0) * (Y0-Y1); # Largo * Ancho ffunción Privado Función Perímetro () → Real # retorna el perímetro del rectángulo ← 2 * ((X1-X0) + (Y0-Y1)); ffunción Privado Función Diagonal () → Real # retorna el valor de la diagonal del rectangulo Real aux; aux ← ((X1 – X0) ^ 2) – ((Y1 – Y0) ^ 2) ; ← aux ^ (1/2) ; ffuncion fclase
AMBIENTE DE REFERENCIACIÓN
Está dado por el segmento de código en el cual un objeto dado puede ser referenciado
o utilizado. Tenemos entonces 2 tipos de objetos en una acción:
Objetos No locales a una acción:
Objetos que están definidos en otro método, en la clase o en el algoritmo principal, pero
que tienen alcance (pueden ser utilizados) en el método.
Objetos locales a una acción:
Son aquellos objetos que son definidos dentro de cada método.
Ejemplo: Clase Ejemplo Entero X, Y; Acción P1() Entero X, Z; P2 (); facción P1
49
Acción P2() Real Y, W; facción P2 Acción P3() Lógico P1, Y, Z; facción P3 Acción Principal P1(); P3(); facción Principal
Veámoslo gráficamente:
Podemos ver entonces:
Locales No Locales
Principal X. Y, P1, P3
P1 X (P1), Z, P2 Y, P3, P1
P2 Y, W X(P1), Z, P2, P1, P3
P3 P1, Y, Z X(alg. Ppal), P3
Principal
Entero X, Y
P1
P2
P3
Entero X, Z
Real Y, W
Lógico P1, Y, Z
50
TEMA 7: TIPOS DE DATOS ESTRUCTURADOS Arreglos unidimensionales y multidimensionales: Declaración y Operaciones. Algoritmos de
búsqueda secuencial y binaria. Algoritmos de ordenamiento por selección y por intercambio.
Registros. Archivos Secuenciales: Declaración, Operaciones, Archivos de Texto. Algoritmo de
mezcla de archivos.
ESTRUCTURA DE DATOS
Es una herramienta mediante la cual es posible almacenar datos estructurados en la
memoria del computador, permitiendo manipular datos complejos de forma sencilla.
Estas estructuras de datos están formadas por más de un elemento, donde estos
pueden ser todos del mismo tipo de dato (ED homogénea) o de tipos de datos
diferentes (ED heterogénea).
ARREGLOS
Un arreglo es un Tipo de Dato Estructurado (TDE) cuya implantación implica una
estructura de datos conformada por una sucesión de celdas, que permite almacenar en
la memoria principal del computador un conjunto finito de elementos homogéneo (del
mismo tipo de dato). Para hacer referencia a cualquiera de las celdas del arreglo es
necesario el nombre del arreglo y el valor de uno de los elementos perteneciente al
conjunto de índices asignado, lo que permite tener acceso aleatorio.
La notación que vamos a utilizar para definir arreglos es la siguiente:
Arreglo <Identificador> de <Tipo> [Li...Ls]
1 2 3 . . . N -1 N
Tipo
Número de
Componentes Elemental
Estructurado
Entero, caracter, lógico, real
Enumerado
Subrango
Homogéneos: archivos
arreglos
Heterogéneos: registros
1
n
Tipo de
Componentes =
≠
51
Donde:
Li: es el limite inferior del arreglo
Ls es el limite superior del arreglo
Acceso a los elementos de un arreglo
Para acceder a los elementos almacenados en un arreglo, contamos con 2 operaciones:
Operación Constructora:
Permite asociarle a un arreglo un valor estructurado correspondiente a las
características del arreglo, es decir, permite indicar explícitamente cuales son todos los
valores que va a almacenar el arreglo. La operación constructora es utilizada en el
momento de la declaración del arreglo.
La notación que vamos a utilizar para la operación constructora es la siguiente:
Arreglo Vocales de caracter [ ] = {‘a’,’e’,’i’,’o’,’u’}
Para este caso tendríamos declarado un arreglo de 5 posiciones, ubicadas de la
siguiente manera:
Operación Selectora:
Permite referenciar un componente individual de un arreglo para lo cual se debe indicar
el nombre del arreglo seguido de un valor particular del intervalo de definición.
La forma de utilizar la operación selectora es la siguiente:
<Identificador del arreglo>[<posición>]
En el caso del ejemplo anterior, la operación selectora equivalente sería:
1 2 3 4 5
‘a’ ‘e’ ‘i’ ‘o’ ‘u’
52
Vocales[1] ← ‘a’; Vocales[2] ← ‘e’; Vocales[3] ← ‘i’; Vocales[4] ← ‘o’; Vocales[5] ← ‘u’;
Ejemplo:
Inicializar un arreglo
Acción Inicializar (Var Arreglo A, Entero N) #Incializa el Arreglo A de N posiciones con valore s dados por el #usuario. Entero i, j ; Para i ← 1 hasta N hacer Leer (j); A[i] ← j; fpara faccion
Ejercicios Resueltos:
Hallar el máximo valor en un arreglo de N elementos enteros
Acción Máximo Entero max, i ; Arreglo A de Entero [1…N]; Leer (N); Inicializar(A); max ← A[1]; Para i ← 2 hasta N hacer Si (A[i] > max) entonces max ← A[i]; fsi fpara facción
Dado un arreglo A de N elementos enteros, almacenar en un arreglo B, las sumas
parciales de los elementos de A
Acción Sumas_Parciales Entero ant, i ; Arreglo A de Entero [1…N]; Arreglo B de Entero [1…N]; Leer (N); Inicializar(A); ant ← 0;
53
Para i ← 1 hasta N hacer B[ ] ← ant + A[i]; ant ← B[i]; fpara facción
Dados 2 arreglos A y B de longitudes N y M, el primero ordenado ascendente y el
segundo ordenado descendente, crear un nuevo arreglo C de N + M elementos
intercalando los elementos de A y B de modo que c quede ordenado ascendente.
Acción Mezcla Entero j, i, k ; Arreglo A de Entero [1…N]; Arreglo B de Entero [1…M]; Arreglo C de Entero [1…N+M]; Leer (N); Leer (M); Inicializar(A); Inicializar(B); i ← 1; j ← M; k ← 1; Mientras (k ≤ N+M) hacer Selección i = N: Para j ← j hasta 1 en –1 hacer C[ k ] ← B [j]; k ← k +1; fpara
j = 1: Para i ← i hasta N hacer C[k] ← A [i]; k ← k +1; fpara
(i ≠ N) y (j ≠ 0): Si (A[i] ≤ B[j]) entonces C[k] ← A [i]; i ← i + 1; sino C[k] ← B [j]; j ← j - 1; fsi k ← k + 1; fseleccion fmientras facción
ARREGLOS MULTIDIMENSIONALES
Es una extensión de los arreglos unidimensionales al considerar que el tipo base es un
arreglo unidimensional o multidimensional.
54
ARREGLO BIDIMENSIONAL
Es un arreglo cuyas componentes son arreglos unidimensionales (comúnmente llamado
Matriz)
Especificación:
Arreglo <Identificador> de <Tipo> [Li 1...Ls 1], [Li 2...Ls 2]
Donde:
Li1 : limite inferior del arreglo
Ls1: limite superior del arreglo
Li2: limite inferior de los arreglos componentes
Ls2: limite superior de los arreglos componentes
La operación selectora sería:
<Identificador>[<posición> 1][<posición> 2]
La operación constructora para el caso de una matriz de 3 x 4
Arreglo A de entero [ ] [ ]={{1,2,3,4},{0,0,0,0},{-1, 2, 8, 100}};
Li1 Ls1 Li2
Ls2
11 12 13 14
21 22 23 24
31 32 33 34
55
Ejemplo:
Acción Inic_matriz (Entero N, M; Var Arreglo M) # Inicializa una matriz de NxM Entero i, j; Para i ← 1 hasta N hacer Para j ← 1 hasta M hacer Leer (M[i,j]); fpara fpara faccion Inic_matriz
Ejercicios Resueltos:
Dadas 2 matrices A y B de NxM, obtener la suma de ellas en otra matriz C
Acción Principal Entero i, j; Arreglo A de Entero [1…N][1…M]; Arreglo B de Entero [1…N][1…M]; Arreglo C de Entero [1…N][1…M]; Leer (N); Leer (M); Inic_matriz(N,M,A); Inic_matriz(N,M,B); Para i ← 1 hasta N hacer Para j ← 1 hasta M hacer C[i,j] ← A[i,j]+B[i,j]; fpara fpara faccion
Multiplicación de 2 matrices
Clase Multiplicar_Matrices Entero N,M,P; Arreglo A de Entero [1…N][1…M];
1 2 3 4
0 0 0 0
-1 2 8 100
56
Arreglo B de Entero [1…M][1…P]; Arreglo C de Entero [1…N][1…P]; Funcion Prod ( Entero i, j) -> Entero Entero k, p; Para k ← 1 hasta M hacer p ← p+ A[i,k] * B[k,j]; fpara ← p función Acción Inic_matriz (Entero N, M; Var Arreglo M) # Inicializa una matriz de NxM Entero i, j; Para i ← 1 hasta N hacer Para j ← 1 hasta M hacer Leer (M[i,j]); fpara fpara faccion Inic_matriz Accion Principal Entero I, j; Inic_matriz(N,M,A); Inic_matriz(M,P,B); Para i ← 1 hasta N hacer Para j ← 1 hasta P hacer C[i,j] ← Prod(i,j); fpara fpara faccion fclase
ALGORITMOS DE ORDENAMIENTO
Vamos a ver 3 algoritmos de ordenamiento, no quiere decir que sean los mejores ni los
únicos.
Selección Directa
Consiste en lo siguiente:
Buscar el elemento más pequeño de la lista.
Intercambiarlo con el elemento ubicado en la primera posición de la lista.
Buscar el segundo elemento más pequeño de la lista.
Intercambiarlo con el elemento que ocupa la segunda posición en la lista.
Repetir este proceso hasta que se haya ordenado toda la lista.
57
El algoritmo es el siguiente:
Acción Seleccion_Directa (Entero N; Arreglo A) # Acción que ordena un arreglo por selección direct a Entero i, j, k, min; Para i ← 1 hasta N -1 hacer Min ← A[i]; Para J ← i hasta N hacer Si A[j] < min entonces Min ← A[j]; K ← j fsi fpara Intercambiar(A[i], A[k]); fpara faccion Ejemplo: dado el arreglo
4 3 5 2 1
1 - 3 - 5 - 2 – 4 se busca el menor y se intercambia con el de la posición 1
1 - 2 - 5 - 3 – 4 se busca el menor desde la posición 2 y se intercambia con el
que ocupa dicha posición
1 - 2 - 3 - 5 – 4 se busca el menor desde la posición 3 y se intercambia con el
que ocupa dicha posición
1 - 2 - 3 - 4 – 5 se busca el menor desde la posición 4 y se intercambia con el
que ocupa dicha posición
Inserción Directa
El algoritmo consiste en lo siguiente:
Se toma el primer elemento
Se toma el segundo y se compara con el primero: si es mayor, se coloca a la derecha, y
si es menor a la izquierda
Se toma el tercer elemento y se compara con los dos anteriores, desplazándolo hasta
que quede en su posición final.
Se continua haciendo esto, insertando cada carta en la posición que le corresponde,
hasta que este ordenado.
El algoritmo es:
58
Acción Insercion_directa(Entero N; Arreglo A) # Ordena un arreglo por inserción directa Entero i, j, temp; Para i ← 2 hasta N hacer temp ← A[ i ]; j ← i - 1; Mientras ((A[ j ] > temp) y (j>=1)) hacer A[ j+1] ← A[ j ]; j ← j -1; fmientras A[ j + 1 ] ← temp; fpara
Ejemplo, dado el arreglo del ejemplo anterior:
4 - 3 - 5 - 2 – 1
temp toma el valor del segundo elemento, 3. La primera carta es el 4. Ahora
comparamos: 3 es menor que 4. Luego desplazamos el 4 una posición a la derecha y
después copiamos el 3 en su lugar.
4 - 4 - 5 - 2 – 1
3 - 4 - 5 - 2 – 1
El siguiente elemento es 5. Comparamos con 4. Es mayor que 4, así que no ocurren
intercambios.
Continuamos con el 2. Es menor que cinco: desplazamos el 5 una posición a la
derecha:
3 - 4 - 5 - 5 – 1
Comparamos con 4: es menor, así que desplazamos el 4 una posición a la derecha:
3 - 4 - 4 - 5 – 1
Comparamos con 3. Desplazamos el 3 una posición a la derecha:
3 - 3 - 4 - 5 – 1
Finalmente copiamos el 2 en su posición final:
2 - 3 - 4 - 5 – 1
El último elemento a ordenar es el 1. Cinco es menor que 1, así que lo desplazamos
una posición a la derecha:
2 - 3 - 4 - 5 – 5
Continuando con el procedimiento la lista va quedando así:
2 - 3 - 4 - 4 - 5
2 - 3 - 3 - 4 - 5
2 - 2 - 3 - 4 - 5
59
1 - 2 - 3 - 4 – 5
Burbujas
Consiste en desplazarse repetidamente a través del arreglo, comparando elementos
adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente
posición se intercambian.
El algoritmo es el siguiente:
Acción Burbujas (Entero N; Arreglo A) # Ordena un arreglo por el método de burbujas Entero i, j; Para i ← 2 hasta N hacer Para j ← N hasta I en –1 hacer Si A[ j-1] > A[ j ] entonces Intercambiar(A[j-1], A[ j ]); fsi fpara fpara
Ejemplo:
4 - 3 - 5 - 2 - 1
4 - 3 - 5 - 1 – 2
4 - 3 - 5 - 1 – 2
4 - 3 - 1 - 5 – 2
4 - 1 - 3 - 5 – 2
1 - 4 - 3 - 5 – 2
1 - 4 - 3 - 5 – 2
1 - 4 - 3 - 2 – 5
1 - 4 - 2 - 3 – 5
1 - 2 - 4 - 3 – 5
1 - 2 - 4 - 3 – 5
1 - 2 - 3 - 4 – 5
ALGORITMOS DE BÚSQUEDA
Vamos a ver 3 algoritmos de búsqueda, no quiere decir que sean los mejores ni los
únicos.
60
Búsqueda Lineal
La búsqueda consiste en recorrer secuencialmente el arreglo hasta encontrar la primera
aparición del elemento buscado.
Existen dos condiciones que ponen fin a la búsqueda:
Se encontró el elemento buscado
Se recorrió todo el arreglo.
El algoritmo es el siguiente:
Función Busqueda_lineal (Entero N, x; Arreglo A) → Entero # Acción que busca un elemento x en un arreglo Entero i, pos; pos ← 0; Para i ← 1 hasta N hacer Si (A[i] = x) entonces pos ← i; fsi fpara ← pos ffuncion
Búsqueda Lineal (Arreglo Ordenado)
En este caso, el arreglo sobre el que se va a hacer la búsqueda está ordenado
El algoritmo es:
Función Busqueda_lineal2 (Entero N, x; Arreglo A) → Entero # Acción que busca un elemento x en un arreglo Entero i, pos; pos ← 0; Mientras (i<N) y (A[i] < x) hacer i ← i+1; fpara Si (A[i] = x) entonces pos ← i; fsi ← pos ffuncion
Búsqueda Binaria
Este algoritmo requiere como condición inicial que el arreglo este ordenado.
61
El algoritmo de basa en que para buscar un elemento en un arreglo de tamaño N, se
puede reducir el problema a buscar en la mitad de los elementos, dado que el arreglo
esta ordenado. Así, podemos comparar el elemento ubicado en el medio del arreglo
(A[med]) con el elemento a buscar, y según la comparación tenemos las siguientes
acciones:
A[med] = x : esto implica que se encontró el elemento
A[med] > x : Si esto es cierto, el elemento buscado debe encontrarse entre las
posiciones 1 y med-1.
A[med] < x : Si esto es cierto, el elemento buscado debe encontrarse entre las
posiciones med+1 y N.
Es necesario establecer en que sub-arreglo estamos trabajando, para ello utilizaremos 2
variables, Li y Ls que nos indicaran los limites inferior y superior de tal subarreglo.
El algoritmo es el siguiente:
Función Busqueda_binaria (Entero N, x; Arreglo A) → Entero # Acción que busca un elemento x en un arreglo Entero Li, Ls, med, pos; pos ← 0; Si (x ≥ A[1]) y (x ≤ A[N]) entonces Li ← 1; Ls ← N; Mientras (Li ≤ Ls) y (pos ≠ 0) hacer Med ← (Li + Ls) div 2; Selección A[med] < x : Li ← med + 1; A[med] > x: Ls ← med – 1;
A[med] = x: pos ← med; fseleccion
fmientras fsi ← pos ffuncion
ARCHIVOS
Es una estructura de datos que consiste en una secuencia de elementos del mismo tipo
que residen en la memoria secundaria del computador.
Características principales
62
Residen en memoria secundaria
Independencia respecto a los programas
Permanencia de la información almacenada
Gran capacidad de almacenamiento
Tipos de organización
Secuencial
Aleatoria o directa
Indexada
La declaración de un archivo secuencial sería:
Archivo <Identificador>;
Operaciones Básicas sobre Archivos
Las operaciones básicas sobre un archivo secuencial son:
Escritura o lectura
Cabezal
M Cabezal N
1 2 3 4
63
Abrir el archivo
Esta operación debe realizarse antes de cualquier otra operación sobre el archivo. Esta
operación prepara el ambiente para trabajar con los archivos
AbrirArchivo (<Identificador> A ,“nombre del archivo”, <Argumentos>);
Donde <Argumentos> es uno o más de las siguientes palabras reservadas:
Escribir: indica que el archivo se abre de solo escritura
Lectura: indica que el archivo de abre de solo lectura
Texto: indica que el archivo a abrir es un archivo de texto
Binario: indica que el archivo a abrir es un archivo binario
Añadir: indica que el archivo se abre de escritura pero todo lo que se escriba se añade
al final del archivo
Los argumentos de combinan con el operador lógico y. Por ejemplo:
AbrirArchivo (A, “prueba.txt”, Lectura y Texto );
Cerrar el archivo
Una vez que se ha utilizado el archivo, es cerrado para dejarlo disponible a un nuevo
uso.
CerrarArchivo (<Identificador> A );
Fin de archivo
Es una función que retorna verdadero cuando se alcanza el fin del archivo, y falso en
caso contrario.
FDA(<Identificador> A );
Operaciones de Entrada y Salida
Son las que permiten escribir y leer el archivo
Leer del archivo
64
LeerArchivo (<Identificador> A , <Identificador>);
Escribir en el archivo
EscribirArchivo (<Identificador> A, <Identificador>);
Ejemplo: Imprimir todos los caracteres de un archivo.
Acción Principal Archivo A; Caracter c; AbrirArchivo (A, “prueba.txt”, Lectura y Texto ); Mientras No FDA(A) hacer LeerArchivo (A, c); Escribir ( c ); fmientras CerrarArchivo (A); faccion
Ejercicios Resueltos:
Dado un archivo de texto se quiere generar otro igual al anterior pero suprimiendo las
vocales.
Acción Principal Archivo A; Archivo A; Caracter c; AbrirArchivo (A, “prueba.txt”, Lectura y Texto ); AbrirArchivo (B, “res.txt”, Escribir y Texto ); LeerArchivo (A, c); Mientras No FDA(A) hacer Si No Vocal ( c ) entonces EscribirArchivo (B, c ); fsi LeerArchivo (A, c); fmientras CerrarArchivo (A); CerrarArchivo (B); faccion
REGISTROS
Estructura de datos formada por una colección finita de elementos, no necesariamente
homogéneos, llamados campos, y permiten almacenar una serie de datos relacionados
entre sí bajo un nombre común.
65
Especificación
Registro <nombre_de_registro> = <Tipo> 1 <Identificador> 1 <Tipo> 2 <Identificador> 2 ..... <Tipo> N <Identificador> N fregistro
Acceso a los elementos de un Registro
Para acceder a los elementos de un registro contamos con dos operaciones
Operación Constructora
Permite asociarle al nombre de un registro un dato estructurado que se corresponda
componente a componente.
Ejemplo:
Registro Fecha = Entero día, mes, año; fregistro Registro Persona = Entero CI; String Nombre; Fecha Fnacimiento; fregistro Persona ← {10234223, “Somebody”, {10,10,1986} }
Operación Selectora
Permite referenciar una componente particular del registro.
<nombre>.<campo>
Así como un arreglo, el registro puede ser pasado por parámetros, así como cada
campo individual.
Ejemplo:
Definir una estructura de datos que permita almacenar toda la información relevante del
curso de algoritmos y programación: notas, profesores, preparadores, estudiantes.
Registro estudiante= Entero cedula;
66
String nombre; String seccion; Entero nota; fregistro
Registro AlgyProg String prof; String prep; String seccion; Arreglo est de estudiante[1…N]; fregistro
Ejercicios Resueltos:
Dadas dos fechas, decir cuál de ellas es más antigua.
Registro Fecha = Entero día, mes, año; fregistro Acción Principal Fecha f1, f2; Leer (f1.dia); Leer (f1.mes); Leer (f1.año); Leer (f2.dia); Leer (f2.mes); Leer (f2.año); Selección f1.año > f2.año: Escribir (f1.dia, f1.mes, f1.año); f1.año < f2.año: Escribir (f2.dia, f2.mes, f2.año); f1.año = f2.año: Selección f1.mes > f2.mes: Escribir (f1.dia, f1.mes, f1.año);
f1.mes < f2.mes: Escribir (f2.dia, f2.mes, f2.año); f1.mes = f2.mes: Selección
f1.dia > f2.dia: Escribir (f1.dia, f1.mes, f1.año); f1.dia < f2.dia: Escribir (f2.dia, f2.mes, f2.año); f1.dia = f2.dia: Escribir (“son iguales”);
fseleccion fseleccion fseleccion faccion
Dado un archivo de estudiantes, imprimir aquellos cuya cédula de identidad sea mayor
que 10 millones. Use la siguiente especificación:
Tipo Registro Estudiante = Entero CI; String Nombre;
67
Entero ND; fregistro
Acción Principal Archivo Arch_Est; Estudiante est; AbrirArchivo (Arch_Est, “estudiantes.bin”, lectura y binario ); Mientras No FDA(Arch_Est) hacer LeerArchivo (Arch_Est, est); Si (est.CI > 10000000) entonces Escribir (est.CI, est.Nombre, est.ND); fsi fmientras CerrarArchivo (Arch_Est); faccion Dados dos archivos de estudiantes ordenados ascendentemente por el campo CI,
generar un tercer archivo que sea la mezcla ordenada de los anteriores.
Tipo Registro Estudiante = Entero CI; String Nombre; Entero ND; fregistro Accion Principal Archivo Arch1, Arch2, Arch3; Estudiante est1, est2; AbrirArchivo (Arch1, “est1.bin”, lectura y binario ); AbrirArchivo (Arch2, “est2.bin”, lectura y binario ); AbrirArchivo (Arch_Est, “est3.bin”, escritura y binario ); SI No FDA(Arch1) entonces
LeerArchivo (Arch1, est1); fsi Si No FDA(Arch2) entonces
LeerArchivo (Arch2, est2); fsi Mientras (No FDA(Arch1) y No FDA(Arch1)) hacer Si (est1.CI ≥ est2.CI) entonces EscribirArchivo (Arch3, est2);
LeerArchivo (Arch2, est2); Sino EscribirArchivo (Arch3, est1);
LeerArchivo (Arch1, est1); fsi fmientras Mientras No FDA(Arch1) hacer
LeerArchivo (Arch1, est1); EscribirArchivo (Arch3, est1);
fmientras Mientras No FDA(Arch2) hacer
LeerArchivo (Arch2, est2);
68
EscribirArchivo (Arch3, est2); fmientras CerrarArchivo (Arch1); CerrarArchivo (Arch1); CerrarArchivo (Arch3); faccion
69
REFERENCIAS
Arnold, K., Gosling, J., Holmes, D. El lenguaje de programación Java. 3a Edición.
Addison-Wesley. 2001.
Booch, G. Análisis y diseño orientado a objetos. Addison Wesley. Segunda edición,
1996.
Carmona, R. El enfoque Orientado a Objetos. Escuela de Computación, UCV
Coto, Ernesto. Lenguaje pseudoformal para la construccion de algoritmos. Escuela de
Computación. 2003.
Deitel, H. y Deitel, P. Java: Cómo Programar. 5ta. Edición. Prentice-Hall, 2004.
Fowler, Martin. UML Gota a Gota. Addison Wesley Longman. 1999.
Jaime Sisa, Alberto. Estructuras de Datos y Algoritmos. Prentice-Hall. 2002.
Meyer, B. Construcción de Software Orientado a Objetos. Prentice Hall. Segunda
Edición. 1999