1.10.2. ЗАДАЧА О ЦЕПОЧКАХ Рассмотрим следующую задачу [Вир 77]. Требуется найти объектное выражение Oe, обладающее следующими свойствами.
| (1) | Oe не содержит скобок, а всякий входящий в него символ является одним из символов 1, 2 или 3. | |
| (2) | Oe имеет заданную длину len. | |
| (3) | Не существует таких
объектных выражений Oea, Oeb и Oec,
что Oec - не пусто и при этом Oe = Oea Oec Oec Oeb т.е. Oe не содержит двух смежных непустых совпадающих подвыражения. |
|
Для построения требуемого выражения можно поступить следующим образом: начать с пустого выражения, а затем постепенно добавлять к нему числа, следя за тем, чтобы не получалось запрещенной комбинации. При этом, чтобы гарантировать, что цепочка не имеет вида Oea Oec Oec Oeb, где Oec - непустое, достаточно после добавления каждого числа проверять, что не образовалось выражение вида
Oea Oec Oec
Для распознавания выражений такого вида определим предикат Unacceptable?.$func? Unacceptable? e.String = ;
Unacceptable? e.String =
<Div <Length e.String> 2> :: s.Max,
{
s.Max : 0
= $fail;
= 1
$iter \{ <"<" (sK) (s.Max)> = <"+" sK 1>; }
:: sK,
<Right 0 sK <Middle 0 sK e.String>> :: eU,
<Right 0 sK e.String> :: eV,
eU : eV;
};
Теперь определим функцию Extend?, которая пытается добавить к выражению очередной символ, пока цепочка не достигнет заданной длины. Если цепочку продолжить невозможно, происходит возврат назад, и делается попытка изменить предыдущие символы.$func? Extend? s.Len e.String = e.String;
Extend? s.Len e.String =
{
<Length e.String> : s.Len
= e.String;
= 1 $iter \{ <"<" (s.Digit) (3)> = <"+" s.Digit 1>; }
:: s.Digit,
e.String s.Digit :: e.String,
# <Unacceptable? e.String>,
<Extend? s.Len e.String>;
};
Теперь осталось определить начальную функцию Find-String?, которая получает в качестве параметра желаемую длину цепочки, и выдает искомую цепочку (если она существует), либо терпит неудачу (если она не существует).$func? Find-String? s.Len = e.String;
Find-String? s.Len =
<Extend? s.Len >;