Travaux Pratiques #3
Algo & Prog avec R

Table des matières

1. Factorielles
2. Quelques fonctions prédéfinies pour les conversions
3. Épluchages d’entiers KEY
4. Jeu de hasard KEY
5. Algorithme d’Euclide UCANCODE
6. Représentation des nombres en machines

1. Factorielles

Les choix algorithmiques et d’implémentation que vous ferez influent sur la qualité du programme en terme de complexité et donc de vitesse d’exécution.

Fonctions factorielle

Programmez plusieurs fonctions prenant un entier positif n et retournant la factorielle n! de n. Par exemple, 5! est égal à 120.

Par récurrence, sous la forme d’une fonction FactRec(n), en supposant le problème résolu pour n-1. Vérifier FactRec(5) grâce à la fonction prédéfinie factorial.
Par une itération (boucle while) sous la forme d’une fonction Fact(n).
R est-il capable de calculer 1000! ?
Pour chronométrer un calcul en R, il suffit d’appeler la fonction system.time : system.time(replicate(1000,factorial(100))). Qui est le plus rapide entre Fact(100) et FactRec(100) ?

Petites factorielles

Ecrivez une fonction itérative AfficherFact() faisant afficher toutes les factorielles des entiers de 1 à 10, une par ligne.

En utilisant la fonction Fact ou FactRec, combien votre programme fera-t-il de multiplications ?
Sans utiliser cette fonction, tâchez de faire baisser le nombre de multiplications ! Combien votre programme fera-t-il de multiplications ?

2. Quelques fonctions prédéfinies pour les conversions

L’exercice suivant est un complément de cours. Cherchez la documentation sur les fonctions intToBits, strtoi, et as.hexmode.

Comment demande-t-on au toplevel R de voir l’écriture binaire (base 2) de 233 ? Que remarquez-vous ?

intToBits(233)

Sur papier, quel est le résultat de l’addition 11010 + 10111 en binaire ? Vérifiez votre réponse au toplevel.

strtoi("11010", base = 2) + strtoi("10111", base = 2)

Quelle est l’écriture hexadécimale (base 16) de l’entier qui s’écrit 164 en décimal ? Vérifiez-le au toplevel.

as.hexmode(164)

Sur papier, quel est le résultat de l’addition 3F + A2 en hexadécimal ? En binaire ? Vérifiez votre réponse au toplevel.

as.hexmode("3F") + as.hexmode("A2")
as.integer(as.hexmode("3F") + as.hexmode("A2"))

3. Épluchages d’entiers KEY

En utilisant l’idée d’épluchage d’un entier, programmez les fonctions suivantes.

Somme des chiffres d’un nombre

La fonction SomCh(n) prenant un entier n, et retournant la somme des chiffres de n en base 10.
```
SomCh(3456)
```
```
[1] 18
```
La fonction SomChBin(n) retournant cette fois la somme des chiffres de n en binaire.
```
SomChBin(3456)
```
```
[1] 4
```
Généraliser en une fonction SomCh(n, base) retournant la somme des chiffres du nombre pour une base quelquonque en ajoutant un second paramètre base.
```
as.hexmode(3456)
SomCh(3456, base = 16)
```
```
[1] "d80"
[1] 21
```

Renversement d’un nombre

La fonction Renverser(n) prenant un entier positif n et retournant l’entier obtenu en prenant les chiffres de n en sens inverse.
```
Renverser(3456)
Renverser(34560)
```
```
[1] 6543
[1] 6543
```

La fonction Renverser(n, base) prenant un entier positif n et retournant l’entier obtenu en prenant les chiffres de n en base b en sens inverse.

## 3456 en décimal devient 110110000000 en binaire
## qui se renverse en (0000000)11011 en binaire soit 27 en décimal
Renverser(3456, base = 2)
Renverser(as.hexmode("ABC"), base = 16)

[1] 27
[1] "cba"

4. Jeu de hasard KEY

Virginie lance trois dés numérotés de 1 à 6.

Si elle obtient une somme de 18, elle gagne 50 euros,
entre 10 et 17, elle gagne 5 euros,
sinon elle ne gagne rien.

Écrivez une fonction JeuHasard utilisant la fonction sample pour simuler un lancer de dés, puis renvoyant le gain.
Pour faire la somme des valeurs renvoyées par sample, utilisez la fonction sum ainsi : sum(sample(...)).
Écrire une simulation où Virginie joue jusqu’à ce que son gain total dépasse 50.
Quelle est la probabilité de gagner 50 euros ? Quelle est l’espérance de gain ? Proposer un tarif pour jouer à ce jeu ? Justifier.

5. Algorithme d’Euclide UCANCODE

Lisez le début de la page wikipedia du Plus Grand Diviseur Commun (PGCD), puis attentivement la section sur l’algorithme d’Euclide. Calculer le PGCD de 8 et 20 par la méthode soustractive, puis par divisions.

Nous allons implémenter plusieurs fonctions pour le calcul du PGCD de deux entiers relatifs. Nous utiliserons la définition du plus grand au sens de la divisibilité.

Méthode soustractive

Le PGCD de deux entiers a et b est aussi celui de a et de a - b.

Programmez une fonction récursive PgcdSubRec(a,b)
Programmez une fonction itérative PgcdSubIter(a,b)

La fonction TestPGCD effectue des tests simples pour vérifier que le résultat est correct.

TestPGCD <- function(pgcd) {
  system.time(
    stopifnot(
      pgcd(12,8) == 4,
      pgcd(8,12) == 4,
      pgcd(87,116) == 29
      ## Ajouter des tests
      ## ...
    ))
}

Il faut passer en paramètre la fonction à tester.

TestPGCD(PgcdSubRec)
TestPGCD(PgcdSubIter)

Ajouter des tests à la fonction pour vérifier des cas généraux (premiers entre eux ou pas, négatifs, etc) et des cas limites (0, 1, etc).

Méthode par divisions

Le PGCD de deux entiers a et b est aussi celui de a et du reste de la division de b par a.

Programmez une fonction récursive PgcdDivRec(a,b)
Programmez une fonction itérative PgcdDivIter(a,b)

N’oubliez pas de tester vos fonctions.

TestPGCD(PgcdDivRec)
TestPGCD(PgcdDivIter)

La fonction PerfPGCD mesure le temps total d’exécution d’une fonction pour des cas de test avec différents ordres de grandeur.

PerfPGCD <- function(pgcd) {
  n <- 2**seq(1, 31, 3)
  n <- c(n-1, n)
  df <- expand.grid(a = n, b = n)
  ## print(df) ## afficher les cas de tests
  system.time(apply(df, 1, function(x) pgcd(x[1], x[2])))
}

Comparez les performances des différentes fonctions et interprétez les résultats.

Fraction irréductible

Comment feriez-vous pour savoir si la fraction 51/85 est irréductible ? En d’autres termes, peut-on la simplifier ? Par combien ?

Programmez une fonction AfficherFraction(a,b) qui prend en paramètres deux entiers a et b représentant une fraction a/b et affiche sa fraction irréductible c/d.

Exercice UCAnCODE

Vous avez maintenant confiance dans la correction et l’efficacité de votre programme de calcul du PGCD. Allez résoudre l’exercice UCAnCODE !

6. Représentation des nombres en machines

La fonction typeof renvoie le type d’un objet.

typeof(2105)

[1] "double"

la reponse du « top level » est interessante.

Qu’est ce qu’un double en R ?
double fait partie des 6 basic atomic vector types de R. donc 2015 est un vector (des cellules contigues) d’une seule cellule.
Pourquoi ca rend double ?
Voir la réponse ici.

Comment travailler avec un entier ?

typeof(2015L)
 v <- 2015
 typeof(as.integer(v))

[1] "integer"
[1] "integer"

Comment sont représentés les entiers en machine ?
```
intToBits(2015)
```
```
[1] 01 01 01 01 01 00 01 01 01 01 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00
[26] 00 00 00 00 00 00 00
```
Les entiers sont représentés dans un système binaire (base 2). Le système binaire le plus courant est l’équivalent en base deux de la numération de position que nous utilisons en base dix dans la vie courante.
les objets de base de R sont les vecteurs.
Même un entier « tout seul » est représenté par un vecteur … d’une seule cellule. C’est comme ça : basic types ; expressions.

Travaux Pratiques #3Algo & Prog avec R