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

 

 


Tema destacado: Arreglado, de nuevo, el registro del warzone (wargame) de EHN


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Problema: Búsqueda en Array
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Problema: Búsqueda en Array  (Leído 4,741 veces)
j retirado

Desconectado Desconectado

Mensajes: 61



Ver Perfil WWW
Problema: Búsqueda en Array
« en: 28 Junio 2009, 21:15 pm »

Problema: Se recibe un arreglo X de numeros enteros definido en [0, n-1] y un entero x.
Se quiere determinar si existen i, j en [0, n-1] tal que X + X[j] = x.
Diseñe un algoritmo para resolver el problema cuya complejidad sea O(n*log(n)).


Plantear más soluciones.

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define FALSE 0
  5. #define TRUE !FALSE
  6. typedef int Bool;
  7.  
  8. /* Algoritmo O(n^2). Analizando todos los casos. */
  9. Bool f1(int *a, int x, int tam);
  10.  
  11. /* Algoritmo O(n*log(n)). Ordeno con quicksort y uso busqueda binaria "n" veces. Me queda 2*n*log(n) que es O(n*log(n))*/
  12. Bool f2(int *a, int x, int tam);
  13. void quicksort(int *, int, int);
  14. void pivot(int *, int, int, int *);
  15. void swap(int *, int, int);
  16.  
  17. int main()
  18. {
  19. int tam, contador, x;
  20. Bool b;
  21.  
  22. printf("Ingrese 'x': ");
  23. scanf("%d", &x);
  24. printf("Tamaño del array (>=2): ");
  25. scanf("%d", &tam);
  26. int *a = (int *) calloc (tam, sizeof(int));
  27.  
  28. for(contador=0; contador<tam; contador++)
  29. {
  30. printf("Ingrese el contenido de la celda %d: ", contador);
  31. scanf("%d", &a[contador]);
  32. }
  33.  
  34. printf("\n\n");
  35. for(contador=0; contador<tam; contador++)
  36. printf("%d  ", a[contador]);
  37.  
  38. /* ********************************************** */
  39. b = f2(a, x, tam); /* solo cambiar "f1" por "f2" para cambiar de algoritmos */
  40. if(b == TRUE)
  41. printf("\n\nHay solucion\n");
  42. else
  43. printf("\n\nNo hay solucion\n");
  44. /* ********************************************** */
  45.  
  46. free(a);
  47. a=NULL;
  48.  
  49. system("pause");
  50. return 0;
  51. }
  52.  
  53. /* Algoritmo O(n^2). Analizando todos los casos. */
  54. Bool f1(int *a, int x, int tam)
  55. {
  56. Bool b=FALSE;
  57. int i, j;
  58. for(i=0; i<tam; i++)
  59. for(j=0; j<tam; j++)
  60. if(a[j]+a[i] == x)
  61. return b=TRUE; /* solución encontrada */
  62.  
  63. return b; /* no hay solución */
  64. }
  65.  
  66. /* Algoritmo O(n*log(n)). Ordeno con quicksort y uso busqueda binaria "n" veces. */
  67. Bool f2(int *a, int x, int tam)
  68. {
  69. quicksort(a, 0, tam-1);
  70.  
  71. Bool b = FALSE;
  72. int izq=0, med, der=tam-1, k=0;
  73.  
  74. while(izq<=der && !b && k<tam)
  75. {
  76. med = (izq+der)/2;
  77.  
  78. if( x<(a[k]+a[med]) )
  79. der = med;
  80. else if ( x>(a[k]+a[med]) )
  81. izq = med;
  82. else if ( x==(a[k]+a[med]) )
  83. return b=TRUE; /* hay solución */
  84.  
  85. k++;
  86. }
  87.  
  88. return b; /* no hay solución */
  89. }
  90.  
  91. void quicksort(int *a, int izq, int der)
  92. {
  93. int piv;
  94. if(izq<der)
  95. {
  96. pivot(a, izq, der, &piv);
  97. /* { Para todo x en a: a[izq,piv] son <= a[piv] && */
  98. /* Para todo x en a: a[piv+1,der] son > a[piv] } */
  99. quicksort(a, izq, piv-1);
  100. quicksort(a, piv+1, der);
  101. }
  102. }
  103.  
  104. void pivot(int *a, int izq, int der, int *piv)
  105. {
  106. int i = izq+1;
  107. int j = der;
  108. *piv = izq;
  109.  
  110. while(i <= j)
  111. {
  112. /* { *piv<i<=j+1 && (Para todo x en a: a[izq,i]<=a[*piv]) && (Para todo x en a: a[j+1,der] > a[*piv]) } */
  113. if(a[i] <= a[*piv])
  114. i=i+1;
  115. else if(a[j] > a[*piv])
  116. j=j-1;
  117. else if(a[i] > a[*piv] && a[j] <= a[*piv])
  118. {
  119. swap(a, i, j);
  120. i = i+1;
  121. j = j+1;
  122. }
  123. }
  124. /* i vale j+1, (Para todo x en a: a[izq,j] <= a[*piv]) && (Para todo x en a: a[i,der] > a[piv] */
  125.  
  126. /* dejando el pivot en una posición más central */
  127. swap(a, *piv, j);
  128. /* nueva posición para pivot */
  129. *piv = j;
  130. }
  131.  
  132. void swap(int *a, int i, int j)
  133. {
  134. int aux = a[i];
  135. a[i] = a[j];
  136. a[j] = aux;
  137. }

Saludos


« Última modificación: 28 Junio 2009, 21:17 pm por j.rm » En línea

leogtz
. . .. ... ..... ........ ............. .....................
Colaborador
***
Desconectado Desconectado

Mensajes: 3.069


/^$/


Ver Perfil WWW
Re: Problema: Búsqueda en Array
« Respuesta #1 en: 29 Junio 2009, 04:58 am »

La verdad no entiendo el enunciado, ¿podrias explicar con tus palabras de que trata el algoritmo?


En línea

Código
  1. (( 1 / 0 )) &> /dev/null || {
  2. echo -e "stderrrrrrrrrrrrrrrrrrr";
  3. }
  4.  
http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com
j retirado

Desconectado Desconectado

Mensajes: 61



Ver Perfil WWW
Re: Problema: Búsqueda en Array
« Respuesta #2 en: 29 Junio 2009, 08:15 am »

Tienes un array, ejemplo: a = [1,2,3,4,5,6,7]
Sea x = 5

Código
  1. ¿Existen un a[i] y un a[j] tal que a[i]+a[j] = x?
  2. Verdadero. En particular, a[1]+a[2] = 5.
  3.  

Si quieres puedes mostrar los índices, todas las soluciones, etc. Pero es simplemente decir "si" si hay al menos una solución ó "no" si no existe solución.

Saludos.

PD: uso la etiqueta code sino me imprime una parte en cursiva...
« Última modificación: 29 Junio 2009, 08:20 am por j.rm » En línea

leogtz
. . .. ... ..... ........ ............. .....................
Colaborador
***
Desconectado Desconectado

Mensajes: 3.069


/^$/


Ver Perfil WWW
Re: Problema: Búsqueda en Array
« Respuesta #3 en: 30 Junio 2009, 08:13 am »

Oh, ya entiendo un poco más, en caso de lo contrario hasmelo saber, a ver si era esto:

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. int main()
  4. {
  5.    signed int n_elementos, numero_usuario;
  6.    do
  7.    {
  8.    printf("\nNumero de elementos : ");
  9.    setbuf(stdin, NULL);
  10.    } while(scanf("%d", &n_elementos) != 1);
  11.    signed int *array = (int *)malloc(n_elementos * sizeof(int));
  12.    for(signed int i = 0; i < n_elementos; i++)
  13.    {
  14.        printf("array[%d] = ", i);
  15.        scanf("%i", &array[i]);
  16.    }
  17.    do
  18.    {
  19.    printf("Numero : ");
  20.    setbuf(stdin, NULL);
  21.    } while(scanf("%d", &numero_usuario) != 1);
  22.    for(signed int i = 0; i < n_elementos; i++)
  23.    {
  24.        for(signed int j = 0; j < n_elementos; j++)
  25.        {
  26.            if(array[i] + array[j] == numero_usuario)
  27.            {
  28.                printf("array[%d] + array[%d] = %d\n", i, j, numero_usuario);
  29.            }
  30.        }
  31.    }
  32.    return 0;
  33. }
  34.  

Salida de ejemplo:

Código:
C:\>codes.exe

Numero de elementos : 10
array[0] = 10
array[1] = 20
array[2] = 30
array[3] = 40
array[4] = 50
array[5] = 60
array[6] = 70
array[7] = 80
array[8] = 90
array[9] = 100
Numero : 50
array[0] + array[3] = 50
array[1] + array[2] = 50
array[2] + array[1] = 50
array[3] + array[0] = 50

C:\>

Saludos.
En línea

Código
  1. (( 1 / 0 )) &> /dev/null || {
  2. echo -e "stderrrrrrrrrrrrrrrrrrr";
  3. }
  4.  
http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com
leogtz
. . .. ... ..... ........ ............. .....................
Colaborador
***
Desconectado Desconectado

Mensajes: 3.069


/^$/


Ver Perfil WWW
Re: Problema: Búsqueda en Array
« Respuesta #4 en: 30 Junio 2009, 08:24 am »

Lo hice a función y lo acorté:
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. void busqueda(signed int array[], signed int n_elementos, signed int numero);
  4. int main()
  5. {
  6.    signed int n_elementos, numero_usuario;
  7.    do
  8.    {
  9.    printf("\nNumero de elementos : ");
  10.    setbuf(stdin, NULL);
  11.    } while(scanf("%d", &n_elementos) != 1);
  12.    signed int *array = (int *)malloc(n_elementos * sizeof(int));
  13.    for(signed int i = 0; i < n_elementos; i++)
  14.    {
  15.        printf("array[%d] = ", i);
  16.        scanf("%i", &array[i]);
  17.    }
  18.    do
  19.    {
  20.    printf("Numero : ");
  21.    setbuf(stdin, NULL);
  22.    } while(scanf("%d", &numero_usuario) != 1);
  23.    busqueda(array, n_elementos, numero_usuario);
  24.    return 0;
  25. }
  26. void busqueda(signed int array[], signed int n_elementos, signed int numero_usuario)
  27. {
  28.    for(signed int i = 0; i < n_elementos; i++)
  29.        for(signed int j = 0; j < n_elementos; j++)
  30.            if(array[i] + array[j] == numero_usuario)
  31.                printf("array[%d] + array[%d] = %d\n", i, j, numero_usuario);
  32. }
  33.  

Salida:
Código:
C:\>codes.exe

Numero de elementos : 10
array[0] = 10
array[1] = 20
array[2] = 30
array[3] = 40
array[4] = 50
array[5] = 60
array[6] = 70
array[7] = 80
array[8] = 90
array[9] = 100
Numero : 50
array[0] + array[3] = 50
array[1] + array[2] = 50
array[2] + array[1] = 50
array[3] + array[0] = 50

C:\>
En línea

Código
  1. (( 1 / 0 )) &> /dev/null || {
  2. echo -e "stderrrrrrrrrrrrrrrrrrr";
  3. }
  4.  
http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com
j retirado

Desconectado Desconectado

Mensajes: 61



Ver Perfil WWW
Re: Problema: Búsqueda en Array
« Respuesta #5 en: 30 Junio 2009, 09:31 am »

Exactamente, es eso. Ése es el algoritmo en el que analizas todos los casos, y en ese caso te queda O(n^2) donde n es la cantidad de numeros ingresados.

La otra forma (que a mi se me ocurrió, seguro hay otras) es ordenar el array con quicksort que tiene costo n*log(n). Luego uso búsqueda binaria que tiene costo log(n), en el peor caso se hacen n veces búsqueda binaria por lo tanto tengo n*log(n). En total tengo n*log(n)+n*log(n)=2*n*log(n) que es del orden de O(n*log(n)) pues las constantes multiplicativas son despreciables para n suficientemente grande.

Aunque en realidad cabe destacar que quicksort tiene costo n*log(n) en el caso medio (que es lo más probable que suceda). En tal caso lo anterior es correcto. Pero en el peor caso quicksort tiene costo n^2 (por ejemplo si el array ya esta ordenado, el pivote no queda muy al centro que digamos...). Entonces tendría n*log(n) por la busqueda binaria  y n^2 por quicksort, luego el algoritmo es n*log(n)+n^2 que es O(n^2). Pero esto en el peor caso, lo cual es mejor que usar brute force pues de esa forma me queda O(n^2).

Saludos.
En línea

Eliptico

Desconectado Desconectado

Mensajes: 153


Ver Perfil
Re: Problema: Búsqueda en Array
« Respuesta #6 en: 7 Julio 2009, 00:12 am »

¡¡¡Buenas!!!

Si restringes los valores del vector, a enteros no negativos, puedes hacer una ordenacion tipo cubeta (creo recordar que era de orden O(n)) y luego aplicar la busqueda binaria.

Hace mucho que no trabajo con metodos de ordenacion (de echo si alguna vez me hace falta alguno recurro al quick sort) y no recuerdo si se podia generalizar a un conjunto cualquiera (finito) de valores enteros.

Espero que te sirva.

¡¡¡Un saludo!!!

PD: A ver si refresco algo la memoria y puedo dejar el codigo por aqui. (de momento me toca ver Airbag :D )
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Problema haciendo una busqueda y replazo con VB Script
Scripting
Gallusser 3 4,206 Último mensaje 11 Enero 2011, 17:01 pm
por Novlucker
Problema en sentencia de búsqueda con varios valores.
Bases de Datos
mokoMonster 5 7,546 Último mensaje 27 Febrero 2014, 13:21 pm
por leo1972
Busqueda binaria de un array desordenado « 1 2 3 »
Programación C/C++
David_RM 21 16,366 Último mensaje 13 Noviembre 2011, 16:55 pm
por CobraCY
Problema con Array
Programación C/C++
Ja_90 5 8,039 Último mensaje 20 Octubre 2015, 19:29 pm
por Ja_90
Busqueda y mostrar elemento en array
Programación C/C++
matver 3 2,171 Último mensaje 6 Febrero 2017, 03:44 am
por JS3
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines