PDF de programación - EXÁMENES RESUELTOS PROGRAMACIÓN III

EXÁMENES
RESUELTOS
PROGRAMACIÓN


III



Recopilación de Exámenes de Programación III



Esta recopilación de exámenes incluye desde el año 1996
hasta septiembre de 2008. Llevo unos dos años haciéndola y
no hubiera sido posible sin la inestimable ayuda de Ali,
por ello creí conveniente nombrarla ya que ha sido de gran
ayuda en la resolución de problemas y dudas que han hecho
posible esta colección de exámenes.



Antonio Rivero Cuesta
Alicia Sánchez Ferro

Palma de Mallorca, septiembre de 2008



n=
2

2

T n
( )

................................... Divide y Vencerás

Problemas de Programación III

Febrero 1996-1..................Calcular
Febrero 1996-1..................Calcular recubrimiento de vértices................ Voraz
Febrero 1996-2..................Dominó ......................................................... Vuelta Atrás
Febrero 1996-2..................Fibonacci....................................................... Divide y Vencerás
Septiem 1996 ....................Cartógrafo ..................................................... Voraz
Septiem 1996 ....................Calcular 2 = d(d(m(d(7))))............................ Vuelta Atrás
Septiem 1996-R ................f x c Alumnos ................................................ Divide y Vencerás
Septiem 1996-R ................Seleccionar carreteras ................................... Voraz
Febrero 1997-1..................n Cintas n Registros ...................................... Voraz
Febrero 1997-1..................El 31.............................................................. Vuelta Atrás
Febrero 1997-2..................Grabar n Canciones....................................... Voraz
Septiem 1997 ....................n Motos n Clientes ........................................ Ramificación y Poda
Septiem 1997 ....................Tablero.......................................................... Vuelta Atrás
Febrero 1998-1..................El Continental. .............................................. Vuelta Atrás
Febrero 1998-1..................Metro Japón. ................................................. Voraz
Febrero 1998-2..................Línea Horizonte ............................................ Voraz
Febrero 1998-2..................Mecano 8 piezas............................................ Ramificación y Poda
Septiem 1998 ....................n rectángulos ................................................. Voraz
Septiem 1998 ....................Cadena euleriana........................................... Voraz
Febrero 1999-1..................Nave Mir. ...................................................... Ramificación y Poda
Febrero 1999-1..................Colorear 3 colores. ........................................ Vuelta Atrás
Febrero 1999-2..................Mínimo Colores ............................................ Vuelta Atrás
Febrero 1999-2..................Liga n equipos............................................... Divide y Vencerás
Febrero 2000-1..................Tablero Genérico........................................... Vuelta Atrás
Febrero 2000-2..................Base Aerea .................................................... Ramificación y Poda
Septiem 2000 ....................Mayoritario ................................................... Divide y Vencerás
Febrero 2001-1..................Río Guadalhorce ........................................... Vuelta Atrás, Ramificación y Poda
Febrero 2001-2..................Torneo n participantes................................... Divide y Vencerás
Septiem 2001 ....................Tablero.......................................................... Vuelta Atrás, Ramificación y Poda
Febrero 2002-1..................Caja de Bombones ........................................ Divide y Vencerás
Febrero 2002-2..................8 casillas........................................................ Vuelta Atrás
Septiem 2002 ....................Laberinto....................................................... Ramificación y Poda
Septiem 2002-R ................Buscaminas ................................................... Divide y Vencerás
Diciem 2002.....................Multiplicación de polinomios ....................... Vuelta Atrás
Febrero 2003-1..................Laberinto....................................................... Vuelta Atrás
Febrero 2003-2..................Fibonacci....................................................... Divide y Vencerás
Septiem 2003 ....................Operadora Teleco.......................................... Voraz
Septiem 2003-R ................Daniel Tesoros .............................................. Ramificación y Poda
Diciem 2003.....................Taller Sleepy ................................................. Voraz
Febrero 2004-1..................Matriz de 3 colores........................................ Vuelta Atrás
Febrero 2004-2..................Grafo dirigido................................................ Recorrido profundidad
Septiem 2004 ....................Vectores texto ............................................... Ramificación y Poda
Septiem 2004-R ................n Agentes n Tareas........................................ Ramificación y Poda
Febrero 2005-1..................Conjunto operaciones.................................... Vuelta Atrás
Febrero 2005-2..................Estructura Montículo..................................... Divide y Vencerás
Septiem 2005 ....................Votación Elecciones...................................... Divide y Vencerás
Septiem 2005-R ................Sudoku .......................................................... Vuelta Atrás
Febrero 2006-1..................n montadores................................................. Ramificación y Poda
Febrero 2006-2..................Dos socios ..................................................... Vuelta Atrás
Septiem 2006 ....................Salto caballo.................................................. Vuelta Atrás
Septiem 2006-R ................Repartidor de Pizzas...................................... Voraz
Diciem 2006......................Grabación Cd ................................................ Ramificación y Poda
Febrero 2007-1..................Taller Sleepy ................................................. Voraz
Febrero 2007-2..................Suma exacta C............................................... Vuelta Atrás
Septiem 2007 ....................n objetos volumen ......................................... Ramificación y Poda
Septiem 2007-R ................Parejas estables ............................................. Vuelta Atrás
Febrero 2008-1..................n Huertas ....................................................... Ramificación y Poda
Febrero 2008-2..................n Agentes n Tareas........................................ Ramificación y Poda
Septiem 2008 ....................n Agentes n Tareas........................................ Ramificación y Poda
Septiem 2008-R ................n Agentes n Tareas........................................ Ramificación y Poda





Escuela Universitaria de Informatica de la UNED

Ingeniera Tecnica de Sistemas e Ingeniera Tecnica de Gestion

Programacion III - Convocatoria de Febrero

Examen primera semana - Curso
- 



Problema
( puntos). El tiempo de ejecucion de un algoritmo viene dado
por T (n) = n
. Encontrar una forma eciente de calcular T (n), suponiendo que
el coste de multiplicar dos enteros es proporcional a su tamaño en representacion
binaria.

Problema  ( puntos). Un recubrimiento de vertices de un grafo no dirigido
G = hV; Ai es un conjunto de vertices tales que cada arista del grafo incide en,
al menos, un vertice de V. Diseñar un algoritmo que, dado un grafo no dirigido,
calcule un recubrimiento de vertices de tamaño mnimo para un grafo dado.

La resolucion de cada problema debe incluir:

Eleccion razonada del esquema algortmico.

Descripcion del esquema usado e identicacion con el problema.

Estructuras de datos.

Algoritmo completo a partir del renamiento del esquema general.

Estudio del coste.

Segun el esquema elegido hay que especicar, ademas:

Voraz: demostracion de optimalidad.

Divide y venceras: preorden bien fundado.

Vuelta atras: descripcion del arbol de busqueda asociado.





RESPUESTAS EXAMEN Programación III. Febrero 1996 (Primera Semana)

Problema 2 (5 puntos). Un recubrimiento R de vértices de un grafo no dirigido G = +N,A, es un
conjunto de vértices tales que cada arista del grafo incide en, al menos, un vértice de R. Diseñar un
algoritmo que, dado un grafo no dirigido, calcule un recubrimiento de vértices de tamaño mínimo.

Solución:

Elección razonada del esquema

El esquema voraz se adapta perfectamente al problema, ya que:


• Se trata de un problema de optimización: No solo hay que encontrar un recubrimiento, sino que

éste ha de ser de tamaño mínimo.



• De entre un conjunto de vértices (candidatos) hay que seleccionar un subconjunto que será la
solución. Solo hay que encontrar la función de selección adecuada (si existe) para resolver el
problema mediante un algoritmo voraz.


El esquema de divide y vencerás es descartable, pues no hay forma obvia de dividir el problema en
subproblemas idénticos cuyas soluciones puedan combinarse en una solución global. El esquema de
vuelta atrás es un esquema muy general y casi siempre muy costoso que no debemos usar si podemos
dar un algoritmo voraz