DM3 Ensemble d'entiers - Terminaison - Pile ¶

Exercice 1 : Ensemble d'entiers¶

Première partie du sujet zéro de ccmp à télécharger ci-dessous :

Remarques

Le maillon de tête ne change jamais car une liste est toujours "encadrée" par les deux valeurs extrêmes INT_MIN et INT_MAX. On n'a donc pas besoin de passer par référence l'adresse du pointeur de tête ("pas de **")
Il faut bien avoir compris la spécification de la fonction de localisation : le champ donnée du maillon renvoyé est strictement inférieur à la valeur cherchée et le maillon suivant n'a pas cette propriété (son champ donnée est supérieur ou égal à la valeur cherchée).
Habituellement on nomme le struct avec le suffixe _s, dans cet énoncé le struct n'a pas de suffixe et c'est le type qui porte le suffixe _t.

Fonction init

Corrigé

maillon_t *init(void)
{
    // Création des 2 maillons encadrant la liste
    maillon_t *premier = malloc(sizeof(maillon_t));
    maillon_t *dernier = malloc(sizeof(maillon_t));
    premier->donnee = INT_MIN;
    premier->suivant = dernier;
    dernier->donnee = INT_MAX;
    dernier->suivant = NULL;
    return premier;
}

Fonction de localisation

Corrigé

maillon_t *localise(maillon_t *t, int v)
{
    // On s'arrête lorsque la valeur du maillon suivant est > ou =
    while (t->suivant->donnee < v)
    {
        t = t->suivant;
    }
    return t;
}

Jeu de données de test

Insertion dans une liste ne contenant pas encore l'élément

état initial

graph LR
    Start[-∞] --> A[ -4]
    A --> B[ 2]
    B --> C[ 3]
    C --> D[ 7]
    D --> End[+∞]

on insère 5, la fonction renvoie true

état final

graph LR
    Start[-∞] --> A[ -4]
    A --> B[ 2]
    B --> C[ 3]
    C --> D[ 5]
    D --> E[ 7]
    E --> End[+∞]

Insertion dans une liste contenant déjà l'élément

état initial

graph LR
    Start[-∞] --> A[ -4]
    A --> B[ 2]
    B --> C[ 3]
    C --> D[ 7]
    D --> End[+∞]

on insère 3, la fonction renvoie false

état final

graph LR
    Start[-∞] --> A[ -4]
    A --> B[ 2]
    B --> C[ 3]
    C --> D[ 7]
    D --> End[+∞]

A la ligne 7 du code proposé : maillon_t *p = localise(&t, v);, on passe en argument l'adresse de t qui est de type pointeur sur maillon, on passe donc l'adresse de l'adresse d'un maillon alors que la fonction localise attend simplement un pointeur sur un maillon. On propose de corriger cette ligne en maillon_t *p = localise(t, v);

La fonction insere_erronne ne traite pas le cas où l'élément à inséré est déjà présent dans la liste. D'autre part on pourrait aussi tester que la fonction malloc n'échoue pas. On propose la version corrigée suivante :

Corrigé

bool insere(maillon_t *t, int v)
{
    maillon_t *p = localise(t, v);
    if (p->suivant->donnee == v)
    {
        return false;
    }
    maillon_t *n = malloc(sizeof(maillon_t));
    n->suivant = p->suivant;
    n->donnee = v;
    p->suivant = n;
    return true;
}

Fonction de suppression d'un maillon

Corrigé

bool supprime(maillon_t *t, int v)
{
    maillon_t *p = localise(t, v);
    if (p->suivant->donnee != v)
    {
        return false;
    }
    maillon_t *temp = p->suivant;
    p->suivant = p->suivant->suivant;
    free(temp);
    return true;
}

Les fonction insere et supprime n'effectuent que des opérations élémentaires mais elles utilisent la fonction localise qui parcourt les éléments de la liste (jusqu'à trouver l'emplacement cherché), cette fonction a une complexité linéaire en fonction de la taille de la liste. Donc insere et supprimer ont une complexité en \(\mathcal{O}(n)\) où \(n\) est le nombre d'éléments de la liste.
Un programme C peut stocker ses données dans :
- la pile ,
- le tas (allocation dynamique par le programmeur),
- le segment des données statiques
Dans le programme fourni,
- int v = 717 déclare une variable globale qui sera stocké dans le segment des données statiques
- Cette valeur est utilisée à la ligne 17 comme paramètre de la fonction insere elle est donc stockée dans la pile lors de l'appel à insere
- La fonction insere va allouer dynamiquement de la mémoire dans le tas pour le nouveau maillon, donc la valeur 717 sera aussi stocké dans le tas.

Exercice 2 : Terminaison d'une fonction¶

Montrer la terminaison de la fonction ci-dessous pour tout \(n \in \mathbb{N}^*\) :

let rec f n =
  if n=1 then 0
  else if n mod 2 = 0 then 1 + f (n/2)
  else 1 + f (n+1);;

Correction

Si \(n \leq 2\) alors la fonction termine en moins de deux appels récursifs. Supposons maintenant que \(n>2\) et montrons que les valeurs prises par \(n\) lors des appels récursifs de rang pair est un variant. On note \(n'\) (resp. \(n''\)) la valeur de \(n\) après le premier (resp. le second) appel récursif.

Si \(n\) est pair, on note \(n=2k\) (k>1) et donc \(n'=k\) puis,
- si \(k\) est pair alors \(n'' = \frac{k}{2}\) et donc \(n < n''\).
- sinon, \(n'' = k+1\) , puisque \(k>1\), \(2k>k+1\) et on a encore \(n > n''\).
Si \(n\) est impaire, on note \(n=2k+1\) (k>1) et donc \(n'=2k+2\), \(n'\) est donc nécessairement pair et donc \(n'' = k+1\), on obtient encore \(n>n''\).

Les valeurs prises par \(n\) lors des appels récursifs de rang pair sont donc strictement décroissantes comme de plus \(n \in \mathbb{N}\), c'est un variant et donc cette fonction termine.

Exercice 3 : Pile¶

Résoudre l'exercice 10 du chapitre 8 en utilisant OCaml

Corrigé

On suit l'indication, et on utilise une pile, on parcourt un à un les caractères :

si on rencontre un caractère identique à celui situé au sommet de la pile, alors on dépile.
sinon on empile ce caractère.

(* Fonction annexe permettant de renvoyer la liste des caractères présente dans la pile*)
let rec voir p =
  if Stack.is_empty p then "" else
    let c = Stack.pop p in
    (voir p) ^ (String.make 1 c);;

let () =
  let reader = open_in "mystere.txt" in
  let ma_pile = Stack.create () in
  try
    while true do
      let caractere = input_char reader in
      if Stack.is_empty ma_pile then Stack.push caractere ma_pile else
        (let sommet = Stack.top ma_pile in
         if caractere<>sommet then Stack.push caractere ma_pile else ignore (Stack.pop ma_pile)
        )
    done;
  with
  | End_of_file -> print_endline (voir ma_pile);
    close_in reader;

Même question en langage C

Corrigé

On utilise une implémentation des piles avec une liste chainée

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


struct maillon
{
    char valeur;
    struct maillon * suivant;
};
typedef struct maillon maillon;
typedef maillon* pile;

pile cree_pile()
{
    return NULL;
}

void empile(pile *p, char v)
{
    pile np=malloc(sizeof(maillon));
    np->suivant = *p;
    np->valeur =v;
    *p = np;
}

bool est_vide(pile p)
{
    return (p==NULL);
}

char  depile(pile *p)
{
    if (p!=NULL)
    {
        pile ls = (*p)->suivant;
        char val = (*p)->valeur;
        free(*p);
        *p = ls;
        return val;
    }
    return 0;
}

char sommet(pile p)
{
    return p->valeur;
}

void affiche(pile p)
{
    while (p!=NULL)
    {
        printf("%c<",p->valeur);
        p = p->suivant;
    }
    printf("\n");
}

int main()
{
    pile p = cree_pile();
    FILE * reader = fopen("mystere.txt","r");
    char c;
    while ((c=fgetc(reader))!=EOF)
    {
        if (est_vide(p) || (sommet(p)!=c))
        {empile(&p,c);}
        else
        {depile(&p);}
    }
    affiche(p);
}