Non Brute Force Solution dla projektu Euler 25
Sekwencja Fibonacciego jest zdefiniowana przez relację powtarzania:
Fn = Fn-1 + Fn-2, gdzie F1 = 1 i F2 = 1. Stąd pierwsze 12 terminów to 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. kadencja, F12, jest pierwszym terminem zawierającym trzy cyfry.
Jaki jest pierwszy termin w sekwencji Fibonacciego zawierający 1000 cyfr?
Zrobiłem rozwiązanie brutalne w Pythonie, ale obliczenie rzeczywistego rozwiązania wymaga absolutnie zawsze. Czy ktoś może zaproponować rozwiązanie, które nie jest brutalne?
def Fibonacci(NthTerm):
if NthTerm == 1 or NthTerm == 2:
return 1 # Challenge defines 1st and 2nd term as == 1
else: # recursive definition of Fib term
return Fibonacci(NthTerm-1) + Fibonacci(NthTerm-2)
FirstTerm = 0 # For scope to include Term in scope of print on line 13
for Term in range(1, 1000): # Arbitrary range
FibValue = str(Fibonacci(Term)) # Convert integer to string for len()
if len(FibValue) == 1000:
FirstTerm = Term
break # Stop there
else:
continue # Go to next number
print "The first term in the\nFibonacci sequence to\ncontain 1000 digits\nis the", FirstTerm, "term."