Programa del algoritmo ingenuo en C
yirachan
-
yira Mensajes publicados 43 Estado Miembro -
yira Mensajes publicados 43 Estado Miembro -
Hola,
Quisiera recibir ayuda sobre un programa en C del algoritmo ingenuo con bucle interno, sin bucle rápido, sin sentinela.
Gracias.
Quisiera recibir ayuda sobre un programa en C del algoritmo ingenuo con bucle interno, sin bucle rápido, sin sentinela.
Gracias.
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 -
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;
}
}
}-
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ónint 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?-
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
-
-
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? !!!
