===== 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 ==

  * <jsm>\exists j \in \left[\left[0, n-1\right]\right] | t\left[j\right] = x </jsm> ((<jsm>\left[\left[0, n-1\right]\right] </jsm> 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 <jsm>\left[0.. n-1\right] </jsm> ))\\ la valeur x est la valeur d'un élément du tableau
  * <jsm>\forall i \in \left[\left[0, n-1\right]\right] | t\left[i\right] \geq x </jsm> \\ 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 |

(( où ''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. ))

== é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 ==

  * <jsm>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]</jsm>


== é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  
    * <jsm> p\in \mathbb{N} : \forall i \in \left[0..n-1\right]\quad p | t\left[i\right] </jsm>
    * <jsm> \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] </jsm>


== é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 ===

[[semantics_td_1_4| ma copie (privée)]]

== 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 ==