1

Есть вот такая пирамида чисел. введите сюда описание изображения

Нужно найти все возможные пути на которых сумма чисел буде 35,45 и 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;
            }

    }
}

Я хочу перебрать все возможные варианты, но где-то неверно сделал алгоритм.

1 ответ 1

5

Если вы реально хотите переходить к любой цифре следующего уровня - то

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

}

Всего 496 решений.

Вы уверены, что можно переходить к любой цифре следующего ряда?

4
  • да, на счет перехода уверен.
    – Hardc0re
    24 дек 2016 в 20:20
  • Тогда вот вам решение полным перебором... В пути не указывается. например, первая или вторая четверка выбрана на третьем уровне, но это вы уже сами допишете без проблем...
    – Harry
    24 дек 2016 в 20:22
  • сложность как я понмаю будет О(n^n-1) ?
    – Hardc0re
    25 дек 2016 в 6:15
  • n! путей, если считать одно суммирование O(1), то n*n!.
    – Harry
    25 дек 2016 в 7:12

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.