Если кто не знает или не помнит они определяются так:

F1 = 1,
F2 = 1,
Fn = Fn−1 + Fn−2.

Например:

F1=1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

12-е число Фибоначчи состоит из 3 цифр. Какое число по номеру состоит из 1000 цифр?

Здравствуйте, vitaly_spb, Вы писали:

Отсюда?

Здравствуйте, vitaly_spb, Вы писали:

_>12-е число Фибоначчи состоит из 3 цифр. Какое число по номеру состоит из 1000 цифр?

Всё тот же Nemerle с IntX

Автор: Oyster
Дата: 23.03.05

:

using System.Console;
using Oyster.Math;

def fiboN(x, y, n)
{
    | (x, _, _) when x.ToString().Length == 1000 => n
    | _ => fiboN(x + y, x, n + 1)
};
WriteLine(fiboN(IntX(1), IntX(1), 2))

Выводит 4782.

К>Отсюда?

Да. Я заглянул, там большинство решили brute force'ом. А мне чего-то не хотелось. Впрочем, там все не сложно с учетом оценки n-го члена последовательности через золотое сечение.

> 12-е число Фибоначчи состоит из 3 цифр. Какое число по номеру состоит из 1000 цифр?

Брутфорсный ответ уже дали. Как это можно решить без брутфорса.

F(n) выражается через степень золотого сечения.
Решаем уравнение ]lg(F(n))[ = 100 или, по крайней мере, находим приближение.
Далее поиск в окресностях этого n.

Вот такой ход мысли.
Формулу навскидку не помню, поэтому запуляю только идею.
Доберутся руки — попробую.

Здравствуйте, Кодт, Вы писали:

К>F(n) выражается через степень золотого сечения.
К>Решаем уравнение ]lg(F(n))[ = 100 или, по крайней мере, находим приближение.
К>Далее поиск в окресностях этого n.

К>Вот такой ход мысли.
К>Формулу навскидку не помню, поэтому запуляю только идею.
К>Доберутся руки — попробую.

+1. Формула вроде в Кнуте была. Ещё можно числа считать за log(N) — тоже быстрее будет.

Здравствуйте, Кодт, Вы писали:

>> 12-е число Фибоначчи состоит из 3 цифр. Какое число по номеру состоит из 1000 цифр?

К>Брутфорсный ответ уже дали. Как это можно решить без брутфорса.

К>F(n) выражается через степень золотого сечения.
К>Решаем уравнение ]lg(F(n))[ = 100 или, по крайней мере, находим приближение.
К>Далее поиск в окресностях этого n.

К>Вот такой ход мысли.
К>Формулу навскидку не помню, поэтому запуляю только идею.
К>Доберутся руки — попробую.

http://www.research.att.com/~njas/sequences/A072353

Здравствуйте, Кодт, Вы писали:

К>Формулу навскидку не помню, поэтому запуляю только идею.

Кстати, можно было бы ускорить это дело даже без знания формулы. Собственно, можно было бы постепенно приближать...

> Кстати, можно было бы ускорить это дело даже без знания формулы. Собственно, можно было бы постепенно приближать...

Так ведь вычислять надо... а там примерно 100-значные числа...

Здравствуйте, Кодт, Вы писали:

К>Так ведь вычислять надо... а там примерно 100-значные числа...

Так и формула нам не даст точного ответа — всё равно надо будет делать "поиск в окресностях" и вычислять. Если мы об одном и том же, конечно...

Здравствуйте, vitaly_spb, Вы писали:

_>12-е число Фибоначчи состоит из 3 цифр. Какое число по номеру состоит из 1000 цифр?
Про брутфорс и вычисления написали.
А что если делать просто в long double? Наверняка точности хватит, т.к. числа очень быстро растут.

Здравствуйте, vitaly_spb, Вы писали:


_>12-е число Фибоначчи состоит из 3 цифр. Какое число по номеру состоит из 1000 цифр?

def digitcount(n):
    if n==0:
        return 1
    a=0
    while n>=1:
        n=(n-(n%10))/10;a+=1;
    return a

if __name__ == "__main__":
    a=1 
    b=1
    counter=2
    while digitcount(b)<1000:
        a,b=b,a+b
        counter+=1
    print counter

4782