Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 08.12.2016, 13:10   #1
ashvosk
 
Регистрация: 07.12.2016
Сообщений: 3
Репутация: 10
По умолчанию Двумерное динамическое программирование

opamagite reshit zadachu prashu ochen nado

дана A[n][m] матрица из натуральных чисел (2<=n,m<=100), и при прохождении (i,j) обьекта начисляется штраф A[i][j]. Наше задание попасть из любового элемента первой строчки в n-ную строчку. При этом из конкретного элемента можно продолжить движение к 3 соседним элементам нижней строчки.
Напишите программу которая выполнит данную задачу и минимизирует размер шрафа..
ashvosk на форуме Добавить отзыв для ashvosk Пожаловаться на это сообщение

(C++)
ashvosk вне форума   Ответить с цитированием
Старый 08.12.2016, 13:15   #2
p51x
Профессионал
 
Регистрация: 15.02.2010
Сообщений: 14,711
Репутация: 2631
По умолчанию

http://www.programmersforum.ru/showthread.php?t=300954
__________________
Запомните раз и навсегда: помочь != "решите за меня"!
p51x вне форума   Ответить с цитированием
Старый 08.12.2016, 13:18   #3
ashvosk
 
Регистрация: 07.12.2016
Сообщений: 3
Репутация: 10
По умолчанию

ne obezatelno reshit za meya mojna dat bodskazku
ashvosk вне форума   Ответить с цитированием
Старый 08.12.2016, 13:28   #4
p51x
Профессионал
 
Регистрация: 15.02.2010
Сообщений: 14,711
Репутация: 2631
По умолчанию

Так задача в лоб решается просто:
1. строим прямой путь от одного элемента до нужно, например, по прямой
2. https://en.wikipedia.org/wiki/Backtracking с параметром из предыдущего шага
3. по условию задачи отсекаем или добавляем решения
__________________
Запомните раз и навсегда: помочь != "решите за меня"!
p51x вне форума   Ответить с цитированием
Старый 08.12.2016, 13:48   #5
Croessmah
Вредный кошак
Профессионал
 
Аватар для Croessmah
 
Регистрация: 14.10.2012
Сообщений: 1,159
Репутация: 379
По умолчанию

Звучит-то как, - "Двумерное программирование".
Croessmah вне форума   Ответить с цитированием
Старый 08.12.2016, 14:38   #6
olej.tsil
Заблокирован
 
Регистрация: 30.11.2016
Сообщений: 215
Репутация: -8
По умолчанию

Цитата:
Сообщение от ashvosk Посмотреть сообщение
mojna dat bodskazku
Даю бодсказку :

- это классически рекурсивная задача...
- для текущей позиции в цикле (по 3-м соседям) вызываете всё ту же функцию накопления штрафа...
- и суммируете значения штрафов...
- при этом где-то (в статической, глобальной переменной, дополнительном параметре функции...) храните минимально найденное до сих пор значение накопленного штрафа.
olej.tsil вне форума   Ответить с цитированием
Старый 08.12.2016, 17:47   #7
olej.tsil
Заблокирован
 
Регистрация: 30.11.2016
Сообщений: 215
Репутация: -8
По умолчанию

Цитата:
Сообщение от olej.tsil Посмотреть сообщение
- это классически рекурсивная задача...
Интересно стало (задача).
У вас должно получиться что-то типа такого:
Код:
#include <vector> 
#include <iostream> 
using namespace std; 

typedef vector<vector<float>> matrix;

ostream& operator <<( ostream& out, vector<int>& v ) {
   out << "[ ";
   for( auto i = v.rbegin(); i < v.rend(); i++ ) cout << *i << " ";
   return out << "]";
} 

float min_trace( matrix& m, int y, int x, vector<int>& t ) {
   if( y == (int)m.size() - 1 ) {
      t.push_back( x );
      return m[ y ][ x ];
   }
   float mval = 1E99;
   vector<int> tvec;
   for( int ix = x - 1; ix <= x + 1; ix++ ) {
      if( ix < 0 ) continue;
      if( ix == (int)m[ y ].size() ) continue;
      vector<int> vec;
      float val = m[ y ][ x ] + min_trace( m, y + 1, ix, vec );
      if( val < mval ) {
         mval = val; 
         vec.push_back( x );
         t = vec;
      }
   }
   return mval; 
}

int main( void ) {
   matrix M = { 
      { 1, 2, 3, 4, 5, 4, 3, 2, 1 },
      { 2, 3, 4, 5, 4, 3, 2, 1, 0 },
      { 3, 4, 5, 4, 3, 2, 1, 0, 1 },
      { 4, 5, 4, 3, 2, 1, 0, 1, 2 }, 
   };
   cout << "матрица [ " << M.size() << "x" << M[ 0 ].size() << " ] :" << endl;
   for( auto &y : M ) {
      for( auto x : y ) cout << x << " ";
      cout << endl;
   }
   cout << "--------------------------------" << endl;   
   float mval = 1E99;      
   vector<int> tvec;
   for( int i = 0; i < (int)M[ 0 ].size(); i++ ) {
      vector<int> vec;
      float val = min_trace( M, 0, i, vec );
      if( val < mval ) {
         mval = val;
         tvec = vec;
      }   
   }
   cout << "минимальная трасса " << mval << " : ";
   cout << tvec << endl;
}
Это будет работать для матриц любой ширины и глубины:
Код:
$ ./straf 
матрица [ 4x9 ] :
1 2 3 4 5 4 3 2 1 
2 3 4 5 4 3 2 1 0 
3 4 5 4 3 2 1 0 1 
4 5 4 3 2 1 0 1 2 
--------------------------------
минимальная трасса 1 : [ 8 8 7 6 ]
olej.tsil вне форума   Ответить с цитированием
Ответ

Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Двумерное динамическое программирование ashvosk Помощь студентам 0 07.12.2016 21:42
Динамическое программирование 4ubak01 Windows Forms 0 21.04.2016 22:22
Динамическое программирование Hyskills Общие вопросы по Java, Java SE, Kotlin 0 24.02.2016 22:34
динамическое программирование stefan0202 Паскаль 3 07.02.2011 23:05


20:10.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.