Laboratório 3

Exercício 1 – Palíndromos

Uma string é um palíndromo se ela pode ser lida da mesma forma da esquerda para a direita e da direita para a esquerda. Por exemplo, "arara", "osso" e "a" são palíndromos, enquanto "casa" e "teste" não são.

Escreva uma função recursiva que determine se um trecho de uma string é um palíndromo.

Função a implementar

int eh_palindromo_rec(char str[], int inicio, int fim);

Os parâmetros inicio e fim indicam, respectivamente, as posições do primeiro e do último caractere do trecho de str que deve ser verificado. Os dois extremos fazem parte do trecho.

A função deve retornar 1 se o trecho entre inicio e fim for um palíndromo e 0 caso contrário.

Por exemplo, para verificar a string "arara" inteira, a chamada será

eh_palindromo_rec("arara", 0, 4)

que deve retornar:

1

Enquanto

eh_palindromo_rec("casa", 0, 3)

deve retornar:

0

Considere que str contém apenas letras minúsculas do alfabeto (a–z). Sua função não deve modificar a string recebida.

O CodeRunner será responsável por criar a string e chamar a função. Portanto, envie apenas a implementação de eh_palindromo_rec, sem uma função main.

Aviso

Importante: a verificação deve ser feita utilizando recursão. Não utilize laços for, while ou do while para percorrer a string.

E o caractere \0?

Como toda string em C, str termina com o caractere nulo \0. Entretanto, o índice fim não aponta para o \0: ele indica o último caractere que faz parte do trecho que deve ser analisado.

Em um programa completo

Em um programa completo, o mais natural seria escrever uma função não recursiva, por exemplo eh_palindromo, que recebe apenas a string, determina seu comprimento e então chama a função recursiva com os índices correspondentes ao primeiro e ao último caractere da string.

Neste laboratório, o objetivo é praticar diretamente a construção da função recursiva. Por isso, o CodeRunner fornecerá os valores de inicio e fim na chamada inicial.

Exercício 2 – Componente conexa em uma matriz

Considere uma matriz cujos elementos são apenas 0 e 1. Duas posições contendo 1 são consideradas vizinhas quando compartilham um lado, isto é, quando uma está imediatamente acima, abaixo, à esquerda ou à direita da outra.

Uma componente conexa é um conjunto de posições contendo 1 em que é possível ir de qualquer posição do conjunto a qualquer outra passando apenas por posições vizinhas que também contêm 1.

Por exemplo, considere a matriz abaixo:

1 1 0 0 1 0
1 0 0 1 1 0
0 0 1 0 0 0
0 1 1 1 0 1
0 0 1 0 1 1

As posições na diagonal não são consideradas vizinhas. Assim, por exemplo, o 1 da posição (2, 2) não pertence à mesma componente que o 1 da posição (1, 3).

Escreva uma função recursiva que receba uma posição (i, j) da matriz e devolva o número de elementos da componente conexa de 1s que contém essa posição.

Função a implementar

int tamanho_componente(int n_linhas, int n_colunas,
                       int mat[n_linhas][n_colunas],
                       int i, int j);

Se mat[i][j] == 0, a função deve retornar 0.

Se mat[i][j] == 1, a função deve retornar o tamanho da componente conexa que contém essa posição. Além disso, todos os elementos dessa componente devem ser substituídos por 0 na matriz. Os demais elementos da matriz devem permanecer inalterados.

Por exemplo, para a matriz acima, a chamada

tamanho_componente(5, 6, mat, 2, 2)

deve retornar:

5

Após a chamada, mat deverá conter:

1 1 0 0 1 0
1 0 0 1 1 0
0 0 0 0 0 0
0 0 0 0 0 1
0 0 0 0 1 1

Note que os 1s das posições (0, 0), (0, 1) e (1, 0), por exemplo, não pertencem à componente visitada e por isso não são alterados.

Você pode assumir que a posição inicial é válida, isto é, 0 <= i < n_linhas e 0 <= j < n_colunas. Entretanto, durante as chamadas recursivas, será necessário tomar cuidado para não acessar posições fora dos limites da matriz.

Aviso

A exploração da componente deve ser feita utilizando recursão. Não utilize laços for, while ou do while, nem estruturas auxiliares para armazenar as posições visitadas.

Dica para evitar laços infinitos

Sua função pode (e deve) modificar a matriz recebida. Pense em como usar isso para evitar que uma mesma posição seja processada mais de uma vez.

O CodeRunner será responsável por criar e preencher a matriz e chamar a função. Portanto, envie apenas a implementação de tamanho_componente e de eventuais funções auxiliares, sem uma função main.