1 / 1 / 0
Регистрация: 30.04.2019
Сообщений: 89
1

Рекурсивная функция: поиск наименьшего пути из левого верхнего угла матрицы в правый нижний

13.05.2019, 23:28. Показов 985. Ответов 1
Метки нет (Все метки)

Здравствуйте!

Осваиваю рекурсивные функции на C++

Написал классический алгоритм (динамическое программирование) для поиска наименьшего пути из левого верхнего угла в правый нижний.

Мне кажется есть ошибка в рекурсии. Прошу проверить.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
 
using namespace std;
 
int ShortestPath(vector< vector<int> > D, int i, int j)
{
 
    int cost;
    
    if (i == 0 && j == 0)
    {
        return D[i][j];
    }
 
    if (i == 0)
    {
        ShortestPath(D, i, j-1);
    }
    if (j == 0)
    {
        ShortestPath(D, i-1, j);
    }
    else
    {
        cost = D[i][j];
        cost = cost + min ( ShortestPath(D, i-1, j), ShortestPath(D, i, j-1) );
    }
 
    return cost; 
 
} 
 
int main()
{
    int n = 3;
    int m = 4;
 
    vector< vector<int> > D = { { 1, 1, 1, 1 }, {5, 2, 2, 100}, {9, 4, 2, 1} };
    int result = 0;
 
    result = ShortestPath(D, 3, 4);
 
    cout << result; 
 
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2019, 23:28
Ответы с готовыми решениями:

Сколько различных путей существует добраться из левого верхнего угла в правый нижний?
Всем привет! Недавно решал одну любопытную задачу, но к сожалению не смог решить на 100%. Вот...

Минимальное нахождение пути из верхнего левого угла в правый нижний
Помогите решить задачу на C# Windows Forms Произошло радиоактивное заражение местности....

Перемещение картинки по диагонали с верхнего левого угла в нижний правый и обратно
как сделать чтоб картинка перемещалась по диагонали с верхнего левого угла в нижний правый и...

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

1
3757 / 3075 / 853
Регистрация: 25.03.2012
Сообщений: 11,386
Записей в блоге: 1
14.05.2019, 04:38 2
Цитата Сообщение от constantin_01 Посмотреть сообщение
C++
1
2
3
ShortestPath(D, i, j-1);
 
        ShortestPath(D, i-1, j);
может всё-таки cost=ShortestPath , а не просто так ?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
14.05.2019, 04:38
Помогаю со студенческими работами здесь

Лабиринт задан двумерным массивом. Из левого верхнего угла лабиринта пройти в правый нижний
Лабиринт задан двумерным массивом. Из левого верхнего угла лабиринта пройти в правый нижний. Массив...

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

Найти кратчайший путь из левого верхнего в правый нижний элемент матрицы
Во входном файле задается число n&lt;=200, равное размерности квадратной матрицы. Матрица заполняется...

Определить, сколько существует различных маршрутов, ведущих из левого верхнего в правый нижний угол
Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный...

Изобразить шарик двигающийся из левого верхнего угла экрана в правый верхний угол
1.изобразить шарик двигающийся из левого верхнего угла экрана в правый верхний угол; 2.Изобразить...

Как в PictureBox начальные координаты с верхнего левого угла перенести на нижний левый?
Помогите пожалуйста, как это реализовать в с++ windows forms (это необходимо для задачи с шариком...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru