Q15: sous_liste_de

Profil

sous_liste_de: liste x liste -> booleen

Exemples

sous_liste_de( (b c), (a b c d) ) = vrai
sous_liste_de( (b c), (a c d b) ) = faux
sous_liste_de( (a b c), (a b d e a b c d) ) = vrai

Idée: il faut chercher le debut de la sous-liste, puis verifier les elements deux a deux -> passer par une fonction auxiliaire:

sous_liste_de( (b c), (a b c d) ) 
 =   sous_liste_de( (b c), (b c d) ) 
 =   aux( (b c), (b c d) ) 
 =   aux( ( c ), (c d)) 
 =   aux( (), ( d ) ) 
 =   vrai

sous_liste_de( (b c), (a c d b) ) 
 =  sous_liste_de( (b c), (c d b) ) 
 =  sous_liste_de( (b c), (d b) ) 
 =  sous_liste_de( (b c), (b) )
 =  aux( (b c), (b) ) 
 =  aux( ( c ), ()) 
 =  faux

la fonction "aux" sert a verifier que les elements d'une liste L1 sont les premiers éléments d'une liste L2

Attention: le premier element commun n'est peut-etre pas le bon:

sous_liste_de( (a b c), (a b d e a b c d) ) 
 =  aux( (a b c), (a b d e a b c d)) OU sous_liste_de( (a b c), (b d e a b c d) )
 =  aux( (b c), (b d e a b c d)) OU sous_liste_de( (a b c), (d e a b c d))
 =  aux( ( c ), (d e a b c d)) OU sous_liste_de( (a b c), (e a b c d))
 =  faux OU sous_liste_de( (a b c), (a b c d))
 =  aux( (a b c), (a b c d)) OU sous_liste_de( (a b c), (b c d))
 =  aux( (b c), (b c d)) OU sous_liste_de( (a b c), (c d))
 =  aux( ( c ), (c d)) OU sous_liste_de( (a b c), (d))
 =  aux( ( ), (d)) OU sous_liste_de( (a b c), ())
 =  vrai ou faux 
 =  vrai

Axiomes

sous_liste_de( liste_vide() , L2) = vrai
sous_liste_de( cons(x1, L1), liste_vide() ) = faux
sous_liste_de( cons(x1, L1), cons(x2, L2) ) 
 =  sialorsfinsi(x1x2, aux(cons(x1, L1), cons(x2, L2)) 
    ou sous_liste_de( cons(x1, L1), L2), sous_liste_de(cons(x1, L1), L2))

Le dernier axiome peut egalement s'ecrire:

sous_liste_de( cons(x1, L1), cons(x2, L2) )
 =  (x1x2 et aux(cons(x1, L1), cons(x2, L2))) 
     ou sous_liste_de(cons(x1, L1), L2)
aux(liste_vide(), L) = vrai
aux(cons(x1, L1), liste_vide() ) = faux
aux(cons(x1, L1), cons(x2, L2) ) = (x1 = x2) et aux(L1, L2)

Traduction en C

bool suite_sous_liste_de(liste L1, liste L2)
{
  if (est_vide(L1)) return true;
  if (est_vide(L2)) return false;
  return (prem(L1) == prem(L2)) && suite_sous_liste_de(reste(L1), reste(L2));
}

bool sous_liste_de(liste L1, liste L2)
{
  if (est_vide(L1)) return true;
  if (est_vide(L2)) return false;
  return ( (prem(L1) == prem(L2)) && suite_sous_liste_de(reste(L1), reste(L2)) ) || (sous_liste_de(L1, reste(L2)));
}