Guia divide y vencerás

Facultad de Inform´tica a Metodolog´ y Tecnolog´ de la Programaci´n ıa ıa o
Clara Segura, Alberto Verdejo, Octubre 2003

Divide y vencer´s a
Ejercicio 1 Dos amigos matan el tiempo de espera en lacola del cine jugando a un juego muy sencillo: uno de ellos piensa un n´mero natural positivo y el otro debe adivinarlo preguntando solamente si u es menor o igual que otros n´meros. Dise˜ar unalgoritmo eficiente para adivinar el n´mero. u n u Ejercicio 2 Dado un vector ordenado V [1..n] de n n´meros enteros distintos, escribir un algoritmo que u en tiempo O(log n) encuentre un n´mero i tal que 1≤ i ≤ n y V [i] = i, siempre que exista. u Ejercicio 3 Dados un vector V [1..n] y un n´mero natural k entre 1 y n−1, dise˜ar un algoritmo eficiente u n que transponga los k primeros elementos de V conlos elementos en las n − k ultimas posiciones, sin ´ hacer uso de un vector auxiliar. Por ejemplo, si V es el siguiente vector con 10 elementos
a b c d e f g h i j

y k = 3, el resultado deseadoes
d e f g h i j a b c

Ejercicio 4 Dado un vector V [1..n] de elementos que se pueden ordenar, se desea hallar los m elementos m´s peque˜os, donde m es mucho m´s peque˜o que n. ¿Qu´ es mejor, a n an e e (a) ordenar V [1..n] y despu´s coger los m primeros elementos V [1..m], (b) ir seleccionando el primer elemento, despu´s el segundo, y as´ hasta el elemento m-´simo, o e ı e (c) utilizar alg´notro m´todo? u e Generalizar el mejor m´todo para, fijada una posici´n p del vector, hallar los m elementos que e o ocupar´ en el vector ordenado las posiciones p, p + 1, . . . , p + m − 1. ıanEjercicio 5 Dado un vector V [1..n] de n elementos que se pueden ordenar, demostrar que los tres problemas siguientes son linealmente equivalentes; es decir, que si uno de ellos se puede resolver en tiempolineal entonces los tres problemas se pueden resolver en tiempo lineal: Selecci´n: Dado k entre 1 y n, seleccionar el k-´simo menor elemento del vector V [1..n]. o e Mediana: Calcular la mediana del...