Solutions du TD-9, Exploration
La solution est la classe Monnaie.
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.