Задача про черепашку. Динамическое программирование

@Alex_The_King · Регистрация: 31.07.2014

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

Здравствуйте, никак не могу дойти до решения задачи про черепашку.
Условие:
На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму.

Формат входных данных
Первая строка — N — размер доски.
Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску.

Формат выходных данных
Одно число — максимальная сумма.

Решение здесь и я с ним не согласен, если я его правильно понял.

Находить максимум для двух клеток и идти там где больше не всегда верно.
Например, для матрицы:
2 1 3 5
4 0 1 1
0 1 2 7

При поиске максимального как с начала, так и с конца дальнейшее решение будет неверное.
Может я что-то не правильно понял, прошу объяснить мне как для чайника.
Пока что решил лишь одну задачу из динамического программирования (про мячик прыгающий со ступенек) - еле - еле и кое-как.

Заранее благодарю!

@Sergio Leone · 23.05.2015, 00:11

Alex_The_King, там по в учебнике по исходному массиву заполняется массив B
ты его заполни, выведи на экран и всё сразу поймёшь!

а ещё загляни сюда - https://www.cyberforum.ru/post6573276.html

Добавлено через 4 минуты
кстати.

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

На квадратной доске расставлены

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

Например, для матрицы:
2 1 3 5
4 0 1 1
0 1 2 7

уверен, что это квадратная матрица?!

@Alex_The_King · 23.05.2015, 00:30 **[ТС]**

А ну да для квадратной. Правда вроде сильно ничего не меняется
2 1 3 5
4 0 1 9
1 1 0 1
0 1 2 7
Сейчас посмотрю, что там с массивом B

@Sergio Leone · 23.05.2015, 00:36

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

Правда вроде сильно ничего не меняется

ну, это не принципиально, просто в условии квадратная, поэтому я и обратил на это твоё внимание.

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

Сейчас посмотрю, что там с массивом B

ты по моей ссылке зря не сходил.

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

2 1 3 5
4 0 1 9
1 1 0 1
0 1 2 7

для этой матрицы получаем матрицу B такую:

Code
1
2
3
4
5
  0  0  0  0  0
  0  2  3  6 11
  0  6  6  7 12
  0  7  8  8 13
  0  7  9 11 20

Ответ: 20

Есть ещё вопросы?

код программы я для простоты тут ещё раз продублирую:

Pascal
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
{
учебник по динамическому программированию - 
   [url]http://lisiynos.googlecode.com/git-history/8097cf84c4bd915d8ec01e4a52df109f857e277e/s2/dynamic_problems.html[/url]
 
[url]https://www.cyberforum.ru/post6573276.html[/url]
черепашка}
 
const
  ConstArr : array[1..4,1..4] of integer = (
    ( 2, 1, 3, 5 ),
    ( 4, 0, 1, 1 ),
    ( 1, 1, 0, 1 ),
    ( 0, 1, 2, 7 )
    );
 
function Max(a,b : integer) : integer;
begin  if a>b then Max := a else Max := b end;
 
var
  A: array [1 .. 50, 1 .. 50] of integer;
  B: array [0 .. 50, 0 .. 50] of integer;
  i, j, N: integer;
begin
  { Чтение исходных данных }
  N := 4;
  for i := 1 to N do
    for j := 1 to N do
      A[i,j] := ConstArr[i,j];
  { Инициализация динамики }
  for i := 0 to N do begin
    B[i,0] := 0;
    B[0,i] := 0
  end;
  { Общий шаг }
  for i := 1 to N do
    for j := 1 to N do
       B[i,j] := max( B[i-1,j], B[i,j-1] ) + A[i,j];
 
  for i := 0 to N do begin
    for j := 0 to N do
      Write( B[i,j]:3);
    WriteLn;
  end;
  
  { Вывод ответа }
  writeln(B[N,N]);
end.

@Alex_The_King · 23.05.2015, 00:47 **[ТС]**

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

Добавлено через 1 минуту
Сейчас попробую сам написать на С++ код

@Shamil1 · 28.05.2015, 01:33

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

Пока что решил лишь одну задачу из динамического программирования (про мячик прыгающий со ступенек) - еле - еле и кое-как.

1. Часто задачу можно разбить на несколько более простых подзадач. Хороший способ проверить - это записать решение через рекурсию.

Кликните здесь для просмотра всего текста

Например, в задаче про черепашку:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n,n} = max(s_{n-1,n}, s_{n-1,n}) + a_{n,n}$

1.1. Если эти подзадачи не пересекаются, то можно применить "разделяй и властвуй".

Кликните здесь для просмотра всего текста

В задаче про черепашку подзадачи пересекаются. Например, и $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n-1,n}$ , и $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n,n-1}$ зависят от $https://www.cyberforum.ru/cgi-bin/latex.cgi?s_{n-1,n-1}$ .

1.2. Когда подзадачи пересекаются, то можно применить "динамическое программирование".
1.2.1. В более простом варианте "сверху вниз" мы просто запоминаем значения подзадач в хэш-таблице, чтобы не вычислять их более одного раза.
1.2.2. В более сложном, но более быстром варианте "снизу вверх" мы строим решение, начиная с самого простого.

Кликните здесь для просмотра всего текста

В задаче про черепашку мы начинаем вычислять решения подзадач с левого верхнего угла. Решения подзадач сохраняем в массиве.

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@Alex_The_King 1 / 1 / 0 Регистрация: 31.07.2014 Сообщений: 55

	Задача про черепашку. Динамическое программирование 22.05.2015, 23:25. Показов 25007. Ответов 5 Метки нет (Все метки) Здравствуйте, никак не могу дойти до решения задачи про черепашку. Условие: На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму. Формат входных данных Первая строка — N — размер доски. Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску. Формат выходных данных Одно число — максимальная сумма. Решение здесь и я с ним не согласен, если я его правильно понял. Находить максимум для двух клеток и идти там где больше не всегда верно. Например, для матрицы: 2 1 3 5 4 0 1 1 0 1 2 7 При поиске максимального как с начала, так и с конца дальнейшее решение будет неверное. Может я что-то не правильно понял, прошу объяснить мне как для чайника. Пока что решил лишь одну задачу из динамического программирования (про мячик прыгающий со ступенек) - еле - еле и кое-как. Заранее благодарю! 0

@Alex_The_King 1 / 1 / 0 Регистрация: 31.07.2014 Сообщений: 55
	23.05.2015, 00:30 [ТС]
	А ну да для квадратной. Правда вроде сильно ничего не меняется 2 1 3 5 4 0 1 9 1 1 0 1 0 1 2 7 Сейчас посмотрю, что там с массивом B 0

@Alex_The_King 1 / 1 / 0 Регистрация: 31.07.2014 Сообщений: 55
	23.05.2015, 00:47 [ТС]
	Я по ссылочке сходил. Массив проверил стало понятней. Сейчас вот дохожу. Вообщем вроде все стало ясней. Спасибо большое за помощь Добавлено через 1 минуту Сейчас попробую сам написать на С++ код 0