13_Seminario_Examen_Final

Programación Dinámica
Seminario: Examen Final

Company

LOGO

Agenda

1. Algoritmos recursivos
2. Pilas
3. Colas
4. Listas Enlazadas

Primer problema
 Para un número real x mayor que 1,
diseñe un algoritmo que empleando sólo
las operaciones aritméticas básicas (+, -, /,
*), permita calcular la raíz cuadrada de x
con una aproximación hasta las
milésimas.

Plan de acción
Generamos unaaproximación g para
el valor de la raíz cuadrada de x.

Calculamos x/g.

Si x/g está lo suficientemente cerca
de g, g es nuestra respuesta.
Si no lo es, necesitamos generar una
mejor aproximación.

Estructura Jerárquica
Módulo
Principal

Calcular raíz
cuadrada
Verificar si la
aproximación
es buena
Generar una
mejor
aproximación

Módulo Principal
Proceso principal
Definir resultado como Real;
Definirvalor_ingresado como Real;
Repetir
Leer valor_ingresado;
Hasta que valor_ingresado > 1;
resultado <- calcular_raiz_cuadrada(valor_ingresado, 1);
Escribir resultado;
FinProceso

Calcular raíz cuadrada
Funcion resultado <- calcular_raiz_cuadrada(un_numero,
aproximacion)
Definir resultado Como Real;
Si estamos_cerca(un_numero, aproximacion) Entonces
resultado <- aproximacion;

Sino
resultado <-calcular_raiz_cuadrada(un_numero,
generar_aproximacion(un_numero, aproximacion));
FinSi
FinFuncion

¿Es una buena
aproximación?
Funcion resultado <- estamos_cerca(un_numero, aproximacion)
Definir resultado Como Logico;
Definir diferencia como Real;
resultado <- Falso;
diferencia <- un_numero/aproximacion - aproximacion;
Si diferencia < 0 Entonces

diferencia <- -1 * diferencia;
FinSi
Si diferencia <=0.001 Entonces
resultado <- Verdadero;
FinSi
FinFuncion

Generar una nueva
aproximación
Funcion resultado <- generar_aproximacion(
un_numero, aproximacion)
Definir resultado como Real;
resultado <- (un_numero/aproximacion +
aproximacion) / 2;
FinFuncion

Probemos

Segundo problema (I)
 Se tiene (ya existen) los siguientes
archivos físicos:




ALUMNOS.DAT: cod_alum(entero de 4
dígitos), Nomb(cadena de 30 caracteres),
Edad(entero).
CURSOS.DAT: cod_curso (cadena de 5
caracteres), cod_alum, nota_final (real).

Segundo problema (II)
 Diseñe un algoritmo que permita:




Almacenar en los nodos de una Lista (Pila o
Cola): código del curso, número de alumnos
inscritos y el promedio de las notas finales de
los inscritos en dicho curso.
Eliminar de la Lista creada en a) aquellos
nodos cuyospromedios de notas finales es
menor a 6.

Plan de acción (a)
Necesitamos una lista para almacenar la
información de cursos.

Recorremos los registros del archivo.

En caso se trate de un curso no
registrado, agregamos el elemento a la
lista.
En caso se trate de un curso que ya está
en la lista, actualizamos la información
de inscritos y el promedio.

Definir Estructuras
Información
de alumnosNota del
alumno

Información
de cursos

Estructura alumno
Definir codigo_alumno como Entero;
Dimension nombre[30];
Definir nombre como Caracter;
Definir edad como Entero;
FinEstructura
Estructura nota_alumno
Dimension codigo_curso[5];
Definir codigo_curso como Caracter;
Definir codigo_alumno como Entero;
Definir nota como Real;
FinEstructura
Estructura curso
Dimension codigo_curso[5];
Definircodigo_curso como Caracter;
Definir alumnos_inscritos como Entero;
Definir *puntero_siguiente como curso;
FinEstructura

Estructura jerárquica
Módulo
Principal
Registrar
información
de curso

Apilar

Mostrar
listado de
cursos

Depurar
cursos

Módulo Principal
Proceso principal
Definir archivo_notas como Archivo;
Definir *puntero_lista como curso;
Definir una_nota como nota_alumno;
Definirnumero_notas como Entero;
Definir contador_notas como Entero;
puntero_lista <- NULO;
Abrir "cursos.dat" como archivo_notas para Lectura;
numero_notas <- LDA(archivo_notas)/tamaño_de(nota_alumno);
Para contador_notas <- 0 Hasta numero_notas - 1 Hacer

Leer archivo_notas, contador_notas, una_nota;
actualizar_curso(una_nota, puntero_lista);
FinPara
depurar_lista(puntero_lista);
mostrar_lista(puntero_lista);...