TUZ_2-24 n - й член последовательности Ван Эка
2.24 n - й член последовательности Ван Эка
Рассмотрим последовательность S, состоящую из положительных целых чисел.
Первый член S равен 0. Есть ли ноль перед текущим нулем? Нет, поэтому последовательность равна (0, 0).
Для последнего числа (в данном случае для второго нуля) задается тот же вопрос: есть ли ноль перед текущим (вторым) нулем?
Да, поэтому последовательность равна (0, 0, 1).
И снова для последнего числа (1) задается вопрос: есть ли «единица» перед текущей единицей? Нет, значит, последовательность равна (0, 0, 1, 0).
И снова для последнего числа (0) задается вопрос: есть ли ноль перед текущим нулем? Да, поэтому последовательность равна (0, 0, 1, 0, 2) и т. д.
Проще говоря, последовательность подсчитывает количество шагов, необходимых для достижения первого запрошенного числа,
если следовать начиная с хвоста последовательности до запрошенного числа, и подсчет прекращается, когда обнаруживается искомое число.
Эта популярная последовательность называется последовательностью Ван Эка. Ее члены определяются рекурсивно, поскольку каждый следующий член вычисляется на основе предыдущих.
Ваша задача: написать функцию, которая принимает положительное целое число n и возвращает n-й член последовательности Ван Эка.
В табл. 2.24 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.24. Некоторые ожидаемые результаты для задачи поиска n?го члена последовательности Ван Эка |
| n |
Ожидаемый результат |
| 258 |
3 |
| 25 |
4 |
| 2 |
1 |
| 2089 |
0 |