- Considere uma seqüência de elementos entre {, }, [, ], ( e
). Dizemos que uma tal seqüência é bem-formada se
- ela é vazia ou
- ela é {S}R ou [S]R ou (S)R, onde S e R são
seqüências bem-formadas.
Escreva uma função que recebe como parâmetros um inteiro n e
string com uma seqüência de n elementos entre {, }, [,
], ( e ), e devolve 1 se tal seqüência é bem-formada, 0 caso
contrário.
- Converta as seguintes expressões para notação posfixa usando o
algoritmo visto em aula. Mostre em cada passo o conteúdo da
pilha de operadores.
- A - B / C * (D - (E + F)) / G + H * I
- ( A + B ) / C * D - E / (F * G)
- Considere expressões que, além dos operadores binários +, -, *
e /, têm também o operador binário ^, de exponenciação. O
operador ^ tem precedência maior que os operadores
acima. Ademais, o operador de exponenciação, diferente dos
demais, tem prioridade da direita para a esquerda. Ou seja, a
expressão 2^3^2 = 2^(3^2) = 2^9 = 512, e não 64. Adapte o
algoritmo visto em aula para aceitar também expressões com
^. Depois simule o seu algoritmo com a seguinte expressão:
- A ^ B ^ C + D
- A ^ B + C ^ D
- A ^ B + C * D ^ E ^ F - G / H ^ (I + J)
- 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:
cria_fila(10);
insere_fila(1);
insere_fila(2);
printf("%d", remove_fila());
insere_fila(3);
printf("%d", remove_fila());
printf("%d", remove_fila());
insere_fila(4);
insere_fila(5);
printf("%d", remove_fila());
printf("%d", remove_fila());
- 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: insere_esquerda e insere_direita.
A remoção é sempre feita da extremidade esquerda.
Qual seria o resultado das seguintes operações sobre uma fila dupla:
cria_filad(10);
insere_esquerda_filad(1);
insere_direita_filad(2);
printf("%d", remove_filad());
insere_direita_filad(3);
printf("%d", remove_filad());
printf("%d", remove_filad());
insere_direita_filad(4);
insere_esquerda_filad(5);
printf("%d", remove_filad());
printf("%d", remove_filad());
- Escreva o 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 as quais o rato pode chegar.