TD-3, récursivité

Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/X.97/TD-3/enonce.html

Vos programmes à déposer sous la forme Prenom.Nom par ftp sur poly en /users/profs/maranget/TD-3.

1  Une récursion simple

Écrire un programme qui lit un entier non-signé (type unsigned int, format "%u") au clavier, puis l'affiche en base deux. Le recours à la récursivité permet d'écrire une fonction d'affichage qui reste simple. En effet, la solution non-récursive qui vient immédiatement à l'esprit ne fait pas l'affaire, puisqu'elle imprime les chiffres à l'envers. 
void affiche(unsigned int n)
{
  if (n == 0) {
    printf("0");
  }
  while (n > 0) {
    printf("%u",n % 2);
    n = n / 2;
  }
}
La solution récursive s'inspire de la remarque suivante : le chiffre des unités de n, (n % 2) doit être affiché après tous les autres.

2  Un compte est bon simplifié

On simplifie le célèbre jeu, en se restreignant à la somme. On commence par se donner un tirage de cinq plaques : 
#define NPLAQUES 5
int plaque[NPLAQUES] = {1,5,5,10,25};
Votre programme devra lire un entier n, puis écrire n comme une somme de plaques lorsque c'est possible. Par exemple : 
Entrez n : 46
46 = 25+10+5+5+1

Entrez n : 30
30 = 25+5
Nous vous conseillons d'adopter la démarche suivante :
  1. Commencez par écrire une fonction récursive qui renvoie vrai lorsque n s'écrit comme une somme de plaques et faux dans le cas contraire.
  2. Modifiez votre fonction pour qu'elle affiche les plaques utilisées.

3  Sous-ensembles

Écrire un programme qui lit un entier n au clavier puis affiche tous les sous-ensembles de l'ensemble des entiers compris entre 1 et n.

Voici quelques indications que vous pouvez utiliser ou pas. Le coeur du programme est une fonction sous_aux dont voici le prototype : 
void sous_aux(int m,int i,int t[])
Le tableau t contient i éléments t0, t1, ..., ti-1, tous compris entre m+1 et n. La fonction sous_aux doit afficher tous les ensembles formés de la réunion de t0, t1, ..., ti-1 et d'un sous-ensemble des entiers compris entre 1 et m.

Donc, si m est nul, alors sous_aux se contente d'afficher t. Sinon, sous_aux doit se rappeler récursivement, pour afficher d'une part, les sous-ensembles qui ne contiennent pas m et d'autre part ceux qui contiennent m.

4  Il vous reste du temps !

On considère un échiquier de taille NMAX par NMAX. Un cavalier part d'une case quelconque de l'échiquier. On demande de trouver un parcours du cavalier qui passe une et une seule fois par toutes les cases de l'échiquier.
Ce document a été traduit de LATEX par HEVEA.