Travaux Pratiques #7
Algo & Prog avec R
Table des matières
1. Ensembles et Dictionnaires
Ensemble d’entiers aléatoires
- Définissez deux ensemble
e2
ete3
de 10 entiers aléatoires de [0,20]. - Faites afficher la réunion, l’intersection, la différence asymétrique, et la différence symétrique de
e2
ete3
.
e2 <- sample(0:20, 10, replace=FALSE) e3 <- sample(0:20, 10, replace=FALSE) print(e2) print(e3) union(e2,e3) intersect(e2,e3) setdiff(e2,e3) union(setdiff(e2,e3),setdiff(e3,e2))
[1] 17 7 11 4 20 0 12 13 16 1 [1] 12 20 14 0 16 10 13 3 18 15 [1] 17 7 11 4 20 0 12 13 16 1 14 10 3 18 15 [1] 20 0 12 13 16 [1] 17 7 11 4 1 [1] 17 7 11 4 1 14 10 3 18 15
Histoire de s’amuser !
Supposons que R ne dispose pas des fonctions ensemblistes. Comment programmeriez-vous les fonctions Union(x,y)
, Intersection(x,y)
, et Difference(x,y)
(asymétrique) sur des vecteurs non triées avec répétitions.
Union <- function(x, y) unique(append(x,y)) Intersection <- function(x, y) x[ x %in% y ] Difference <- function(x, y) x[ !(x %in% y) ] x <- sample(1:5) y <- sample(4:8) print(x) print(y) print(Union(x,y)) print(Intersection(x,y)) print(Difference(x,y))
[1] 5 1 4 2 3 [1] 5 6 4 7 8 [1] 5 1 4 2 3 6 7 8 [1] 5 4 [1] 1 2 3
Dictionnaire simple
Créez un petit dictionnaire d1 ayant trois couples var:val dont les valeurs ont des types distincts.
- Faites afficher le type de d1.
- Faites afficher la liste des clés de d1.
- Faites afficher l’ensemble des valeurs de d1.
- Demandez la valeur de la clé « foo », puis « toto ».
d1 <- list("foo"=0, "bar"=1:2, "team"="foobar") class(d1) names(d1) paste(d1) d1["foo"] d1[["foo"]] d1["toto"] d1[["toto"]]
[1] "list" [1] "foo" "bar" "team" [1] "0" "1:2" "foobar" $foo [1] 0 [1] 0 $<NA> NULL NULL
Dictionnaire aléatoire
- Programmez une fonction
RandomDict()
, retournant un dictionnaire aléatoire de longueur 10.- Les 10 clés distinctes seront choisies au hasard parmi les entiers de [0,20].
- Les valeurs associées à ces clés (non nécessairement distinctes) seront choisies parmi les voyelles ’a’,’e’,’i’,’o’,’u’,’y’.
- Posons ensuite
d2 <- RandomDict()
. - Faites afficher le nombres de clés paires de
d2
. - Faites afficher les valeurs distinctes de
d2
.
RandomDict <- function() { res <- sample(c('a','e','i','o','u','y'),10,replace=TRUE) names(res) <- sample(0:20,10,replace=FALSE) return(res) } d2 <- RandomDict() print(d2) sum(as.integer(names(d2)) %% 2 == 0) unique(d2)
15 4 5 19 8 16 0 6 3 14 "o" "u" "y" "e" "y" "e" "u" "e" "y" "y" [1] 6 [1] "o" "u" "y" "e"
Filtrage des clés par valeur
Programmez une fonction GetKeys(d,v)
retournant l’ensemble des clés d’un dictionnaire quelconque d
, dont la valeur associée est v
.
Rappel : les clés sont uniques, mais pas les valeurs!
d1 <- list('a'=5, 'b'=6, 'c'=5, 'd'='b', 'e'=0:1, 'f'=list(0,1)) GetKeys <- function(d, v) { ind <- logical(length(d)) for(i in seq_along(d)) { if(all(d[[i]] == v) ) {ind[i]=TRUE} } return(names(d)[ind]) } GetKeys(d1,5) GetKeys(d1,'b') GetKeys(d1,0:1) GetKeys(d1,0:2)
[1] "a" "c" [1] "d" [1] "e" "f" character(0)
2. Fréquence des mots dans une chaîne
Vous êtes invités à essayer la méthode strsplit
qui renvoie une liste de vecteurs de character
séparés par un séparateur split
:
txt <- 'le chien et le loup font la course' strsplit(txt,' ') txt <- 'Nice, Antibes, Monaco' unlist(strsplit(txt,split=', ')) txt <- 'foo bar' unlist(strsplit(txt,' ')) unlist(strsplit(txt,' +',fixed=FALSE))
[[1]] [1] "le" "chien" "et" "le" "loup" "font" "la" "course" [1] "Nice" "Antibes" "Monaco" [1] "foo" "" "" "bar" [1] "foo" "bar"
- Utilisez les méthodes
strsplit
ettable
pour programmer une fonctionFrequences(str)
prenant une chaînestr
et retournant un vecteur nommé contenant les fréquences d’apparition de chaque mot destr
. - Modifiez votre solution pour que le résultat soit trié par la fréquence en utilisant la fonction
sort
. - En déduire une fonction
PlusFrequents(str)
retournant les mots les plus fréquents.
Frequences <- function(str) { words <- unlist(strsplit( trimws(str),' +',fixed=FALSE)) res <- table(words) res <- sort(res, decreasing=TRUE) return(res) } PlusFrequents <- function(str) { r <- Frequences(str) names(r[ r == r[1] ]) }
Frequences(" ") str <- "do re do mi do la la mi la" Frequences(str) PlusFrequents(str)
integer(0) words do la mi re 3 3 2 1 [1] "do" "la"
3. Algorithme de Bezout
L’algorithme de Bezout prolonge l’algorithme d’Euclide. Il dit qu’il est possible d’écrire le PGCD g de a et b comme combinaison linéaire de a et b à coefficients entiers : il existe u et v (non uniques) tels que g = a*u + b*v. Par exemple 4 = 8*(-1) + 12*1.
- On se propose de programmer une fonction
bezout(a,b)
retournant un triplet (g,u,v). - Montrez que si l’on sait calculer bezout(b,a %% b), alors on peut en déduire bezout(a,b).
- Programmez une fonction
bezout(a,b)
récursive. Testez-la surbezout(8,12)
.bezout <- function(a,b) { ## fonction récursive if(b == 0) return(c(a,1,0)) x <- bezout(b, a %% b) return( c(x[1], x[3], x[2] - a %/% b * x[3])) } print(bezout(8, 12))
[1] 12 0 1 [1] 4 -1 1
- Programmez une fonction
aff_bezout(a,b)
affichant la décomposition g = a*u + b*v.aff_bezout <- function(a,b) { bz <- bezout(a,b); cat(bz[2],'*',a,'+',bz[3],'*',b,'=',bz[1], '\n') }
aff_bezout(8, 12) aff_bezout(120,23) aff_bezout(5040,4116)
-1 * 8 + 1 * 12 = 4 -9 * 120 + 47 * 23 = 1 9 * 5040 + -11 * 4116 = 84
- Programmez une fonction
bezout(a,b)
itérative. Testez-la surbezout(8,12)
.bezout <- function(a,b) { ## fonction itérative bz <- c(a,1,0,b,0,1) ## égalités r = a*u+b*v et r' = a*u'+b*v' sont des invariants de boucle while(bz[4] != 0) { q <- bz[1] %/% bz[4] bz <- c(bz[4:6], bz[1:3]-q*bz[4:6]) ##print(bz) } return(bz[1:3]) } aff_bezout(8, 12) aff_bezout(120,23) aff_bezout(5040,4116)
-1 * 8 + 1 * 12 = 4 -9 * 120 + 47 * 23 = 1 9 * 5040 + -11 * 4116 = 84
4. Jeu de Pendu
Le pendu est un jeu consistant à trouver un mot en devinant quelles sont les lettres qui le composent.
- Programmer une fonction
JeuPendu()
sans limite du nombre de coups. Le joueur entre une lettres au clavier jusqu’à ce qu’il ait trouvé le mot. - Modifier la fonction
JeuPendu(n)
pour que le joueur soit déclaré perdant aprèsn
erreurs.
Vous pouvez utiliser la fonction suivante pour capturer les saisies au claviers.
Read1 <- function(x) { cat(sprintf("Entrer %s :\n", x)) word <- scan(file = "", what = "character", n = 1, quiet = TRUE) stopifnot(length(word) == 1) return(word) }
Le déroulement du jeu doit s’inspirer de l’exemple ci-dessous.
JeuPendu <- function(n = Inf) { ## Type a word word <- Read1("un mot") cat("Tapez Ctrl + L pour effacer l'écran.\n") ## Init. search objects word.code <- utf8ToInt(tolower(word)) word.mask <- !logical(nchar(word)) i <- 1 j <- 0 while(any(word.mask) && j < n) { ## Type a letter letter <- Read1("une lettre") stopifnot(nchar(letter) == 1) ## Update search status word.letter <- word.code != utf8ToInt(letter) if(all(word.letter)) { j <- j + 1 } word.mask <- word.mask & word.letter ## Pretty print of the search status word.current <- word.code word.current[word.mask] <- utf8ToInt("_") cat(sprintf("Tour %d : %s\n", i, intToUtf8(word.current))) ## Increment round i <- i + 1 } cat( ifelse( any(word.mask), "Perdu\n", "Gagné\n")) } }
> JeuPendu() Entrer un mot : 1: ici Tapez Ctrl + L pour effacer l'écran. Entrer une lettre : 1: a Tour 1 : ___ Entrer une lettre : 1: i Tour 2 : i_i Entrer une lettre : 1: b Tour 3 : i_i Entrer une lettre : 1: c Tour 4 : ici >