UP | HOME

Travaux Pratiques #3
Algo & Prog avec R

Table des matières

1 Factorielles   KEY

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’importer la fonction system.time : system.time(replicate(1000,factorial(100))). Qui est le plus rapide entre Fact(100) et FactRec(100) ?

Petites factorielles

Ecrivez un programme itératif faisant afficher toutes les factorielles des entiers de 0 à 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, utf8ToInt, strtoi, et as.hexmode.

  1. Comment demande-t-on au toplevel R de voir l’écriture binaire (base 2) de 233 ? Que remarquez-vous ?
intToBits(233)
  1. 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)
  1. 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)
  1. 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

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.

5 Algorithme d’Euclide

L’algorithme d’Euclide pour calculer le PGCD de deux entiers a et b ≥ 0 consiste à appliquer les deux règles suivantes :

  • si b = 0, le PGCD de a et de b est a
  • sinon, le PGCD de a et b est le même que celui de b et du reste de la division de a par b

6 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 ?

Indice : calcul du pgcd par la méthode soustractive ou encore mieux avec l’algorithme d’euclide.

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

Created: 2021-09-09 jeu. 16:58