Статья Автор: Лебедев Дмитрий

TUZ_2-26 Поиск k - го слова Фибоначчи

TUZ_2-26 Поиск k - го слова Фибоначчи

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

Можно рассмотреть и такое определение для строк Фибоначчи
Строки Фибоначчи удовлетворяют рекуррентному соотношению:
fn=fn−1fn−2,  при n > 1
f0=y
f1=x.
Начальные значения fn :
  • f0=y
  • f1=x
  • f2=xy
  • f3=xyx
  • f4=xyxxy
  • f5=xyxxyxyx

Алгоритм
.Решение задачи заключается в создании последовательности до k-й позиции и извлечении указанного элемента.
Однако этот метод имеет высокую временную и пространственную сложность.
Для поиска k-го символа используются формулы 2.8 и 2.9, где phi обозначает золотое число.

 


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать