Поиск максимальной суммы в пирамиде чисел сверху вниз

Question

Не выходит решить задачу.

Условие задачи:

Дано: натуральное число n, треугольная пирамида высотой n из неотрицательных чисел (исходные данные записаны в файле). Вычислить наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке пирамиды и заканчивающемся на её основании. Каждый шаг на пути может идти вниз по диагонали влево или вниз по диагонали вправо. Определить путь, на котором может быть достигнута максимальная сумма. Число строк в пирамиде больше 1 и не больше 100 ( 1 ≤ ? ≤ 100)

С нахождением суммы проблем нет, но вот не могу сообразить как вывести элементы этой самой суммы.

Мой код:

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    int n;
    ifstream In;
    In.open("Input.txt");
    In >> n;
    int k = 0;
    int** Pyr = new int* [n];
    for (int i = 0; i < n; i++)
    {
        Pyr[i] = new int[n];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            In >> Pyr[i][j];
        }
    }

    for (int i = n - 1; i > 0; i--)
    {
        for (int j = 0; j < i + 1; j++)
        {
            Pyr[i - 1][j] += max(Pyr[i][j], Pyr[i][j + 1]);

        }
    }

    cout << Pyr[0][0] << endl;

    for (int i = 0; i < n; i++)
    {
        delete Pyr[i];
    }
    delete[] Pyr;

    In.close();
}

Answer 1

Создаём дополнительную матрицу путей, запоминаем оригинальные числа. Записываем выбор максимального. И печатаем путь. В конце программы вы неправильно удаляете массив.

// g++ -Wall -Wextra -Wpedantic -Winline -std=c++17 -Os path.cpp -o path
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    int n;
    ifstream In;
    In.open("Input.txt");
    In >> n;

    // запоминаем путь и копии элементов
    int** Pyr = new int* [n];
    int** Put = new int* [n];
    int** Ele = new int* [n];
    for (int i = 0; i < n; i++)
    {
        Pyr[i] = new int[n];
        Put[i] = new int[n];
        Ele[i] = new int[n];
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i + 1; j++)
        {
            In >> Pyr[i][j];
            
            // сохраняем копии
            Ele[i][j] = Pyr[i][j];
        }
    }

    for (int i = n - 1; i > 0; i--)
    {
        for (int j = 0; j < i + 1; j++)
        {
          
          // запоминаем выбор
          if(Pyr[i][j]> Pyr[i][j + 1]) {
            Pyr[i - 1][j] += Pyr[i][j] ;
            Put[i - 1][j] = j ; } 
          else {
            Pyr[i - 1][j] += Pyr[i][j + 1] ;
            Put[i - 1][j] = j + 1 ; }
          //Pyr[i - 1][j] += max(Pyr[i][j], Pyr[i][j + 1]);

        }
    }

    // печатаем весь путь
    int x = 0 , y = 0 ;
    for(int i = 0 ;i<n-1;++i) {
      cout << Ele[x][y] << endl;
      y = Put[x][y];
      ++ x;
      cout <<"x="<<x<<endl;      
      cout <<"y="<<x<<endl; }
    cout << Ele[x][y] << endl;

    for (int i = 0; i < n; i++)
    {
    
        // !! удалять нужно массив, а не элемент
        delete [] Pyr[i];
        delete [] Put[i];
        delete [] Ele[i];
    }
    delete[] Pyr;
    delete[] Put;
    delete[] Ele;

    In.close();
}

БЛОГ НА HUSL

Поиск максимальной суммы в пирамиде чисел сверху вниз

Ответы (1 шт):