Solutions du TD-9, Exploration

La monnaie

La solution est la classe Monnaie.

Le compte est bon

La solution est la classe Ceb. A utiliser avec les classes Op, Add, Sub, Mul et Div.

Pour ceux que ça intéresse, voici mon meilleur essai selon cette technique d'énumération. Le programme ceb.c est écrit en C, il prend en arguments les plaques (données dans l'ordre croissant) et affiche toutes les solutions de 1 à 999. 
# ./a.out 1 2 3 4 5 6 7
  1: 1
  2: 2
  3: 3
  4: 4
  5: 5
  6: 6
  7: 7
  8: ((((((1+2)*7)+6)/3)-5)+4)
  9: ((((1+2)*7)+6)/3)
    .
    .
    .
990: (((((1+2)*7)+(3*4))*6)*5)
991: (((((1+5)*(4*6))-2)*7)-3)
992: (((1+3)*(2+6))*((5*7)-4))
993: (((((1+4)*7)-2)*(5*6))+3)
994: ((((((1+3)*5)+4)*6)-2)*7)
995: ((((1+3)*(2*(4*6)))+7)*5)
996: ((1+2)*((7*((3+5)*6))-4))
997: (((((1+5)*(4*6))-2)*7)+3)
998: (((6-1)*((3+7)*(4*5)))-2)
999: ((((1+4)*7)+2)*((5*6)-3))
On peut donner l'option ``-o'', auquel cas, les solution minimisent le nombre de plaques utilisées. 
# ./a.out 1 2 3 4 5 6 7
  1: 1
  2: 2
  3: 3
  4: 4
  5: 5
  6: 6
  7: 7
  8: (1+7)
  9: (2+7)
     .
     .
     .
990: (3*((4+7)*(5*6)))
991: (1+(3*((4+7)*(5*6))))
992: ((((1+6)*(5*7))+3)*4)
993: ((1+((4+7)*(5*6)))*3)
994: ((((1+5)*(4*6))-2)*7)
995: ((((1+6)*(4*7))+3)*5)
996: ((((1+5)*(4*7))-2)*6)
997: (((((1+5)*(4*6))-2)*7)+3)
998: (2*((3*(4*(6*7)))-5))
999: ((2+(5*7))*(3+(4*6)))
Sans exagérer, la programmation recherche l'efficacité. Les cas de base de la récursion (2 plaques) sont particularisés, On cherche aussi à restreindre l'espace d'énumération, en utilisant la commutatitivité/associativité de l'addition et de la multiplication, ainsi qu'une remarque sur l'ordre des plaques. Enfin, le code n'est pas générique fonction des opérateurs, +, - etc.

Certaines techniques d'optimisation sont plutôt propres à C. Les macros sont souvent utilisées en place des fonctions (voir ADD, SUB etc.) Les allocations temporaires se font en pile (technique appliquée aux variables an et bn), tandis que les allocations définitives sont faites statiquement (tableau save). Enfin, les tableaux sont parcourrus par des pointeurs, plutôt que par des indices.

Ce document a été traduit de LATEX par HEVEA.