busq_l.pas

   1                (**************************************)\r
   2                (**************************************)\r
   3                (**                                  **)\r
   4                (** ALGORITMOS DE BUSQUEDA EN PASCAL **)\r
   5                (**                                  **)\r
   6                (**************************************)\r
   7                (**************************************)\r
   8 \r
   9 (***************************************************************************\r
  10  *\r
  11  * Busqueda Secuencial\r
  12  *\r
  13  *   Recorre el vector y compara hasta encontrar el elemento.\r
  14  *   Devuelve el indice del elemento.\r
  15  *\r
  16  ***************************************************************************)\r
  17 \r
  18 function bSecuencial(var v: Vector;   { Vector en donde se va a buscar }\r
  19                          d: Dato)     { Dato a buscar (igual que el elemento de v }\r
  20                           : Integer;  { Indice en donde se encuentra el dato buscado o cero si no esta }\r
  21 \r
  22  var\r
  23     i, resultado: Integer;\r
  24 \r
  25  begin\r
  26       resultado := 0;\r
  27       for i := 1 to TAM do             { TAM es el tama¤o del vector }\r
  28           if v[i] = d then begin       { Si encontro el dato d en v ... }\r
  29              resultado := i;           { Asigna el indice actual al resultado }\r
  30              break;                    { Finaliza el ciclo for }\r
  31           end; { if }\r
  32       bSecuencial := resultado;\r
  33  end; { function bSecuencial }\r
  34 \r
  35 {===========================================================================}\r
  36 \r
  37 (***************************************************************************\r
  38  *\r
  39  * Busqueda Secuencial Auto-organizada moviendo al frente el elemento encontrado\r
  40  *\r
  41  *   Recorre el vector y compara hasta encontrar el elemento. Al encontrar el\r
  42  *     elemento, lo mueve automaticamente al inicio del vector.\r
  43  *   Devuelve true si se encontro o false si no se encontro.\r
  44  *\r
  45  ***************************************************************************)\r
  46 \r
  47 function bSecuencialAutoOrganizadaMoverAlFrente\r
  48                     (var v: Vector;   { Vector en donde se va a buscar }\r
  49                          d: Dato)     { Dato a buscar (igual que el elemento de v }\r
  50                           : Boolean;  { True si lo encontr¢, False si no lo hizo. La posicion es 1 siempre }\r
  51 \r
  52 (***************************************************************************\r
  53  *\r
  54  * Mueve el elemento que se encuentra en el indice i hasta el inicio,\r
  55  *  desplazando al resto de los indices hacia abajo.\r
  56  *\r
  57  ***************************************************************************)\r
  58 \r
  59  procedure moverAlFrente(var v: Vector;      { Vector a procesar }\r
  60                              pos: Integer);  { Indice a mover al frente }\r
  61 \r
  62    var\r
  63       tmp: Dato;\r
  64       i: Integer;\r
  65 \r
  66    begin\r
  67         if pos > 1 then begin\r
  68            tmp := v[1];\r
  69            v[1] := v[pos];\r
  70            for i := pos - 2 downto 1 do\r
  71                v[i+1] := v[i+2];\r
  72            v[2] := tmp;\r
  73         end; { if pos > 1 }\r
  74    end; { procedure moverAlFrente }\r
  75 \r
  76  (*******************************************************************)\r
  77 \r
  78  { continuacion de la funcion bSecuencialAutoOrganizadaMoverAlFrente }\r
  79 \r
  80  var\r
  81     i: Integer;\r
  82     resultado: Boolean;\r
  83 \r
  84  begin\r
  85       resultado := false;\r
  86       for i := 1 to TAM do             { TAM es el tama¤o del vector }\r
  87           if v[i] = d then begin       { Si encontro el dato d en v ... }\r
  88              moverAlFrente(v, i);      { Mueve al frente el elemento en i }\r
  89              resultado := true;        { Asigna true al resultado }\r
  90              break;                    { Finaliza el ciclo for }\r
  91           end; { if }\r
  92       bSecuencialAutoOrganizadaMoverAlFrente := resultado;\r
  93  end; { function bSecuencialAutoOrganizadaMoverAlFrente }\r
  94 \r
  95 {===========================================================================}\r
  96 \r
  97 (***************************************************************************\r
  98  *\r
  99  * Busqueda Secuencial Auto-organizada moviendo el elemento encontrado a la\r
 100  *   posicion del elemento anterior.\r
 101  *\r
 102  *   Recorre el vector y compara hasta encontrar el elemento. Al encontrar el\r
 103  *     elemento, lo mueve automaticamente a la posicion anterior del vector.\r
 104  *   Devuelve el indice del elemento.\r
 105  *\r
 106  ***************************************************************************)\r
 107 \r
 108 function bSecuencialAutoOrganizadaMoverAnterior\r
 109                     (var v: Vector;   { Vector en donde se va a buscar }\r
 110                          d: Dato)     { Dato a buscar (igual que el elemento de v }\r
 111                           : Integer;  { Indice en donde se encuentra el dato buscado o cero si no esta }\r
 112 \r
 113  var\r
 114     i, resultado: Integer;\r
 115     aux: Dato;\r
 116 \r
 117  begin\r
 118       resultado := 0;\r
 119       if v[1] = d then\r
 120          resultado := 1\r
 121       else\r
 122          for i := 2 to TAM do             { TAM es el tama¤o del vector }\r
 123              if v[i] = d then             { Si encontro el dato d en v ... }\r
 124                aux := v[i];               { Realiza el intercambio del elemento }\r
 125                v[i] := v[i-1];            {   encontrado con el primer elemento }\r
 126                v[i-1] := aux;             {   del vector v                      }\r
 127                resultado := i - 1;        { Pone como resultado a la nueva posicion de d }\r
 128                break;                     { Finaliza el ciclo for }\r
 129              end; { if }\r
 130       bSecuencialAutoOrganizadaMoverAnterior := resultado;\r
 131  end; { function bSecuencialAutoOrganizadaMoverAnterior }\r
 132 \r
 133 {===========================================================================}\r
 134 \r
 135 (***************************************************************************\r
 136  *\r
 137  * Busqueda Binaria Recursiva.\r
 138  *\r
 139  *   Requiere que el vector este ordenado de menor a mayor (creciente).\r
 140  *   Parte el vector al medio y compara. Si es igual, lo encontro y devuelve\r
 141  *     la posicion. Si el valor buscado es menor, toma la primera mitad y le\r
 142  *     la segunda mitad y le aplica la funcion recursivamente.\r
 143  *   Devuelve el indice del elemento.\r
 144  *\r
 145  ***************************************************************************)\r
 146 \r
 147 function bBinariaRecursiva(var v: Vector;   { Vector en donde se va a buscar }\r
 148                                ini,         { Indice por el cual empieza la busqueda }\r
 149                                fin: Integer;{ Indice por el cual termina la busqueda }\r
 150                                d: Dato)     { Dato a buscar (igual que el elemento de v }\r
 151                                 : Integer;  { Indice en donde se encuentra el dato buscado o cero si no esta }\r
 152 \r
 153  var\r
 154     medio: Integer;\r
 155 \r
 156  begin\r
 157       if (v[ini] > d) or (v[fin] < d) then begin { Si d no esta entre el mayor y menor valor de v ... }\r
 158          bBinariaRecursiva := 0                  { Asigna 0 al resultado, indicando que no encontro el dato }\r
 159       else begin                                 { Si esta entre los valores ... }\r
 160          medio := ini + ((fin - ini) div 2);     { Parte el vector en dos con el valor medio }\r
 161          if v[medio] = d then                    { Si el dato esta en la posicion del medio ... }\r
 162             bBinariaRecursiva := medio           { Asigna a la funcion el valor de dicho indice }\r
 163          else if v[medio] < d then               { Si el valor intermedio es menor que el buscado ... }\r
 164             { Asigna a la funcion (recursivamente) el valor de ella misma evaluada con inicio en el medio  }\r
 165             { mas 1 (la posicion del medio ya fue comparada) y el mismo fin. Esto se debe a que el vector  }\r
 166             { esta ordenado de forma creciente y el dato buscado es mayor que el dato intermedio, entonces }\r
 167             { si se encuentra el valor buscado, estara en la segunda mitad del vector                      }\r
 168             bBinariaRecursiva := bBinariaRecursiva(v, medio + 1, fin, d)\r
 169          else                                    { Si el valor intermedio es mayor que el buscado ... }\r
 170             { Igual que el anterior pero lo busca en la primera mitad }\r
 171             bBinariaRecursiva := bBinariaRecursiva(v, ini, medio - 1, d);\r
 172       end; { if (v[ini] > d) or (v[fin] < d) }\r
 173  end; { bBinariaRecursiva }\r
 174 \r
 175 {===========================================================================}\r
 176 \r
 177 (***************************************************************************\r
 178  *\r
 179  * Busqueda Binaria Recursiva.\r
 180  *\r
 181  *   Requiere que el vector este ordenado de menor a mayor (creciente).\r
 182  *   Parte el vector al medio y compara. Si es igual, lo encontro y devuelve\r
 183  *     la posicion. Si el valor buscado es menor, toma la primera mitad y le\r
 184  *     la segunda mitad y le aplica la funcion recursivamente.\r
 185  *   Devuelve el indice del elemento.\r
 186  *\r
 187  ***************************************************************************)\r
 188 \r
 189 function bInterpolacionRecursiva\r
 190                       (var v: Vector;   { Vector en donde se va a buscar }\r
 191                            ini,         { Indice por el cual empieza la busqueda }\r
 192                            fin: Integer;{ Indice por el cual termina la busqueda }\r
 193                            d: Dato)     { Dato a buscar (igual que el elemento de v }\r
 194                             : Integer;  { Indice en donde se encuentra el dato buscado o cero si no esta }\r
 195 \r
 196  var\r
 197     medio: Integer;\r
 198 \r
 199  begin\r
 200       if (v[ini] > d) or (v[fin] < d) then begin { Si d no esta entre el mayor y menor valor de v ... }\r
 201          bBinariaRecursiva := 0                  { Asigna 0 al resultado, indicando que no encontro el dato }\r
 202       else begin                                 { Si esta entre los valores ... }\r
 203          medio := ini + ((fin - ini) div 2);     { Parte el vector en dos con el valor medio }\r
 204          if v[medio] = d then                    { Si el dato esta en la posicion del medio ... }\r
 205             bBinariaRecursiva := medio           { Asigna a la funcion el valor de dicho indice }\r
 206          else if v[medio] < d then               { Si el valor intermedio es menor que el buscado ... }\r
 207             { Asigna a la funcion (recursivamente) el valor de ella misma evaluada con inicio en el medio  }\r
 208             { mas 1 (la posicion del medio ya fue comparada) y el mismo fin. Esto se debe a que el vector  }\r
 209             { esta ordenado de forma creciente y el dato buscado es mayor que el dato intermedio, entonces }\r
 210             { si se encuentra el valor buscado, estara en la segunda mitad del vector                      }\r
 211             bBinariaRecursiva := bBinariaRecursiva(v, medio + 1, fin, d)\r
 212          else                                    { Si el valor intermedio es mayor que el buscado ... }\r
 213             { Igual que el anterior pero lo busca en la primera mitad }\r
 214             bBinariaRecursiva := bBinariaRecursiva(v, ini, medio - 1, d);\r
 215       end; { if (v[ini] > d) or (v[fin] < d) }\r
 216  end; { bBinariaRecursiva }\r
 217 \r