Q16: sous_sequence_de

Profil

sous_sequence_de: liste x liste -> booleen

Exemples

sous_sequence_de( (b c), (a b c d) ) = vrai

sous_sequence_de( (b c), (a c d b) ) = faux

sous_sequence_de( (c b), (a c d b) ) = vrai

sous_sequence_de( (a b c), (a b d e a b c d) ) = vrai

Contrairement à Q15 (sous_liste_de), il n'y a pas besoin ici de passer par une fonction auxiliaire

sous_sequence_de( (b c), (a b c d) ) 
 =  sous_sequence_de( (b c), (b c d) ) 
 =  sous_sequence_de( ( c ), (c d)) 
 =  sous_sequence_de( (), ( d ) )vrai
sous_sequence_de( (b c), (a b d c) ) 
 =  sous_sequence_de( (b c), (b d c) ) 
 =  sous_sequence_de( ( c ), (d c) ) 
 =  sous_sequence_de( ( c ), ( c ) )
 =  sous_sequence_de( (  ), () )

Axiomes

sous_sequence_de( liste_vide() , L2) = vrai

sous_sequence_de( cons(x1, L1), liste_vide() ) = faux

sous_sequence_de( cons(x1, L1), cons(x2, L2) ) = (x1 = x2 et sous_sequence_de(L1, L2)) ou sous_sequence_de(cons(x1, L1), L2)

Traduction en C

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