Raisonner pour programmer

Où l'on cherche à exprimer formellement un problème et à établir les liens entre les différentes formes d'énoncés.

Quelques problèmes classiques

Pour chacun des problèmes suivants :

  • Préciser données et résultat
  • Écrire un énoncé qui qualifie le résultat
  • Écrire un énoncé qui définit le résultat
  • Écrire un programme impératif en langage C.

(1)

Description

Le plus petit nombre (x) d'un tableau t de n nombres.

données et résultat
  • données : un tableau de nombres t de taille n
  • résultat : l'élément du tableau t de plus faible valeur
énoncé qualifiant le résultat
  • \exists j \in \left[\left[0, n-1\right]\right] | t\left[j\right] = x 1)
    la valeur x est la valeur d'un élément du tableau
  • \forall i \in \left[\left[0, n-1\right]\right] | t\left[i\right] \geq x
    et la plus petite
énoncé définissant le résultat
x(a) = a s'il s'agit d'un tableau à un seul élément
x(a::t) = x(t) si x(t) < a
a sinon

2)

énoncé exécutable en C
int
min (int *t, int n){
    int x=t[0], i;
    for (i=1;i<n;i++){
        if (x>t[i]) x = t[i];
        }
    return x;
    }

(2)

Description

Le quotient q de la division euclidienne de deux nombres entiers a et b

données et résultat
  • données : deux entiers a et b, b différent de 0 (ou > 0)
  • résultat : un entier q tel que q * b ≤ a et (q+1)*a > b.
énoncé qualifiant le résultat
  • a, q\in \mathbb{N}, b\in \mathbb{N}^+ \quad | \quad \left[q\times b \leq a\right]\& \left[\left(q+1\right)\times b \gt a\right]
énoncé définissant le résultat
q(a, b) = 0 si a < b
1 + q(a-b, b) sinon
énoncé exécutable en C
int quot(int a, int b){
    int q = 0;
    if (a >= b) q = 1 + quot(a-b, b);
    return q;
}

(3)

Description

Le plus grand diviseur (p) d'un tableau t de n nombres

données et résultat
  • données : tableau t de n nombres entiers
  • résultat : un entier p tel que
    • p divise tous les éléments de t[] (résidus nuls)
    • si un entier q divise tous les éléments de t[], q ≤ p.
énoncé qualifiant le résultat
  • résultat : un entier p tel que
    • p\in \mathbb{N} : \forall i \in \left[0..n-1\right]\quad p | t\left[i\right]
    • \forall q\in \mathbb{N}, \left( \forall i \in \left[0..n-1\right] \; Q | t\left[ i\right]\right) \rightarrow \left[ q \leq p \right]
énoncé définissant le résultat
p(a) = a
p(a::t) = pgcd(a, p(t))
pgcd(a, b) = b : si a = 0 (ou a = b)
pgcd(a-b, b) : si a > b
pgcd(b, a) : si a < b
énoncé exécutable en C
int 
divComm(int *t, int n){
int i=0, p=t[0];
for (i=1; i< n ; i++) [p = pgcd(p,t[i]);
}
return p;
}

int pgcd(int a, int b){
    if (a==0) return b;
    if (a>b) return pgcd(a-b, b);
    if (b>a) return pgcd(b, a);
    }

—-

(4) : à rendre le 18/02

Description

La racine carrée (r) d'un nombre carré n

données et résultat
énoncé qualifiant le résultat
énoncé définissant le résultat
énoncé exécutable en C

(5)

Description

Le tri d'un tableau t de n nombres (on nomme u le tableau trié).

données et résultat
énoncé qualifiant le résultat
énoncé définissant le résultat
énoncé exécutable en C

"La plus petite somme"

Mêmes questions que précédemment pour le problème suivant :

Description

Étant donnée un tableau t de n nombres, le résultat s est la plus petite somme d'éléments consécutifs dans t.

Exemple :

indice 0 1 2 3 4 5 6 7 8 9 10
élément 1 -2 3 -1 -5 -4 1 0 -2 5 -1
s = -11 + + + + +
données et résultat
énoncé qualifiant le résultat
énoncé définissant le résultat
énoncé exécutable en C
1) \left[\left[0, n-1\right]\right] est la notation choisie pour indiquer les entiers de 0 à n-1 pour éviter confusion avec un intervalle continu fermé, et peut aussi être écrit \left[0.. n-1\right]
2)a::t est notation empruntée de Caml–je crois–signifiant un élément a suivi d'un tableau t, qui peut être un seul élément.
 
m1ilc/semantics_td_1.txt · Dernière modification: 2010/02/08 09:08 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki