Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

Подробнее »



Вопрос # 2 511

/ вопрос открыт /

Здравствуйте, эксперты! Не могли бы вы помочь мне решить одну задачку...
Задача:
В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

Желательно с пояснениями...очень хотелось бы именно понять как это делается...Заранее спасибо!

Anrie Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: Anrie (статус: Посетитель)
Вопрос отправлен: 12 марта 2009, 21:04
Состояние вопроса: открыт, ответов: 1.

Ответ #1. Отвечает эксперт: Вадим К

Здравствуйте, Anrie!
Посидел, поразмышлял и написал примитивный минимальный вариант (Внимание! это консольное приложение. Я просто себе наброски делал на фрипаскале под Линусом, но это всё будет работать под делфи, если понимать, что делаешь)

program findways;
uses
  SysUtils,  Classes;
 
const Nx = 3; Ny = 3;
 M:array[1..Nx, 1..Ny] of integer = ((1,5,1),(4,2,2),(1,6,2));
 
 var minsum:integer;
 
 procedure FindWay(x, y :integer; sum:integer);
 begin
   if (x = Nx) and (y = Ny) then //всё, это конец?
   begin
     if sum < minsum then//сравниваем текущую сумму с минимальной
       minsum := sum;
   end;
   if x < Nx then FindWay(x+1, y, sum + M[x+1, y]);//пробуем по оси х шаг
   if y < Ny then FindWay(x, y+1, sum + M[x, y+1]);//пробуем по у шаг
 end;
 
begin
  minsum := maxint; //зададим заведомо большое число, что бы не усложнять алгоритм.
  FindWay(1,1,M[1,1]); //запустим поиск с первой клеточки.
  writeln(minsum);
  readln;
end.
Этот минимальный пример находит минимальную сумму и выводит её. Кстати, она оказалась равной одиннадцати. И таких минимальных путей тут три:). Но вот интересный путь, по которому следовать надо. Я приведу простой и не слишком оптимальный, а оптимизацию оставлю как домашнее задание.
var minsum:integer;
     minway:string;
 procedure FindWay(x, y :integer; sum:integer; way:string);
 begin
   way := way + format(' (%d,%d)', [x,y]);
   if (x = Nx) and (y = Ny) then
   begin
     if sum < minsum then begin
       minsum := sum;
       minway := way;
     end;
   end;
   if x < Nx then FindWay(x+1, y, sum + M[x+1, y], way);
   if y < Ny then FindWay(x, y+1, sum + M[x, y+1], way);
 end;
 
begin
  minsum := 10000;
  FindWay(1,1, M[1,1], '(1,1) ');
  writeln(minsum);
  writeln(minway);
end.
Как видно, я не сильно утруждал себя и просто в строковую переменую добавлял текущую позицию. А когда находил минимум - запоминал. В красивом построении это должно трансформироваться в массив.
Понятное дело, что для понимания того, как работает рекурсия, надо хорошо понимать, что такое область действия переменной, что такое локальная и глобальная переменная, как локальная переменная храниться на стеке и что это дает...

Ответ отправил: Вадим К (статус: Академик)
Время отправки: 18 марта 2009, 00:59
Оценка за ответ: 5


Мини-форум вопроса

Всего сообщений: 17; последнее сообщение — 12 апреля 2009, 03:25; участников в обсуждении: 8.
min@y™

min@y™ (статус: Доктор наук), 12 марта 2009, 22:04 [#1]:

Если движение только вправо и вниз, то достаточно сравнивать перед каждым ходом 2 числа, которые справа и внизу и идти к меньшему числу.
Делаю лабы и курсачи по Delphi и Turbo Pascal. За ПИВО! Пишите в личку, а лучше в аську. А ещё лучше - звоните в скайп!
Мережников Андрей

Мережников Андрей (статус: Абитуриент), 13 марта 2009, 05:42 [#2]:

to Min@y предлагаемое Вами сравнение не всегда даст нужный результат. Например, матрица
1 5 1
4 2 2
1 6 2
По предлагаемому Вами алгоритму сумма получится 14, а минимальная - 11
Пока вижу только перебор всех вариантов и определение среди них минимума
Вадим К

Вадим К (статус: Академик), 13 марта 2009, 08:47 [#3]:

Да, правильный вариант - рекурсивный перебор. Эта задача есть разновидностью задачи коммивояжера - любимого типа задач на любой олимпиаде:)
Хотите увидеть решение?
Галочка "подтверждения прочтения" - вселенское зло.
seryoga

seryoga (статус: 1-ый класс), 13 марта 2009, 10:42 [#4]:

да
Пупкин В В

Пупкин В В (статус: 2-ой класс), 13 марта 2009, 10:59 [#5]:

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

Вадим К (статус: Академик), 13 марта 2009, 11:25 [#6]:

Данную задачу можно рассматривать как транспортную, но с очень большой натяжкой. Очень большой.
А как задача коммивояжера через рекурсию она решается примитивно.
Вот только надо сесть и написать...
Галочка "подтверждения прочтения" - вселенское зло.
seryoga

seryoga (статус: 1-ый класс), 13 марта 2009, 11:46 [#7]:

Просто уже забыл как это делается
Вадим К

Вадим К (статус: Академик), 13 марта 2009, 11:53 [#8]:

Такое нельзя забыть.
Галочка "подтверждения прочтения" - вселенское зло.
Виталий

Виталий (статус: 2-ой класс), 13 марта 2009, 12:29 [#9]:

Однозначно перебор. Рекурсивно шагаете во все стороны. Когда добирётесь до нужного места, то записываете в переменную минимальную сумму. В самой рекурсивной функции делаете проверку : если текущая сумма больше уже записаной, то выходите из функции, не идя дальше.
seryoga

seryoga (статус: 1-ый класс), 13 марта 2009, 13:12 [#10]:

to Виталий а если матрица 20х10 сколько путей мы имеем? и сколько эта рекурсивная фуункция дней считать будет?
seryoga

seryoga (статус: 1-ый класс), 13 марта 2009, 13:13 [#11]:

это так к слову
Вадим К

Вадим К (статус: Академик), 13 марта 2009, 13:24 [#12]:

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

Виталий (статус: 2-ой класс), 14 марта 2009, 11:35 [#13]:

Не долго.
Anrie

Anrie (статус: Посетитель), 18 марта 2009, 19:46 [#14]:

максимальный размер матрицы для данной задачи 20х20
Anrie

Anrie (статус: Посетитель), 18 марта 2009, 19:49 [#15]:

А если матрица не постоянна, а каждый раз вводить новую, и Nx и Ny тоже не константы?
Вадим К

Вадим К (статус: Академик), 18 марта 2009, 21:25 [#16]:

можно завести большую матрицу и все. а можно динамический массив.
Галочка "подтверждения прочтения" - вселенское зло.
Yurchik

Yurchik (статус: 3-ий класс), 12 апреля 2009, 03:25 [#17]:

Я, конечно, понимаю, что вопрос утратил актуальность. Тем не менее, мне он понравился, и у меня есть некоторые соображения. Вот, собственно, и они (пока на уровне идеи).
Для каждой клетки введем понятия "цена" - это то число, которое записано в клетке по условию задачи, и "стоимость" - это та минимальная сумма, которую нужно затратить, чтобы попасть в эту клетку. Переформулировав вопрос задачи, можно сказать, что необходимо найти "стоимость" клетки с координатами [N,M].
По условиям задачи, можно двигаться либо вправо, либо вниз. Это значит, что в следующую клетку можно попасть либо слева, либо сверху, либо и слева, и сверху. Если предположить, что "стоимость" клетки слева и клетки сверху известна, то очевидно, что "стоимость" следующей клетки запишется как (min ("стоимость" клетки слева, "стоимость" клетки сверху) + "цена" следующей клетки).
Также понятно, что для клеток первой строки матрицы нет клеток сверху; для клеток первого столбца матрицы нет клеток слева. Вычисление "стоимости" для этих клеток упрощается: ( "стоимость" клетки слева/сверху + "цена" клетки ). А для верхней левой клетки "цена" и "стоимость" совпадают.
Далее можно показать, что если обходить матрицу слева направо и сверху вниз (бежать построчно) либо сверху вниз и слева направо (бежать по столбцам), то можно без проблем вычислить "стоимости" каждой клетки. И, таким образом, из исходной матрицы "цен" размерности NxM можно сформировать матрицу "стоимостей" той же размерности NxM.
Время формирования матрицы "стоимостей" будет линейно зависеть от количества ячеек матрицы "цен".
Ответ задачи будет содержаться в клетке матрицы "стоимостей" с координатами [N,M].

Также, развивая эту идею, можно легко создать матрицу, которая будет содержать информацию о наиболее "дешевом" маршруте в каждую точку (в т.ч. в наиболее интересную точку [N,M]).

Программно реализовать это нетрудно. Если надо, то сообщите, я напишу.

PS. Может быть я где-то ошибся.. Не судите строго... В любом случае, спасибо за внимание.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.

Версия движка: 2.6+ (26.01.2011)
Текущее время: 23 июля 2019, 18:54
Выполнено за 0.03 сек.
Рейтинг@Mail.ru