Условие
Та же задача, если требуется, чтобы число операций было
пропорционально
log
n. (Переменные должны быть
целочисленными.)
Подсказка
Пара соседних чисел Фибоначчи получается из предыдущей
умножением на матрицу
-- так что задача сводится к возведению матрицы в степень
n. Это можно сделать за
C log
n действий тем же
способом, что и для чисел.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
А.Шень |
|
Название |
Программирование: теоремы и задачи |
|
Издательство |
МЦНМО |
|
Издание |
второе |
|
Год издания |
2004 |
|
глава |
|
Номер |
1 |
|
Название |
Переменные, выражения, присваивания |
|
параграф |
|
Номер |
1 |
|
Название |
Задачи без массивов |
|
задача |
|
Номер |
1.1.10 |
