On connaît bien la suite de Fibonacci dans laquelle chaque terme d'indice \(n \ge 2\) est égal à la somme des deux termes précédents :
\[F_n = F_{n-1}+F_{n-2}\]
On s'intéresse dans cet exercice à une autre suite récurrente, un peu plus subtile, la suite de Hofstadter-Conway qui est définie par \(a_1 = a_2 = 1\) et, pour tout \(n \ge 3\) :
\[a_n = a_{a_{n-1}} + a_{n-a_{n-1}}\]
On remarque que le calcul de \(a_n\) fait intervenir le terme précédent, \(a_{n-1}\), en tant qu'indice. Pour calculer \(a_n\), il faut en effet additionner :
le terme d'indice \(a_{n-1}\)
et le terme d'indice \(n-a_{n-1}\).
On garantit que, pour tout entier naturel \(n\), on a \(n-a_{n-1}>0\).
Les premiers termes sont les suivants :
Rang \(n\)
\(1\)
\(2\)
\(3\)
\(4\)
\(5\)
\(6\)
\(7\)
Valeur\(a_n\)
\(a_1=1\)
\(a_2=1\)
\(a_3=2\)
\(a_4=2\)
\(a_5=3\)
\(a_6=4\)
\(a_7=4\)
Le calcul de \(a_7\) fait donc intervenir \(a_6=4\) en effectuant la somme de \(a_{a_6}=a_4\) et de \(a_{7-a_6}=a_{7-4}=a_{3}\). On obtient ainsi \(a_7=a_4+a_3=4\).
Écrire une fonction suite_hc prenant en paramètre un entier n>0 et renvoyant le n-ième terme de la suite de Hofstadter-Conway.
Dans cette version, les tests se limitent à de petites valeurs de \(n\), inférieures à \(100\). On pourra donc utiliser une approche récursive sans craindre de dépasser la profondeur de récursivité maximale (le plus souvent limitée à 1000 par défaut).
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Dans cette version, les valeurs de \(n\) peuvent être grandes, jusqu'à \(100~000\). Une approche récursive ne fonctionnera donc pas du fait d'une profondeur de récursivité trop importante.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)