There is such a pyramid of numbers. enter image description here

It is necessary to find all possible ways on which the sum of the numbers will be 35.45 and 55.

#define SIZE 7 int matrix [SIZE][SIZE]={ {5}, {8,7}, {9,4,4}, {6,7,5,3}, {4,8,3,7,5}, {3,9,4,9,3,8}, {5,7,9,2,4,9,3}}; void search_path(int matrix [SIZE][SIZE], int sum){ int current_sum=0,current_i=0,current_j=0, way[7]; int i,j,k=1,d; for(d=0;d<SIZE;d++){ for(i=0;i<SIZE;i++){ for(j=0;j<k;j++){ current_sum += matrix[current_i][current_j]; way[i] = matrix[current_i][current_j]; if(current_sum>sum){break;} ++current_i; ++current_j; } k++; } if(current_sum == sum && current_i == (SIZE-1) && current_j == (SIZE-1)){ print_way(way); current_i=current_j=current_sum=0; } } }

I want to go through all the possible options, but somewhere the wrong algorithm did.

    1 answer 1

    If you really want to go to any digit of the next level - then

     #include <stdlib.h> #include <stdio.h> #include <string.h> #define SIZE 7 int m[SIZE][SIZE]={ {5}, {8,7}, {9,4,4}, {6,7,5,3}, {4,8,3,7,5}, {3,9,4,9,3,8}, {5,7,9,2,4,9,3} }; int main(int argc, const char * argv[]) { for(int i1 = 0; i1 < 2; ++i1) for(int i2 = 0; i2 < 3; ++i2) for(int i3 = 0; i3 < 4; ++i3) for(int i4 = 0; i4 < 5; ++i4) for(int i5 = 0; i5 < 6; ++i5) for(int i6 = 0; i6 < 7; ++i6) { int sum = m[0][0] + m[1][i1] + m[2][i2] + m[3][i3] + m[4][i4] + m[5][i5] + m[6][i6]; if (sum == 35 || sum == 45 || sum == 55) { printf("%d = %d + %d + %d + %d + %d + %d + %d\n", sum,m[0][0],m[1][i1],m[2][i2],m[3][i3],m[4][i4],m[5][i5],m[6][i6]); } } }

    A total of 496 solutions.

    Are you sure you can move to any digit in the next row?

    • Yes, at the expense of transition sure. - Hardc0re
    • Then here is a brute force solution ... Not indicated on the way. for example, the first or second four is selected at the third level, but you will add it yourself without any problems ... - Harry
    • complexity as I understand it will be O (n ^ n-1)? - Hardc0re
    • n! paths, if we count one summation O(1) , then n*n! . - Harry