DS 1 (MP2I 2021-2022) — Reprise des TP et crible d'Ératosthène¶
Devoir surveillé · MP2I · 2021-2022 · partie I du DS 1 (4 h au total)
Cours : Programmation impérative · Récursivité
Autres parties : II. Tours de Hanoï et couvertures
Tout document interdit. Tout dispositif électronique interdit.
On vous demande d'écrire lisiblement et de bien présenter. Les programmes en particulier doivent être bien indentés et lisibles.
Bon courage et Don't panic! Le barème et les indications de temps sont purement indicatifs.
Reprise des TPs - 10pts¶
On demande ici de redonner les programmes correspondant plus ou moins directement à des questions posées dans les TP1 à 4.
OCaml - 5pts¶
Les programmes à donner en réponse ici doivent être écrits en OCaml.
Attention
On utilise ici les types par défaut de OCaml. C'est particulièrement
important pour les listes.
Question 1
(OCaml - 5 min - 1/2 pt)
Écrire une fonction pow2 : int -> int telle que pow2 n renvoie \(2^n\) où
\(n \ge 0\) (c'est acquis que \(n\) ne sera jamais négatif donc ne vous en
préoccupez pas dans les questions).
Corrigé
let rec pow2 n =
if n = 0
then 1
else 2 * pow2 (n-1)
Question 2
(OCaml - 5 min - 1/2 pt)
Écrire une fonction suplog2 : int -> int telle que suplog2 n renvoie le
plus petit \(d \in \N\) tel que \(n < 2^d\). On supposera \(n \ge 0\).
Corrigé
let rec suplog2 n =
if n = 0
then 0
else 1 + suplog2 (n/2)
Question 3
(OCaml - 5 min - 1/2 pt)
Écrire une fonction comb : int -> int -> int telle que comb n k calcule
\(\binom{n}{k}\) avec la relation du triangle de Pascal :
On rappelle que \(\binom{n}{0}=\binom{n}{n} = 1\) et \(\binom{n}{k} = 0\) par convention quand \(k \not \in \{0,\dots,n\}\).
Corrigé
let rec comb n k =
if k > n || k < 0
then 0
else if k = n
then 1
else comb (n-1) (k-1) + comb (n-1) k
Question 4
(OCaml - 5 min - 1/2 pt)
Écrire une fonction trib : int -> int telle que trib n calcule \(T_n\) où
\(T_0=T_1=0\), \(T_2 = 1\) et
Corrigé
let rec trib n =
if n <= 1
then 0
else if n = 2
then 1
else trib (n-1) - trib (n-2) * trib (n-3)
Question 5
(10 min - 3/4 pt)
On considère \(C_n\) le nombre de noeuds dans l'arbre d'appels récursifs de la
fonction trib.
Déterminer une relation de récurrence satisfaite par la suite \((C_n)_{n\in\N}\).
Corrigé
On a \(C_0 = C_1 = C_2 = 1\) et si \(n > 2\),
Question 6
(OCaml - 10 min - 3/4 pt)
Écrire une fonction applique : 'a list -> ('a -> 'b) -> 'b list telle que
l'appel à applique l f renvoie la liste obtenue en appliquant à chaque
élément de l la fonction f.
Exemple :
applique [1;2;3] (fun x -> 4 + x)
(* renvoie *)
[5;6;7]
Corrigé
let rec applique l f =
match l with
| [] -> []
| t::q -> f t :: applique q f
Question 7
(OCaml - 10 min - 3/4 pt)
Écrire une fonction nieme : 'a list -> int -> 'a option telle que l'appel à
nieme l n renvoie Some x où x est le n-ième élément de l ou None
s'il n'y en a pas.
Corrigé
let rec nieme l n =
match l, n with
| [], _ -> None
| t::_, 0 -> Some t
| _::q, _ -> nieme q (n-1)
Question 8
(OCaml - 10 min - 3/4 pt)
Écrire une fonction pourtout : 'a list -> ('a -> bool) -> bool telle que
l'appel à pourtout l f renvoie true si et seulement si tous les
éléments x de l sont tels que f x soit égale à true.
Corrigé
let rec pourtout l f =
match l with
| [] -> true
| t::q -> f t && pourtout q f
C - 5pts¶
Les programmes à donner en réponse ici doivent être écrits en C.
Question 9
(C - 5 min - 1/2 pt)
Écrire une fonction de signature int suplog2(int n) qui renvoie le plus
petit entier \(d \ge 0\) tel que \(0 \le n < 2^d\).
Corrigé
int suplog2(int n)
{
int p = 1;
int d = 0;
while (n >= p)
{
p = p*2;
d = d+1;
}
return d;
}
Question 10
(C - 5 min - 1/2 pt)
Écrire une fonction de signature int factorielle(int n) qui renvoie \(n!\).
Attention
On ne fera pas de fonction récursive.
Corrigé
int factorielle(int n)
{
int p = 1;
for (int i = 1; i <= n; i++)
{
p = p*i;
}
return p;
}
Question 11
(C - 5 min - 1/2 pt)
Écrire une fonction de signature int somme_cubes(int t[], int nb_elts) qui
calcule la somme des cubes des éléments du tableau donné en arguments.
Corrigé
int somme_cubes(int t[], int nb_elts)
{
int s = 0;
for (int i = 0; i < nb_elts; i++)
{
s = s + t[i]*t[i]*t[i];
}
return s;
}
Question 12
(C - 2 min - 1/4 pt)
Écrire une fonction de signature void swap(int t[], int i, int j) qui
échange les valeurs aux indices i et j dans le tableau t.
Corrigé
void swap(int t[], int i, int j)
{
int v = t[i];
t[i] = t[j];
t[j] = v;
}
Question 13
(C - 10 min - 1 pt)
Écrire une fonction de signature int indice_minimum(int t[], int i, int j)
qui renvoie l'indice du plus petit élément situé entre les indices \(i\) et \(j\)
(inclus).
On supposera que la fonction sera toujours appelée avec \(0 \le i < j < n\) où \(n\) est le nombre d'éléments du tableau.
Corrigé
int indice_minimum(int t[], int i, int j)
{
int val_min = t[i];
int indice_min = i;
for (int k = i+1; k <= j; k++)
{
if (val_min > t[k])
{
val_min = t[k];
indice_min = k;
}
}
return indice_min;
}
Question 14
(C - 10 min - 1 pt)
En déduire une fonction de signature void tri(int t[], int nb_elts) qui trie
le tableau donné en argument à l'aide des deux fonctions précédentes.
Corrigé
void tri(int t[], int nb_elts)
{
for (int i = 0; i < nb_elts-1; i++)
{
int j = indice_minimum(t, i, nb_elts-1);
swap(t, i, j);
}
}
Question 15
(2 min - 1/4 pt) Comment s'appelle ce tri ?
Corrigé
C'est un tri par sélection car on sélectionne le minimum des éléments non triés pour le placer à la bonne position.
Question 16
(C - 10 min - 1 pt)
Écrire une fonction de signature int recherche_motif(char s[], char m[]) qui
renvoie l'indice de la première occurrence de la chaine m dans la chaîne s
si elle s'y trouve, ou \(-1\) dans le cas contraire.
Corrigé
int recherche_motif(char s[], char m[])
{
int n = strlen(s);
int p = strlen(m);
for (int i = 0; i <= n-p; i++)
{
int j;
for (j = 0; j < p; j++)
{
if (s[i+j] != m[j])
{
break;
}
}
if (j == p)
{
return i;
}
}
return -1;
}
Autour du crible d'Eratosthène - 2pts¶
On cherche ici à déterminer tous les nombres premiers \(\le N\) où \(N\) est une limite qu'on se fixe à l'avance.
L'idée du crible d'Eratosthène consiste à aligner tous les nombres de \(2\) à \(N\), puis d'effectuer le processus suivant :
- Déterminer le plus petit entier \(n\) non barré et non encore étudié.
- Barrer tous les multiples de \(n\) qui sont \(> n\).
- S'il reste des nombres non barrés \(> n\) retourner à l'étape 1.
- Les nombres non barrés sont premiers.
Par exemple pour \(N = 9\) :
- a) initialisation : \(2~3~4~5~6~7~8~9\)
- b) étape 1 -- \(n = 2\) on barre donc \(4,6,8\) : \(2~3~\not{4}~5~\not{6}~7~\not{8}~9\)
- c) étape 2 -- \(n = 3\) on barre donc \(6,9\) (mais \(6\) est déjà barré) : \(2~3~\not{4}~5~\not{6}~7~\not{8}~\not{9}\)
- d) étape 3 -- \(n = 5\) mais il n'y a pas de multiples : \(2~3~\not{4}~5~\not{6}~7~\not{8}~\not{9}\)
- e) étape 4 -- \(n = 7\) mais il n'y a pas de multiples : \(2~3~\not{4}~5~\not{6}~7~\not{8}~\not{9}\)
- f) étape 5 -- il n'y a plus de nombres non barrés, on a donc trouvé les premiers \(\le 9\) : \(2~3~5~7\)
Question 17
(C - 20 min - 2 pt)
Écrire, en C, une fonction de signature void crible(int p[], int N) qui
prend en entrée un tableau de \(N+1\) valeurs entières (non initialisées) et les
remplit de sorte que p[i] contienne \(1\) si \(i\) est premier et \(0\) sinon.
On appliquera la méthode précédente.
On essaiera de faire en sorte que la fonction n'utilise que des additions ou des multiplications par deux (ni multiplication, ni division, ni modulo). Si vous n'y arrivez pas, écrivez tout de même la fonction avec ces opérations (mais vous aurez moins de points).
Corrigé
void crible(int p[], int N)
{
int i;
p[0] = 0;
p[1] = 0;
for (i = 2; i <= N; i++)
{
p[i] = 1;
}
for (i = 2; i <= N; i++)
{
if (p[i] == 1)
{
int m = 2*i;
while (m <= N)
{
p[m] = 0;
m = m + i;
}
}
}
}