В таблице клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из клетки A(1,1) в клетку A(N,N)

@Lilechka · Регистрация: 08.04.2013

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

В таблице NхN, клетки заполнены случайным образом цифрами от 0 до 9. Найти маршрут из клетки A(1,1) в клетку A(N,N) такой, что:

1) он будет состоять из отрезков, соединяющих центры клеток, имеющих общую сторону

2) длина маршрута минимально возможная

3) из всех маршрутов, удовлетворяющих условиям (1) и (2), искомый маршрут тот, сумма цифр в клетках которого максимальна.

Решение. Пусть клетка (1,1) это левый верхний угол таблицы, а (N,N), соответственно, правый нижний угол. Из условия (2) задачи следует, что за каждый шаг мы будем продвигаться по таблице либо на шаг вправо, либо на шаг вниз, что сразу нам гарантирует минимальность в длине пути и избавляет от анализа вариантов по данному критерию. Рассмотрим произвольную клетку таблицы (i,j). В нее мы можем прийти или из клетки (i-1,j), или из (i,j-1). Тогда, если мы уже знаем оптимальные маршруты из клетки (1,1) в каждую из этих двух клеток, то оптимальным маршрутом в клетку (i,j) будет подмаршрут с максимальной из двух сумм суммой + отрезок соединяющий (i,j) с концом выбранного подмаршрута. Оптимальные маршруты из (1,1) в (1,2) и (2,1) определены однозначно. Зная их, по указанному выше способу мы найдем оптимальные маршруты в (1,3), (2,2), (3,1) и запишем их в соответствующих клетках таблицы (записывать нужно только сумму цифр маршрута и направление его последнего отрезока). Этот процесс можно продолжить пока вся таблица не будет заполнена, причем заполнять ее можно по строчкам слева направо. В клетке (N,N) мы в итоге получим значение суммы цифр искомого маршрута и последний его отрезок. По такой таблице легко восстановить и весь маршрут. Рассмотрим любую часть оптимального маршрута, например, между клетками (i1,j1) и (i2,j2). Докажем, что эта часть маршрута является решением исходной задачи для указанных клеток. Пусть это не так и существует маршрут с большей суммой, соединяющий эти клетки и имеющий такую же длину. Тогда и для клеток (1,1) и (N,N) мы можем построить лучший маршрут, используя отрезки, cоединяющие (1,1) и (i1,j1), а также (i2,j2) и (N,N) из старого маршрута + улучшеный маршрут из (i1,j1) в (i2,j2), а это противоречит тому, что мы изначально рассматривали часть из уже оптимального маршрута. Значит, любая часть оптимального маршрута в свою очередь является оптимальной.

Pascal

const nn=20;
 
var a:array[1..nn,1..nn] of record
 
                              s:integer;
 
                              d:(up,left);
 
                            end;
 
   i,j,n:integer;
 
procedure print(i,j:integer); {печатает решение}
 
  {процедура рекурсивная для того, чтобы печатать маршрут от (1,1)
 
   до (N,N), а не наоборот, рекурсии можно было бы избежать, заведя
 
   массив длиной 2n-1}
 
begin
 
  if (i<>1)or(j<>1) then
 
    case a[i,j].d of
 
      left:print(i,j-1);
 
        up:print(i-1,j);
 
    end;
 
  writeln('(',i,',',j,')')
 
end;
 
begin
 
  readln(n);
 
  randomize;
 
  for i:=1 to n do
 
    for j:=1 to n do
 
      a[i,j].s:=random(10);
 
  for i:=2 to n do {отдельно вычислим маршруты для первой строки и
 
                    первого столбца, так как они однозначные}
 
    begin
 
      a[1,i].s:=a[1,i-1].s+a[1,i].s;
 
      a[1,i].d:=left;
 
      a[i,1].s:=a[i-1,1].s+a[i,1].s;
 
      a[i,1].d:=up
 
    end;
 
  for i:=2 to n do
 
    for j:=2 to n do
 
      if a[i-1,j].s>a[i,j-1].s then
 
        begin
 
          a[i,j].s:=a[i-1,j].s+a[i,j].s;
 
          a[i,j].d:=up
 
        end
 
      else
 
        begin
 
          a[i,j].s:=a[i,j-1].s+a[i,j].s;
 
          a[i,j].d:=left
 
        end;
 
  print(n,n)
 
end.

Нашла код в интернете, а он не работает, помогите разобраться почему
P.S. выводит ошибку неизвестное имя left.
P.P.S. курсовую скоро сдавать, очень нужна помощь!!!

@Kordn · 07.06.2013, 16:01

Pascal

const
  nn = 20;
 
type
  move = (up, left);
 
var
  a: array[1..nn, 1..nn] of record
    
    s: integer;
    
    d: move;
  
  end;
  
  i, j, n: integer;
 
procedure print(i, j: integer);{печатает решение}
 
  {процедура рекурсивная для того, чтобы печатать маршрут от (1,1)
 
   до (N,N), а не наоборот, рекурсии можно было бы избежать, заведя
 
   массив длиной 2n-1}
 
begin
  
  if (i <> 1) or (j <> 1) then
    
    case a[i, j].d of
      
      left: print(i, j - 1);
      
      up: print(i - 1, j);
    
    end;
  
  writeln('(', i, ',', j, ')')
  
end;
 
begin
  
  readln(n);
  
  randomize;
  
  for i := 1 to n do
    
    for j := 1 to n do
      
      a[i, j].s := random(10);
  
  for i := 2 to n do {отдельно вычислим маршруты для первой строки и
  
                    первого столбца, так как они однозначные}
  
  begin
    
    a[1, i].s := a[1, i - 1].s + a[1, i].s;
    
    a[1, i].d := left;
    
    a[i, 1].s := a[i - 1, 1].s + a[i, 1].s;
    
    a[i, 1].d := up
    
  end;
  
  for i := 2 to n do
    
    for j := 2 to n do
      
      if a[i - 1, j].s > a[i, j - 1].s then
      
      begin
        
        a[i, j].s := a[i - 1, j].s + a[i, j].s;
        
        a[i, j].d := up
        
      end
      
      else
      
      begin
        
        a[i, j].s := a[i, j - 1].s + a[i, j].s;
        
        a[i, j].d := left
        
      end;
  
  print(n, n)
  
end.

	07.06.2013, 16:01