На этом шаге мы приведем формулировку этой задачи.
В задаче "Станции водоочистки" есть n городов со станциями водоочистки, расположенных по одну сторону реки, как показано на рисунке 1.
Рис.1. Задача о станциях водоочистки
Допустим, что города упорядочены слева направо. Каждый город - источник грязной воды, которую необходимо очистить на станции (не обязательно своей) и сбросить в реку по трубам, соединяющим соседние города. Работающая станция забирает сточные воды своего и соседних городов и после очистки сбрасывает их в реку. Но станция может не работать, и тогда сточная вода её города плюс вода любого соседнего с ней города направляется в другой город. Учитывая, что вода по трубе, соединяющей города, может течь лишь в одном из направлений, задача состоит в вычислении количества способов сброса очищенной воды в реку для n городов. Кроме того, мы должны быть уверены в том, что хотя бы одна из станций работает, то есть способна очистить и сбросить очищенную воду в реку.
Мы рассмотрим два рекурсивных решения этой задачи подсчёта. Первое моделирует переток воды между городами и использует множественную рекурсию. Второе рассматривает сброс воды в реку по каждому городу и опирается на три взаимно-рекурсивные функции.
На следующем шаге мы рассмотрим переток воды между городами.
