Дано целое число N (> 1), являющееся числом Фибоначчи: N = FK . Найти целое число K — порядковый номер числа Фибоначчи N

@лесечка1993 · Регистрация: 26.12.2012

Author24 — интернет-сервис помощи студентам

помогите пожалуйста на с написать, или хотя бы какой нить толчок сделать. Дано целое число N (> 1), являющееся числом Фибоначчи: N = FK . Найти целое число K — порядковый номер числа Фибоначчи N.

@helter · 10.04.2013, 02:16

Вариантов море. Можно тупо считать все числа Фибоначчи подряд, пока не уткнётесь в данное. Можно и хитрее. Во-первых, числа Фибоначчи можно считать по формуле, без всяких рекурсий. Во-вторых, для них есть показательная асимптотика, которая, наверно, позволит прямо находить номер через логарифм.

@Catstail · 10.04.2013, 14:24

А на Лиспе не подойдет? А то вот:

Lisp

(defun get-num-fib (N)
 (let ((p 1) (c 1) (z 0) (k 2))
  (loop
     (when (= c n) (return k))
     (when (> c n) (return 'not_found))
     (setq z (+ p c) p c c z k (1+ k)))))
 
==> get-num-fib
 
(get-num-fib 34)
 
==> 9
 
(get-num-fib 55)
 
==> 10
 
(get-num-fib 267914296)
 
==> 42
 
(get-num-fib 267914295)
 
==> not_found

@лесечка1993 0 / 0 / 0 Регистрация: 26.12.2012 Сообщений: 5
		1
	Дано целое число N (> 1), являющееся числом Фибоначчи: N = FK . Найти целое число K — порядковый номер числа Фибоначчи N 09.04.2013, 22:31. Показов 2052. Ответов 2 Метки нет (Все метки) помогите пожалуйста на с написать, или хотя бы какой нить толчок сделать. Дано целое число N (> 1), являющееся числом Фибоначчи: N = FK . Найти целое число K — порядковый номер числа Фибоначчи N. 0

@helter 4527 / 3521 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	10.04.2013, 02:16	2
	Вариантов море. Можно тупо считать все числа Фибоначчи подряд, пока не уткнётесь в данное. Можно и хитрее. Во-первых, числа Фибоначчи можно считать по формуле, без всяких рекурсий. Во-вторых, для них есть показательная асимптотика, которая, наверно, позволит прямо находить номер через логарифм. 0

	10.04.2013, 14:24