Estructuras de datos (Prof. Edgardo A. Franco)
1
Practica 04: Soluciones Recursivas
M. en C. Edgardo Adrián Franco Martínez http://[email protected]@edfrancom edgardoadrianfrancom
Contenido
• Problema
•Descripción
•Observaciones
•Opcional
• Reporte de práctica
• Rubrica de evaluación del reporte
• Entrega vía Web
• Fechas de entrega
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
2
• En matemáticas, la serie de Fibonacci es la siguiente sucesióninfinita de números naturales:
• El primer elemento es 0, el segundo es 1 y cada elemento restantees la suma de los dos anteriores:
• A cada elemento de esta sucesión se le llama número deFibonacci.
• Esta serie fue descrita en Europa por Leonardo de Pisa, matemático italiano delsiglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones enciencias de la computación, matemáticas y teoría de juegos.
Practica 04 "Soluciones Recursivas"Parte A: Serie de Fibonacci & Tribonacci
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
3
• Programar en ANSI C la implementación recursiva deltermino n de la serie de Fibonacci
• Investigar la variante llamada serie de Tribonacci yprogramar de manera recursiva esta variante paraencontrar el termino n de la serie.• Tribonacci
• x0=1, x1=1, x2=2
• Ecuación de recurrencia: xn= xn-1+xn-2+xn-3
• Programar las implementaciones considerando podertrabajar con números enteros grandes de C (long long).
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
4
Parte A: Serie de Fibonacci & TribonacciRequerimientos
• Tenemos tres astas A, B y C, y un conjunto de aros, todos dedistintos tamaños.
• El enigma comienza con todos los aros colocados en el asta Ade tal forma que ninguno de ellos debe estar sobre uno máspequeño a él; es decir, están apilados, uno sobre el otro, conel más grande hasta abajo, encima de él, el siguiente entamaño y así sucesivamente.
Practica 04 "Soluciones Recursivas" Parte B: Torres de Hanoi
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
5
• El propósito del enigma es lograr apilar los cincos aros, en el mismo orden, pero en el asta C.
• Una restricción es que durante el proceso, puedes colocar los aros en cualquier asta, pero debe
apegarse a las siguientes reglas:• Solo puede mover el aro superior de cualquiera de las
astas.
• Un aro más grande nunca puede estar encima de uno más pequeño.
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
6
• Programar en ANSI C la implementación recursiva de lasTorres de Hanoi.
• Documentar de manera clara y grafica elfuncionamiento del algoritmo recursivo.
• Mostrar los movimientos que se deberán ir realizandopara llegar a resolver las Torres de Hanoi para n discos.
• *Representar de manera gráfica el funcionamiento(Modo carácter es suficiente).
*Opcional
Parte B: Torres de HanoiRequerimientos
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
7
• En computación ordenar información es una de las operacionesmas comunes, el lograr esto sea eficiente es importante:
• El algoritmo de ordenamiento por mezcla (merge sort) es unalgoritmo de ordenamiento basado en la técnica divide y venceráscon complejidad O(n log n).
Practica 04 "Soluciones Recursivas"Parte C: Ordenamiento por mezcla
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
8
Merge-Sort(a, p, r){
if ( p < r ){
q = parteEntera((p+r)/2);Merge-Sort(a, p, q);Merge-Sort(a, q+1,r);Merge(a, p, q, r);
}}
• Programar en ANSI C la implementación recursiva delordenamiento por mezcla para un arreglo de tamaño
n de números enteros que se recibirán por la entradaestándar.
• 0<n<10,000,000 *Se da archivo con 10,000,000 de números diferentes
para probar el ordenamiento
• Se deberá de considerar una entrada línea a línea y la salidadeberá ser los números ordenados de menor a mayorseparados por guion medio.
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
9
Parte C: Ordenamiento por mezclaRequerimientos
INPUT OUTPUT
3614
146
Número de números a ordenar
Números a ordenar
• Se deberá de realizar la implementación de Fibonacci yTribonacci con base en su definición recursiva sin realizarninguna optimización a sus implementaciones.
• El algoritmo para resolver las de Torres de Hanoi aimplementar debe ser recursivo. *No utilizar pilas
• Para el ordenamiento por mezcla respetar el formato de laentrada y la salida para poder redirigir la entrada estándar yprobar con la n máxima de 100,000 números.
• En el reporte se deberá de explicar de manera detallada comoopera cada algoritmo recursivo implementado apoyándose deun ejemplo grafico para n pequeñas (Fibonacci y Tribonacci),pocos discos (Torres de Hanoi) y pocos números (Mergesort).
10
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
• Algunos puntos que da valor agregado a la calificación son:
• La implementación de Fibonacci y Tribonacci con el termino n masgrande y correcta que rebaza la capacidad de un long long sin signo enC (Explicar como trabajan con resultados mayores para que seancorrectos).
• La implementación de Torres de Hanoi que muestre la representacióngráfica del proceso.
11
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Reporte de práctica• Portada
• Introducción
• Planteamiento del problema
• Diseño y funcionamiento de la solución (Descripción de la abstracción delproblema y su solución, apoyándose de diagramas y figuras)
• Implementación de la solución (Según la solución recursiva como seimplemento en el lenguaje de programación)
• Funcionamiento (Verificación de la solución, pruebas y resultados de las seriescon diferentes n, diferentes n discos para Hanoi y arreglos de tamaño n a ordenar)
• Errores detectados (Si existe algún error detectado, el cuál no fue posibleresolver o se desconoce el motivo y solo ocurre con ciertas condiciones es necesariodescribirlo)
• Posibles mejoras (Describir posibles disminuciones de código en laimplementación o otras posibles soluciones)
• Conclusiones (Por cada integrante del equipo)
• Anexo (Códigos fuente *con colores e instrucciones de compilación)
• Bibliografía (En formato IEEE)
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
12
Rubrica de evaluación del reporte
13
Indicador Excelente Muy bien Bien Deficiente
Construcción de párrafos Todos los párrafos incluyen una
introducción, explicaciones o
detalles y una conclusión
Los párrafos incluyen
información relacionada pero
no fueron generalmente bien
organizados
La estructura del párrafo no
estaba clara y las oraciones no
estaban generalmente
relacionadas
Los párrafos son tomados de
otras fuentes y no son
originales.
Redacción No hay errores de gramática,
ortografía y puntuación y la
redacción es coherentemente
No hay errores de gramática,
ortografía y puntuación, pero la
redacción presenta
incoherencias
Pocos errores de gramática,
ortografía y puntuación
Muchos errores de gramática,
ortografía y puntuación
Cantidad de información
Portada, Introducción, Planteamiento del problema,
algoritmos e implementación, actividades y pruebas,
errores detectados, posibles mejoras, conclusiones y
anexos
Todos los temas son tratados de
manera clara y precisa, según lo
solicitado.
La mayoría de los temas son
tratados de manera clara y
precisa
Dos temas no están tratados o
están imprecisos y no cumplen
lo solicitado.
Tres o más temas no están
tratados o están imprecisos y no
cumplen lo solicitado.
Calidad de la información La información está claramente
relacionada con el tema
principal y proporciona varias
ideas secundarias y/o ejemplos
La información da respuestas a
las preguntas principales, y solo
da algunos detalles y/o
ejemplos
La información da respuestas a
las preguntas principales, pero
no da detalles y/o ejemplos
La información tiene poco o
nada que ver con las preguntas
planteadas.
Algoritmos Los algoritmos dan solución
apoyándose de pseudocódigo,
diagramas y/o figuras en un
lenguaje claro.
La mayoría de los algoritmos
dan solución apoyándose de
pseudocódigo, pero diagramas
y/o figuras.
Los algoritmos son mencionados
textualmente pero no se
describen
Los algoritmos no son
expresados en el reporte.
Organización La información está muy bien
organizada con párrafos bien
redactados y con subtítulos con
estilos adecuados
La información está organizada,
pero no se distingue en estilos
adecuados
La información está organizada,
pero los párrafos no están bien
redactados
La información proporcionada
no parece estar organizada o es
copiada de referencias externas
de manera literal
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Entrega vía Web
• En un solo archivo comprimido (ZIP, RAR, TAR, JAR o GZIP)• Reporte (DOC, DOCX o PDF)
• Códigos fuente (.C, .H, etc.)
• Código documentado: Titulo, descripción, fecha, versión, autor.
• (Funciones y Algoritmos: ¿Qué hace?, ¿Cómo lo hace?, ¿Qué recibe?, ¿Qué devuelve?, ¿Causa de errores?).
• OBSERVACIONES
• *NO enviar ejecutables o archivos innecesarios, las instrucciones decompilación van en el anexo del reporte. (Yo compilare los fuente)
14
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Grupo Contraseña
1CM8 Estructuras1cm8
Fechas de entrega
Compiladores (Análisis Léxico II - Edgardo A. Franco)
• Demostración Laboratorio de Programación 1 (1107)
• 1CM8 “Lunes 06 de mayo de 2019”.
• Entrega de reporte y código
• En un solo archivo comprimido.
• Fecha y hora limite de entrega vía Web
• Lunes 13 de mayo de 2019 a las 23:59:59 hrs.
15
Estr
uct
ura
s d
e d
ato
sP
ract
ica
04
: So
luci
on
es R
ecu
rsiv
asP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez