1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Exercício de um programação

Discussão em 'Programação' iniciada por Albus Severus, 8 de Junho de 2012. (Respostas: 0; Visualizações: 591)

  1. Boas, tenho um exercício de programação para fazer.
    Desenvolvi um algoritmo e para os casos de teste fornecidos para exemplo obtive os resultados certos, no entanto, obtenho como resultado, do meu exercício, resposta errada.

    Abaixo segue o enunciado do problema mais o caso de teste exemplo fornecido. De seguida o meu código. Caso alguém saiba onde está o erro ou se souberem onde posso testar este problema on-line digam se faz favor.

    Para a resolução do problema, eu crio uma lista de adjacências, na qual, para cada nó do grafo é inserido o nó necessário para formar uma rua. De seguida inicio a busca de caminhos começando sempre no nó um. A cada nó que chego, marco como nó expandido, impedindo assim, que aconteçam ciclos e que apareçam ruas repetidas.

    O código está na linguagem C.

    Descrição

    Ultimamente, reparaste que a tua amiga Sara se está a sentir aborrecida. Ela está aborrecida dos seus sapatos, da comida da escola, dos professores e de tomar o mesmo caminho da casa até à escola todos os dias.

    Tu decidiste ajudá-la neste terrível momento na vida dela. Não há muito que possas fazer para além de usares as tuas habilidades de programação, de modo a descobrir caminhos alternativos para a escola. Sendo assim, tu imprimes um mapa da Internet mostrando as ruas da casa da Sara até à escola. Agora, tu queres descobrir quantos caminhos existem da casa dela até à escola, tendo em conta que não podem haver ruas em comum nos diversos caminhos. Felizmente, Sara vai se sentir mais feliz no seu caminho para a escola.

    Consegues descobrir o número máximo de tais caminhos no mapa?

    Input

    Cada rua é caracterizada por dois fins. O fim de uma rua pode também ser o fim de uma ou mais outras ruas, por exemplo, uma junção ou uma intersecção. Caso contrério, é um caminho sem fim. Sara pode andar em ambas as direcções na rua. É assumido que há pelo menos um caminho da casa da Sara para a escola.

    A primeira linha de cada caso de teste indica o número de ruas (m) e o número de junções de ruas, intersecções e, ou, de caminhos sem fim (n). Depois, m linhas seguem. Cada linha descreve uma rua por dois inteiros, que são os índices dos seus fins. Assume que a casa da Sara é na localização um e a escola dela é na localização n.

    Há no máximo 500 ruas e 70000 intersecções de ruas ou caminhos sem fim.

    Output

    Para cada caso de teste, imprime o número máximo de caminhos com ruas disjuntas que a Sara pode tomar de casa até à escola.

    Exemplo

    Input
    5 5
    1 3
    1 4
    1 5
    2 3
    3 5
    23 10
    1 2
    1 7
    1 9
    1 10
    2 4
    2 5
    2 6
    2 9
    2 10
    3 7
    3 8
    3 9
    4 6
    4 7
    4 8
    4 10
    5 7
    5 8
    5 9
    5 10
    6 8
    6 9
    7 9

    Output
    2
    4




    #include<stdio.h>
    #include<stdlib.h>

    typedef struct No
    {
    int vertice;
    struct No *next;
    } node;

    int n,m;
    node *vertices;
    int *nos_ja_expandidos;
    int size;

    void input_list(void);
    node *criar_vertices(void);
    int *vector_int(int valor);
    node *criar_node(int vertice);
    void add_node(int vertice,node *no);
    void libertar_memoria(void);
    void libertar_lista_adj(node *vertices);
    int algoritmo(void);
    int func_rec(int pos);

    int main(void)
    {
    int res;
    while (scanf(" %d %d",&m,&n)!=EOF)
    {
    size=n+1;

    vertices=criar_vertices();

    input_list();

    nos_ja_expandidos=vector_int(0);

    res=algoritmo();

    printf("%d\n",res);

    libertar_memoria();
    }
    return 0;
    }

    void input_list(void)
    {
    int k;
    int i,j;
    node *novo_no;
    for (k=0;k<m;k++)
    {
    scanf(" %d %d",&i,&j);
    novo_no=criar_node(j);
    add_node(i,novo_no);
    novo_no=criar_node(i);
    add_node(j,novo_no);
    }

    }

    node *criar_vertices(void)
    {
    node *ptr=(node *) malloc(sizeof(node)*size);
    int i;
    for (i=1;i<size;i++)
    {
    ptr.vertice=i;
    ptr.next=NULL;
    }
    return ptr;
    }

    node *criar_node(int vertice)
    {
    node *ptr=(node *) malloc(sizeof(node));
    ptr->vertice=vertice;
    ptr->next=NULL;
    return ptr;
    }

    void add_node(int vertice,node *no)
    {
    node *ptr=&vertices[vertice];
    no->next=ptr->next;
    ptr->next=no;
    }

    int algoritmo(void)
    {
    node *ptr=vertices[1].next;
    int soma_caminhos=0;

    nos_ja_expandidos[1]=1;

    while (ptr)
    {
    if (!nos_ja_expandidos[ptr->vertice])
    soma_caminhos=soma_caminhos+func_rec(ptr->vertice);
    ptr=ptr->next;
    }

    return soma_caminhos;
    }


    int func_rec(int pos)
    {
    node *ptr;
    int res=0;

    if (pos==n)
    return 1;

    nos_ja_expandidos[pos]=1;

    ptr=vertices[pos].next;

    while (ptr)
    {
    if (!nos_ja_expandidos[ptr->vertice])
    res=res+func_rec(ptr->vertice);
    ptr=ptr->next;
    }

    return res;
    }

    int *vector_int(int valor)
    {
    int *ptr=(int *) malloc(sizeof(int)*size);
    int i;
    for (i=1;i<size;i++)
    ptr=valor;
    return ptr;
    }

    void libertar_memoria(void)
    {
    libertar_lista_adj(vertices);
    free(nos_ja_expandidos);
    }

    void libertar_lista_adj(node *vertices)
    {
    int i;
    node *ptr,*aux;
    for (i=1;i<size;i++)
    {
    ptr=vertices.next;
    vertices.next=NULL;
    while (ptr)
    {
    aux=ptr;
    ptr=ptr->next;
    aux->next=NULL;
    free(aux);
    }
    }
    }
     
    Última edição: 8 de Junho de 2012

Partilhar esta Página