J'ai une fonction, c'est-à-dire
f (n) = (2 * f (n-1)) - (2 * f (n-2)) Où f (0) = 0 et f (1) = 1
J'ai une liste (num_list). Comment vérifier si les éléments de num_list ont été générés par la fonction f (n). Où n> 1.
3 Réponses :
Vous pouvez analyser la fonction elle-même plutôt que d'utiliser une approche de force brute. En regardant wolfram, il devrait y avoir une condition pour vérifier s'il existe. En regardant les 13 premières valeurs:
[0,1,2,2,0, -4, -8, -8,0,16,32,32,0]
Je suppose que si vous regardez
log2 (abs (f (n))) -> [-, 0,1,1,2,3,3, -, 4,5,5, -]
Simplifié logiquement à [0,1,1,2,3,3,4,5,5] en ignorant les 0.
Nous avons donc un motif. Je pense que cela peut être résolu d'une manière où:
Donc, si le sqrt de abs (num) est un entier. Il est possible de faire partie du modèle. Nous avons ensuite besoin d'une vérification des valeurs si elles doivent être négatives ou positives.
Pour plus de détails: valeurs positives [0,1,1,4,5,5,8,9,9, ...] Valeurs négatives [2,3,3,6,7,7,10,11,11 ...]
On peut alors vérifier si n% 4 == 0 ou (n-1)% 4 == 0. Si cela est vrai et que la valeur d'origine est positive -> que oui, elle a été faite à partir de f (n) Si la valeur false et originale est négative -> également faite à partir de f (n)
sinon elle ne l'était pas.
import numpy as np
def test(x):
if x == 0 or x == 1:
return True
if x == -1 or x == -2:
return False
val = np.log2(abs(x))
if val%1==0:
if(val%4 == 0 or (val-1)%4==0) and x >0:
return True
elif (val%4!=0 and (val-1)%4 != 0) and x <0:
return True
else:
return False
else:
return False
Je ne donne aucune garantie que mes calculs correct. Je l'ai testé et semble fonctionner. Il peut y avoir des bogues mathématiques.
Le rsolve de Sympy peut être utilisé pour trouver une formule générale pour une récursion.
def is_in_the_squence(x):
if not isinstance(x, int):
return False
elif x == 0:
return True
else:
k = 0
while x != 1 and x != -1:
k += 1
if x % 2 != 0:
return False
x //= 2
return ( x == -1 and k % 4 >= 2) or ( x == 1 and k % 4 < 2)
Pour cette équation particulière, la solution implique des nombres imaginaires embêtants, et sympy a du mal à simplifier l'équation pour grand n. Pour des équations plus simples, soit s.subs (n, k) .simplify () ou s.subs (n, k) .evalf () devrait donner une réponse adéquate même pour un grand n.
Comme noté par @JasonChia, et étant donné que vous êtes seulement intéressé à savoir si un nombre peut être généré ou non, on pourrait aussi simplement regarder la séquence:
[0, 1, 2, 2, 0, -4, -8, -8, 0, 16, 32, 32, 0, -64, -128, -128, 0, 256, 512, 512, 0, -1024, -2048, -2048, 0, 4096, 8192, 8192, 0, ...]
Toutes les puissances de 2, accompagnées de 0, apparaissent mais sous forme de nombre positif ou négatif. Les nombres négatifs sont de la forme 2 k lorsque k mod 4 est égal à 2 ou 3. Et écrivez une fonction comme:
from sympy import rsolve, Function, log
from sympy.abc import n
f = Function('f', real=True)
T = f(n) - (2* f(n-1) - 2* f(n-2))
s = rsolve(T, f(n), {f(0): 0, f(1): 1})
print ("solution for n:", s)
'''I*((1 - I)**n - (1 + I)**n)/2'''
for k in range(10):
print(k, s.subs(n, k).simplify())
Il existe un moyen plus simple de tester si un nombre non nul est une puissance de 2; (x & (x-1)) == 0 . Vous pouvez donc tester ceci pour abs (x) , puis faire le test de signe séparément.
Il s'agit d'une relation de récurrence linéaire, donc f (n) peut être écrit sous une forme fermée. La relation de récurrence est:
f (n + 2) - 2f (n + 1) + 2f (n) = 0
Puisque le côté gauche est linéaire et le côté droit est zéro, il s'agit d'une forme plus simple du problème plus général de résolution d'une relation de récurrence linéaire: nous n'avons pas besoin de trouver une "solution particulière" à satisfait le côté droit, seule la "solution générale" suffit.
La solution générale peut être trouvée en résolvant l'équation f (n) = x n pour trouver les valeurs de x satisfaisant la relation de récurrence. En substituant et en simplifiant, nous obtenons l'équation quadratique:
x 2 - 2x + 2 = 0
Les solutions de cette équation sont les nombres complexes x = 1 + i et x = 1 - i où i est le unité imaginaire . Par linéarité, il s'ensuit que toute fonction de la forme
f (n) = a (1 + i) n + b (1 - i) n
est une solution; en substituant les conditions aux limites f (0) = 0 et f (1) = 1, on obtient a = −i / 2 et b = i / 2. Ainsi, l'expression de forme fermée pour f (n) est:
f (n) = (i / 2) ((1 - i) n - (1 + i) n )
Cela peut être réécrit en appliquant formule d'Euler , puisque nous connaissons f (n ) est toujours un nombre réel:
f (n) = (−1/2) (√2) n Im (e −nπ / 4 - e nπ / 4 ) = (√2) n sin (nπ / 4)
L'expression sin (nπ / 4) est la suite [0, 1 / √2, 1, 1 / √2, 0, −1 / √2, −1, −1 / √2,. ..] , qui se répète avec le point 8. Il s'ensuit que pour chaque entier naturel k, la séquence prend les valeurs:
Par conséquent, la fonction génère un nombre si et seulement s'il est de l'une de ces formes.
Je ne pense pas qu'il existe un moyen de faire cela pour des fonctions arbitraires.
Merci beaucoup pour votre commentaire.
La seule méthode à laquelle je puisse penser est une approche par force brute.
C'est vrai, mais qu'en est-il de la complexité temporelle, si n = 10 ^ 8, la fonction récursive prendrait des années pour la calculer.
Voici un exemple de séquence Lucas .