Travaux Pratiques #3
Algo & Prog avec R

Fonctions factorielle

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

  FactRec <- function(n) {
    if(n > 1) return(FactRec(n-1) * n)
    else return (1)
  }
  cat('FactRec(0) =',FactRec(0), '\n')
  cat('FactRec(5) =',FactRec(5), '\n')
  

  FactRec(0) = 1
  FactRec(5) = 120

• Par une itération (boucle while) sous la forme d’une fonction Fact(n).
  

  Fact <- function(n) {
    acc <- 1;
    while(n > 1) {
      acc <- acc * n
        n <- n - 1
    }
    return(acc)
  }
  cat('FactRec(0) =',FactRec(0), '\n')
  cat('FactRec(5) =',FactRec(5), '\n')
  

  FactRec(0) = 1
  FactRec(5) = 120

• R est-il capable de calculer 1000! ?
  

  factorial(1000)
  

  [1] Inf

• 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) ?
  

  ## On apprendra plus tard à écrire une version vectorisée
  FactVec <- function(n) {
    return(prod(1:n))
  }
  cat('Test : FactRec(100)\n')
  system.time(replicate(2000, FactRec(100)))
  cat('Test : Fact(100)\n')
  system.time(replicate(2000, Fact(100)))
  cat('Test : FactVec(100)\n')
  system.time(replicate(2000, FactVec(100)))
  cat('Test : factorial(100)\n')
  system.time(replicate(2000, factorial(100)))
  

  Test : FactRec(100)
  utilisateur     système      écoulé
        0.166       0.000       0.165
  Test : Fact(100)
  utilisateur     système      écoulé
        0.011       0.000       0.011
  Test : FactVec(100)
  utilisateur     système      écoulé
        0.004       0.000       0.004
  Test : factorial(100)
  utilisateur     système      écoulé
        0.001       0.000       0.001
  

Petites factorielles

• En utilisant la fonction Fact ou FactRec, combien votre programme fera-t-il de multiplications ?
  

  cat('Voici les factorielles des entiers de [1,10] :\n')
  i <- 1
  while (i <= 10) {
    ## la boucle d'iteration effectue en tout 1+2+3+...+10 = 55 multiplications
    cat(i,'! =', Fact(i), '\n')
    i <- i + 1
  }
  ## Si l'on remplace 10 par N, on obtiendrait N(N+1)/2 multiplications, polynome du
  ## second degre. On dit que l'algorithme a un cout QUADRATIQUE. Pas fameux...
  

  Voici les factorielles des entiers de [1,10] :
  1 ! = 1
  2 ! = 2
  3 ! = 6
  4 ! = 24
  5 ! = 120
  6 ! = 720
  7 ! = 5040
  8 ! = 40320
  9 ! = 362880
  10 ! = 3628800
  

• Sans utiliser cette fonction. Tâchez de faire baisser le nombre de multiplications ! Combien votre programme fera-t-il de multiplications ?
  

  ## Si l'on veut faire tomber le nombre de multiplications, il ne FAUT PAS
  ## utiliser une fonction factorielle qui repart chaque fois du debut, mais maintenir
  ## dans une variable f la derniere factorielle calculee !
  AfficherFact <- function(n) {
    cat('Voici les factorielles (rapides) des entiers de [1,", n, "] :\n', sep = "")
    i <- 1
    acc <- 1
    while (i <= n) {
      ## la boucle effectue en tout 10 multiplications !!!
      cat(i,'! =', acc, '\n')
      i <- i + 1
      acc <- acc * i
    }
    ## Le cout d'affichage des factorielles des entiers de [1,N] est donc maintenant de N,
    ## le cout est devenu LINEAIRE. Difficile de faire mieux dans le cas present...
  }
  AfficherFact(10)
  

  Voici les factorielles (rapides) des entiers de [1,10] :
  1 ! = 1
  2 ! = 2
  3 ! = 6
  4 ! = 24
  5 ! = 120
  6 ! = 720
  7 ! = 5040
  8 ! = 40320
  9 ! = 362880
  10 ! = 3628800
  

Somme des chiffres d’un nombre

SomCh <- function(n, base=10) {
  n <- abs(n);
  base <- abs(base)
  acc <- 0;
  while(n > 0) {
    acc <- acc + n %% base;
    n <- n %/% base;
  }
  return(acc)
}

SomChBin <- function(n) SomCh(n, base = 2)

• 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

Renverser <- function(n, base = 10) {
  n <- abs(n);
  acc <- 0;
  while(n > 0) {
    acc <- acc * base + n %% base;
    n <- n %/% base;
  }
  return(acc)
}

• 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"

Méthode soustractive

PgcdSubRec <- function(a, b) {
  ExecPgcdSubRec <- function(a, b) {
    if(a > b) ifelse(b == 0, a, ExecPgcdSubRec(b, a))
    else ifelse(a == 0, b, ExecPgcdSubRec(a, b - a))
  }
  return(ExecPgcdSubRec(abs(a), abs(b)))
}

PgcdSubIter <- function(a, b) {
  a <- abs(a)
  b <- abs(b)
  if(a == 0) return(b)
  while(b != 0) {
    ## cat(a, b, "\n")
    if(b  >= a) {
      b <- b - a
    } else {
      a <- a - b
    }
  }
  return(a)
}

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

TestPGCD(PgcdSubRec)
TestPGCD(PgcdSubIter)

TestPGCD <- function(pgcd) {
  system.time(
    stopifnot(
      ## identité
      pgcd(12,12) == 12,
      ## non premiers entre eux
      pgcd(12,8) == 4,
      pgcd(8,12) == 4,
      ## nombres négatifs
      pgcd(-8,12) == 4,
      pgcd(8,-12) == 4,
      pgcd(-8,-12) == 4,
      ## premiers entre eux
      pgcd(27,64) == 1,
      pgcd(64,27) == 1,
      ## nombres négatifs
      pgcd(-64,27) == 1,
      pgcd(64,-27) == 1,
      pgcd(-64,-27) == 1,
      ## avec 1
      pgcd(64,1) == 1,
      pgcd(1,64) == 1,
      pgcd(1,1) == 1,
      ## avec 0
      pgcd(63,0) == 63,
      pgcd(0,63) == 63,
      pgcd(0,0) == 0
    ))
}

Méthode par divisions

PgcdDivRec <- function(a,b) {
  ExecPgcdSubRec <- function(a, b) ifelse(b == 0, a, PgcdDivRec(b, a %% b))
  ExecPgcdSubRec(abs(a), abs(b))
}

PgcdDivIter <- function(a, b) {
  a <- abs(a)
  b <- abs(b)
  while(b != 0) {
    ## cat(a, b, "\n")
    r <- a %% b
    a <- b
    b <- r
  }
  return(a)
}

TestPGCD(PgcdDivRec)
TestPGCD(PgcdDivIter)

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])))
}

PerfPGCD(PgcdDivRec)
PerfPGCD(PgcdDivIter)

utilisateur     système      écoulé
      0.025       0.000       0.025
utilisateur     système      écoulé
      0.006       0.000       0.006

Fraction irréductible

AfficherFraction <- function(a, b) {
  d <- PgcdDivIter(a, b)
  cat(sprintf("%d/%d = %d/%d\n", a, b, a/d, b/d))
}

AfficherFraction(58,87)

58/87 = 2/3

Exercice UCAnCODE