Une suite récurrente.
On définit une suite Q par \( Q(0)=0, Q(1)=1, Q(2)=1 \) et pour tout entier n ≥ 3 : \( Q(n)=Q(n-Q(n-1))+Q(n-Q(n-2))\)
Déterminer la somme \( S=\sum_{j=2014}^{2500} Q(j) \)
c'est à dire \(S=Q(2014)+Q(2015)+...+Q(2500)\).
Il s'agit d'une énigme du site Pydéfis.
On détermine les valeurs successives de la suite à l'aide d'une liste.
def listeTermes(n) :
q = [0,1,1] # liste [Q(0),Q(1),Q(2)]
for j in range(3,n+1) :
q.append(q[j-q[j-2]]+q[j-q[j-1]])
return q
L = listeTermes(12)
for j in range(13) :
print('Q({}) = {}'.format(j, L[j]))
ce qui donne :
Q(0)=0 Q(1)=1 Q(2)=1 Q(3)=2 Q(4)=3 Q(5)=3 Q(6)=4 Q(7)=5 Q(8)=5 Q(9)=6 Q(10)=6 Q(11)=6 Q(12)=8
On peut maintenant calculer la somme demandée :
def listeTermes(n) :
q = [0,1,1]
for j in range(3,n+1) :
q.append(q[j-q[j-2]]+q[j-q[j-1]])
return q
L = listeTermes(2500)
s = 0
for j in range(2014,2501) :
s += L[j]
print(s)
Ce que l'on peut abréger en :
def listeTermes(n) :
q = [0,1,1]
for j in range(3,n+1) :
q.append(q[j-q[j-2]]+q[j-q[j-1]])
return q
L=listeTermes(2500)
print(sum(L[2014: ]))
La somme obtenue : 551207.
Triangle étoilé.
Écrire un programme qui :
- demande à l'utilisateur un entier n > 0,
- puis affiche un triangle d'étoiles, suivant le modèle des exemples ci-dessous.
Avec n = 4 :
* *** ***** *******
Avec n = 7 :
*
***
*****
*******
*********
***********
*************
Le triangle comporte donc n lignes, la première compte une étoile, chaque ligne compte deux étoiles de plus que la précédente.
Une première version a été vue dans les exercices sur les chaînes de caractères.
Il est demandé ici une autre version qui cherchera à calculer chaque ligne en fonction de la ligne précédente.
Pour cela, on remarquera qu'une ligne est constituée de 2n-1 caractères (* ou espace). Et, pour chaque caractère de la ligne :
- Si le caractère est une étoile, le caractère de même indice de la ligne suivante sera aussi une étoile.
- Si le voisin de gauche du caractère (lorsqu'il existe) est une étoile, le caractère de même indice de la ligne suivante sera aussi une étoile.
- Si le voisin de droite du caractère (lorsqu'il existe) est une étoile, le caractère de même indice de la ligne suivante sera aussi une étoile.
- Dans les autres cas, le caractère de même indice de la ligne suivante sera une espace.
def lg(n) :
""" n est un entier strictement positif.
La fonction retourne un entier égal à la longueur des lignes
du triangle, c'est à dire 2n-1. """
return 2*n-1
def voisinage(j, n):
""" j est un entier compris entre 0 et lg(n)-1.
C'est l'indice d'un caractère constituant une ligne
du triangle (une ligne étant de type str).
La fonction retourne la liste des indices des
caractères voisins dans la chaîne ligne,
un voisin étant ici le caractère gauche lorsqu'il existe,
le caractère droit lorsqu'il existe,
et le caractère d'indice j lui-même."""
if j == 0 :
return [0,1]
if j == lg(n)-1 :
return [lg(n)-2, lg(n)-1]
return [j-1,j,j+1]
def etoileChezUnVoisin(j, ligne) :
""" j est un entier compris entre 0 et lg(n)-1.
C'est l'indice d'un caractère constituant ligne,
qui est une ligne du triangle (de type str).
La fonction retourne True si un voisin de ligne[j]
est une étoile et retourne False sinon."""
for v in voisinage(j,n) :
if ligne[v] == '*' : return True
return False
def ligneSuivante(ligne) :
""" ligne est une chaîne de caractères,
ligne du triangle.
La fonction retourne la chaîne de caractères
correspondant à la ligne suivante du triangle."""
nvligne=''
for j in range(len(ligne)) :
if etoileChezUnVoisin(j, ligne) :
nvligne += '*'
else :
nvligne += ' '
return nvligne
def ligneDepart(n) :
""" n est un entier strictement positif.
La fonction retourne la première ligne (type str)
du triangle de n lignes."""
return ' '*(n-1)+'*'+' '*(n-1)
def triangleEtoiles(n) :
""" n est un entier strictement positif.
La fonction retourne le triangle (type str)
de n lignes."""
ligne=ligneDepart(n)
triangle = ''
for k in range(n) :
triangle += ligne+'\n'
ligne=ligneSuivante(ligne)
return triangle
n=int(input('Nombre de lignes : '))
print(triangleEtoiles(n))