-
Para solucionar este problema podemos usar la simetria que poseen los numero binarios, pues cuando uno cuenta desde un numero cualquiera se va a observar un ciclo de repeticiones de los bits de la misma poscion
0001
0010
0011
0100
Se examina el bit menos significativo de todos los n elementos del arreglo original (de derecha a izquierda). Al observar este bit, se pueden diferenciar dos conjuntos: el de los elementos que tienen el bit con 0 (pares) y los que tienen el bit en 1 (impares). Como falta un elemento, un conjunto será mayor que el otro. Se toma el conjunto con menos elementos, éste subarreglo tendrá n/2 elementos del arreglo original.
Al nuevo subarreglo de n/2 elementos le aplicamos la misma estrategia, pero se examina el segundo bit menos significativo . Se tienen dos conjuntos: los que tienen el bit en 0 y los que tiene el bit en 1. Se toma el conjunto con menos elementos, éste nuevo subarreglo tendrá n/4 elementos del arreglo original.
Al nuevo subarreglo de n/4 elementos le aplicamos la misma estrategia, examinando si el tercer bit menos significativo esta en 0 ó en 1, luego tomamos el conjunto con menos elementos, éste conjunto tendrá n/8 del arreglo original.
Seguimos aplicando la misma estrategia al nuevo subarreglo generado hasta llegar al número “perdido”.Con ésta estrategia obtenemos un tiempo proporcional a n + n/2 + n/4 + n/8 + ... + 1 lo cual se acerca a 2n = O (n).
2. Dibujar la recursion del merge sort, y decir por que es mas efectivo un buen algoritmo de divide y venceras que tener en un archivo memorizado la solucion de un problema de estos.
-
Por empezar podemos decir que es mejor un algoritmo de divide y vencerás que un tener momorizada la respuesta de este, pues el tiempo de búsqueda de la respuesta seguramente va a ser superior, a realizar el algoritmo pues generalmente un buen algortimo de divide y venceras va a tardar log n para solucionar un problema, lo cual es mucho menor que la busqueda de la respuesta.
3. Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car’s gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations on his route. The professor wishes to make as few gas stops as possible along the way. Give an efficient method by which Professor Midas can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution.
En este punto lo que se desea es buscar una estrategia optima para el recorrido del profesor midas y que tenga que hacer el menor numerod e paradas, para cargar su tanque de gas,
-
En la vida normal uno se detiene a tanquear cuando tiene el tanque vacio, recarga y sigue hasta que se vuelve a vaciar el tanque; como estamos buscando el algoritmo mas optimo vamos a los siguientes parmetros.
-
Consideremos P el numero de paradas de nuestro algoritmo voraz, el cual es un arreglo que contiene a las paradas que se van a hacer, ahora consideremos a O que es una solucion optima, ademas contamos con i y j, i es el costo de P y j el costo O, como O es optimo siempre i<j, y a partir de esto llegamos a las siguientes conclusiones en busca del algoritmo.
-
Ahora consideremos a D como la distancia entre dos paradas, y sabemos que tenemos al conjunto de paradas P, y al conjunto de paradas O,y empezamos a comparar las distancias P y D, con el lugar de origen.
-
Si D(Newark, P1) <= D(Newark,O1), no pasa nada pues se esta considerando que la solucion optima sigue siendo mejor, pero si D(Newark, P1) >= D(Newark,O1), implica que se esta recorriendo mas distancia usando la parada P1, lo cual resulta mas productivo.
-
Si con la P1, se a recorrido mayor distancia se considera mas optima y en el conjunto de las paradas optimas se cambia P1 por O1, y nace un nuevo conjunto y esto se hace varias veces para encontrar la solucion optima, ya no tomando el recorrido desde el origen sino desde la parada anterior.
-
Haciendo esto repetidamente podemos encontrar, la solucion mas optima que implica incluso que se van a hallar costos mucho menores que los planteados en un principio.