2

Estou a fazer um projecto para uma disciplina, mas estou com alguns problemas. O problema a ultrapassar é, num ficheiro de texto, composto por um id \t e uma sequencia de 2048 fixa '0' e '1', inserir um sequência e procurar os elementos mais parecidos.

O meu código tem só um algoritmo de pesquisa, mas que não resolve o problema, pois se a sequência introduzida não for igual à que existe no ficheiro, não encontra um macth.

#include <stdio.h>
#include <stdlib.h>
//#include "ler.h"

int pesquisa(){

    int n,*s,i,*c,a,j;
    FILE *fp;
    int *v;
    fp = fopen("tesste.txt", "r");
    v=(int*)malloc(sizeof(int));

    while(!feof(fp)){
        fscanf(fp,"\t%d",&v);
    }

    //printf("Valor n %d\n",v);
    //scanf("%d",&n);

    s=(int*)malloc(sizeof(int));
    c=(int*)malloc(sizeof(int));

    printf("Introduza a sequencia e tamanho da seq\n");

    scanf("%d",&a);

    for(j=0;j<a;j++){
        scanf("%d\n",&s[j]);
    }

    for(i=0;i<a;i++){
        if(s[i]==v[i])
            //printf("%d",a);
            //c[i]=s[i];
            return (1);
         else
            return (0);
    }

    // printf("%d",c);

    free(v);
    free(s);
    free(c);

    fclose(fp);

    return 0;

}
0

1 Resposta 1

0

Esse problema é bem parecido com o "Longest prefix match", famoso por causa dos protocolos de roteamento IPv4 e IPv6.

O algoritmo de força bruta para esse problema seria o seguinte:

Longest_Prefix_Match(IN)

  1. N = 0
  2. S = primeira entrada
  3. M = quantos bits iguais tem no início de S e IN
  4. Se M > N

    a. OUT = S

    b. N = M

  5. Se tiver mais entradas

    a. S = proxima entrada

    b. Volta para a linha 3.

  6. return OUT

Um erro que tu estás cometendo é que tu não compara todas as sequências, e sim retorna 1 se o primeiro bit das sequências são iguais e 0 caso contrário.

int count = 0;
for(i=0;i<a;i++){
    if(s[i]==v[i])
        count++;
     else
         break;
    }

...
return count;

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .