J'essaie de trouver le dernier chiffre de la Somme de la série Fibonacci. Je calcule la somme comme f (n + 2) - 1 . Le code ci-dessous fonctionne bien, mais il est lent pour les nombres volumineux (E.g 99999 ).
Comment puis-je optimiser cela?
5 Réponses :
Voici le code optimisé spécifiquement pour le dernier chiffre:
def fib(n):
a, b = 0, 1
r = 1
if n < 1:
return 0
for i in range(n - 1):
a, b = b, (a + b)%10
r += b
r %= 10
return r
La série de chiffres finaux des numéros de fibonacci répète avec un cycle de 60. Par conséquent, vous pouvez optimiser le calcul de la somme de n termes à sortie: f ((n + 2)% 60) - 1 . De plus, pour rester dans la gamme INTEGER, vous ne pouvez conserver que le dernier chiffre de chaque terme:
Regardez sur cette table: http: //www.maths.surrey.ac.uk/hosted-Sites/r.knott/fibonacci/fibtable.html
remarquez que fib (60) dernier chiffre est 0 et fib (61) dernier chiffre est 1 , c'est-à-dire identique à fib (0) et fib (1) , démarrant donc à 60 Derniers chiffres commence à répéter. Vous pouvez donc calculer le dernier chiffre pour FIB (N% 60) plutôt que FIB (N) .
Par exemple, le dernier chiffre est identique pour fib (115) et fib (55) et égal à 5 . . .
Essayez d'utiliser le PIISANO PIÈCE PROPRIÉTÉ . Si vous souhaitez calculer le dernier chiffre, la période de pisano de 10 sera 60. Connaissant cela, vous pouvez avoir une fonction similaire à: pour plus d'informations, voir SAVERIOGZZ GITUB CS_CURRICULUM Repo . Bravo!
Voici un programme C ++ simple
//outputs last digit of ( sum of fib number till n)
#include<iostream>
using namespace std;
int64_t fib_sum_digit(int64_t n)
{
int fl[60] ={0};
fl[0] = 0;
fl[1] = 1;
// int64_t sum60 = 1;
for(int i = 2 ; i<60 ; i++)
{
fl[i] = (fl[i-1] +fl[i-2])%10 ;
//sum60 += fl[i];
}
int64_t sum = 0;
// sum += (sum60*(n/60)); ///sum60%10 always = 0 ;
for(int i = 1; i<=(n%60); i++ )
{
sum += (fl[i]);
//cout<<i<<","<<sum<<"->"; ///debug
}
return sum%10;
}
int main()
{
int64_t n;
cin>>n;
int64_t ans = fib_sum_digit(n);
cout<<ans;
return 0;
}
La séquence Fibonacci se développe très rapidement (exponentiellement), ce qui provoque le recours à Python sur des types de précision arbitraires. Vous aurez besoin de règles mathématiques MODULO pour conserver les chiffres dans une gamme d'entiers de 32/64 bits.
Il y a un moyen ... Vérifiez ma réponse ci-dessous.