PRG4 - TD1

Benoît Hoessen
Université d'Artois
1ème semestre 2014-2015

Informations pratiques:

30 heures travaux dirigés
10 heures travaux pratiques
contact: hoessen@cril.fr
Référence sur le C:

Pseudo-language

Pour ce premier TD, nous nous intéressons prioritairement à l'algorithmique. De ce fait, la plupart des algorithmes seront décris en pseudo-language.

Types:

Booléen
Entier
Caractère
Chaîne de caractères
Réel

Operations:

Var {variable} : {type}: déclaration
Constante {nom} [: {valeur}]: déclaration de constante
'←' ou '=': affectation
'+', '-', '*': addition, soustraction, multiplication
'/': division réelle
mod: reste de la division entière
div: résultat de la division entière
'<', '≤', '>', '≥', '≡', '≠': comparaisons de valeurs

Branchement conditionel

si {condition booléenne} alors
{instructions}
sinon
{instructions}
finsi

Boucle

tantque {condition booléenne} alors
{instructions}
fintantque

! {condition booléenne} est fausse

Boucle pas à pas

pour {variable} ← {valeur initiale}
à {valeur finale} [pas:{valeur}] alors
{instructions}
finpour

! {variable} ≥ {valeur finale}

Exercice 1:

Soit le nombre entier n, donner le plus petit entier x tel que 2^x ≥ n

Solution:

Var n : entier;
Var x : entier;
Var v : entier; ! valeur de 2^x
x ← 0;
v ← 1;
tantque v < n alors
v ← v*2;
x ← x+1;
fintantque

Exercice 2:

Soit le nombre entier n, donner la valeur du n^ième nombre de Fibonacci. La solution proposée doit utiliser la programmation itérative.
Rappel: fib(0)=0, fib(1)=1, fib(2)=1, ..., fib(n) = fib(n-1) + fib(n-2)

Solution:

Var n : entier;
Var f : entier; !valeur de f(n)
si n < 2 alors
  si n ≡ 0 alors f←0 sinon f←1 finsi
sinon
  Var j : entier; ! j ≤ n
  Var a : entier; ! valeur de f(j-2)
  Var b : entier; ! valeur de f(j-1)
  Var c : entier; ! valeur de f(j)
  j ← 2; a ← 0; b ← 1; c ← 1;
  tantque j < n alors
    j ← j+1; a ← b; b ← c; c ← a+b;
  fintantque
  f ← c;
finsi

Tableaux:

Déclaration:

Tab {nom du tableau} [ {expression constante} ] : {type};

Utilisation:

{variable}[{expression entière}]

Exercice 3: Crible d'Ératosthène

Définir un tableau de booléens premier tel que premier[i] est vrai si et seulement si i est premier. Pour se faire, on met à vrai tout les éléments du tableau. Ensuite, on met à faux tout les éléments multiple de 2, de 3 et ainsi de suite jusqu'à atteindre T.

Solution:

Constante T;
Tab premier[T] : Booléen;
premier[0] ← false;
premier[1] ← false;
Var i : Entier;
!∀k_(2≤k<i) ∀j_{(2≤j<T)∧(j mod k ≡ 0)}, premier[j]≡⊥
pour i←2 à Tdiv2 alors
  Var l : Entier; ! multiple de i
  pour l←i*2 à T pas: i alors
    premier[l] ← false;
  finpour
finpour

Exercice 4: Filtre d'image

Soit un tableau src d'entier de taille N×N représentant une image. Les valeurs de ce tableau vont de 0 à 255 représentant des niveaux de gris. La valeur du pixel (i,j) est donnée par src[i*N+j].
On cherche à appliquer un filtre sur cette image. Le filtre est défini par un tableau de réels flt représentant une matrice taille 3×3.

Écrire le code permettant d'appliquer le filtre flt sur src.

Exemples de filtres:

Initial	Réduction de bruit

Augmentation de bruit	Détection de bords

Solution:

Constante N;
Tab src[N*N] : Entier;
Tab out[N*N] : Réel;
Tab flt[9] : Réel;
Var i, j : Entier; pour i←1 à N-1 alors
  pour j←1 à N-1 alors
    Var nv : Réel;
    ! calculer nv
    out[i*N + j] ← nv;
  finpour
finpour

! calcul de nv
nv ← flt[0] * src[(i-1)*N+(j-1)]
   + flt[1] * src[(i-1)*N+j]
   + flt[2] * src[(i-1)*N+(j+1)]
   + flt[3] * src[i*N+(j-1)]
   + flt[4] * src[i*N+j]
   + flt[5] * src[i*N+(j+1)]
   + flt[6] * src[(i+1)*N+(j-1)]
   + flt[7] * src[(i+1)*N+j]
   + flt[8] * src[(i+1)*N+(j+1)];

Exercice 5

Un vecteur mur de taille N représente la hauteur de différents murs consécutifs. On cherche à connaitre le nombre maximum d'unités d'eau qui pourraient être stocké par les cuvettes formées par les murs.

Solution:

Constante N;
Tab mur[N] : Entier;
Var i, j : Entier; ! 0 ≤ i ≤ j < N
Var k, l : Entier;
! k = max(mur[0 .. i-1]), l = max(mur[j+1 .. N-1])
Var v : Entier;
! v = volume(mur[0 .. N-1]) - volume(mur[i .. j])

i ← 0; j ← N - 1; k ← 0; l ← 0; v ← 0;
tantque i < j alors
  si mur[i] > k alors k ← mur[i];finsi
  si mur[j] > l alors l ← mur[j];finsi
  si k ≥ l alors
     v ← v + (l - mur[j]);
     j ← j - 1;
  sinon
     v ← v + (k - mur[i]);
     i ← i + 1;
  finsi
fintantque

Exercice 6

Soit une matrice de booléens fg de taille N*N représentée par un vecteur. On cherche la coordonée du dernier point faisant partie du plus grand carré constitué de valeurs vrai ainsi que la taille de ce dernier.

Solution:

Constante N;
Tab fg[N*N] : Entier; Tab last[N] : Entier;
! der[i] = taille du carré se terminant en i-N
Var i,l,p : Entier; ! 0 ≤ p < i, p est la position du dernier élément d'un carré de taille l*l et il n'y a pas de plus grand carré se terminant avant p

!Initialisation
l ← 0;
pour i ← 0 à N-1 alors
  si fg[i] alors
    p← 1; l←1; der[i]← 1;
  sinon
    der[i]← 0;
  finsi
finpour
pour i ← 0 à N - 1 alors
  !mettre à jour der[j*N + i]
  !si besoin, mettre à jour l et p
finpour

!mettre à jour der[i]
si fg[i] et i mod N ≠ 0 alors
  si der[i-1] ≡ der[i] alors
    si fg[i-(der[i]*N)-der[i]] alors
      der[i] ← der[i] + 1;
    sinon der[i] ← max(der[i], 1);finsi
  sinon
    der[i] ← min(der[i],der[i-1]) + 1;
  finsi
sinon si fg[i] alors
  der[i] ← 1;
sinon
  der[i] ← 0;
finsi

!si besoin, mettre à jour l et p
si der[i] ≥ l alors
l ← der[i];
p ← i;
finsi

Fonctions:

fonction {nom fonction}(Val {nom var} : {type}, ... ) : {type de retour} définie par
{opérations}
finfonction

Si la fonction doit retourner une valeur, une variable portant le nom de la fonction est implicitement définie. À la fin de la fonction, c'est la valeur contenue dans cette variable qui sera retournée.
Si l'on veut passer des paramètres par variable plutôt que par valeur, il faut utliser le mot-clé Var à la place de Val

Rappel
Lorsqu'une variable x est passée par valeur, la fonction reçoit une copie de la valeur de x. De ce fait, dans le corps de la fonction, toute modification n'aura aucun effet sur la valeur de x.

fonction f(Val x : Entier) définie par
x ← x + 1;
finfonction
Var x : Entier;
x ← 3;
f(x);
! x vaut encore trois

Rappel
Lorsqu'une variable x est passée par variable, la fonction reçoit un accès à x. De ce fait, dans le corps de la fonction, toute modification sera faite sur x.

fonction f(Var x : Entier) définie par
x ← x + 1;
finfonction
Var x : Entier;
x ← 3;
f(x);
! x vaut quatre désormais

Exercice 7

Soit un nombre x, fournir une représentation de ce nombre sous forme de texte, en base b. On suppose que les nombres 0 à 9 peuvent être représentés avec le chiffre base 10 correspondant. Pour tout chiffre supérieur à 9, les lettres a-z seront utilisées. Pour plus de facilité, nous considérons que la base ne peut être supérieure à 36.
Écrire le code de la fonction rep prenant trois paramètres: la valeur de x, de la base b ainsi qu'un tableau que l'on suppose suffisamment grand qui contiendra le résultat.

Solution:

fonction rep(Var x:Entier, Var b:Entier, Tab t[N]:Entier)
définie par
  Var i, v:Entier
  tantque x<0 alors
    v ← x mod b
    si v ≤ 9 alors t[i]←'0' + v;
    sinon t[i]←'a' + v - 10; finsi
  x← x div b;
  i← i + 1;
  fintantque

  v←i div 2;
  x←i ;
  pour i←0 à v alors
    t[i], t[x-i] ← t[x-i], t[i];
  finpour
finfonction

PRG4 - TD1

Pseudo-language

Types:

Operations:

Branchement conditionel

Boucle

Boucle pas à pas

Exercice 1:

Solution:

Exercice 2:

Solution:

Tableaux:

Déclaration:

Utilisation:

Exercice 3: Crible d'Ératosthène

Solution:

Exercice 4: Filtre d'image

Exemples de filtres:

Solution:

Exercice 5

Solution:

Exercice 6

Solution:

Fonctions:

Exercice 7

Solution:

Bibliographie: