Travaux Pratiques #8
Algo & Prog avec R
Table des matières
1. Memo-Fonctions
Une récurrence simple
On considère la suite définie par récurrence de la manière suivante : \(u_0=2\) et \(u_n = \frac{1}{2} u_{n-1} + 3\).
Coefficients binomiaux
Vous connaissez tous le Triangle de Pascal [sinon : Google!]. Il est bâti sur les coefficients \(C_n^p\) et se construit à la main par des additions :
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ...
Autrement dit : \[ C_n^p = C_{n-1}^p + C_{n-1}^{p-1} \qquad (10 = 4 + 6 = 6 + 4) \] Nous nous proposons de programmer la fonction binomial(n,p)
retournant \(C_n^p\).
- Vérifiez que la fonction ci-dessous conduit à une pauvre programmation.
Demandez par exemple à calculer \(C_5^3\), puis \(C_{52}^{13}\) qui représente le nombre de mains de 13 cartes parmi 52 au bridge.
- Programmez
binomial
sous la forme d’une mémo-fonction qui se souvient des calculs déjà effectués. Vérifiez qu’alors le calcul de \(C_{52}^{13}\) est immédiat ! - Faîtes afficher le Triangle de Pascal jusqu’à la ligne 10 incluse. Tâchez d’avoir des colonnes bien alignées !
- N.B. Il existe une autre formule pour \(C_n^p\), basée sur des factorielles et utilisée en combinatoire :
\[ C_n^p = \frac{n!}{p!(n-p)!} \] Vous pouvez la programmer en R, en vous posant quand même la question : ne suis-je pas en train de faire trop de multiplications ?
2. Jeu de Nim (Fibonacci) HARD
La page de Jean-Paul Dalavan peut vous aider.
Décomposition de Zeckendorf
Étant donné un entier naturel \(n\), déterminer la liste des facteurs de la décomposition de Zeckendorf de \(n\), c’est-à-dire les uniques nombres de Fibonacci deux à deux distincts et non consécutifs de somme égale à \(n\)
Jeu de Nim
Deux joueurs tirent à tour de rôle des allumettes d’une boîte, avec les règles suivantes :
- Chaque joueur tire à chaque fois au moins une allumette.
- Le premier joueur ne retire pas la totalité des allumettes au premier tour.
- Un joueur tire au plus deux fois le nombre d’allumettes tirées par le joueur précédent.
- Le joueur qui retire la dernière allumette a gagné.
On peut montrer que si le nombre initial d’allumettes n’est pas un nombre de Fibonacci, une stratégie gagnante pour le joueur 1 consiste à tirer autant d’allumettes que le plus petit terme de la décomposition de Zeckendorf du nombre d’allumettes.
Écrire une fonction prenant en argument un entier n
(nombre d’allumettes), et mettant en place la stratégie gagnante si c’est possible (on alternera le jeu de l’ordinateur, qui commence, et le jeu de l’utilisateur, à qui on demandera une valeur, en précisant dans quel intervalle il a le droit de tirer).