Lenguaje de Diseño:

Estructuración de Datos

Teoría Nº 8

Primer Cuatrimestre 2017

Resolución de Problemas y Algoritmos

ENUNCIADO: DADO UN NÚMERO ENTERO POSITIVO, ENCONTRAR EL ALGORITMO QUE DETERMINE EL FACTORIAL DE DICHO NÚMERO.

• DAR UN VALOR A UN OBJETO.

• CALCULAR LA SUMA DE DOS NÚMEROS

• CALCULAR EL PRODUCTO DE DOS NÚMEROS

• MIENTRAS <condición> HACER

<acciones primitivas>

FINMIENTRAS

2017

La determinación de los objetos es una parte importante en el proceso de resolución

Restricción: los objetos deben determinarse en función de los cuatro tipos de datos primitivos.

Ejemplo:

Una empresa recibe mensualmente información sobre las ventas de cada una de sus tres sucursales. Se desea obtener un listado de aquellas sucursales cuyas ventas superan el promedio de las mismas. 2017

Versión 1: t1 - Leer los datos de las sucursales. t2 - Determinar el promedio. t3 - Comprobar cual o cuáles de las sucursales tiene venta superior al promedio.

Versión 2:

t11 - Para cada sucursal leer sus ventas y acumularlas. t2 - Determinar el promedio. t31 - Para cada sucursal leer sus ventas, comparar- las con el promedio. Si es mayor al promedio, informar.

2017

Dia

gram

a de

Flu

jo d

e la

solu

ción

en

Leng

uaje

del

Pro

blem

a

C

Ingresar la venta de la sucursal .

De 1 a 3

Acumular la venta.

Calcular el promedio.

F

informo venta > promedio

V F Ingresar la venta de la sucursal .

De 1 a 3

¿Objetos?

2017

Objetos?

venta - guarda la venta de cada sucursal.

acumulo - acumula las ventas

promedio - almacena promedio.

i - lleva la cuenta de la sucursal que trato.

2017

Algoritmo en lenguaje de diseño:

ALGORITMO “Ventas” COMENZAR VENTA, ACUMULO, PROMEDIO: real I: entero PROMEDIO 0 ACUMULO 0 PARA I DESDE 1 HASTA 3 CON PASO 1 HACER LEER VENTA ACUMULO ACUMULO + VENTA FINPARA PROMEDIO ACUMULO / 3 PARA I DESDE 1 HASTA 3 CON PASO 1 HACER LEER VENTA SI VENTA > PROMEDIO ENTONCES

ESCRIBIR I, VENTA FINSI FINPARA FIN

¿Desventajas?

2017

Objetos

vent1 - guarda la venta de sucursal 1.

vent2 - guarda la venta de sucursal 2.

vent3 - guarda la venta de sucursal 3.

promedio - acumula las ventas y saca promedio.

Solución 2:

2017

Algoritmo en lenguaje de diseño: ALGORITMO “Ventas” COMENZAR VENT1, VENT2, VENT3, PROMEDIO: real LEER VENT1, VENT2, VENT3 PROMEDIO (VENT1+ VENT2 + VENT3) / 3 SI VENT1 > PROMEDIO ENTONCES

ESCRIBIR VENT1 FINSI SI VENT2 > PROMEDIO ENTONCES ESCRIBIR VENT2 FINSI SI VENT3 > PROMEDIO ENTONCES

ESCRIBIR VENT3 FINSI FIN

2017

100 Objetos?

vent1 - guarda la venta de sucursal 1. vent2 - guarda la venta de sucursal 2.

...

vent100 - guarda la venta de sucursal 100.

2017

ALGORITMO “Ventas” COMENZAR VENT1, VENT2, ..., VENT100, PROMEDIO: real LEER VENT1, VENT2, ..., VENT100 PROMEDIO (VENT1+ VENT2 + .. + VENT100) / 100 SI VENT1 > PROMEDIO ENTONCES

ESCRIBIR VENT1 FINSI SI VENT2 > PROMEDIO ENTONCES ESCRIBIR VENT2 FINSI

. .

. SI VENT100 > PROMEDIO ENTONCES

ESCRIBIR VENT100 FINSI FIN 2017

Otro Problema: Existen ocasiones donde los objetos no se pueden representar solamente con primitivas.

Es necesario relacionar 2 o más tipos primitivos para poder construir nuestro nuevo objeto.

Ejemplo: Representar el objeto número complejo.

número complejo

real imaginaria

Nuevo objeto, de tipo complejo, conformado o estructurado con objetos de tipo primitivo.

real real Preal Pimag

2017

Todas las formas posibles en que nosotros relacionemos lógicamente datos primitivos para construir nuevos objetos se denomina:

ESTRUCTURACIÓN DE DATOS

Características:

4 toda estructura se construye a partir de objetos primitivos 4 el conjunto de datos se identifica con un único nombre 4una estructura se diferencia de otra por la forma en que sus

componentes están relacionadas y el tipo de las mismas 4se encuentran tanto en memoria principal como en memoria secundaria.

Nos concentraremos en la estructuras de memoria principal 2017

Existe una estructura en particular que nos interesa denominada:

ARREGLO LINEAL DE DATOS

Tipos de Estructuras de Datos:

Estructuras Contiguas o Físicas: los datos se encuentran en posiciones adyacentes de memoria.

Estructuras Enlazadas: los datos no se encuentran en posiciones adyacentes de memoria.

2017

578 120 625 1230 1 2 3 99 100

Solución 3: Reunir los 100 objetos en un solo objeto estructurado.

578 120 625 1230 1 2 3 99 100

Arreglo Lineal

VECTOR

VENTA

VENTA[3] 625

Arreglo Lineal

2017

4 Todos los elementos del arreglo son del mismo tipo primitivo por lo tanto es una estructura homogénea.

4Es una estructura lineal de acceso directo, es decir se accede a un dato en forma directa con sólo indicar la posición o subíndice. El número que indica la posición (subíndice) es un número natural.

Donde:

4Es una estructura estática, es decir su tamaño (cantidad y tipo de elementos del arreglo) se define en tiempo de compilación a partir de la declaración y no cambia durante la ejecución del programa. (Es posible definir arreglos cuya dimensión se modifique en tiempos de ejecución (estructuras dinámicas) pero este concepto no será abordado en este curso).

4El número de elementos o dimensión, se define con la declaración junto con el límite mínimo y límite máximo o rango.

2017

Solución 3: Reunir los 100 objetos en un solo objeto estructurado.

578 120 625 1230 1 2 3 99 100

Arreglo Lineal

VECTOR

VENTA

578 120 625 1230 1 2 3 99 100

VENTA[3] 625

Donde:

4 todos los elementos del arreglo son del mismo tipo primitivo. 4 el número que indica la posición (subíndice) es un número natural.

Arreglo Lineal

2017

Declaración:

VENTA: arreglo[1..100] de real

Usos y operaciones: VENTA[15] (valor almacenado en la posición 15 del arreglo)

VENTA[I] (valor almacenado en la posición indicada por el valor almacenado en I)

I 20 VENTA[I] ≡ VENTA[20]

VENTA[K+5] (valor almacenado en la posición indicada por el valor resultante de la expresión K+5)

K 20 VENTA[K+5] ≡ VENTA[20 +5] ≡ VENTA[25]

Asignar un valor VENTA[10] 30

Operación J 13 * J + VENTA[I]

arreglo <Nombre> : [ Li .. Ls] de <tipo>

2017

Objetos:

VENTA - arreglo de 100 elementos de tipo real.

I - variable índice del arreglo.

PROMEDIO - para el cálculo del promedio.

ALGORITMO “Ventas” COMENZAR VENTA: arreglo [1..100] de real PROMEDIO: real I: entero PROMEDIO 0 PARA I DESDE 1 HASTA 100 CON PASO 1 HACER

LEER VENTA[I] PROMEDIO PROMEDIO + VENTA[I]

FINPARA PROMEDIO PROMEDIO / 100 PARA I DESDE 1 HASTA 100 CON PASO 1 HACER

SI VENTA[I] > PROMEDIO ENTONCES ESCRIBIR I, VENTA[I] FINSI

FINPARA FIN

2017

Suponga Ud. que se desea hacer un programa relacionado con los 250 empleados de una empresa.

Ejemplo:

¿Es posible definir el siguiente arreglo?

Los datos de cada empleado que el programa va a necesitar son: el año de ingreso de esa persona a la empresa, género (F para Femenino y M para Masculino) y si es profesional o no (Verdadero o Falso). Todos esos datos se almacenarán en un único arreglo.

2017

Ejemplo:

Diseñe y dibuje de qué manera estructurar el almacenamiento de los siguientes datos en una única estructura. A y B son matrices de nxn valores enteros.

¿Dimensión del arreglo?

La selección de una estructura de datos y de la manera de relacionar dichos datos es una decisión importante, ya que ello influye decisivamente en el algoritmo que va a usarse para resolver un determinado problema.

PROGRAMACION= ESTRUCTRAS DE DATOS + ALGORITMOS

2017

Ejemplo:

Lea atentamente el siguiente ejemplo para luego diseñar y dibujar 2 formas (una, utilizando más de una estructura y otra, utilizando una única estructura) de cómo estructurar el almacenamiento de todos los datos.

Suponga usted que necesita almacenar datos de los alumnos del nivel secundario de la Esc. Nº 48 Gral. San Martin. Turno mañana y tarde. Por cada turno, el nivel secundario posee 6 cursos mixtos (varones y mujeres). Por cada curso existen 2 divisiones (A y B)

2017

Ejemplo:

Solución:

- Ingresar los elementos en el arreglo.

- Encontrar el menor elemento del arreglo y mostrarlo.

- Repetir la operación anterior para los restantes sin

considerar el elemento ya encontrado.

Escribir un algoritmo que dado un arreglo de 7 elementos enteros positivos menores a 5000, los muestre ordenados de menor a mayor.

2017

ALGORITMO “Ordenar”

COMENZAR

V: arreglo [1..7] de entero

I,J, MIN: entero

PARA I DESDE 1 HASTA 7 CON PASO 1 HACER

LEER V[I]

FINPARA

PARA I DESDE 1 HASTA 7 CON PASO 1 HACER

MIN 1

PARA J DESDE 1 HASTA 7 CON PASO 1 HACER

SI V[J] < V[MIN] ENTONCES

MIN J

FINSI

FINPARA

ESCRIBIR V[MIN]

V[MIN] 100000

FINPARA

FIN

Se debería controlar que los números i n g r e s a d o s s e a n positivos y no mayor que 5000

2017

Ejemplo:

Escribir un algoritmo que ordene de menor a mayor los elementos de un arreglo de 7 elementos enteros positivos.

Solución: - Encontrar el menor elemento del arreglo. - Intercambiarlo con el primero del arreglo. - Repetir la misma operación para los restantes sin considerar al elemento ya ordenado.

2017

Ejemplo: estado inicial: 21 35 17 8 14 42 2

1º intercambio: 2 35 17 8 14 42 21

2º intercambio: 2 8 17 35 14 42 21

3º intercambio: 2 8 14 35 17 42 21

4º intercambio: 2 8 14 17 35 42 21

5º intercambio: 2 8 14 17 21 42 35

6º intercambio: 2 8 14 17 21 35 42

2017

Objetos: V - arreglo de enteros a ordenar. I,J - variables índice del arreglo. MIN - variable auxiliar que indica el índice donde se

encuentra el elemento mínimo. VAL_MI - variable auxiliar usada para el intercambio

de valores.

2017

Versión 1:

t1 - Ingresar los elementos del arreglo.

t2 - Repetidamente mientras el arreglo no esté

ordenado, buscar el menor del arreglo, luego

colocarlo en la posición correspondiente.

t3 - Mostrar el arreglo ordenado.

Versión 2:

t1 - Ingresar los elementos del arreglo.

t20 - Repetidamente mientras el arreglo no esté

ordenado

t21 - Buscar el menor del arreglo y guardarlo en

MIN.

t22 - Intercambiar con el lugar que corresponda

en el ordenamiento el valor de V[MIN].

t3 - Mostrar el arreglo ordenado.

2017

ALGORITMO “Ordenar” COMENZAR V: arreglo [1..7] de entero I,J, MIN, VAL_MI: entero PARA I DESDE 1 HASTA 7 CON PASO 1 HACER LEER V[I] FINPARA PARA I DESDE 1 HASTA 7-1 CON PASO 1 HACER MIN I PARA J DESDE I+1 HASTA 7 CON PASO 1 HACER

SI V[J] < V[MIN] ENTONCES MIN J FINSI

FINPARA VAL_MI V[MIN] V[MIN] V[I] V[I] VAL_MI FINPARA PARA I DESDE 1 HASTA 7 CON PASO 1 HACER ESCRIBIR V[I] FINPARA FIN

2017

V[1] V[2] V[3] V[4] V[5] V[6] V[7] I MIN J VAL_MIdespués dela lectura

21 35 17 8 14 42 2ingreso alpara externo

16

1er iteraciónsobre I

1 1ingreso alpara interno

27

1er iteraciónsobre J

22da iteraciónsobre J

3 33er iteraciónsobre J

4 44ta iteraciónsobre J

55ta iteraciónsobre J

66ta iteraciónsobre J

7 7salida delpara interno

2 35 17 8 14 42 21 22da iteraciónsobre I

2 2ingreso alpara interno

37

1er iteraciónsobre J

3 32da iteraciónsobre J

4 43er iteraciónsobre J

54ta iteraciónsobre J

65ta iteraciónsobre J

7salida delpara interno

2 8 17 35 14 42 21 8

2017

Ejemplo:

Versión 1: t0 – Definir objetos y asignar valores. t1 - Ingresar 10 valores enteros en un arreglo A. t2 - Ingresar hasta 25 caracteres en un otro arreglo B.

Escribir un algoritmo que le permita al usuario ingresar 10 valores enteros en un arreglo y hasta 25 caracteres en otro arreglo.

¿Objetos?

2017

Versión 2: t0- Definir objetos y asignar valores . t11- Repetir 10 veces: Ingresar un valor entero en la posición que corresponda del arreglo A. los caracteres en el otro arreglo. t22- Ingresar un carácter en la posición que corresponda del arreglo B. Repetir hasta que el usuario decida terminar y no mas allá de 25 veces.

2017

Ejemplo:

En el último año de una institución privada, se dictan 10 materias que completa el cursado del ciclo Secundario. Almacene en una estructura de datos apropiada el Nro. De documentos de cada alumno y las notas que obtuvo en cada asignatura. ¿Cómo se debería hacer para calcular el promedio?

Ejemplo:

Un palíndromo es una palabra, o frase que se lee igual hacia adelante que hacia atrás. Si se trata de un número, se llama capicúa. ¿Cómo se debería hacer para que reconozca si una palabra es palíndromo o capicúa?. Ej. Neuquen, No deseo yo ese don 2017