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

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

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

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

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

Вопрос задал: 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

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

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 (статус: 1-ый класс), 13 марта 2009, 10:42 [#4]: да

Пупкин В В (статус: 2-ой класс), 13 марта 2009, 10:59 [#5]: в экономическом моделировании есть особый вид задач - транспортные задачи, там есть свой алгоритм вычисления наименьших и наибольших расходов, должно помочь. (к слову)

Вадим К (статус: Академик), 13 марта 2009, 11:25 [#6]: Данную задачу можно рассматривать как транспортную, но с очень большой натяжкой. Очень большой. А как задача коммивояжера через рекурсию она решается примитивно. Вот только надо сесть и написать... Галочка "подтверждения прочтения" - вселенское зло.

seryoga (статус: 1-ый класс), 13 марта 2009, 11:46 [#7]: Просто уже забыл как это делается

Вадим К (статус: Академик), 13 марта 2009, 11:53 [#8]: Такое нельзя забыть. Галочка "подтверждения прочтения" - вселенское зло.

Виталий (статус: 2-ой класс), 13 марта 2009, 12:29 [#9]: Однозначно перебор. Рекурсивно шагаете во все стороны. Когда добирётесь до нужного места, то записываете в переменную минимальную сумму. В самой рекурсивной функции делаете проверку : если текущая сумма больше уже записаной, то выходите из функции, не идя дальше.

seryoga (статус: 1-ый класс), 13 марта 2009, 13:12 [#10]: to Виталий а если матрица 20х10 сколько путей мы имеем? и сколько эта рекурсивная фуункция дней считать будет?

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

Вадим К (статус: Академик), 13 марта 2009, 13:24 [#12]: Поверьте, не так долго. Но если матрица действительно очень большая, то тут уже применяют эмпирические методы. То есть, ищут не самое лучшее решение, а "достаточно хорошее". Галочка "подтверждения прочтения" - вселенское зло.

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

Anrie (статус: Посетитель), 18 марта 2009, 19:46 [#14]: максимальный размер матрицы для данной задачи 20х20

Anrie (статус: Посетитель), 18 марта 2009, 19:49 [#15]: А если матрица не постоянна, а каждый раз вводить новую, и Nx и Ny тоже не константы?

Вадим К (статус: Академик), 18 марта 2009, 21:25 [#16]: можно завести большую матрицу и все. а можно динамический массив. Галочка "подтверждения прочтения" - вселенское зло.

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

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