Travaux Pratiques #6
Algo & Prog avec R

Recherche simple

Recherche à partir d’une position

• Avec une boucle.
  

  MaxFrom <- function(x, i = 1) {
    vmax <- -Inf
    j <- max(i,1)
    while(j <= length(x)) {
        if(x[j] > vmax) {
          vmax <- x[j]
        }
        j <- j + 1
      }
    return(vmax)
  }
  

  print(MaxFrom(c(), 1))
  x <- sample(1:100, 6, replace = TRUE)
  print(x)
  print(MaxFrom(x,0))
  print(MaxFrom(x,4))
  print(MaxFrom(x,7))
  

  [1] -Inf
  [1] 51 57 98 30 19 75
  [1] 98
  [1] 75
  [1] -Inf

• Avec des fonctions prédéfinies. Indices : tail et max.
  

  MaxFrom <- function(x, i = 1) {
    if(i > 1) {
      x <- tail(x,-i+1)
    }
    return(max(x))
  }
  

  print(MaxFrom(c(), 1))
  print(MaxFrom(x,0))
  print(MaxFrom(x,4))
  print(MaxFrom(x,7))
  

  [1] -Inf
  Warning message:
  In max(x) : aucun argument pour max ; -Inf est renvoyé
  [1] 98
  [1] 75
  [1] -Inf
  Warning message:
  In max(x) : aucun argument pour max ; -Inf est renvoyé

Recherche de la valeur et de la position

• Avec une boucle.
  

  MaxAndIdx <- function(x) {
      imax=0;
      vmax=-Inf
      for (i in seq_along(x)) {
        if(x[i] > vmax) {
          imax=i;
          vmax=x[i];
        }
      }
      return (c(vmax, imax))
    }
  

  x <- runif(6);
  print(x)
  print(MaxAndIdx(x))
  

  [1] 0.2560613 0.7291801 0.5234866 0.2992518 0.3504035 0.4288227
  [1] 0.7291801 2.0000000

• Avec des fonctions prédéfinies. Indice : which.max.
  

  MaxAndIdx <- function(x) c(max(x), which.max(x))
  

  print(MaxAndIdx(x))
  

  [1] 0.7291801 2.0000000

• Attention, l’affichage facilite la lecture, mais peut induire en erreur sur le type des données.
  

  x <- c(0, 0.25, 0.5)
  print(x)
  print(x[-2])
  print(x[1])
  print(typeof(x[1]))
  

  [1] 0.00 0.25 0.50
  [1] 0.0 0.5
  [1] 0
  [1] "double"

Recherche des k plus grands éléments.

• Programmez une fonction avec une boucle Max2(x) prenant un vecteur x numérique, et retournant le couple des deux plus grands éléments de x, le maximum étant en première position.
  

  Max2 <- function(x) {
    v1=-Inf
    v2=-Inf
    for (v in x) {
      if(v > v1) {
        v2 <- v1
        v1 <- v
      } else if(v > v2) {
        v2 <- v
      }
    }
    return(c(v1,v2))
  }
  

  print(Max2(c()))
  x <- runif(6);
  print(x)
  print(Max2(x))
  

  [1] -Inf -Inf
  [1] 0.6031135 0.1285228 0.3853113 0.7070992 0.7411141 0.9772133
  [1] 0.9772133 0.7411141

• Programmez une fonction avec une boucle Kmax(x, k) prenant un vecteur x numérique, et retournant les k plus grands éléments de x triés par ordre non croissant. Indices : inspirez-vous du tri par sélection.
  
• Reprogrammez une fonction Kmax(x, k) avec des fonctions prédéfinies. Indices : sort et head.
  

  Kmax <- function(x, k) {
    k <- max(0,k)
    return( head( sort(x, decreasing = TRUE), k) )
  }
  

  x <- sample(1:100, 6, replace = TRUE)
  print(x)
  print(Kmax(x, 0))
  print(Kmax(x, 2))
  print(Kmax(x, 4))
  print(Kmax(x, 7))
  

  [1] 40 25 25 37 97 56
  integer(0)
  [1] 97 56
  [1] 97 56 40 37
  [1] 97 56 40 37 25 25

Nombres non multiples d’un entier k

NoMult <- function(k,a,b) {
  x <- a:b;
  return(x[ x %% k != 0])
}

NoMult(5,10,30)

[1] 11 12 13 14 16 17 18 19 21 22 23 24 26 27 28 29

NoMult <- function(k,a,b) Filter(function(n) n %% k != 0 , a:b)

NoMult(2,11,31)

[1] 11 13 15 17 19 21 23 25 27 29 31

Nombres premiers avec un entier k   HARD

• Programmez une fonction CoPremiers(k,a,b) retournant le vecteur des entiers copremiers avec k dans l’intervalle [a,b].
  

  CoPremiers <- function(k,a,b) {
      k <- abs(k)
      ## Le plus simple est de créer un vecteur des diviseurs possibles allant de 2 à k.
      if(k < 2) return(numeric(0))
      ## Mais, on va éliminer les nombres multiples de 2 ou 3.
      divk <- c(2, 3)
      ## En utilisant la congruence à 6, ils ont la forme 5 + 6k
      if(k >= 5) divk <- c(divk, seq(5, k, 6))
      ## ou 1 + 6k
      if(k >= 7) divk <- c(divk, seq(7, k, 6))
  
      ## On trouve les diviseurs de k parmi les candidats de divk.
      divk <- divk[ k %% divk == 0]
      ## Un nombre n est copremiers avec k si il n'a aucun diviseur commun avec k.
      Filter(function(n) all(n %% divk != 0), a:b)
  }
  

  CoPremiers(15,10,30)
  

  [1] 11 13 14 16 17 19 22 23 26 28 29

• Programmez une fonction CoPremiersPGCD(k,a,b) avec les mêmes spécifications, mais utilisant une fonction auxiliaire calculant le pgcd de deux entiers de manière itérative.
  

  PGCD <- function(a,b) {
      while ( b != 0 ) {
          tmp = a %% b
          a = b
          b = tmp
      }
      return(a);
   }
  CoPremiersPGCD <- function(k,a,b) Filter(function(n) PGCD(n,k) == 1 , a:b)
  

• Programmez une fonction TestCoPremiers(func, n) qui affiche le résultat des tests de performance de catégorie n (à définir) pour la fonction func passée en paramètre. Comparer les performances des deux fonctions. Quelle est la plus efficace en théorie ? En pratique ?
  

  TestCoPremiers <- function(func, n) {
      for(k in 10**seq(n)) {
          for(a in 10**seq(n)) {
              func(k, a, 10 * a)
          }
      }
  }
  for(n in seq(3)) {
      cat("n=", n, "\n")
      cat("Avec vectorisation\n")
      print(system.time(TestCoPremiers(CoPremiers, n)))
      cat("Avec pgcd\n")
      print(system.time(TestCoPremiers(CoPremiersPGCD, n)))
  }
  

  n= 1
  Avec vectorisation
  utilisateur     système      écoulé
        0.009       0.000       0.009
  Avec pgcd
  utilisateur     système      écoulé
        0.002       0.000       0.003
  n= 2
  Avec vectorisation
  utilisateur     système      écoulé
        0.001       0.000       0.002
  Avec pgcd
  utilisateur     système      écoulé
        0.005       0.000       0.005
  n= 3
  Avec vectorisationy
  utilisateur     système      écoulé
        0.025       0.000       0.025
  Avec pgcd
  utilisateur     système      écoulé
        0.054       0.000       0.054