*Fib> fib’ 40
102334155
*Fib> fib’ 4040
700852629
Вычисления происходят мгновенно. Если задача состоит из множества подзадач, которые самоподобны
и для вычисления последующих подзадач используются решения из предыдущих, стоит задуматься об ис-
пользовании мемоизации. Такие задачи называются задачами динамического программирования. Вычисление
чисел Фибоначчи яркий пример задачи динамического программирования.
Рассмотрим такую задачу. Дана прямоугольная “карта местности”, в каждой клетке целым числом ука-
зана высота точки. Необходимо разметить местность по следующим правилам:
• Из каждой клетки карты вода стекает не более чем в одном из четырёх возможных направлений (“се-
вер”, “юг”, “запад”, “восток”).
• Если у клетки нет ни одного соседа с высотой меньше её собственной высоты, то эта клетка – водосток,
и вода из неё никуда дальше не течёт.
• Иначе вода из текущей клетки стекает на соседнюю клетку с минимальной высотой.
• Если таких соседей несколько, то вода стекает по первому из возможных направлений из списка “на
север”, “на запад”, “на восток”, “на юг”.
Все клетки из которых вода стекает в один и тот же водосток принадлежат к одному бассейну водосбо-
ра. Необходимо отметить на карте все бассейны. Решение этой задачи встретилось мне в статье Дмитрия
Астапова “Рекурсия+мемоизация = динамическое программирование”. Здесь оно и приводится с незначи-
тельными изменениями.
Карта местности представлена в виде двумерного массива, в каждой клетке которого отмечена высота
точки, нам необходимо получить двумерный массив того же размера, который вместо высот содержит метки
водостоков. Мы будем отмечать их буквами латинского алфавита в том порядке, в котором они встречаются
при обходе карты сверху вниз, слева направо. Например:
186 | Глава 11: Ленивые чудеса
1 2 3 4 5 6
a a a b b b
7 8 9 2 4 5
a a b b b b
3 5 3 3 6 7
->
c c d b b e
6 4 5 5 3 1
f g d b e e
2 2 4 5 3 7
f g g h h e
Для представления двумерного массива мы воспользуемся типом Array из стандартного модуля
Data.Array. Тип Array имеет два параметра:
data Array i a
Первый указывает на индекс, а второй на содержание. Массивы уже встречались нам в главе о типе ST.
Напомню, что подразумевается, что этот тип является экземпляром класса Ix, который описывает целочис-
ленные индексы, вспомним его определение:
class Ord a => Ix a where
range
:: (a, a) -> [a]
index
:: (a, a) -> a -> Int
inRange