динамические программирование

[erorai 1990]

Дан текст, оканчивающийся точкой. Среди литер этого текста особую роль играет знак #, появление которого в тексте означает отмену предыдущей литеры текста; k знаков # подряд отменяют k предыдущих литер (если такие есть). Напечатать данный текст, исправленный с учетом такой роли знака # (например, текст ХЭ#Е##НЕLО#LО должен быть напечатан в виде НЕLLО). помогите . я непонемаю

[Сtrl]

Полный код на C++:

#include <iostream>
#include <string>
#include <iterator>

using namespace std;

string delsharp(string str, char key = '#');

int main()
{
	cout << "Enter your string: ";
	string str;
	getline(cin, str);
	cout << "Edited string: " << delsharp(str) << endl;
	cin.get();
}

string delsharp(string str, char key)
{
	string result;
	string::const_reverse_iterator iter = str.rbegin();
	while (iter != str.rend())
	{
		int n = 0;
		while (iter != str.rend() && *iter == key)
		{
			++iter;
			++n;
		}
		for (int i = 0; iter != str.rend() && i != n; ++i)
			++iter;
		if (iter != str.rend())
			result.push_back(*iter++);
	}
	return string(result.rbegin(), result.rend());
}

[erorai 1990]

спасибо , но надо на паскале

[Serge_Bliznykov]

меня немного смущают слова "динамические программирование"...

а так, "в лоб"
решение #1

var s1 : string;
  i : integer;
begin
  s1 := 'ХЭ#Е##НЕLО#LО';
  i:=1;
  while i<=Length(s1) do begin
    if (s1[i]='#') and (i>1) then
       begin Delete(s1,i-1,2); Dec(i) end
    else Inc(i);
  end;
  WriteLn(s1);
  Readln
end.

решение #2

var s1,s2 : string;
  i : integer;
begin
  s1 := 'ХЭ#Е##НЕLО#LО';
  s2:='';
  for i:=1 to Length(s1) do begin
    if (s1[i]='#') and (Length(s2)>0) 
       then Delete(s2, Length(s2), 1)
    else s2 := s2 + s1[i];
  end;
  WriteLn(s2);
  Readln
end.

решение #3

var s1,s2 : string;
  i, DelCount : integer;
begin
  s1 := 'ХЭ#Е##НЕLО#LО';
  s2:='';
  DelCount := 0;
  for i:=Length(s1) downto 1 do begin
    if (s1[i]='#') then Inc(DelCount)
    else
       if DelCount>0 then Dec(DelCount)
       else s2 := s1[i]+s2;
  end;
  WriteLn(s2);
  Readln
end.

Достаточно?!


p.s. буду искренне признателен, если кто-то мне объяснит, как эту задачу решать с точки зрения динамического программирования (либо алгоритм, либо решение)!

[Plague]

может как то так?

procedure a(var s:string);
  begin
    if pos('#',s)>0 then 
      begin
        delete(s,pos('#',s)-1,2);
        a(s);
      end;
  end;
var st:string;
begin
  st:='ХЭ#Е##НЕLО#LО';
  a(st);
  writeln(st);
end.

[erorai 1990]

это задание в разделе Динамические структуры данных

[DiemonStar]

p.s. буду искренне признателен, если кто-то мне объяснит, как эту задачу решать с точки зрения динамического программирования (либо алгоритм, либо решение)!

Есть подозрение, с учётом специфики раздела, что строка в данном задании представлена динамическим линейным массивом символов. Что-то вроде:

type
   pCharElement = ^CharElement;
  CharElement = record;
    ch : char;
    Next : pCharElement;
    Prev : pCharElement;
  end;{record}

и дальше реализуется вручную заполнение, поиск и удаление элементов из массива по предложенным вариантам с учётом специфики динамических структур.