UP | HOME

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\).

  • Programmez la fonction u(n) par récurrence et afficher la liste des termes de 0 à 10.
  • Reprogrammez-la par une boucle.
  • Quel est le coût du calcul de cette liste en fonction de N ?
  • Reprogrammez la fonction u(n) sous la forme d’une mémo-fonction, qui se souvienne des calculs qu’elle a déjà effectués.

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).

Created: 2023-08-23 mer. 14:41