Counting sequence of numbers recursively in a matrix C

Question

Counting sequence of numbers recursively in a matrix C

Navigation

#1 by (1 votes)

1

So, I have the following problem:

I need to count how many descending sequences of numbers exist in an array in a recursive way, but only a sequence is considered if it is complete to the number 1. Ex: The user informs the value that he wants to start the sequence, in case 12 , the descending sequence of 12 is: 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1. Failing any digit that makes up the sequence this should be disregarded. From this I made the following algorithm (with the already initialized array):

Just to make it clear that fuzzy gets the array, the row, the column, and the number that starts the sequence. qtdseq(mat,2,6,12);

Here is the code I tried:

 #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));

}

As you can see there are 4 ways to get to number 1 in the matrix, however in my function I can only return the value 2.

Would anyone know to tell me what I'm doing wrong?

Thank you.

c matriz

asked by anonymous 06.07.2018 / 04:42

1 answer

Error when trying to backup database in postgresql Selector 'not' does not work

score 1 · Accepted Answer

First thing, this from here:

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

Can be replaced by this:

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

That is, you do not need else if the if that precedes it ends with a return . The same would apply to if terminated with break , continue , goto , exit or throw (in the case of C ++, JavaScript, Java, C # and other similar languages) / p>

Second thing, here:

int a;

// Um monte de coisa aqui.

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

You can simplify the code by deleting the a variable by doing this:

// Um monte de coisa aqui.

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

Putting these concepts together, you can simplify your code a lot:

#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));
}

Now that the code has already been simplified, it is easier to analyze it in search of the wrong things. We can see the following:

In this if(lin>=10 && col>=12) , the correct would be || and not && , after all, it suffices that one of these numbers is outside the limit, so that it would try to access the matrix in an invalid position, it is necessary that both are out.
If qtdseq does not enter any if , the execution stream reaches the end of the function without finding any return . This causes garbage to be returned.
The subexpression matriz[lin][col] <= num repeats over the last 4% with% s. The code would be simpler if this was checked only once, and if it is false, zero is already returned and it is unnecessary to test it later.
The if subexpression is suspect. Why matriz[lin][col] <= num instead of <= ? The idea is to check whether == is the right number, and therefore should be matriz[lin][col] .
Your == is also suspect. Why if(num < 1) and not < ? If there were zero or negative numbers in the array, that would make things go wrong. As the idea is to find 1, then the ideal would be to return 1 if at position == there is number 1.

With these considerations, your code looks like this:

#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));
}

There are even more things wrong:

Let's suppose that matriz[lin][col] is 0. When evaluating col , the column accessed will be -1. This is not going to do what you want. So in the% s of% s that check the adjacent positions of the array, you need to check the boundaries as well. It would also be good to matriz[lin][col - 1] from the start of the function check negative numbers.
However, if the% s from the beginning of the function check all boundaries of the array, and also if the position contains the number is expected, that means you do not need to check them on if s of recursive calls. It would be enough to check whether or not the recursive callback was zero.
However, you are looking for multiple paths. In the first%% of the function to collide, it will interrupt the search without checking for other possible paths. The solution then is to check all recursive calls to count how many results each finds and the total result is the sum of the four.

Considering this, your code looks like this:

#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));
}

The output produced is this:

Quantidade de sequências encontradas = 4

See here working on ideone.