Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Ejercicios 08: Diseño de soluciones Greedy
1
Análisis de algoritmos
M. en C. Edgardo Adrián Franco Martínez http://[email protected]@edfrancom edgardoadrianfrancom
http://www.eafranco.com/mailto:[email protected]
1. Ordenando una Secuencia de Tres Valores
2
Diseño de soluciones con Programación Voraz
https://omegaup.com/arena/problem/Ordenando-Sec-Tres-Val#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/Ordenando-Sec-Tres-Val#problems
2. Voltea monedas consecutivas
3
https://omegaup.com/arena/problem/Voltea-monedas-consecutivas#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/Voltea-monedas-consecutivas#problems
3. Permutación Hermosa
4
https://omegaup.com/arena/problem/Permutacion-Hermosa#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/Permutacion-Hermosa#problems
4. Carrera de Larga Distancia
5
https://omegaup.com/arena/problem/Carrera-de-Larga-Distancia#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/Carrera-de-Larga-Distancia#problems
5. Metro
6
https://omegaup.com/arena/problem/metro#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/metro#problems
6. Andar Chido Reloaded
7
https://omegaup.com/arena/problem/Andar-Chido-Reloaded#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/Andar-Chido-Reloaded#problems
7. Función Horrible
8
https://omegaup.com/arena/problem/Formula-Horrible/#problems
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://omegaup.com/arena/problem/Formula-Horrible/#problems
8. B - Fito y los bichos del bosque
9
http://matcomgrader.com/problem/33/fito-y-los-bichos-del-bosque/
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
http://matcomgrader.com/problem/33/fito-y-los-bichos-del-bosque/
9. A - Cake
10
http://matcomgrader.com/problem/9145/cake/
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
http://matcomgrader.com/problem/9145/cake/
10. G - Gran subsecuencia
11
http://matcomgrader.com/problem/350/gran-subsecuencia/
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
http://matcomgrader.com/problem/350/gran-subsecuencia/
11. Organizando Cajas
12
http://matcomgrader.com/problem/9236/organizando-cajas/
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
http://matcomgrader.com/problem/9236/organizando-cajas/
12. A - Vuelos baratos
13
http://matcomgrader.com/problem/9477/vuelos-baratos/
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
http://matcomgrader.com/problem/9477/vuelos-baratos/
13. 10020 - Minimal coverage
14
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=961
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=961
14. 10382 - Watering Grass
15
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=1323
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=1323
15. 12405 - Scarecrow
16
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=3836
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=657&page=show_problem&problem=3836
16. 11631 - Dark roads
17
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=673&page=show_problem&problem=2678
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=673&page=show_problem&problem=2678
17. 544 - Heavy Cargo
18
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=485
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=485
18. 1193 - Radar Installation
19
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3634
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3634
19. Bear and Row 01
20
https://www.codechef.com/APRIL17/problems/ROWSOLD
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://www.codechef.com/APRIL17/problems/ROWSOLD
20. Bear and Clique Distances
21
https://www.codechef.com/APRIL17/problems/CLIQUED
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
https://www.codechef.com/APRIL17/problems/CLIQUED
• Se deberá incluir la captura de pantalla del problemaaceptado en el juez online con fecha y hora.
• Incluir la redacción de cada ejercicio.
• Explicar cada solución de Programación Voraz y su análisis delorden de complejidad
• Incluir el algoritmo y código de la solución.
• Para que los ejercicios cuenten al 100% deberán decontestarse al menos 5 correctamente de los 20 propuestos.
• Portada con fotografía y encabezados de pagina.
22
Observaciones
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Lista cotejo de la evaluación del ejercicio
23
Indicador SI NO
Redacción del Problema (El reporte cuenta con encabezados y los datos están redactados
completamente)
Análisis del Problema (Identifica y explica las instrucciones o variables a considerar para el análisis)
Desarrollo del Problema (Explica el análisis realizado y los pasos con lo que llego al resultado,
muestra las pantallas de envió y “Acepted” en el Juez
Online)
Secuencia Lógica (Hay una correcta interpretación de los conceptos, cálculos y formulas)
Código (El código es original, esta autodocumentado y documentado. )
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
Fecha máxima de entrega en el sitio Web
24
• La entrega se realizará a través de la página:
http://www.eafranco.comEntregar a más tardar el día viernes 31 de Mayo de 2019
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez
http://www.eafranco.com/
• Grupo y contraseña
• Escribir y almacenar las claves de confirmación, paraaclaraciones a con respecto a la evaluación.
Grupo Contraseña
3CM3 analisis3cm3
3CM4 analisis3cm4
25
An
ális
is d
e al
gori
tmo
sEj
erc
icio
s 0
8:
Dis
eño
de
solu
cio
nes
Gre
ed
yP
rof.
Edga
rdo
Ad
rián
Fra
nco
Mar
tín
ez