Мины, Динамическое программирование Опции

[setare]

Здравствуйте! Нам дали задачу на динамическое программирование толком не обьяснив как можно эту тему использовать в решении задач. Мне дали следующую задачу:
Есть строка, которую вводит пользователь, например: 1 2***3*1 После этого надо написать программу, которая бы сосчитала сколькими способами можно поставить мины, как в игре сапере под каждой цифрой. Как можно подойти к этой задаче? И как рассчитать эти способы? А также массив будет двумерный или одномерный только для самых мин? Спасибо за ответ! И я пользовалась поиском, но по-моему такой темы у вас не была. По крайней мере я ничего не нашла.

Сообщение отредактировано: setare - 12.12.2005 23:52

[Lapp]

setare, я извиняюсь за задержку - перед праздниками очень туго со временем . Но если уж пообещал - пришлось сделать . Правда, я сомневаюсь, что у тебя еще есть потребность в решении..
Итак, вот программа и небольшие пояснения к ней.
Фактически, вариантом является число, записанное в двоичной форме (1-мина, 0-пусто). Перебор вариантов ведем от 0 до 2^n - 1, где n - разрядность (или число символов в строке), верхние разряды заполняем нулями. В обычном алгоритме честно проверяем каждый вариант. В алгоритме с динамическим программированием (ДП) запоминаем результат проверки варианта и используем его в следующих шагах. Получается быстрее, но нужно много памяти. При длине строки n нужно 2^n байт (точнее - булевских переменных, но в паскале они представляются байтом). Таким образом, при длине строки 30 нужен гигабайт памяти. Программа действительно работает быстрее, но при малой длине строки это мало заметно. Для сравнения я поместил тут оба варианта - с ДП и без ДП (последний - мой, он сильно отличается от того, что предложил Malice). Комментарии самые минимальные. Если нужны подробности - спрашивай.

1. Алгоритм с ДП

uses CRT;
const
  Len=29;  {Длина строки. Не больше 30}
  mx=255;
  border=17;   {Признак конца данных}

type
  tField=array[0..mx]of byte;
  tData=array[0..1 shl Len]of boolean;

var
  s,m:tField;
  si:byte;
  n,n1,i,k,left,center,t,v:integer;
  c:char;
  b,mask:LongInt;
  y:boolean;
  D:tData;

procedure Inc_m;  {Увеличение варианта на единицу}
var
  i:integer;
begin
  Inc(m[1]);
  i:=1;
  while m[i]=2 do begin
    m[i]:=0;
    Inc(i);
    Inc(m[i]);
  end;
  Inc(b);
  if i=k then begin
    Inc(k);  {Запоминаем длину значащей части}
    mask:=1 shl (k-2)-1;  {Маска выделения предка}
  end
end;

procedure WriteArray(s:tField);   {Вывод варианта}
begin
  for i:=1 to Pred(n) do Write(Char(s[i]+$30)); WriteLn
end;

begin
  Write('Input line (1,2,3 or space): ');
  n:=1;  {Длина введенной строки +1}
  v:=0;  {Число найденных вариантов}

  repeat   {Ввод исходной строки}
    c:=ReadKey;
    case c of
      ' ','_':begin
        s[n]:=0; Write('_'); Inc(n)
      end;
      '1','2','3':begin
        s[n]:=Byte©-$30; Write©; Inc(n)
      end;
      #8:if n>1 then begin
        Write(c,' ',c); Dec(n)
      end;
      else Write(#7)
    end;
  until c=#13;
  WriteLn;
  s[n]:=border;
  n1:=Succ(n);
  WriteArray(s);

  for i:=0 to mx do m[i]:=0;
  b:=0;          {Вариант, начальное значение}
  mask:=0;
  D[0]:=true; D[1]:=true;
  k:=1;          {Начальная длина значащей части варианта +1 }
  repeat         {Цикл перебора вариантов}
    if k<4 then i:=1 else i:=k-3;
    left:=m[i-1];
    center:=m[i];
    if D[b and mask] then begin  {Проверяем результат предка}
      repeat                    {Цикл проверки варианта}
        t:=left+center;
        left:=center;
        si:=s[i];
        Inc(i);
        center:=m[i];
        Inc(t,center);
        y:=(si=0)or(si=t);
        if i=k-2 then     {Запоминаем результат проверки предпоследнего разряда}
          D[b and mask]:=y
        else if i=Pred(k) then
          D[b]:=y
      until not y;
      if i=n1 then begin Inc(v); WriteArray(m) end
    end
    else D[b]:=false;
    Inc_m
  until m[n]<>0;
  WriteLn('Number of possible combinations: ',v);
  ReadLn
end.

2. Алгоритм без ДП

uses CRT;
const
  mx=255;
  border=17;

type
  tData=array[0..mx]of byte;

var
  s,m:tData;
  si:byte;
  n,n1,i,left,center,t,v:integer;
  c:char;

procedure Inc_m;
begin
  Inc(m[1]);
  i:=1;
  while m[i]=2 do begin
    m[i]:=0;
    Inc(i);
    Inc(m[i]);
  end
end;

procedure WriteArray(s:tData);
begin
  for i:=1 to Pred(n) do Write(Char(s[i]+$30)); WriteLn
end;

begin
  for i:=0 to mx do m[i]:=0;
  Write('Input line (1,2,3 or space): ');
  n:=1;  {Длина введенной строки + 1}
  v:=0;  {Число найденных вариантов}
  repeat
    c:=ReadKey;
    case c of
      ' ','_':begin
        s[n]:=0; Write('_'); Inc(n)
      end;
      '1','2','3':begin
        s[n]:=Byte©-$30; Write©; Inc(n)
      end;
      #8:if n>1 then begin
        Write(c,' ',c); Dec(n)
      end;
      else Write(#7)
    end;
  until c=#13;
  WriteLn;
  s[n]:=border;
  n1:=Succ(n);
  WriteArray(s);

  repeat
    i:=1;
    left:=0;
    center:=m[1];
    repeat
      t:=left+center;
      left:=center;
      si:=s[i];
      Inc(i);
      center:=m[i];
      Inc(t,center);
    until (si<>0)and(si<>t);
    if i=n1 then begin Inc(v); WriteArray(m) end;
    Inc_m;

  until m[n]<>0;
  WriteLn('Number of possible combinations: ',v);
end.