Consignes

Vous devrez soumettre votre travail (un unique fichier Caml valide) en utilisant l'interface TPLab.

Le seul fait que votre programme fonctionne ne suffit pas pour avoir une bonne note. Les points suivants seront pris en compte :

  1. la lisibilité de votre programme (choix pertinent pour les noms de variables etc.),
  2. la présence de commentaires aux endroits appropriés,
  3. ...

Attention : les points suivants ne rapportent rien, mais ne pas les respecter pourra retrancher jusqu'à 10 points sur la note finale :

Liens utiles

1. la suite de Conway

La suite de Conway est la suite suivante : 

1
11
21
1211
111221
312211
13112221
...

Si vous ne connaissez pas cette suite, passez quelques minutes à essayer de deviner comment on la calcule avant de passer à la suite.

Pour calculer le terme suivant, on lit simplement le terme précédent :

Si on part avec le terme 777777778888888, on obtient : 

777777778888888
8778
182718
111812171118
3118111211173118
...

1.1. Première version

Programmez une fonction conway : int list -> int -> int list qui calcule le n-ème terme de la suite à partir d'une suite initiale d'entiers.

Attention : il est conseillé de découper votre code en plusieurs fonctions

La taille du terme de la suite semble augmenter à chaque étape.

Écrivez une fonction conway_croissance : int list -> int -> float list qui calcule la facteur de croissance de la suite.

Par exemple, conway_croissance [1] 7 donnera [2.; 1.; 2.; 1.5; 1.; 1.33333333] car la taille des sept premiers termes est 1, 2, 2, 4, 6, 6, 8.

Expérimentez et expliquez ce que vous constatez.

1.2. Version récursive terminale

Vérifiez que toutes vos fonctions sont récursives terminales. Si ce n'est pas le cas, écrivez des variantes de vos fonctions pour obtenir une fonction principale conway_term qui soit récursive entièrement récursive terminale.

Attention, cela signifie que toutes les fonctions auxiliaires doivent être récursives terminales. En même temps, essayez de ne pas être trop inefficace en temps...

2. la suite de Robinson

La suite de Robinson ressemble à la suite de Conway, à cela prêt qu'on compte le nombre total d'un chiffre dans la liste, et qu'on les compte par ordre croissant. Si on part de 1, cela donne: 

1
11
21
1112
3112
211213
312213
...

Par exemple, le passage de la ligne 3 à la ligne 4 se fait de la manière suivante : au total, 21 contient un 1 et un 2, soit 1112. La ligne 7 est obtenue par : 211213 contient trois 1, deux 2 et un 3, soit 312213.

2.1. Calcul et expériences

Programmez (de manière récursive terminale) la fonction robinson : int list -> int -> int list.

Calculez robinson [1] 1, robinson [1] 2, robinson [1] 3, ..., robinson [1] 50.

Que constatez-vous ?

Même question si on commence avec [6;7] au lieu de [1].

2.2. Variante

Comment pouvez-vous modifier votre code compter les nombre dans l'ordre décroissant ?

Que se passe-t'il ?

2.3. Calcul de la prépériode et de la période

La suite de Robinson est toujours ultimement périodique.

Programmer une fonction qui donne :

Attention : essayez de ne pas faire trop de calculs. Vous pouvez utilisez les propriétés suivantes :

  • lorsqu'on atteint la période, la taille du terme courant ne change plus,
  • la période est forcément 1, 2 ou 3.

3. Retour sur le crible d'Eratosthene (facultatif)

Reprogrammez le crible d'Eratosthene (fonction crible2 ou crible3 du tp2) en faisant attention à n'utiliser que des fonctions récursives terminales.