| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
SwimPiii
Registrado: 17 Mar 2013
Mensajes: 6
|  Publicado: 17/03/2013 5:16 pm | | | Título: Algoritmo de busqueda |
| Muy buenas a todos,
Estoy intentando hacer un algoritmo de busqueda de un patron en una serie de numeros almacenada en un fichero, del tipo:
1, 1, 7, 5, 13, 1, 3, 11, 9, 7, 15, 1, 5, 5, 11, 7, 1, 13, 7, 13, 13, 1, 3, 3, 9, 3, 15, 9, 5, 11, 11, 15, 1, 9, 7, 5, 13, 7, 3, 11, 9, 15, 15, 1, 5, 1, 11, 7, 1, 5, 7, 13, 13, 5, 3, 3, 9, 11, 15, 9, 5, 7...etc
Lo que quiero plantear (en ANSI C) es buscar si existe (o no) un patrón en una serie dada como esa (mas larga, eso es un mero ejemplo). Para que quede más claro, si la serie fuese esta:
1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5...etc dicho algoritmo tendria que detectar que el patron es: "1,2,3,4,5,"
¿Alguien puede guiarme?
Muchas gracias de antemano, un saludo |
| | Volver arriba | |  | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 18/03/2013 8:22 am | | | Título: |
| Tengo mis dudas.
Si la intención es verificar si la serie puede considerarse como la repetición de otra(s) mas pequeña(s) puedes hacerlo así:
1) Utilizas la función memcmp (prototipo en <string.h>) o una propia para la comparación, me parece que lo políticamente correcto es la segunda (por el "padding", habrá que revisar el estándar).
2) Consideras la serie como trozos de 1, 2, 3, ... N/2 elementos donde N es el numero de elementos de la serie.
3) Si todos los trozos son iguales es un subserie.
Un ejemplo para explicarlo mejor:
| Código: | #include <stdio.h>
#include <stdlib.h>
#include <string.h>
void buscar_ss(char *p, int nb);
int main (void)
{
char serie[] = "121212121212121212121212";
buscar_ss(serie, (int) sizeof serie - 1);
return EXIT_SUCCESS;
}
void buscar_ss(char *p, int nb)
{
int i;
int j;
for (i = 1; i <= nb / 2; i++)
if (nb % i == 0){
for (j = 0; j < nb-i && memcmp(p + j, p + j + i, i) == 0; j += i)
;
if (j == nb-i)
printf("%2d(%2d): %.*s\n", i, nb/i, i, p);
}
} |
Y su salida es:
| Código: | 2(12): 12
4( 6): 1212
6( 4): 121212
8( 3): 12121212
12( 2): 121212121212 |
Pero, de nuevo, tengo mis dudas.
Un saludo
_________________
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 |
| | Volver arriba | | | SwimPiii
Registrado: 17 Mar 2013
Mensajes: 6
| | Publicado: 18/03/2013 2:32 pm | | | Título: |
| Muy buenas,
Muchas gracias por tu aporte y respuesta, de verdad. Lo unico te pediría si es posible que me mandes este trozo de código sin ofuscar, debido a que mi intención poniendo esta duda aquí es obviamente entender como hacerlo, valorar tu idea y entenderla.
for (i = 1; i <= nb / 2; i++)
if (nb % i == 0){
for (j = 0; j < nb-i && memcmp(p + j, p + j + i, i) == 0; j += i)
;
if (j == nb-i)
printf("%2d(%2d): %.*s\n", i, nb/i, i, p);
}
Si no es mucha molestia, me gustaría entenderlo. Muchas gracias
*No necesito una redacción ni mucho menos detallada para entenderlo, simplemente la primera forma en la que fue escrito. |
| | Volver arriba | | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 19/03/2013 6:10 pm | | | Título: |
| | SwimPiii escribió: | | Lo unico te pediría si es posible que me mandes este trozo de código sin ofuscar |
No esta ofuscado.
Se puede cambiar, al gusto, el nombre de los parámetros. Por ejemplo en lugar de "char *p" se puede utilizar "char byte[]" ya que eso es, un array donde se almacena cada uno de los caracteres de la serie. En la misma linea "nb" se puede sustituir por "num_bytes" o "numero_de_bytes". Como puedes ver el primer parámetro es el array donde se almacena la serie y el segundo su numero de elementos.
Utilice caracteres porque ellos permiten el ejemplo mas fácil, con otros tipos como int o long hay que tener en cuenta su tamaño utilizando el operador "sizeof".
| SwimPiii escribió: | | No necesito una redacción ni mucho menos detallada para entenderlo, simplemente la primera forma en la que fue escrito. |
Esa es la primera forma.
Aquí va una explicación:
Supongamos que tenemos una serie con números de un solo dígito (solo 1 y 2):
| Código: | 1 2 1 2 1 2 1 2 1 2 1 2 |
Debemos verificar si esa serie se puede dividir en trozos del mismo tamaño y con el mismo valor:
| Código: | 1 2 1 2 1 2 1 2 1 2 1 2
12 12 12 12 12 12
121 212 121 212
1212 1212 1212
121212 121212 |
Para ese primer paso, verificar las subseries, utilizamos el bucle interno:
| Código: | for (i = 1; i <= nb / 2; i++) |
Se revisan las subseries de 1, 2, ... N/2 elementos donde N es el numero de elementos de la serie y que en este caso es 1, 2, ... 6.
Siguiendo el ejemplo no tiene caso verificar las subseries con 5 elementos ya que no es posible generar la serie con 12 elementos. Para verificar solo los factores de N se utiliza la sentencia condicional:
| Código: | if (nb % i == 0) /* Solo los factores */ |
Para verificar, de nuevo siguiendo el ejemplo, las subseries con 1, 2, 3, 4, y 6 elementos.
El paso mas complicado es verificar que todos los trozos sean iguales. Debemos verificar si el primero es igual al segundo, el segundo igual al tercero, ... el penúltimo igual al ultimo.
Eso se consigue con esta parte de la condición del bucle:
Con ello se comparan todos los elementos con el siguiente, salvo el ultimo ya que es ... el ultimo.
Para la comparación utilizamos la función memcmp que compara un bloque de memoria con otro y resulta en cero si el contenido es el mismo. También se puede utilizar una función propia pero es mas trabajo y, en este caso, da igual.
Si unimos las dos partes:
| Código: | j < nb-i && memcmp(p + j, p + j + i, i) == 0 |
El bucle se ejecuta para comparar todos los pares (primero y segundo, segundo y tercero, etc.) siempre que los trozos sean iguales.
Si eso sucede (todos los trozos son iguales) el bucle termina cuando la condición "j < nb-i" sea falsa lo cual nos lleva a la conclusión: si el valor de j es igual a "nb-i" entonces los trozos son iguales. Eso se realiza con la sentencia if:
| Código: | if (j == nb-i) /* Si son iguales se imprime la subserie */
printf("%2d(%2d): %.*s\n", i, nb/i, i, p); |
Por ultimo la llamada a memcmp:
| Código: | memcmp(p + j, p + j + i, i) |
Esa función requiere las direcciones en memoria de los dos bloques a comparar y el numero de bytes (tamaño) de ambos:
"p + j" es la dirección del trozo
"p + j + i" es la dirección del siguiente trozo
i es el tamaño en bytes (recuerda: 1, 2, 3, 4 y 6).
Bueno, eso es todo.
Un saludo
_________________
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 |
| | Volver arriba | | | SwimPiii
Registrado: 17 Mar 2013
Mensajes: 6
| | Publicado: 20/03/2013 12:51 am | | | Título: |
| Fantástica explicación. Mi problema era que desconocia variables como por ejemplo "nb", debido a que mi nivel de C es intermedio.
Ante todo, muchas gracias por la explicación, solución, y tiempo.
Un saludo! |
| | Volver arriba | | | SwimPiii
Registrado: 17 Mar 2013
Mensajes: 6
| | Publicado: 20/03/2013 1:08 am | | | Título: |
| Porque.....Ahora mirando mejor el codigo, esta linea:
void buscar_ss(char *p, int nb);
Al ponerla, tambien estás declarando directamente esas variables?
Es decir, seria lo mismo que poner dentro del programa:
int nb;
char *p;
Si es asi, pido disculpas. Ahí estaba mi problema, siempre he declarado las variables en C en el propio código y no sabía que pudiera hacerse así. Entendía que así "avisabas" al compilador de la existencia de una funcion tipo Void posterior, y que únicamente servía para eso.
Si también sirve para declarar, entonces ya todo tiene mas sentido...Llegué a pensar que "nb" era una variable """interna""" del propio lenguaje o algo por el estilo...
Un saludo |
| | Volver arriba | | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 7516
Ubicación: Mexico
| | Publicado: 22/03/2013 9:38 am | | | Título: |
| | SwimPiii escribió: | Ahora mirando mejor el codigo, esta linea:
void buscar_ss(char *p, int nb);
Al ponerla, tambien estás declarando directamente esas variables?
Es decir, seria lo mismo que poner dentro del programa:
int nb;
char *p;
Si es asi, pido disculpas. Ahí estaba mi problema, siempre he declarado las variables en C en el propio código y no sabía que pudiera hacerse así. |
No.
| SwimPiii escribió: | | Entendía que así "avisabas" al compilador de la existencia de una funcion tipo Void posterior, y que únicamente servía para eso. |
Correcto.
Detallando la explicación, cuando se utilizan funciones propias en un programa se realizan tres pasos:
* Se declaran las funciones, siguiendo nuestro ejemplo:
| Código: | void buscar_ss(char *p, int nb); |
En una declaración de función el nombre de los argumentos es opcional, por ello esta declaración también es valida:
| Código: | void buscar_ss(char *, int); |
* Con ello y como bien comentas se le da al compilador la información necesaria para que este pueda revisar el programa y advertir cuando la llamada o uso no cumple con los requisitos de la función (por ejemplo pasarle una cadena cuando espera un entero), en nuestro caso no hay problema:
| Código: | buscar_ss(serie, (int) sizeof serie - 1); |
* La definición de una función incluye el cuerpo de esta, en nuestro caso:
| Código: | void buscar_ss(char *p, int nb)
{
/* ... */
} |
La definición al igual que su uso debe coincidir con la declaración, si no es así el compilador generara un mensaje de error.
En la definición de una función sus parámetros son variables locales (únicas o propias) de la función y estas se inicializan con su respectivo argumento (el valor utilizado en la llamada).
Para explicarlo mejor si tenemos una función como esta:
| Código: | void suma(int a, int b, int c)
{
printf("%d\n", a + b + c);
} |
Y se llama de esta forma:
Antes de ejecutarse la primera sentencia de la función "suma" su parámetro "a" se inicializa con el valor 3 (primer argumento), su parámetro "b" con 2 (segundo argumento) y su parámetro "c" con 3 (tercer argumento).
Un saludo
_________________
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 |
| | Volver arriba | | | Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 1344
| | Publicado: 12/04/2013 9:40 am | | | Título: |
| Estaba haciendo un programa relacionado con los diferentes patrones de lanzamientos en malabares( Sí! muy curioso, hay una nomenclatura matemática para los patrones malabares que incluso te permite discernir entre que patrones se pueden hacer y cuáles no ) y resulta que patrones como 1,11,111,1111... o 234, 234234, 234234234... son equivalentes. Así que necesitaba un algoritmo del estilo que se ha expuesto para cribar patrones que representan lo mismo.
Aquí mi algoritmo que sólo depende linealmente de la longitud de la cadena y no, de el número de divisores que tenga esa longitud.
Está escrito en C++11( uso de initializer_list ) y un poco deprisa, si a alguien le apetece depurarlo, pasarlo a C o lo que sea, aquí lo tiene:
| Código: | #include<iostream>
#include<vector>
bool fun( const std::vector<int>& v );
int main()
{
std::vector<int> v = { 1, 2, 1, 2, 1, 1, 2, 1, 2, 1 };
std::vector<int> w = { 1, 2, 1, 2, 1, 5, 1, 2, 1, 2, 1, 5};
std::cout << fun( v ) << std::endl;
std::cout << fun( w ) << std::endl;
return 0;
}
bool fun( const std::vector<int>& v )
{
if( v.size() == 0 )
return true;
std::vector<int> u;
u.push_back( v[0] );
int nrep = 1;
int i, j;
for( i = nrep, j = 0; i < v.size(); ++i, ++j )
{
if( v[i] != u[j] )
{
if( v[i] != u[0] )
{
nrep = i + 1;
j = -1;
}
else
{
nrep = i;
j = 0;
}
}
u.push_back( v[i] );
if( j >= nrep - 1 ) j = -1;
}
return nrep < i and i % nrep == 0;
} |
Un saludo! |
| | Volver arriba | | | | |
| No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
|
|
| |
F.A.Q.
Conéctese para revisar sus mensajes