Сумма чисел Фибоначчи - PullRequest
Новая
       15

Сумма чисел Фибоначчи

2 голосов
/ 06 апреля 2011

Я нашел эту задачу здесь .

С учетом i-го (1 <= i <= 35) числа Фибоначчи F (i) вычислить сумму i-го до i+ 9-е число F (i) + F (i + 1) + ... + F (i + 9) и последняя цифра i + 246-го числа F (i + 246) </p>

Я пытался решить эту проблему, используя python и некоторые хитрости (формула Биннета и хитрое повторение): 

 f=lambda n:((1+5**.5)**n-(1-5**.5)**n)/(2**n*5**.5)
 exec"n=input();print int(55*f(n)+88*f(n+1)+f(n+6)%10);"*input()

, но мне пока не удавалось сжать мысль о том, что предел исходного кода, который составляет 111, и мой115, есть какие-нибудь подсказки, как улучшить мое решение?

Я довольно новичок в Python, поэтому любая помощь, приведшая к успешному решению, будет высоко оценена.

Спасибо,

Ответы [ 6 ]

5 голосов
/ 06 апреля 2011

Вы пытались использовать эту формулу суммы?

http://en.wikipedia.org/wiki/Fibonacci_number#Second_identity («Вторая личность»)?

2 голосов
/ 06 апреля 2011

f = lambda n,t=5**.5:((1+t)**n-(1-t)**n)/(2**n*t) и т. Д. Тратит 8 символов ,t=5**.5, чтобы получить 12: три лота 5**.5 -> t.Это экономия 4 символов, что, по-видимому, вам и нужно.

[РЕДАКТИРОВАТЬ, чтобы исправить опечатку;У меня было 2*n вместо 2**n в знаменателе.]

Вы можете сохранить еще несколько символов с другим поворотом в формуле Бине: f=lambda n:round((1+5**.5)**n/5**.5/2**n).

1 голос
/ 06 апреля 2011

Вот решение 110, хотя мне пришлось переписать формулу и использовать предложение @ Гарета: 

p=5**.5
f=lambda n:((1+p)**n-(1-p)**n)/(2**n*p)
exec "n=input();print int(f(n+11)-f(n+1)+f(n+6)%10);"*input()

Сохранение другого символа, 109 сейчас (манипулирование с n и избавление от +11): 

p=5**.5
f=lambda n:((1+p)**n-(1-p)**n)/(2**n*p)
exec "n=input()+6;print int(f(n+5)-f(n-5)+f(n)%10);"*input()

Редактировать: Новый способ вычисления определенного числа, сохраняет еще 4 символа и позволяет избежать int(): 

def f(n):exec"a=b=1;"+"a,b=b,a+b;"*(n-1);return a
exec "n=input()+6;print f(n+5)-f(n-5)+f(n)%10;"*input()
0 голосов
/ 06 октября 2011

Этот печатает ряд Фибоначчи до п. 

def fib(n):    
    a, b = 0, 1
    while a < n:
        print(a, end=' ')
        a, b = b, a+b
        print()
0 голосов
/ 06 апреля 2011 
p=5**.5
f=lambda n:((1+p)**n-(1-p)**n)/(2**n*p)
exec"n=input();print 55*f(n)+88*f(n+1)+f(n+6)%10;"*input()

106 символов, если вы не заботитесь о функции int () и принимаете значение с плавающей точкой

0 голосов
/ 06 апреля 2011

Извините, я не прочитал ваш вопрос должным образом перед публикацией. Я рад, что вы хотя бы нашли в этом пользу.

Я не знаю Python, но в Mathematica как можно более универсально: 

f[1] = 1;
f[2] = 1;
f[x_] := f[x] = f[x - 1] + f[x - 2]

t = 0;

n = 35;

For[i = 0, i <= 9, i++, t += f[n + i]]

t += f[n + 246] ~Mod~ 10

Или, вкратце, Mathematica, все еще без использования функции Fibonacci: 

f[1|2]=1;a:f@x_:=a=f[x-1]+f[x-2];Sum[f[#+x],{x,0,9}]+f[#+246]~Mod~10&
...