0

Анаграммер — специальное устройство для получения из слова его анаграмм (то есть слов, записанных теми же буквами, но в другом порядке). Это устройство умеет выполнять 2 операции:

Взять очередную букву исходного слова и поместить ее в стек. Взять букву из стека и добавить ее в конец выходного слова.

Стек — это хранилище данных, которое работает по принципу "первый пришел — последний ушел". Стек можно представить себе в виде пирамидки. Когда мы добавляем букву в стек, это соответствует тому, что на стержень пирамидки сверху мы надеваем кольцо, на котором написана соответствующая буква. Когда берем букву из стека, то это соответствует тому, что мы снимаем со стержня верхнее кольцо, и смотрим, какая буква на нем написана.

Например, слово TROT в слово TORT может быть преобразовано анаграммером двумя различными последовательностями операций: 11112222 или 12112212.

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

Входные данные

Первая строка входного файла INPUT.TXT содержит исходное слово, а вторая — слово, которое необходимо получить. Слова состоят только из заглавных латинских букв и имеют длину не более 50 символов. Оба слова имеют одинаковую длину. В этих строках не содержится пробелов.

Выходные данные

В первой строке выходного файла OUTPUT.TXT должно содержаться количество последовательностей операций анаграммера, с помощью которых можно преобразовать первое слово во второе.

INPUT.TXT   OUTPUT.TXT
1   TROT
    TORT            2
2   MADAM
    ADAMM           4
3   LONG
    GONG            0
4   AAAAAAAA
    AAAAAAAA        1430

Пишите, пожалуйста, ваши рассуждения. Решается динамическим программированием.

5
  • 3
    @nicolai, Согласно правилам форума, вопросы не должны сводиться к решению либо завершению учебных заданий за учащихся. Пожалуйста, уточните, что вы сделали сами и что не получилось.
    – insolor
    18 авг 2012 в 13:49
  • 2
    @nicolai Лучше вы напишите ваши рассуждения. 18 авг 2012 в 14:23
  • 2
    Это просто задачка, которую никак не могу решить, подумал, что здесь найду помощь. Это не домашняя работа. И я не просил целиком решение, я просил рассуждения. Это не запрещено по правилам, прочитайте там в правилах в самом внизу "Как ответить на учебные вопросы"
    – nicolai
    19 авг 2012 в 9:53
  • Собственно, все "рассуждения" уже обозначены при постановке задачи.
    – user6550
    19 авг 2012 в 10:59
  • При постановке обозначены рассуждения на счёт постановки. Мне нужны рассуждения на счёт решения.
    – nicolai
    19 авг 2012 в 16:46

1 ответ 1

2

Реализация для Free Pascal/Delphi:

function is_empty(stack:string):boolean;
begin
    is_empty:=length(stack)=0;
end;

function top(stack:string):char;
begin
    top:=stack[length(stack)];
end;

function push(stack:string;item:char):string;
begin
    push:=stack+item;
end;

function pop(stack:string):string;
begin
    setlength(stack,length(stack)-1);
    pop:=stack;
end;

function anagrammer(orig:string; samp:string; stack:string):integer;
var
    count:integer;
    newstack:string;
begin
    count:=0;
    if samp='' then anagrammer:=1
    else
    begin
        if (not is_empty(stack)) and (top(stack)=samp[1]) then
        begin
            newstack:=pop(stack);
            count:=count+anagrammer(orig,copy(samp,2,length(samp)),newstack);
        end;

        if length(orig)>0 then
        begin
            newstack:=push(stack,orig[1]);
            count:=count+anagrammer(copy(orig,2,length(orig)),samp,newstack);
        end;
        anagrammer:=count;
    end;
end;

begin
    writeln(anagrammer('TORT','TROT',''));
    writeln(anagrammer('MADAM','ADAMM',''));
    writeln(anagrammer('LONG','GONG',''));
    writeln(anagrammer('AAAAAAAA','AAAAAAAA',''));
end.

Результат:

2
4
0
1430

Пруф

Стек реализован как строка. Процедура pop последний элемент не вытаскивает, а просто удаляет, т.к. в нашем случае его значение не важно.

Вариант 2.

1.Для оригинальной и целевой строки определяем сколько раз встречается каждая буква. Если "встречаемость" букв не совпадает, сразу выводим 0.

2.К полученным количествам букв применяем следующую функцию:

function anagr(orig:integer; stack:integer);
var count:integer;
begin
    count:=0;
    if (orig=0) and (stack=0) then anagr:=1;
    else
    begin
        if stack>0 then count:=count+anagr(orig, stack-1)  { pop }
        if orig>0 then coutn:=count+anagr(orig-1, stack+1) { push }
        anagr:=count;
    end;
end;

полученные результаты перемножаем. Данная функция - максимально упрощенный вариант первоначальной функции, для случая одинаковых букв. К этой функции уже легко прикрутить меморизацию.

Пример: имеется исходное слово AAAAABBBBCCC и конечное слово CCCBBBBAAAAA

  1. Считаем количества букв: A:5, B:4, C:3. В первом и втором словах совпадает, значит идем дальше.
  2. Применяем функцию: A:42, B:14, C:5
  3. Перемножаем: 2940

Это и есть искомое число способов.

Формального доказательства правильности не будет, т.к. с комбинаторикой знаком очень поверхностно :)

6
  • Спасибо конечно за напечатанный код, но это решение в лоб, перебор всех вариантов, оно не влезет под те ограничения. хотелось бы более элегантного решения...
    – nicolai
    19 авг 2012 в 17:26
  • Ограничения? В первый раз слышу.
    – insolor
    19 авг 2012 в 17:43
  • Красиво написано, я даже слегка изменил своё мнение о паскале :)
    – Error
    19 авг 2012 в 17:50
  • да, не спорю, перебор ты реализовал очень хорошо, но это всё таки перебор. попробуй подставить строки хотя бы длиной 30 символов, программа не завершится удачно. Слишком много рекурсивных вызовов, переполняется внутренняя память. и даже если с памятью проблемы не возникнут, то они возникнут со временем, т. е для 50 символов можно будет фильмец посмотреть, может быть даже два...другое дело, если бы как-то применить к этому методу меморизацию(memoraztion) было бы красиво, и без никаких проблем.
    – nicolai
    19 авг 2012 в 18:13
  • Возможно, если 2 вариант правильный, то можно свести задачу к ДП: функция anagr при первом вызове сохраняет ответ, при следующих вызовах возвращает сохраненное значение. Тогда сложность будет что-то вроде [мощность алфавита]*[кол.-во одинаковых букв]*[длина строки]. 20 авг 2012 в 8:54

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.