1

Então, estou com o seguinte problema:

Preciso contar quantas sequências decrescentes de números existem em uma matriz de maneira recursiva, porém só é considerada uma sequencia se esta for completa até o número 1. Ex: O usuário informa o valor que ele deseja iniciar a sequência, no caso 12, a sequência decrescente de 12 é: 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Caso falte qualquer digito que compõe a sequência esta deve ser desconsiderada. A partir disso fiz o seguinte algoritmo (com a matriz já inicializada):

Só pra deixar claro que afunção recebe a matriz, a linha, a coluna e o número que inicia a sequência. qtdseq(mat,2,6,12);

Esse é o código que tentei:

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

int qtdseq( int matriz[10][12], int lin, int col, int num){

    int conta ;

if(lin>=10 && col>=12){
    return 0;
}
else if(num < 1) {
    return 1;
}
else if(matriz[lin][col] <= num && matriz[lin][col+1] == num-1){
    conta = qtdseq(matriz, lin, col+1, num-1);
    return conta;
}
else if(matriz[lin][col] <= num && matriz[lin][col-1] == num-1){
    conta = qtdseq(matriz, lin, col-1, num-1);
    return conta;
}
else if(matriz[lin][col] <= num && matriz[lin+1][col] == num-1){
    conta = qtdseq(matriz, lin+1, col, num-1);
    return conta;
}
else if(matriz[lin][col] <= num && matriz[lin-1][col] == num-1){
    conta = qtdseq(matriz, lin-1, col, num-1);
    return conta;
    }

}

    int main() {
  int mat[10][12]={{34,45,18,56,98,33,42,67, 6,11,40,10},
                   {88,59,23,34,44,11,34,61,43, 1, 3, 9},
                   {33,32,31,22,33,77,12,11,34,98,72,74},
                   {40,50,21,17,15,52,45,10, 9,32,27,30},
                   { 4,14,32,11,22,33,44,65, 8,52,76,12},
                   { 6,13,56,91,22,45,22,18, 7,45,23,44},
                   { 8, 9,20,87, 2, 5,56, 5, 6 , 5, 4,3},
                   {12,99,23, 4, 3,81,42, 4, 8, 4,77, 2},
                   {98,97,96,95,38, 1, 2, 3,56, 3,56, 1},
                   { 3, 1, 7,45,93,96, 1,46, 1, 2,41,23}};

    printf("Quantidade de Sequencias Encontradas = %d\n", qtdseq(mat,2,6,12));

}

Como se pode perceber existe 4 maneiras de se chegar ao número 1 na matriz, entretanto na minha função só consigo retornar o valor 2.

Alguém saberia me dizer o que estou fazendo de errado?

Obrigado.

3
  • As sequências tem que ser procuradas nas linhas da matriz? Ou também podem ser nas colunas? E nas diagonais? Podem aparecer de trás-para-frente? Commented 6/07/2018 às 4:01
  • Ah, é procurando um caminho qualquer. Pode ser para a direita, para a esquerda, para cima ou para baixo (mas não nas diagonais). E o caminho não precisa ser em uma única direção, ele pode ter váarias esquinas e ser bem tortuoso. Commented 6/07/2018 às 6:16
  • Pergunta duplicata: pt.stackoverflow.com/q/312395/132 - Mas como a outra pergunta está fechada e não tem respostas, convém deixar esta daqui aberta e talvez indicar a outra como duplicata desta. Commented 6/07/2018 às 7:05

1 Resposta 1

1

Primeira coisa, isso daqui:

if (a) {
    b;
    return c;
} else if (d) {

Pode ser substituído por isso:

if (a) {
    b;
    return c;
}
if (d) {

Ou seja, não precisa do else se o if que o precede termina com um return. O mesmo se aplicaria no caso de um if terminado com break, continue, goto, exit ou throw (no caso de C++, JavaScript, Java, C# e outras linguagens parecidas).

Segunda coisa, nisso daqui:

int a;

// Um monte de coisa aqui.

if (b) {
    // Um monte de coisas c
    a = d;
    return a;
}

É possível simplificar o código eliminando a variável a ao fazer isso:

// Um monte de coisa aqui.

if (b) {
    // Um monte de coisas c
    return d;
}

Juntando esses conceitos, dá para simplificar bastante o seu código:

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

int qtdseq(int matriz[10][12], int lin, int col, int num) {
    if (lin >= 10 && col >= 12) return 0;

    if (num < 1) return 1;

    if (matriz[lin][col] <= num && matriz[lin][col + 1] == num - 1) {
        return qtdseq(matriz, lin, col + 1, num - 1);
    }

    if (matriz[lin][col] <= num && matriz[lin][col - 1] == num - 1) {
        return qtdseq(matriz, lin, col - 1, num - 1);
    }

    if (matriz[lin][col] <= num && matriz[lin + 1][col] == num - 1) {
        return qtdseq(matriz, lin + 1, col, num - 1);
    }

    if (matriz[lin][col] <= num && matriz[lin - 1][col] == num - 1) {
        return qtdseq(matriz, lin - 1, col, num - 1);
    }
}

int main() {
    int mat[10][12] = {
        {34, 45, 18, 56, 98, 33, 42, 67,  6, 11, 40, 10},
        {88, 59, 23, 34, 44, 11, 34, 61, 43,  1,  3,  9},
        {33, 32, 31, 22, 33, 77, 12, 11, 34, 98, 72, 74},
        {40, 50, 21, 17, 15, 52, 45, 10,  9, 32, 27, 30},
        { 4, 14, 32, 11, 22, 33, 44, 65,  8, 52, 76, 12},
        { 6, 13, 56, 91, 22, 45, 22, 18,  7, 45, 23, 44},
        { 8,  9, 20, 87,  2,  5, 56,  5,  6,  5,  4,  3},
        {12, 99, 23,  4,  3, 81, 42,  4,  8,  4, 77,  2},
        {98, 97, 96, 95, 38,  1,  2,  3, 56,  3, 56,  1},
        { 3,  1,  7, 45, 93, 96,  1, 46,  1,  2, 41, 23}
    };

    printf("Quantidade de Sequencias Encontradas = %d\n", qtdseq(mat, 2, 6, 12));
}

Agora, que o código já foi simplificado, fica mais fácil analisá-lo a procura de coisas erradas. Podemos ver o seguinte:

  • Nesse if(lin>=10 && col>=12), o correto seria || e não &&, afinal, basta que um desses números esteja fora do limite que então tentar-se-ia acessar a matriz em uma posição inválida, não é necessário que ambos estejam fora.

  • Se o qtdseq não entrar em nenhum if, o fluxo de execução chega ao final da função sem encontrar nenhum return. Isso faz com que lixo seja retornado.

  • A subexpressão matriz[lin][col] <= num se repete nos últimos 4 ifs. O código ficaria mais simples se isso fosse verificado apenas uma vez, e se for falso, já se retorna zero sendo desnecessário testar-se isso posteriormente.

  • A subexpressão matriz[lin][col] <= num é suspeita. Por que <= ao invés de ==? A ideia é verificar se na posição matriz[lin][col] há o número certo, e portanto deveria ser ==.

  • O seu if(num < 1) também é suspeito. Por que < e não ==? Se houvesse zero ou números negativos na matriz, isso faria com que as coisas dessem errado. Como a ideia é encontrar o 1, então o ideal seria retornar 1 se na posição matriz[lin][col] houver o número 1.

Com essas considerações, o seu código fica assim:

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

int qtdseq(int matriz[10][12], int lin, int col, int num) {
    if (lin >= 10 || col >= 12) return 0;
    if (matriz[lin][col] != num) return 0;
    if (num == 1) return 1;
    if (matriz[lin][col + 1] == num - 1) return qtdseq(matriz, lin, col + 1, num - 1);
    if (matriz[lin][col - 1] == num - 1) return qtdseq(matriz, lin, col - 1, num - 1);
    if (matriz[lin + 1][col] == num - 1) return qtdseq(matriz, lin + 1, col, num - 1);
    if (matriz[lin - 1][col] == num - 1) return qtdseq(matriz, lin - 1, col, num - 1);
    return 0;
}

int main() {
    int mat[10][12] = {
        {34, 45, 18, 56, 98, 33, 42, 67,  6, 11, 40, 10},
        {88, 59, 23, 34, 44, 11, 34, 61, 43,  1,  3,  9},
        {33, 32, 31, 22, 33, 77, 12, 11, 34, 98, 72, 74},
        {40, 50, 21, 17, 15, 52, 45, 10,  9, 32, 27, 30},
        { 4, 14, 32, 11, 22, 33, 44, 65,  8, 52, 76, 12},
        { 6, 13, 56, 91, 22, 45, 22, 18,  7, 45, 23, 44},
        { 8,  9, 20, 87,  2,  5, 56,  5,  6,  5,  4,  3},
        {12, 99, 23,  4,  3, 81, 42,  4,  8,  4, 77,  2},
        {98, 97, 96, 95, 38,  1,  2,  3, 56,  3, 56,  1},
        { 3,  1,  7, 45, 93, 96,  1, 46,  1,  2, 41, 23}
    };

    printf("Quantidade de Sequencias Encontradas = %d\n", qtdseq(mat, 2, 6, 12));
}

Há ainda mais coisas erradas:

  • Vamos supor que col seja 0. Ao avaliar-se o matriz[lin][col - 1], a coluna acessada vai ser a -1. Isso não vai fazer o que você quer. Logo, nos ifs que verificam as posições adjacentes da matriz, você precisa verificar os limites também. Também seria bom o if do começo da função verificar números negativos.

  • Entretanto, se os ifs do começo da função verificarem todos os limites da matriz e também se a posição contém o número é o esperado, isso significa que você não precisa verificá-los nos ifs das chamadas recursivas. Bastaria verificar se o retorno da chamada recursiva foi ou não zero.

  • No entanto, você está buscando por diversos caminhos. No primeiro return que a função esbarrar ela já vai interromper a busca sem verificar se há outros caminhos possíveis. A solução então é verificar todas as chamadas recursivas para contar quantos resultados cada uma encontra e o resultado total é a soma das quatro.

Considerando-se isso, o seu código fica assim:

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

int qtdseq(int matriz[10][12], int lin, int col, int num) {
    if (lin >= 10 || col >= 12 || lin < 0 || col < 0) return 0;
    if (matriz[lin][col] != num) return 0;
    if (num == 1) return 1;

    return qtdseq(matriz, lin,     col + 1, num - 1)
         + qtdseq(matriz, lin,     col - 1, num - 1)
         + qtdseq(matriz, lin + 1, col,     num - 1)
         + qtdseq(matriz, lin - 1, col,     num - 1);
}

int main() {
    int mat[10][12] = {
        {34, 45, 18, 56, 98, 33, 42, 67,  6, 11, 40, 10},
        {88, 59, 23, 34, 44, 11, 34, 61, 43,  1,  3,  9},
        {33, 32, 31, 22, 33, 77, 12, 11, 34, 98, 72, 74},
        {40, 50, 21, 17, 15, 52, 45, 10,  9, 32, 27, 30},
        { 4, 14, 32, 11, 22, 33, 44, 65,  8, 52, 76, 12},
        { 6, 13, 56, 91, 22, 45, 22, 18,  7, 45, 23, 44},
        { 8,  9, 20, 87,  2,  5, 56,  5,  6,  5,  4,  3},
        {12, 99, 23,  4,  3, 81, 42,  4,  8,  4, 77,  2},
        {98, 97, 96, 95, 38,  1,  2,  3, 56,  3, 56,  1},
        { 3,  1,  7, 45, 93, 96,  1, 46,  1,  2, 41, 23}
    };

    printf("Quantidade de sequências encontradas = %d\n", qtdseq(mat, 2, 6, 12));
}

A saída produzida é essa:

Quantidade de sequências encontradas = 4

Veja aqui funcionando no ideone.

2
  • Primeiramente Victor, muito obrigado, além de resolver meu problema você me deu uma aula. Só gostaria de saber se entendi direito, a condição ' if (num == 1) return 1; ' é a que conta a sequência de maneira única então? No caso você chama as 4 funções e elas param quando encontram o número '1' indicando que foi uma sequência completa. Correto? Mais uma vez, muito obrigado pela aula =) Commented 6/07/2018 às 13:40
  • @Lóiz Sim, é isso mesmo. Commented 6/07/2018 às 13:48

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .