Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
CarpeJ
0 / 0 / 0
Регистрация: 04.07.2012
Сообщений: 4
#1

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

26.08.2012, 22:32. Просмотров 746. Ответов 1
Метки нет (Все метки)

Помогите составить алгоритм реализации такой программы. Например, есть массив:
1 2 5 7 9
4 6 8 2 1
3 9 7 5 2

Cчитаем сумму для 3: [2][0] + [1][0] т.е 3+4 и записываем в массив 2.
Потом [2][0] + [2][1] т.е 3+9 и тоже записываем в массив 2.
То же проделываем для 4 и 9, 1 и 6 и 7 ну и т.д. Но это очень приблизительно. А составить нормальный алгоритм не получается.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.08.2012, 22:32     Перейти из левого нижнего в правый верхний угол массива, двигаясь вверх либо вбок, суммируя элементы через которые идем. Сумма должна быть минимальной
Посмотрите здесь:

Найти след матрицы, суммируя элементы одномерного массива C++
C++ Вывести те элементы в наборе, которые меньше своего левого соседа
Путем перестановок строк и столбцов (целиком) элемент надо переместить в правый верхний угол подмассива (Перевести программу в c++) C++
C++ Символы из нижнего регистра перевести в верхний
C++ Путем перестановок строк и столбцов элемент переместить в правый верхний угол подмассива (С Turbo Pascal на C++)
C++ как перевести букву из нижнего регистра в верхний C++
C++ Буква из нижнего регистра в верхний
C++ Заполнить матрицу ЛП, от левого нижнего угла по диагонали: влево - вверх.
Заполнение матрицы с левого нижнего угла по диагонали (исправить программу) C++
Движение по шахматной доске коня (с левого нижнего угла в верхний правый угол) C++
Переместить самый максимальный элемент массива в левый верхний угол C++
Заполнить матрицу от левого нижнего угла по диагонали: влево - вверх C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
softmob
1248 / 698 / 155
Регистрация: 20.02.2010
Сообщений: 1,035
26.08.2012, 23:33     Перейти из левого нижнего в правый верхний угол массива, двигаясь вверх либо вбок, суммируя элементы через которые идем. Сумма должна быть минимальной #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <iomanip>
 
const int n = 3, m = 5;
int cost[n][m] = 
{{1, 2, 5, 7, 9},
{4, 6, 8, 2, 1},
{3, 9, 7, 5, 2}}, res[n][m];
 
int main(void)
{
    for (int i = n-1; i >= 0; --i)
    {
        for (int j = 0; j < m; ++j)
            if (i == n-1 && j == 0) 
                res[i][j] = cost[i][j];
            else if (i == n-1)
                res[i][j] = res[i][j-1] + cost[i][j]; 
            else if (j == 0)
                res[i][j] = res[i+1][j] + cost[i][j]; 
            else
                res[i][j] = std::min(res[i+1][j], res[i][j-1]) + cost[i][j]; 
    }
    for (int i = 0; i != n; ++i)
    {
        for (int j = 0; j != m; ++j)
            std::cout << std::setw(2) << res[i][j] << ' ';
        std::cout << std::endl;
    }
    return 0;
}
Добавлено через 12 минут
Цитата Сообщение от CarpeJ Посмотреть сообщение
Помогите составить алгоритм
динамикой res[i][j] = min(res[i+1][j], res[i][j-1]) + cost[i][j]
Yandex
Объявления
26.08.2012, 23:33     Перейти из левого нижнего в правый верхний угол массива, двигаясь вверх либо вбок, суммируя элементы через которые идем. Сумма должна быть минимальной
Ответ Создать тему
Опции темы

Текущее время: 17:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru