- Leia as notas de aula de filas. Entenda o problema e o algoritmo
lá explicado para cálculo da distância. Modifique-o para que a
saída seja a lista de cidades a que posso chegar a partir da cidade
s.
- Considere um grafo G com n vértices, dado por uma matriz
anxn em que a[i][j]=1 se os vértices i
e j são adjacentes, 0 caso contrário. Dizemos que G é
bipartido se podemos colorir os vértices de G com duas
cores de modo que toda aresta de G tenha extremos de cores
distintas. Escreva uma função que recebe como parâmetros um
inteiro n e uma matriz anxn como acima, e devolve 1
se o grafo correspondente for bipartido, 0 caso contrário.
- Qual é a saída da seguinte seqüência de operações sobre uma fila:
queueInit(10);
queuePut(1);
queuePut(2);
printf("%d", queueGet());
queuePut(3);
printf("%d", queueGet());
printf("%d", queueGet());
queuePut(4);
queuePut(5);
printf("%d", queueGet());
printf("%d", queueGet());
- Uma fila dupla é uma variante da fila em que se permite
inserções nas duas extremidades. Ou seja, há duas operações de
inserção numa fila dupla: queuePutL e queuePutR.
A remoção é sempre feita da extremidade esquerda.
Qual seria o resultado das seguintes operações sobre uma fila dupla:
dequeInit(10);
dequePutL(1);
dequePutR(2);
printf("%d", dequeGet());
dequePutR(3);
printf("%d", dequeGet());
printf("%d", dequeGet());
dequePutR(4);
dequePutL(5);
printf("%d", dequeGet());
printf("%d", dequeGet());
- Lembra do problema do ratinho num labirinto procurando o queijo, em MAC2166?
Escreva um programa que resolve o problema do ratinho sem usar a interface de fila,
mas usando um vetor (dois, na verdade) diretamente como uma fila, como foi feito
no cálculo de distância em um grafo, feito em aula.
- Simule o algoritmo do problema do ratinho para a seguinte entrada:
8 9 (tamanho do labirinto)
-2 -2 -2 -2 -1 -2 -1 -1 -2 (-2 indica posição livre, -1 parede)
-2 -2 -1 -2 -2 -2 -1 -2 -2
-2 -2 -2 -1 -1 -2 -1 -2 -1
-2 -1 -2 -2 -1 -2 -2 -2 -1
-2 -1 -1 -2 -1 -2 -1 -2 -2
-2 -2 -2 -2 -2 -2 -1 -1 -2
-2 -2 -1 -2 -1 -2 -2 -1 -2
-2 -1 -1 -2 -1 -1 -2 -2 -2
1 1 (posição do rato)
8 9 (posição do queijo)
Mostre como fica a matriz no fim do programa e qual é a saída do
programa para estes dados.
- Modifique o algoritmo do problema do ratinho para que ele resolva
a seguinte variante do problema: determinar se não existe caminho
do queijo ao rato, se existe exatamente um caminho ou se existem
dois ou mais caminhos do queijo ao rato.
- Você consegue pensar em uma forma de alterar o algoritmo do
problema do ratinho de forma a determinar quantos caminhos de
comprimento mínimo existem do queijo ao rato?
- Escreva um programa que recebe um labirinto, como no problema do
ratinho, e a posição do rato, e imprime todas as posições do
labirinto às quais o rato pode chegar.