Маршрут

@Mayonez · Регистрация: 26.12.2009

Студворк — интернет-сервис помощи студентам

массив 10х10 заполнено числами. Начало маршрута в левом нижнем углу. Конец - в правом верхем. Можна двигаться только прямо или вправо. Найти такой маршрут, чтобы сума чисел в ячейках была максимальной.

@Mayonez · 24.10.2010, 15:53 **[ТС]**

нужно вывести маршрут в формате :RFFRFFRRRRRRRFFFFF
R - шаг вправо
F - шаг вперед

KuKu · 24.10.2010, 16:15

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
i=0;
j=9;
   while((i<9)||(j>0)
   {
    if ((i<9)&&(j>0))
     {
      if ((m[i+1][j]>m[i][j-1]))
      {
         cout << "R";
         i++;
      }
      else
      {
         cout << "F";
         j--;   
      }
     }
   else
   {
     if (i>9) 
     {
         cout << "F";
         j--;
     } 
     else
     {
         cout << "R";
         i++;
     }
   }
   }

на универсальность явно не претендует, но судя по всему больше и не надо.

valeriikozlov · 24.10.2010, 16:21

KuKu, Ничего подобного. Вот Вам контрпример: вся матрица заполнена 1. Левый край и верхний край заполнен 2. А в нижнем правом углу значение 1000000. Ваш алгоритм не найдет нужного ответа.

Mayonez, С динамическим программированием знакомы?

KuKu · 24.10.2010, 16:27

valeriikozlov, Вродь написал, что он не универсальный. У мя такое чувство, глядя на саму матрицу, что там не надо искать путь к выходу специально как и максимальную сумму, а это уже заложено в матрице.

@Mayonez · 24.10.2010, 18:23 **[ТС]**

Сообщение от valeriikozlov

Mayonez, С динамическим программированием знакомы?

если надо - познакомлюсь

Добавлено через 59 минут
Можно что-то поконкретнее...

silent_1991 · 24.10.2010, 18:50

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

@ForEveR · 24.10.2010, 19:07

silent_1991, Ага. Это Дейкстры или Флойда-Уоршалла который кажется? Вроде как оба подойдут

silent_1991 · 24.10.2010, 19:14

Флойда - он находит пути между всеми вершинами... А Дейкстра ищет между одной и всеми остальными. А тут другой немного нужен, который путь между парой ищет (у него незапоминающиеся фамилии))) )

Добавлено через 1 минуту
Хотя конечно можно любой использовать, потом просто выбрать нужный путь и всё. Но тогда куча ненужных расчётов.

valeriikozlov · 24.10.2010, 23:21

Mayonez, В общем эту задачу можно сделать так:
В один массив считываем данные (такие как у Вас на картинке). Создаем второй массив таким же размером. В этом массиве (после того как мы его заполним) в каждой ячейке будет хранится максимальное значение, которое можно для этой ячейки достигнуть, двигаясь только прямо или вправо с нижнего левого угла.
Теперь порядок заполнения значениями этого массива. Вариантов заполнения несколько (но результат всегда одинаковый), я приведу такой.
Сначало заполняем левую сторону вот так (идем снизу вверх):
- самая нижняя ячейка будет равна 15 (я беру данные сейчас для приведенного массива) - а в общем случае самая нижняя ячейка всегда будет равна значению левой нижней ячейки массива со входными данными.
- следующая (левая вторая снизу) будет равна 18 (сумме нижней на одну ступень ячейки второго массива и соответствующей ячейки первого массива) - тут уж не поспоришь (если двигаться можно только вверх и направо, то для данной ячейки самое большое значение может быть только 18)
- следующая (левая третья снизу) - по такой же аналогии (сумма нижней на одну ступень ячейки второго массива и соответствующей ячейки первого массива) - 23
- и т.д. до самого верха самого левого ряда.

Добавлено через 8 минут
Теперь второй слева столбец (и все остальные за ним) заполняются так (начинаем опять снизу):
- самый нижний элемент всегда будет равен сумме предудущего слева элемента во втором массиве и соответствующего элемента в первом массиве (т.е. для второго столбца самый нижний элемент будет равен - 22) тут тоже не поспоришь, ведь путь в эту клетку только один.
- все последующие элементы выбираются так: сравниваем во два элемента во втором массиве (слева от текущего элемента и снизу от текущего элемента), который элемент из этих больше, его значение суммируем с текущим элементом из первого массива и получаем значение текущего элемента во втором массиве. Таким образом мы определяем масимальное значение для каждой клетки которое можно набрать двигаясь только прямо или вправо с нижнего левого угла.

Добавлено через 11 минут
Таким образом мы заполним весь второй массив. В врехнем правом углу получится максимальное значение, которое можно набрать.
Теперь о пути. Путь можно вычислить, после заполнения второго массива, двигаясь обратно. Для этого создаем массив, в котором будем хранить сам путь (хотите типа char сразу, хотите типа int - это все непринципиально). Размер массива всегда будет равен n+(n-2) - не количество пройденных клеток, а количество перемещений между ними.
Итак начинаем с верхнего правого элемента второго массива - будем называть рассматриваемый элемент массива текущим. Если от значения текущего элемента второго массива отнять значение текущего элемента первого массива и получится значение левого от текущего элемента второго массива, то записываем в массив пути F и делаем текущим элемент слева от текущего. Если полученное значение равно значению нижнего от текущего элемента второго массива, то записываем в массив пути R и делаем текущим элемент снизу от текущего. И так до конца (до того момента пока текущим не станет самый ниэний левый элемент).
Вывод результата производить с конца массива пути.

@Mayonez · 25.10.2010, 21:43 **[ТС]**

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;
 
int main()
{
   ifstream fin("input.txt");
   ofstream fout("output.txt");
   vector <char> wayNow;
   vector <char> wayAns;
   int matrix[100][100];
   bool visited[100][100];
   for (int i = 0; i < 100; i++)
      for (int j = 0; j < 100; j++)
            visited[i][j] = 0;
 
   int max = 0;
   int m, n;
   
   fin >> m >> n;
   //
   for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
            fin >> matrix[i][j];
   //
   queue <pair <pair <vector <char>, int>, pair<int, int> > > way;
   way.push(make_pair(make_pair(wayNow, matrix[m-1][0]), make_pair(m-1, 0)));
   while (!way.empty())
   {
      pair <int, int> now = way.front().second;
      wayNow = way.front().first.first;
      int how = way.front().first.second;
      vector <char> temp = way.front().first.first;
      way.pop();
      //
      if (now.first-1 >= 0 && visited[now.first-1][now.second] == 0)
      {
            temp.push_back('F');
            way.push(make_pair(make_pair(temp, how+matrix[now.first-1][now.second]), 
                        make_pair(now.first-1, now.second)));
            temp.pop_back();
      }
      //
      if (now.second+1 <= n && visited[now.first][now.second+1] == 0)
      {
            temp.push_back('R');
            way.push(make_pair(make_pair(temp, how+matrix[now.first][now.second+1]), 
                        make_pair(now.first, now.second+1)));
            temp.pop_back();
      }
      
      if (way.front().first.second > max) 
      {
            max = way.front().first.second;
            wayAns = way.front().first.first;
      }      
      
   }
   for (int i = 0; i < wayAns.size(); i++)
      fout << wayAns[i];   
   return 0;
}

получилось что-то такое
для таблиц до 100х100
вроде работает
а где тут динамическое программирование?

valeriikozlov · 25.10.2010, 21:55

Mayonez, что выдает Ваша программа на приведенные Вами значения в массиве? А потом подайте на вход те же значения массива только исправьте правое нижнее значение на 100000 и напишите что получилось?

KuKu · 25.10.2010, 22:04

valeriikozlov, вы конечно правы. Но одно дело сделать так, чтобы работало всегда, а другое что бы работало как требуется. От него не требуют большего. Так тут в каждом втором задании на форуме можно найти недочеты.

valeriikozlov · 25.10.2010, 22:13

Сообщение от KuKu

тут в каждом втором задании на форуме можно найти недочеты.

абсолютно согласен.

Сообщение от KuKu

Но одно дело сделать так, чтобы работало всегда, а другое что бы работало как требуется.

тоже абсолютно согласен.

Сообщение от KuKu

вы конечно правы.

тоже согласен. (шучу конечно)

я тоже бывает ошибаюсь, ведь я тоже человек.

Просто я практически только вернулся с другого сайта, где даже малейшим ошибкам не было места, или все правильно или не зачет. Наверное это сказывается, Вы тоже в чем-то правы!

@Mayonez · 25.10.2010, 22:19 **[ТС]**

Сообщение от valeriikozlov

А потом подайте на вход те же значения массива только исправьте правое нижнее значение на 100000 и напишите что получилось?

масив типа инт максимальное значение 32767 что меньше 100000

KuKu · 25.10.2010, 22:24

Сообщение от Mayonez

масив типа инт, максимальное значение 32767, что меньше 100000

это для short int.

valeriikozlov · 25.10.2010, 22:25

Что же у Вас за компилятор, который запросто переваривает stl, а в переменной типа int не выносит значений более 32767? Ну тогда запишите туда значение не 100000 а 10000.

@Mayonez · 25.10.2010, 22:28 **[ТС]**

Сообщение от valeriikozlov

и напишите что получилось?

RRRRRRRRRFFFFFFFFF как не странно??

Добавлено через 1 минуту

Сообщение от KuKu

это для short int.

да, ошибся

valeriikozlov · 25.10.2010, 22:33

это и называется динамическим програмированием.

Добавлено через 1 минуту
Если хотите разобраться в нем побольше, Вам нужно что-нибудь почитать об этом.

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874

	Маршрут 24.10.2010, 15:38. Показов 4036. Ответов 18 Метки нет (Все метки) массив 10х10 заполнено числами. Начало маршрута в левом нижнем углу. Конец - в правом верхем. Можна двигаться только прямо или вправо. Найти такой маршрут, чтобы сума чисел в ячейках была максимальной. Миниатюры 0

@Mayonez 392 / 284 / 53 Регистрация: 26.12.2009 Сообщений: 874
	24.10.2010, 15:53 [ТС]
	нужно вывести маршрут в формате :RFFRFFRRRRRRRFFFFF R - шаг вправо F - шаг вперед 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	24.10.2010, 16:21
	KuKu, Ничего подобного. Вот Вам контрпример: вся матрица заполнена 1. Левый край и верхний край заполнен 2. А в нижнем правом углу значение 1000000. Ваш алгоритм не найдет нужного ответа. Mayonez, С динамическим программированием знакомы? 0

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	24.10.2010, 16:27
	valeriikozlov, Вродь написал, что он не универсальный. У мя такое чувство, глядя на саму матрицу, что там не надо искать путь к выходу специально как и максимальную сумму, а это уже заложено в матрице. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	24.10.2010, 18:50
	Уже была недавно подобная тема, я там посоветовал обратить внимание на алгоритм поиска кратчайшего пути между парой вершин во взвешенно орграфе. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	24.10.2010, 19:07
	silent_1991, Ага. Это Дейкстры или Флойда-Уоршалла который кажется? Вроде как оба подойдут 1

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	24.10.2010, 19:14
	Флойда - он находит пути между всеми вершинами... А Дейкстра ищет между одной и всеми остальными. А тут другой немного нужен, который путь между парой ищет (у него незапоминающиеся фамилии))) ) Добавлено через 1 минуту Хотя конечно можно любой использовать, потом просто выбрать нужный путь и всё. Но тогда куча ненужных расчётов. 1

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	24.10.2010, 23:21
	Mayonez, В общем эту задачу можно сделать так: В один массив считываем данные (такие как у Вас на картинке). Создаем второй массив таким же размером. В этом массиве (после того как мы его заполним) в каждой ячейке будет хранится максимальное значение, которое можно для этой ячейки достигнуть, двигаясь только прямо или вправо с нижнего левого угла. Теперь порядок заполнения значениями этого массива. Вариантов заполнения несколько (но результат всегда одинаковый), я приведу такой. Сначало заполняем левую сторону вот так (идем снизу вверх): - самая нижняя ячейка будет равна 15 (я беру данные сейчас для приведенного массива) - а в общем случае самая нижняя ячейка всегда будет равна значению левой нижней ячейки массива со входными данными. - следующая (левая вторая снизу) будет равна 18 (сумме нижней на одну ступень ячейки второго массива и соответствующей ячейки первого массива) - тут уж не поспоришь (если двигаться можно только вверх и направо, то для данной ячейки самое большое значение может быть только 18) - следующая (левая третья снизу) - по такой же аналогии (сумма нижней на одну ступень ячейки второго массива и соответствующей ячейки первого массива) - 23 - и т.д. до самого верха самого левого ряда. Добавлено через 8 минут Теперь второй слева столбец (и все остальные за ним) заполняются так (начинаем опять снизу): - самый нижний элемент всегда будет равен сумме предудущего слева элемента во втором массиве и соответствующего элемента в первом массиве (т.е. для второго столбца самый нижний элемент будет равен - 22) тут тоже не поспоришь, ведь путь в эту клетку только один. - все последующие элементы выбираются так: сравниваем во два элемента во втором массиве (слева от текущего элемента и снизу от текущего элемента), который элемент из этих больше, его значение суммируем с текущим элементом из первого массива и получаем значение текущего элемента во втором массиве. Таким образом мы определяем масимальное значение для каждой клетки которое можно набрать двигаясь только прямо или вправо с нижнего левого угла. Добавлено через 11 минут Таким образом мы заполним весь второй массив. В врехнем правом углу получится максимальное значение, которое можно набрать. Теперь о пути. Путь можно вычислить, после заполнения второго массива, двигаясь обратно. Для этого создаем массив, в котором будем хранить сам путь (хотите типа char сразу, хотите типа int - это все непринципиально). Размер массива всегда будет равен n+(n-2) - не количество пройденных клеток, а количество перемещений между ними. Итак начинаем с верхнего правого элемента второго массива - будем называть рассматриваемый элемент массива текущим. Если от значения текущего элемента второго массива отнять значение текущего элемента первого массива и получится значение левого от текущего элемента второго массива, то записываем в массив пути F и делаем текущим элемент слева от текущего. Если полученное значение равно значению нижнего от текущего элемента второго массива, то записываем в массив пути R и делаем текущим элемент снизу от текущего. И так до конца (до того момента пока текущим не станет самый ниэний левый элемент). Вывод результата производить с конца массива пути. 2

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.10.2010, 21:55
	Mayonez, что выдает Ваша программа на приведенные Вами значения в массиве? А потом подайте на вход те же значения массива только исправьте правое нижнее значение на 100000 и напишите что получилось? 1

KuKu 1563 / 1041 / 94 Регистрация: 17.04.2009 Сообщений: 2,995
	25.10.2010, 22:04
	valeriikozlov, вы конечно правы. Но одно дело сделать так, чтобы работало всегда, а другое что бы работало как требуется. От него не требуют большего. Так тут в каждом втором задании на форуме можно найти недочеты. 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.10.2010, 22:25
	Что же у Вас за компилятор, который запросто переваривает stl, а в переменной типа int не выносит значений более 32767? Ну тогда запишите туда значение не 100000 а 10000. 1

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	25.10.2010, 22:33
	это и называется динамическим програмированием. Добавлено через 1 минуту Если хотите разобраться в нем побольше, Вам нужно что-нибудь почитать об этом. 1