[СПВ][Хочется странного] Фибоначчи

сбегать в школу

Ночью там закрыто, а днем не пускают уже :(

>p.s. да да, я прогуливал математику в школе

Видимо, я тоже :)

Поэтому кроме вычисления всего предыдущего ряда решение только для больших чисел в голову приходит, когда отношение последующих чисел стремится к золотому сечению.

Предлагаю сделать аппаратную реализацию. берем выфера и 220 вольт и тренируем. говорим число из ряда и даем тридцать секунд отдыху, если не называет предыдущее - разряд, называет - орешек. Вот и все проблемы.

Кога числа дойдут до 6ти знаков, я разорюсь на оплате счетов за электричество...

А чего, золотое сечение вроде работает !

>А чего, золотое сечение вроде работает !

Да, но не для первых чисел.

Можно, конечно, тупо - если N < 10 (грубо, я не помню, с какого там формула N-го числа работать начинает), то циклом и перебором, иначе - по соотношению чисел :)

...

А так - меня поразило в своё время, в сколь многих сферах золотое сечение находится, но окончательно добили в этом направлении - именно числа Фибоначчи :)

> узнать два предыдущих числа из ряда

зная два следующих числа (x[n], x[n+1) ?

решаешь линейную систему
x[n] = x[n-1] + x[n-2]
x[n+1] = x[n] + x[n-1]

>зная два следующих числа

А если только одно? :)

http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A4%D0%B8%D0%B...

http://img-fotki.yandex.ru/get/3207/fork-posix.0/0_1cd3b_a5ca2e05_orig

Но это тот ещё гемор, конечно. Гораздо проще оценить число n, просто учитывая асимптотику числа Фибоначчи: F_n ~ \frac{(\frac{1+\sqrt{5}}{{2})^n}{\sqrt{5}}. Т.е. n ~ log(AFn)/log((1+A)/2), где A = sqrt (5), Fn - n-ое число Фибоначчи. Потом просто проверить ближайшие числа n на совпадение с Fn и всё.

> А если только одно? :)

в общем случае -- обращать общую формулу, наверное

Рекурсивно?

Логически - делишь число пополам. Первое предидущее больше этого числа а второе меньше

При n->inf соотношение стремится к известному золотому сечению - через него и узнаёшь. Так как вычисленные значения будут дробными - просто округляешь их до ближайшего целого. Вроде так можно.

>быстро

Как быстро?

По формуле Бине можно узнать любые (и предыдущие) числа в ряду. Хотя это, конечно, читерство.

>A = sqrt (5)

Чего только не придумают люди, незнакомые с (1+sqrt(5))/2 :)

> Чего только не придумают люди, незнакомые с (1+sqrt(5))/2 :)

я скорее всего больше вас знаю про \frac{1+\sqrt{5}}{2}, да там было два использования \sqrt{5} - поэтому использовал именно A=\sqrt{5}.

> http://img-fotki.yandex.ru/get/3207/fork-posix.0/0_1cd3b_a5ca2e05_orig

сейчас посмотрел, повтыкал - решение правильное и единственное (и существует по способу построения уравнения). Просто потому что дискриминант полученного квадратного уравнения будет равен 5c^2 + 4*(-1)^n, т.е. получатся два числа с разницей 8. Нам нужно, чтобы дискриминант был квадратом целого числа, а квадраты целых чисел не могут различаться на 8 => только один из вариантов n - чётн. или нечётн. будет правильным. Потом, x = 1/2*(-с+/-sqrt(D)). Т.к. c>0, то подходит только случай x=1/2*(-c+sqrt(D)) => только одно решение.

testSquare :: Integer -> Bool
testSquare i = floor (sqrt (fromInteger i))^2 == i

norm_discr :: Integer -> Integer
norm_discr c = floor (sqrt (fromInteger ( if testSquare a then a else (5*c^2+4))))
where a = 5*c^2 - 4

prevs :: Integer -> (Integer, Integer)
prevs c = (c - x, x)
where
x = (-c + norm_discr c) `div` 2

testSquare :: Integer -> Bool
testSquare i = floor (sqrt (fromInteger i))^2 == i

norm_discr :: Integer -> Integer
norm_discr c = floor (sqrt (fromInteger ( if testSquare a then a else (5*c^2+4))))
    where a = 5*c^2 - 4

prevs :: Integer -> (Integer, Integer)
prevs c = (c - x, x)
    where
      x = (-c + norm_discr c) `div` 2

fib n = take n fibs
    where
      fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

ну и map prevs (fibs 100)

ну или на питоне:

from math import sqrt

testSquare = lambda i: int (sqrt (i))**2 == i

norm_discr = lambda c: 5*c**2-4 if testSquare (5*c**2-4) else 5*c**2+4

def prevs (c):
    x =  (-c + norm_discr (c)) / 2
    return (c - x, x)

def fib (n):
    return fib(n-1)+fib(n-2) if n > 1 else (1 if n == 1 else 0)

Какие тут все умные!
ЗЫ. Фибоначчи это кто? И от куда у него числа?

> а квадраты целых чисел не могут различаться на 8

ошибся, могут, но только в случае 1 и 9 - достаточно добавить требование F_{n+1} > 1 (а иначе задача будет иметь неединственное решение - в последовательности Фибоначчи есть два числа 1).