3. Преобразования

Задача заключается в выводе рекуррентного соотношения. Рассмотрим двух соседей 00, на следующем шаге эти соседи исчезнут 1010, а еще через шаг пара 00 появится снова 01100110. Кроме того каждая 1 через два шага порождает соседей 00. Количество 1 на каждом шаге удваивается. Окончательно формула выглядит так `S_0=0`, `S_1=0`, `S_k\ =S_{k-2}\ +\ 2^{k\ -\ 2}`. Для вычислений потребуется длинная арифметика (только операция сложения и печать) Частичное решение – выполнение указанных преобразований с помощью строк – дает 18 баллов. Правильная формула с использованием extended вместо длинной арифметики – 24 балла.