Question

Questão 1
Para praticar suas hard skills em desenvolvimento de software a um nível de programador(a) internacional, você decide que vai trabalhar em um projeto open-source. Assim, ao analisar um dos arquivos-fonte do repositório do projeto, você se depara com o seguinte código em linguagem C:

typedef struct NO{
int dado;
NO* prox;
}NO;

typedef struct FILA{
NO* inicio;
NO* fim;
} FILA;

FILA *f;

void enfileira(int valor){
NO* ptr = (NO *) malloc(sizeof(NO));
ptr->dado = valor;
ptr->prox = NULL;
if(f->inicio == NULL)
f->inicio = ptr;
else
f->fim->prox = ptr;
f->fim = ptr;
}

int desenfileira(){
NO* ptr = f->inicio;
int dado;
if(ptr != NULL){
f->inicio = ptr->prox;
ptr->prox = NULL;
dado = ptr->dado;
free(ptr);
return dado;
}
}

int main(){
f = (FILA *) malloc(sizeof(FILA));
f->inicio = NULL;
f->fim = NULL;
enfileira(10);
enfileira(30);
enfileira(50);
desenfileira();
enfileira(14);
}

Assim sendo, responda quais valores que estarão armazenados na fila, imediatamente antes de o programa finalizar sua execução? Escreva os valores começando pelo início da fila, e indo até o fim.

Answer 1

Eis a ideia de um algoritmo que usa uma fila de cidades ativas para resolver nosso problema. Uma cidade i é ativa se dist[i] já foi calculada mas as estradas que começam em i ainda não foram todas exploradas. Em cada iteração, o algoritmo

Segue o código que implementa a ideia. (Veja antes um rascunho em pseudocódigo.)  Para simplificar, as variáveis fila, p, u e dist são globais, ou seja, são definidas fora do código das funções.

#define N 100

int fila[N], int p, u;

int dist[N];

void criafila (void) {

  p = u = 0;

}

int filavazia (void) {

  return p >= u;

}

int tiradafila (void) {

  return fila[p++];

}

void colocanafila (int y) {

  fila[u++] = y;

}

// Esta função recebe uma matriz A

// que representa as interligações entre

// cidades 0..N-1 e preenche o vetor dist

// de modo que dist[i] seja a distância

// da cidade c à cidade i, para cada i.

void distancias (int A[][N], int c) {

  for (int j = 0; j < N; ++j)  dist[j] = N;

  dist[c] = 0;

  criafila ();

  colocanafila (c);

  while (! filavazia ()) {  

     int i = tiradafila ();

     for (int j = 0; j < N; ++j)

        if (A[i][j] == 1 && dist[j] >= N) {

           dist[j] = dist[i] + 1;

           colocanafila (j);

        }

  }

}

Answer 2

Resposta:

30, 50 e 14

Explicação: