elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  algoritmos divide y venceras
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: algoritmos divide y venceras  (Leído 2,777 veces)
m@o_614


Desconectado Desconectado

Mensajes: 389


Ver Perfil
algoritmos divide y venceras
« en: 14 Septiembre 2013, 02:46 am »

Saludos

Estoy estudiando algunos metodos de ordenamiento como Merge-Sort, Quick Sort y el metodo de busqueda binaria, y me he fijado que todos estos algoritmos utilizan la tecnica de dividir vectores en subvectores e irlos ordenando pero me fije que antes  de dividir el vector en 2 hace una suma, la de la variable ini mas el tamanio del vector

ini=1,sup=n;
 i= (ini+sup)/2;

y me pregunto si esto es necesario, no seria mas logico dividir el tamanio del vector sobre 2 sin necesidad de hacer la dichosa suma??? de que me sirve la variable ini??

sup=n;
i= (sup/2);

de antemano gracias



En línea

ecfisa

Desconectado Desconectado

Mensajes: 114


Ver Perfil
Re: algoritmos divide y venceras
« Respuesta #1 en: 14 Septiembre 2013, 07:56 am »

Hola m@o_614.

Citar
no seria mas logico dividir el tamanio del vector sobre 2 sin necesidad de hacer la dichosa suma???

Definitivamente creo que no.

Pongamos como ejemplo la búsqueda dicotómica:
Código
  1. ...
  2. #define ELEM_NOT_FOUND -1
  3.  
  4. int binaria(int buscado, int *arreglo, int fin)
  5. {
  6.  int inicio = 0, medio;
  7.  --fin;
  8.  while(inicio <= fin) {
  9.    medio = (inicio + fin) >> 1;
  10.    if (buscado == arreglo[medio]) return medio;
  11.    if (buscado < arreglo[medio])
  12.      fin = medio - 1;       // la lista se redujo a: 0 - medio-1
  13.    else
  14.      inicio = medio + 1;    // la lista se redujo a: medio+1 - fin
  15.  }
  16.  return ELEM_NOT_FOUND;
  17. }
  18. ...
  19.  

En cada cliclo si el número buscado es mayor que el ubicado en el medio de la lista de elementos, se elimina la mitad inferior de esta, de lo contrario la superior. Y así se sigue reduciendo la lista de elementos a la mitad hasta que se encuentra el elemento o no haya mas elementos que buscar.
Esto no sucedería si siempre tomáramos como cotas a 0 y la cantidad total de elementos.

Citar
de que me sirve la variable ini??
Las variables inicio y fin van variando sus valores acorde a los condicionales como muestra el código anterior y sirven para fijar los nuevos límites luego de reducir la lista de elementos a la mitad en cada ciclo.

Saludos :)


En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: algoritmos divide y venceras
« Respuesta #2 en: 16 Septiembre 2013, 19:43 pm »

Un comentario. Se recomienda evitar la sustitución de la división por el desplazamiento de bits como en este caso:
Código
  1. medio = (inicio + fin) >> 1;
Porque en el desplazamiento a la derecha de un entero con signo si el bit de relleno es cero o uno depende de la implementación. En el caso de enteros sin signo donde el bit de relleno esta garantizado (es cero) es mejor dejar ese tipo de mejoras al compilador.

Un saludo
En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
ecfisa

Desconectado Desconectado

Mensajes: 114


Ver Perfil
Re: algoritmos divide y venceras
« Respuesta #3 en: 16 Septiembre 2013, 21:29 pm »

Hola rir3770.

Aclarando la aclaración :) , tu comentario es muy cierto y se cumple en el caso de enteros con signo negativos.

En este caso, a menos que enviáramos argumentos negativos como límites de la lista, el menor valor que puede tomar "medio" es 0.

Sin embargo, coincido plenamente en que no debe ser la costumbre usar la división por desplazamiento de bits.

Saludos. :)
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ejercicio de Divide y Venceras
Programación General
gian153 3 4,933 Último mensaje 30 Septiembre 2010, 02:30 am
por [L]ord [R]NA
Wikileaks se divide
Noticias
wolfbcn 1 1,330 Último mensaje 10 Noviembre 2010, 22:50 pm
por Draklit
Ayuda entender Divide y Venceras
Programación C/C++
fla2727 5 1,571 Último mensaje 18 Noviembre 2012, 19:19 pm
por fla2727
ayuda con algoritmo divide and conquer
Java
++c 0 783 Último mensaje 29 Abril 2015, 00:47 am
por ++c
algoritmo kadane con divide y venceras?
Java
Tordur 1 696 Último mensaje 21 Octubre 2018, 16:42 pm
por srWhiteSkull
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines