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

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

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

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

26.08.2012, 22:32. Просмотров 759. Ответов 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++
Шахматная фигура «конь» перемещается на 1 клетку по горизонтали и на 2 клетки по вертикали или на 2 клетки по горизонтали и 1 - по...

Заполнить матрицу ЛП, от левого нижнего угла по диагонали: влево - вверх. - C++
Здравствуйте, уважаемые форумчане. Очень нужна ваша помощь: перевести код из С в С++. Сам пытался но ничего путного не вышло. Очень буду...

Заполнить матрицу ЛП, от левого нижнего угла по диагонали: влево - вверх - C++
Здравствуйте! Помогите с кодом. Заполнить матрицу ЛП, от левого нижнего угла по диагонали: влево - вверх.

Заполнить матрицу от левого нижнего угла по диагонали: влево - вверх - C++
Заполнить матрицу А(9,9), от левого нижнего угла по диагонали: влево - вверх. Помогите пожалуйста

Путем перестановок строк и столбцов элемент переместить в правый верхний угол подмассива (С Turbo Pascal на C++) - C++
Можете программу преобразовать в C++?? Задан двумерный массив N x N. Последовательно рассматриваются квадратные подмассивы, правый...

Путем перестановок строк и столбцов (целиком) элемент надо переместить в правый верхний угол подмассива (Перевести программу в c++) - C++
program zadanie_5; uses crt; const nn=5; var i, j, imax, jmax, n, k, m: integer; a: array of real; r: real;...

Найти след матрицы, суммируя элементы одномерного массива - C++
Для заданной квадратной матрицы сформировать одномерный массив из её диагональных элементов. Найти след матрицы, суммируя элементы...

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

Вывести те элементы в наборе, которые меньше своего левого соседа - C++
Дано целое число N (> 1) и набор из N целых чисел. Вывести те эле- менты в наборе, которые меньше своего левого соседа, и количество K...

Буква из нижнего регистра в верхний - 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]
Ответ Создать тему
Опции темы

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