Les suites de nombres
Une suite est une liste de nombres construite avec une règle : chaque terme se calcule à partir des précédents. Les boucles sont faites pour ça.
La somme des premiers entiers
Que vaut 1 + 2 + 3 + ... + 100 ? Avec un accumulateur :
total est un nombre vaut 0
pour i de 1 à 100
total ajoute i
fin pour
affiche total // 5050
Le mathématicien Gauss aurait trouvé la réponse à 9 ans, sans boucle, avec une formule : n × (n + 1) / 2. Vérifions que les deux méthodes s'accordent :
n est un nombre
demande 'Jusqu’à quel nombre ? ' dans n
total est un nombre vaut 0
pour i de 1 à n
total ajoute i
fin pour
affiche 'Avec la boucle : ' + total
affiche 'Avec la formule : ' + (n * (n + 1) / 2)
La formule donne le résultat en un seul calcul, même pour un milliard. Quand elle existe, une formule bat toujours une boucle !
La suite de Fibonacci, avec une boucle
Chaque terme est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13... On garde en mémoire deux termes, que l'on fait glisser à chaque tour :
precedent est un nombre vaut 0
courant est un nombre vaut 1
suivant est un nombre
affiche precedent
affiche courant
pour i de 3 à 10
suivant vaut precedent + courant
affiche suivant
precedent vaut courant
courant vaut suivant
fin pour
Le programme affiche les 10 premiers termes : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
Les trois lignes du milieu sont le cœur de l'algorithme :
- on calcule le terme suivant ;
- l'ancien
courant devient precedent ; - le nouveau terme devient
courant.
Question : Dans la suite de Fibonacci, quel terme vient après 21 et 34 ? — 55. Chaque terme est la somme des deux précédents : 21 + 34 = 55.
La conjecture de Syracuse
Voici une suite toute simple qui résiste aux mathématiciens depuis près d'un siècle. On part d'un nombre entier, puis :
- s'il est pair, on le divise par 2 ;
- s'il est impair, on le multiplie par 3 et on ajoute 1.
Et on recommence. Curieusement, on finit toujours par tomber sur 1... mais personne n'a jamais réussi à prouver que c'est vrai pour tous les nombres !
terme est un nombre
demande 'Nombre de départ ? ' dans terme
etapes est un nombre vaut 0
tant que terme <> 1
si terme mod 2 = 0 alors
terme vaut terme / 2
sinon
terme vaut terme * 3 + 1
fin si
affiche terme
etapes ajoute 1
fin tant que
affiche 'Arrivé à 1 en ' + etapes + ' étapes.'
En partant de 6, on obtient 3, 10, 5, 16, 8, 4, 2, 1 : 8 étapes. Essaie avec 27 : il faut 111 étapes, et la suite monte jusqu'à 9 232 avant de redescendre !
Ici, on ne sait pas à l'avance combien de tours il faudra : c'est donc un tant que.
Quel départ donne le plus long voyage ?
Rangeons le calcul dans une fonction, puis cherchons le record parmi les nombres de 1 à 30 :
fonction dureeVol(depart)
terme est un nombre vaut depart
etapes est un nombre vaut 0
tant que terme <> 1
si terme mod 2 = 0 alors
terme vaut terme / 2
sinon
terme vaut terme * 3 + 1
fin si
etapes ajoute 1
fin tant que
retourne etapes
fin fonction
record est un nombre vaut 0
champion est un nombre vaut 1
pour i de 1 à 30
si dureeVol(i) > record alors
record vaut dureeVol(i)
champion vaut i
fin si
fin pour
affiche 'Record : ' + champion + ' avec ' + record + ' étapes'
Le gagnant est 27, avec ses 111 étapes. On retrouve la recherche du maximum, appliquée au résultat d'une fonction.
En résumé
- Une suite se calcule terme après terme, avec une boucle.
- Il suffit souvent de garder en mémoire un ou deux termes, pas toute la suite.
- Une formule, quand elle existe, remplace toute une boucle.
- Certaines questions très simples à programmer n'ont toujours pas de réponse mathématique.
