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

Ты бы поподробне о задаче рассказала ... если уж ты не можешь нормально ее сформулировать и объяснить что надо сделать .. то как это сделать нам ?

ps спам щас удалю ...

Извините!! Но что вам именно не понятно??? И почему спам??? Как же я могла еще обратить ваше внимание на мою тему?????Задача не игровая, но похожа на игру сапер. Есть строка, сост из цифр 1234, кот вводит пользователь, между кот есть пустота(пробелы). Нужно поссчитать сколькими способами можно расставить мины в нижней строчке! Вот и вся формулировка, кот дал препод.


Ты считаешь что это не спам ?
http://forum.pascal.net.ru/index.php?showtopic=7852


Извините, больше такого не будет, просто я не знала, как обратить ваше внимание на мою тему, которая уходила на 30 план. Спасибо. И извините, пожалуйста!!!

Здравствуйте! Я по подробнее обьяснила условие задачи, теперь хотела бы узнать, вы мне ответите, или закроете тему? Это не спам, просто ответьте, пожалуйста!! Благодарю вас!!!

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

setare, я бы помог (и, думаю, не только я), но входных данных пока - увы! - не хватает. Сделай еще одну попытку описать условия - нормальным языком, без сокращений ("кот" - это зверек такой, а вовсе не "который", ты же не станешь в разговоре так сокращать это слово; ничего, пальчики не отвалятся), все это мешает сосредоточиться - не только читающему, но и тебе самой, а значит - мешает правильно и полно изложить материал.
Я довольно легко нашел твое задание по математике в Инете (кафедра 17, ага? ;) ), но с поиском этого задания не получается. Так что тебе придется поработать, если хочешь получить результат.
И не ссылайся на другие задачи - я, например, так и не понял, какого "сапера" ты имела в виду.
Ок?

Хорошо!! Просто, понимаете, как сформулировал мне задачу преподаватель, так я и пишу ее здесь. Есть строка, состоящая из цифр, например 1234, которую вводит пользователь. Между цифрами есть пустоты (пробелы). Нужно поссчитать сколькими способами можно расставить мины в нижней строчке! Строчка находится прямо под этой строкой. Мины можно ставить как под цифрой, так и нет.
например:
+-мины,*-пустоты

1 2 * * * 3 * * 1
++ +   +++	+
  + + +   ++ ++

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

При всем желании никак не могу врубиться:
а) зачем обозначать пробелы звездочками?
б) если уж обозначено, то почему в примере под пробелами тоже есть плюсы?
в) почему есть плюсы даже за пределами строки?
г) чем это отличается от простой рассановки мин на строчке фиксированной длины - то есть как цифры (и пробелы) влияют на расстановку?
Что-то явно ускользает от моего понимания.. Ты заметила, что никто не отвечает? мне кажется, у остальных такие же проблемы, как и у меня..

Спасибо, за то, что ты попытался разобраться. Я, к сожалению, больше ниак не могу объяснить эту задачу, потому что мне ее так объяснили. Еще раз спасибо!А вообще, ответы на вопросы следуюущие:
1) просто я так обозначила пробелы, чтобы было удобнее понять, сколько там пробелов
2) Я уже в задании говорила, что мы можем мины ставить как под цифрами, так и под пробелами.Например, если стоит цифра один, то мина может стоять как под один, так и около нее, если там есть пробел. Но не может стоять там, где нет пробела (около 1).
3) Плюс, который стоит за пределы еденицы, вышел туда нечаяно. Я просто ошиблась!
4) Цифры показывают сколько мин должно быть , пробелы просто дают еще дополнительное место для того, чтобы поставить эти мины.

setare, в твоем последнем посте наконец-то появилась полезная информация, это обнадеживает . А именно, ты сказала, что цифра означает число мин. Уверяю тебя, это совсем не очевидно и этого не было раньше ни в одном посте. Можешь поверить мне на слово - я сильно сомневаюсь, что у тебя появится желание перечитать тред (как я сделал уже не один раз). Милая девочка, пойми, что задача должна быть правильно сформулирована. Это не "придирки преподавателя", который мучит бедного ребенка ненужными вопросами, хотя и так все понятно. Это желание тебе помочь, которое всякий раз натыкается на недостаток информации. Мы тут все, ясное дело, шибко головастые, и многое понимаем с полуслова, но некоторые вещи понять принципиально невозможно, пойми.

Ты большая любительница сокращать - но Краткость не всегда сестра Таланта! Чье время ты экономишь? Перед отправлением, пожалуйста, перечитай пост. Потому что ошибки ("..стоит за пределы еденицы, вышел туда нечаяно. Я просто ошиблась!") в данном случае вредят тебе самой. Ошибка в решении - это одно, но ошибка в условии - это перечеркнутая задача. Ну, что бы ты сказала, если бы в задачнике была задача с ошибкой? Хорошо, если ошибка очевидная. А если нет?? Твои ошибки не очевидные. Наказывать тебя и снижать оценку мы тут не будем. Но помочь тебе просто не сможем. Дай себе труд, перечитай написанное, исправь ошибки и постарайся вдуматься, все ли тут есть.

Дальше: читай внимательнее то, что тебе пишут. Вот я тебе писал

Я тебя спрашивал: если уж пробелы обозначены звездочками, то почему плюсы стоят не только под звездочками, но и под пробелами, которые, как я понимаю, ничего не означают (см. 2-й, 3-й, 4-й и 6-й плюсы в средней строчке)?
Вот твой пример (я копирую сюда, чтобы ты, бедная, не переутомилась, лазаючи наверх.. ).

Вопрос остается, ты на него не ответила. Появились и новые вопросы.
Первый - число плюсов всегда точно равно цифре? В примере это не так.
Второй - за последней цифрой (или перед первой) могут быть пробелы?
Третий - если пробел является соседним к двум цифрам (типа между 1 и 2), то какие мины под него можно ставить - от 1 или от 2?
...
Знаешь, что я бы тебе посоветовал? Подойди к препу, дай ему в репу ... ой, извини, сбился. Подойди к препу и попроси, чтобы он написал тебе точное условие (именно НАПИСАЛ, а не сказал!). Боюсь, без этого нам тут не справиться..
И еще раз - я тут не занимаюсь придирками. Я стараюсь тебе помочь.
Чао!

Но почему тогда не одна а две строчки с плюсами??

Я думаю, это может быть второй вариант расстановки (коих число и надо найти).

setare! услышь меня! открой завесу тайны!! ты видишь - народ жаждет узнать правду!!
условие!
у-сло-ви-е!
уу-слоо-вии-еее!!!! шайбу, ШАЙ-БУ! тьфу ты, пропасть..
УУУССССЛЛЛЛОООООВВВВИИИИЕЕЕЕ!!!

ну, сделай нам подарок к Новому Году..

Не морочь человеку голову, все понятно. Только это не очень на сапер похоже, рядом с 3-кой в примере полюбому должно какое-то число стоять. Если очень надо могу набросать прогу.

Мил человек, может ты пояснишь, что есть "сапер"? Интересно же..

Сапёр, или WinMine - игрушка, входящая в стандартный набор игр Windows любой версии. lapp, неужели ни разу не играл?! Какая у тебя ОС?

Примерно так:

uses crt;
var s,s1:string;
n,j,i,x:longint;
function check(s,s1:string):boolean;
var s2:string;
i:integer;
begin
s:=' '+s+' '; s1:=' '+s1+' '; s2:=' ';
for i:=2 to length(s1)-1 do begin
s2:=s2+chr(byte(s1[i-1]='1')+byte(s1[i]='1')+byte(s1[i+1]='1')+$30);
if s[i]=' ' then s[i]:=s2[i]; end;
if s=(s2+' ') then check:=true else check:=false;
end;

begin
clrscr;
write ('Исходная строка: '); readln (s);
 x:=(1 shl length(s))-1; n:=0;
for i:=1 to x do begin
s1:='';
for j:=0 to length(s)-1 do
 if ((1 shl j) and i) =0 then s1:=s1+'0' else s1:=s1+'1';
if check(s,s1) then begin writeln (s1); inc(n); end;
end;
writeln ('Всего ',n,' вариантов');
end.

Malice, спасибо за программу, но мне кажется, что она написана не в динамическом программировании! Но все равно спасибо!
Я еще раз привожу пример:
Не обращайте внимание на пробелы, которые я сейчас поставлю. Проблеами здесь являются именно минусики. Я поставлю пробелы только для наглядности. Эти звездочки не попадают прямо под минусики, но я больше не знаю ка это изобразить!Надеюсь сейчас хотя бы это как-то понятно!

- 1 2 - - - 3 - - 1 -
* * * * ** *
* ** ** * *

Притом, мне не трудно еще раз подняться и посмотреть то, что я написала.Я не такая уж ленивая и быстро устающая от таких незначительный дел.

Да, число плюсов точно равно цифрам, и хочу обратить ваше внимание на то, что в примере это именно так!
Да, пробелы могут стоять и впереди и после первой и последней цифры соответсвенно!
Под пробелами не имеет смысла от каких цифр стоит мина. там может быть мина, например, как от 2 так и от 1. Самое главное, чтобы число соответсвовало цифрам. Напримар если стоит 1 пробел пробел 2, то должно стоять в общем только 3 мины рядом с 1 и 2. Значит, может стоять мина под 1 пробелом и проблом, потом пробелом пробелом 2, пробелом 2 иесли там дальше есть пробел или число, то и дальше мина.
Препода я больше не могу найти, его не бывает в университете в течение недели! Плюс он другому человеку дал это же задание и обьяснил его так же как и мне и больше ничего не сказал. Этот другой человек, если вы скажете, чтобы я обратилась к нему за вопросами, сам ничего не смыслит в программировании и в этих задачах!

Я таких слов не знаю, если ты знаешь, то переделай мою программу и все.

Играл! давно было, но - было.. Более того, я ее как-то раз сделал в полном варианте и в графике за пару-тройку часов, пока объяснял одному человеку программирование. Ее название вообще-то minesweeper, и у меня никогда не было русской винды - может, поэтому не проассоциировало.. А может потому, что она мне казалась существенно двумерной (но я был не прав). Еще в заблуждение вводила 4-ка, мозолившая глаза с самого начала - в двумерной версии четверки никак не может быть. Ок, спасибо всем, растолковали.
Malice, твоя прога тоже помогла пониманию (собственно, главным образом именно она), я ее полностью разобрал. Она прекрасно работает, но весьма неоптимальна, а динамическое программирование - это как раз определенный метод оптимизации. Похоже, тут его можно применить, но надо чуть-чуть покумекать.. Беру небольшой тайм-аут

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

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.

Огромное спасибо! Обязательно разберусь в решении!