Q4: neme_reste

Profil

neme_reste: entier x liste -> liste

Exemples

neme_reste(2, (a b c d)) = (c d)

neme_reste(8, (a b c d) = ()

neme_reste(2, (a b c d)) = neme_reste(1, (b c d) = neme_reste(0, (c d)) = (c d)

Axiomes

neme_reste(n, liste_vide()) = liste_vide()

neme_reste(0, L) = L

neme_reste(succ(n), cons(x, L)) = neme_reste(n, L)

Algorithme récursif

fonction neme_reste(n: entier, L: liste): liste
debut
 | si est_vide(L)
 | --------------
 |                | alors retourner L
 |                | sinon si n = 0   
 |                |                   | alors retourner L                        
 |                |                   | sinon retourner neme_reste(n-1, reste(L))
 |                | finsi            
 | finsi         
fin

Algorithme itératif

fonction neme_reste(n: entier, L: liste): liste
 | tant que non (n = 0) et non (est_vide(L)) faire
 | -----------------------------------------------
 |                                                 | n := n-1     
 |                                                 | L := reste(L)
 | fintantque                                     
 | retourner L                                    
debut
fin

Traduction en C

liste neme_resteR(unsigned int n, liste L)
{
  if (est_vide(L))
  {
    return L;
  }
  else
  {
    if (n == 0)
    {
      return L;
    }
    else
    {
      return neme_resteR(n-1, reste(L));
    }
  }
}

liste neme_resteI(unsigned int n, liste L)
{
  while ( (n!=0) && (! est_vide(L)))
  {
    n = n-1;
    L = reste(L);
  }
  return L;
}