6 respuestas
La "nadie" se refiere al carácter evidente o simplista. No sabemos de qué algoritmo hablas. Aclara, por favor (y aclara también qué tipo de ayuda esperas).
Dal, hablo del algoritmo naïf que permite hacer una búsqueda exacta de una palabra en un texto!
Espero que así quede más claro :P
Espero que así quede más claro :P
No, siempre es la niebla, porque solo respondiste a medias: describe tu algoritmo, muestra tu código en C de implementación (copia-pega dentro de las etiquetas "code" - haz clic en el botón a la derecha del botón S), y dinos dónde te atoras.
Justamente Dal, ese es el problema, nunca he hecho C además para el algoritmo solo encontré algunas cosas en Internet, así que te muestro lo que hice pero de cualquier manera porque podrías no entender nada :/
"código"
/* Algoritmo ingenuo, con bucle interno, sin bucle rápido, sin sentinela */
#include <stdio.h>
int i; /*contador*/
int j; /*contador*/
int n ;
int m; /*longitud de una palabra*/
int calcul_occ (int occ); /*para el cálculo de una ocurrencia; para encontrar una ocurrencia*/
char *x (int compt) ;
char *y (int comp);
int calcul_occ (int occ){
j = 0;
while (j <= n-m) {
int i = 0;
while ( (i < m) && (x(i) = y(i+j)) ) {
i = i+1;
if (i >= m) {
return occ;
printf ("Signaler una ocurrencia %d\n", occ);
}
j = j+1;
}
}
}
"código"
/* Algoritmo ingenuo, con bucle interno, sin bucle rápido, sin sentinela */
#include <stdio.h>
int i; /*contador*/
int j; /*contador*/
int n ;
int m; /*longitud de una palabra*/
int calcul_occ (int occ); /*para el cálculo de una ocurrencia; para encontrar una ocurrencia*/
char *x (int compt) ;
char *y (int comp);
int calcul_occ (int occ){
j = 0;
while (j <= n-m) {
int i = 0;
while ( (i < m) && (x(i) = y(i+j)) ) {
i = i+1;
if (i >= m) {
return occ;
printf ("Signaler una ocurrencia %d\n", occ);
}
j = j+1;
}
}
}
Hola Yira,
Si no se especifica el algoritmo, debes determinarlo antes de ponerte a codificar en C.
Esta página seguramente puede ayudarte :https://www.irif.fr/~carton//Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/
Sin embargo, tendrás que mirar tu curso para validar si este algoritmo contiene una "bucle interna", y no contiene una "bucle rápida" o una "sentinela". Estas son nociones que te debieron explicar la persona que redactó el enunciado (¿tu profesor?).
En cuanto a tu código C. Deberías reconsiderar seriamente tus bases.
Creo que confundes la sintaxis de declaración de una función y la de declaración de un arreglo con tus x e y y el prototipo de tu función no tiene sentido para mí.
Aquí tienes una estructura de código C que contiene un prototipo razonable para esta función, y que permite probar la implementación de tu algoritmo.
Me permito citar el pasaje del curso de M. Olivier CARTON, situado en la dirección mencionada, en comentario de la función
A ti de jugar :-)
Dal
Si no se especifica el algoritmo, debes determinarlo antes de ponerte a codificar en C.
Esta página seguramente puede ayudarte :https://www.irif.fr/~carton//Enseignement/Algorithmique/Programmation/Pattern/MorrisPratt/
Sin embargo, tendrás que mirar tu curso para validar si este algoritmo contiene una "bucle interna", y no contiene una "bucle rápida" o una "sentinela". Estas son nociones que te debieron explicar la persona que redactó el enunciado (¿tu profesor?).
En cuanto a tu código C. Deberías reconsiderar seriamente tus bases.
Creo que confundes la sintaxis de declaración de una función y la de declaración de un arreglo con tus x e y y el prototipo de tu función no tiene sentido para mí.
Aquí tienes una estructura de código C que contiene un prototipo razonable para esta función, y que permite probar la implementación de tu algoritmo.
Me permito citar el pasaje del curso de M. Olivier CARTON, situado en la dirección mencionada, en comentario de la función
int premiere_occurrence(char * motif, char * texte).
#include <stdio.h>
/**
* premiere_occurrence - búsqueda naive de texto
*
* motif : motivo a buscar
* texte : texto donde se busca el motivo
*
* retorna :
* -1 si el motivo no está presente
* o la posición de la primera ocurrencia
*/
int premiere_occurrence(char * motif, char * texte)
{
/*
* Para cada posición posible del motivo en el texto,
* se prueba si esta posición es una ocurrencia del motivo.
* Esta prueba se realiza comparando los caracteres del
* motivo con los caracteres del texto de izquierda a derecha.
* Si todos los caracteres del motivo son iguales a los
* caracteres del texto en las posiciones correspondientes,
* se ha encontrado una ocurrencia y se devuelve la posición de esa
* ocurrencia. De lo contrario, la búsqueda continúa
* avanzando a la posición siguiente.
*/
}
int main(void)
{
char * motif = "Toto";
char * texte = "Le professeur demande à Toto :\n"
"- Toto, 3 et 3 ça fait quoi ?\n"
"- Match nul monsieur !";
int position;
position = premiere_occurrence(motif, texte);
if (position == -1)
{
printf("motif [%s] non trouvé dans le texte\n", motif);
}
else
{
printf("le motif [%s] a été trouvé en position %d\n",
motif, position);
/* el resultado correcto es 25 */
}
return 0;
}
A ti de jugar :-)
Dal
Hola Dal :)
¡Muchas gracias!
Creo que no tenemos el mismo algoritmo ingenuo, si no voy a intentar adaptar lo que me hiciste a lo que yo poseo!
Por cierto, ya te dije que soy nulo en C, pero estoy tratando de aprenderlo.
Bueno, voy a abusar un poco más, pero tengo otra pregunta; si en lugar de escribir el algoritmo ingenuo y encontrar una palabra en un texto te piden escribir un analizador léxico que cuente el número de ocurrencias de los motivos: ACAT, ATTA, CGC, CGCAA en una molécula de ADN codificada en forma de un archivo de texto?
¡Muchas gracias!
Creo que no tenemos el mismo algoritmo ingenuo, si no voy a intentar adaptar lo que me hiciste a lo que yo poseo!
Por cierto, ya te dije que soy nulo en C, pero estoy tratando de aprenderlo.
Bueno, voy a abusar un poco más, pero tengo otra pregunta; si en lugar de escribir el algoritmo ingenuo y encontrar una palabra en un texto te piden escribir un analizador léxico que cuente el número de ocurrencias de los motivos: ACAT, ATTA, CGC, CGCAA en una molécula de ADN codificada en forma de un archivo de texto?
Si quieres contar el número de ocurrencias, en principio, “basta” modificar el algoritmo para que, en lugar de devolver la posición de la primera ocurrencia, se incremente un contador de ocurrencias y se continúe la búsqueda en la continuación de la cadena de texto, y luego se devuelva el contador cuando se alcance el final de la cadena de texto.
Dicho esto, no soy muy experto en moléculas de ADN.
Si tienes “CGCAACAT”, y buscas “ACAT”, lo vas a encontrar, y si buscas “CGCAA” también lo vas a encontrar, y no sé si el hecho de que compartan un carácter tiene alguna importancia para ti, en particular si tu búsqueda debe indicar el número de ocurrencias de “ACAT” y de “CGCAA”.
Dal
Dicho esto, no soy muy experto en moléculas de ADN.
Si tienes “CGCAACAT”, y buscas “ACAT”, lo vas a encontrar, y si buscas “CGCAA” también lo vas a encontrar, y no sé si el hecho de que compartan un carácter tiene alguna importancia para ti, en particular si tu búsqueda debe indicar el número de ocurrencias de “ACAT” y de “CGCAA”.
Dal
En realidad Dal, para ser exactos, es un analizador léxico, no sé si has hecho compilación o no, pero justamente eso es lo que hay que hacer; un analizador que permita analizar el número de ocurrencias en las 4 palabras que te había dado, en forma de un archivo de texto.
No sé si soy claro o ¿hay algo raro? !!!
No sé si soy claro o ¿hay algo raro? !!!