TUZ_2-26 Поиск k - го слова Фибоначчи
2.26 Поиск k - го слова Фибоначчи
Слова/строки Фибоначчи – это последовательность, напоминающая обычную последовательность чисел Фибоначчи, с той лишь разницей,
что в роли суммы двух предыдущих чисел рассматривается их конкатенация.
Первый член этой последовательности равен 0, второй – 01 (как строка).
Каждый последующий член получается путем объединения двух предыдущих членов.
Например, третий член получается путем объединения первого и второго членов, что дает в результате 010.
Аналогично четвертый член получается путем объединения второго и третьего членов, что приводит к 01001, и т. д.
Ваша задача: написать функцию, которая принимает целое число k и возвращает k-е «слово» Фибоначчи – k-й символ строки,
состоящей из символов 0 и 1.
(Легко заметить, что "начало" строки Фибоначчи не меняется)
В табл. 2.26 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 2.26. Некоторые ожидаемые результаты для задачи поиска k-го слова Фибоначчи |
| k |
Ожидаемый результат |
| 65 |
0 |
| 170 |
0 |
| 98 |
1 |
| 2022 |
1 |