Le compte est presque bon

Rappelons l'énoncé :

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.

Solution « théorique »

La démarche suggérée peut s'interpréter en terme d'un prédicat calculable par récurrence. Soit donc P(i,s), un prédicat (c'est à dire une fonction à valeurs booléenes), qui vaut vrai lorsque s s'écrit comme une somme de plaques prises entre 0 et i et faux sinon. Répondre au problème posé revient à calculer P(n,NPLAQUES-1).

Considérons d'abord les cas de base de la récurrence. Lorsque s est nul, alors s s'écrit bien comme une somme de (zéro) plaque. Si s est non-nul, mais qu'il ne reste plus de plaques (c'est à dire lorsque i est strictement négatif), alors c'est raté, l'ensemble des plaques utilisables est vide. Dans les deux cas suscités on connaît la valeur de P à l'aide de quelques tests élémentaires sur s et i.

Considérons ensuite l'étape de récurrence. Prenons donc s strictement positif et i positif ou nul. Il y a deux cas à traiter, soit s est une somme de plaques qui comprend la plaque numéro i, soit s est une somme de plaques qui ne comprend la plaque numéro i. Dans le premier cas, s moins la plaque de numéro i devra être une somme de plaques prises entre 0 et i-1 ; dans le second cas, s devra être une somme de plaques prises entre 0 et i-1. Soit, du point de vue du calcul de P :

P(i,s) = P(i-1,s-plaque[i]) ou P(i-1,s)

Nous sommes maintenant en mesure de calculer P :

int calcule_p(int i,int s)
{
  if (s == 0)
   return 1;
  if (i < 0)
   return 0;

  if (calcule_p(i-1,s-plaque[i]))
   return 1;
  return calcule_p(i-1,s);
}

La fonction calcule_p calcule bien P par construction, quand elle retoure un résultat. Mais les programmes informatiques ne terminent pas toujours, la question qu'il faut ensuite se poser est donc : calcule_p termine-t-elle dans tous les cas ?. La réponse est assez facile, tout d'abord, la seule source possible de calcul infini réside dans les appels récursifs. On voit ensuite que, dans les appels récursifs, l'argument i diminue toujours de 1, donc il finira par être strictement négatif et calcule_p finira par se terminer.

Optimiser un peu le programme

Le programme écrit peut être rendu un peu plus efficace en considérant un cas supplémentaire. Lorsque s est strictement négatif, il n'y a plus d'espoir, même s'il reste des plaques. On peut donc écrire :

int calcule_p_bis(int i,int s)
{
  if (s == 0)
   return 1;
  if (s < 0)
   return 0;
  if (i < 0)
   return 0;

  if (calcule_p_bis(i-1,s-plaque[i]))
   return 1;
  return calcule_p_bis(i-1,s);
}

Une modification cosmétique permet un programme, plus compact. On utilise l'opérateur ou logique, s'écrit || en C :

int calcule_p_ter(int i,int s)
{
  if (s == 0)
   return 1;
  if (s < 0 || i < 0)
   return 0;

  return calcule_p_ter(i-1,s-plaque[i]) || calcule_p_ter(i-1,s);
}
La solution du corrigé est encore un peu différente, mais tout cela revient au même.