Calcul d'une suite récurrente d'ordre p (amateur)

Bonjour, quelqu'un(s) !

J'ai une vingtaine d'année et ait redécouvert Python il y a quelques jours. J'ai fait de mon mieux pour me reformer sur ce langage, mais j'ai un problème de calcul que je ne parviens pas à surmonter.
En fait, je voudrais composer un programme capable de résoudre la suite U(n+1) = U(n)*2 - U(n-p) avec p un entier naturel choisi par l'utilisateur et U(0) = 1.
J'arrive à lui faire calculer U(n+1) = U(n)*2 sans problèmes mais la deuxième portion de la soustraction me donne du fil à retordre. J'ai fait de mon mieux pour trouver une solution par les tutos, mais je suis est trop spécifique.
Est-ce que vous sauriez comment procéder ?

Citation:

---

Envoyé par Wend Offelag

Est-ce que vous sauriez comment procéder ?

---

Comment feriez vous en écrivant les premiers items de cette suite sur une feuille de papier?
Si vous ne savez pas faire ça comment arriver à le coder avec Python?
D'où pour l'instant, difficile de coder quoi que ce soit... et vous pouvez aller chercher de l'aide dans un forum de maths ou d'algorithmique.

- W

Bonjour

Les calculs de récurrence ne sont pas très compliqués avec Python, et ils sont même assez amusants.
Mais il y a quelque chose que je comprends pas dans l'énoncé et là, ce n'est pas de la programmation, mais des maths:

U(0)=1 et prenons p=10
U(1) = U(0)*2 - U(0-10)
Mais U(0-10) est inconnu?

L'obstacle au codage est donc pour l'instant purement mathématique.

Salut Tyrtamos,

Je profite de l'occasion pour vous souhaiter une bonne années et une bonne santé (et surtout la santé insiste-t-on dans mon coin).

Citation:

---

Envoyé par tyrtamos

L'obstacle au codage est donc pour l'instant purement mathématique.

---

papier-crayon disent que je sais calculer U_n+1 = U_n*2 - U_n-p pour tout n >= p pourvu que la valeur des p premiers éléments de la liste soit définie (comme la valeur 1 est définie pour U₀). Et pour l'instant, on n'a pas encore fait de maths, juste du français qui fait que le n dans l'écriture U_n est le numéro attribué au n^ième items et de ce fait positif ou nul.

Là où je fais des maths, c'est que je vais pouvoir écrire un algo. sans savoir ce que sont la valeur de ces p premiers items de la suite (j'en fait abstraction comme je peux travailler avec un concept comme un point de dimension nulle: inexistant, invisible,...).

On part des p premiers éléments de la suite U₀, U₁, ... U_p-1
pour en faire un tableau/list à p positions appelée T.
Du coup, le calcul de U_n+1 = U_n*2 - U_n-p pour n=p devient U_p = 2*T[-1] + T[0]
Avant de calculer le suivant, je met à jour T pour refléter les p derniers éléments de la suite: suppression du premier élément et ajout de U_p en dernière position.
Le calcul de U_p+1 sera alors de la même forme: 2*T[-1] + T[0]

Jusqu'ici, j'ai traité un des détails de la réalisation du calcul des termes de la suite pour p > 0. Quand on va coder, il faudra tenir compte de conditions aux limites du genre p = 0 ou bien calculer les n premiers items où n est inférieur à p. En ce qui me concerne, pas besoin de papier-crayon:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

def sequence(n=100, first_values=[]): p = len(first_values)   if p == 0: return [1, ] * n   if p > 0: assert first_values[0] == 1   if n <= p: return first_values[:n]   R = list(first_values) for _ in range(p, n): R.append(2*R[-1] - R[-p]) return R   if __name__ == '__main__': for z in range(2, 5): print(list(sequence(first_values=[1, z]))[-10:])

---

note: si on n'a pas fait le travail papier-crayon, ce code peut paraitre "difficile" à lire.

- W

Bonjour wiztricks

Bravo pour la tentative, mais il faut alors ajouter des données qui ne se trouvent pas dans l'énoncé initial.

Connaissant U(0)=1, il faut en plus connaître de U(1) à U(p), et la 1ère valeur calculable est U(p+1)=U(p)-U(p-p)

Si on n'ajoute pas ces données dans l'énoncé, comment calculer ces U(1)..U(p) ???

Citation:

---

Envoyé par tyrtamos

Connaissant U(0)=1, il faut en plus connaître de U(1) à U(p), et la 1ère valeur calculable est U(p+1)=U(p)-U(p-p)

---

Absolument... mais papier crayon suppose aussi d'aller regarder l'état de l'art sur ce que sont les suites linéaires d'ordre p (ça c'est des maths) qui sont définies en fixant les p premiers termes (de la même manière qu'on fixe ici U₀ = 1).

Après il y a du travail côté maths suivant ces valeurs initiales mais ça nous mène très loin du problème initial (calculer les n premiers items de la suite).

- W