Énumération brute
En Java, naïf
class Ceb {
private static StringBuffer r = new StringBuffer () ;
private static Op [] ops = {new Add (), new Sub (), new Mul (), new Div ()} ;
5 private static int dmax = 0 ;
static void debug (int [] t, int nb) {
System.err.print("[") ;
for (int i=0 ; i < nb ; i++) {
System.err.print("_" + t[i]) ;
10 }
System.err.println("_]") ;
}
static boolean cb(int [] t, int nb, int total) {
15 // debug(t,nb) ;
for (int i = 0 ; i < nb ; i++) {
if (t[i] == total) {
return true;
}
20 for (int j = i+1 ; j < nb ; j++)
for (int k = 0 ; k < ops.length ; k++) {
int res = ops[k].eval(t[i],t[j]) ;
if (res != 0) {
int savei = t[i], savej = t[j];
25 t[i] = res ; t[j] = t[nb-1] ;
if (cb(t, nb-1, total)) {
r.append(Math.max(savei, savej) + "_" + ops[k].symbol() +
"_" + Math.min(savei,savej) + "_=_" + res + '\n') ;
return true ;
30 }
t[i] = savei ; t[j] = savej ;
}
}
}
35 return false ;
}
public static void main (String [] arg) {
int plaque [] = new int [arg.length-1] ;
40 for (int i = 0 ; i < arg.length-1 ; i++)
plaque[i] = Integer.parseInt(arg[i]) ;
int total = Integer.parseInt(arg[arg.length-1]) ;
if (cb(plaque, plaque.length, total)) {
45 System.out.println("Le_compte_est_bon") ;
System.out.print(r.toString()) ;
} else {
System.out.println("Le_compte_est_pas_bon") ;
}
50 }
}
En C, optimisé
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define PMAX 16
5
/* quelques macros pour les opérations « à la compte est bon » */
#define SUB(a,b) ((a) > (b) ? (a)-(b) : (b)-(a))
#define MOD(a,b) ((a) > (b) ? (a)%(b) : (b)%(a))
#define DIV(a,b) ((a) > (b) ? (a)/(b) : (b)/(a))
10 #define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
/* type des entiers manipulés, non signé */
#ifndef LONG
15 typedef unsigned int num ;
#define NUMFORM "%u"
#else
typedef unsigned long num ;
#define NUMFORM "%lu"
20 #endif
/* Plaques et nombre effectif de plaques au départ */
num plaque[PMAX] ;
int pmax ;
25
/* type des noeuds de l'arbre qui représente les opérations */
typedef struct node {
char tag ;
union {
30 num k ;
struct {
struct node *g, *d ;
} n ;
} arg ;
35 } node ;
/* tableau des arbres, parallèle au tableau des plaques */
node nodes[PMAX] ;
40 /* Macro pour affecter les noeuds */
#define SETNODE(p,t,fg,fd) (p)->tag = (t), (p)->arg.n.g = (fg), (p)->arg.n.d = (fd)
#define K '\0'
45 /* Pour copier un arbre vers l'espace de stockage définitif */
node *tcopy(node *to, node *p) {
if (p->tag == K) {
to->tag = K ;
to->arg.k = p->arg.k ;
50 return ++to ;
} else {
to->tag = p->tag ;
to->arg.n.g = to+1 ;
to->arg.n.d = tcopy(to+1,p->arg.n.g) ;
55 return tcopy(to->arg.n.d,p->arg.n.d) ;
}
}
/* Affichage des arbres */
60 void print(node *p) {
if (p->tag == K)
printf(NUMFORM, p->arg.k) ;
else {
printf("(") ;
65 print(p->arg.n.g) ;
printf("%c", p->tag) ;
print(p->arg.n.d) ;
printf(")") ;
}
70 }
int opt=0; /* opt != 0 => chercher les solutions optimales */
/* Chercher les solutions entre BEG et END */
#define BEG 1
75 #define END 999
int found[END-BEG+1] ; /* nombres trouvés */
int depth[END-BEG+1] ; /* et leur profondeur */
node save[END-BEG+1][2*PMAX-1] ; /* espace de stockage des arbres solution */
int remains = END-BEG+1; /* compteur des nombres non encore trouvés */
80
/* Un nombre de l'intervale [BEG..END] a-t-il déja été trouvé */
int was_found(int i) {
if (opt)
return depth[i-BEG] > 0 ;
85 else
return found[i-BEG] ;
}
/*
90 Traitement des résultats de l'énumération.
* s est le nombre.
* t est l'arbre des opérations qui y conduit
* indent est la profondeur de récursion
(pmax-indent+1 majore le nombre de plaques utilisées,
95 majoration atteinte au moins une fois.
pall renvoie vrai quand il est inutile de poursuivre la recherche.
Elle stocke l'arbre dans save[s-BEG] si c'est approprié.
*/
100 int pall(num s, node *t, int indent)
{
#ifdef DEBUG
if (s == 0)
{
105 int k ;
for (k = indent+1 ; k < pmax ; k++)
printf("__") ;
printf(NUMFORM ":_",s) ;
110 print(t) ;
putchar('\n') ;
}
#endif
if ((BEG <= s) && (s <= END)) {
115 if (opt) {
if (depth[s-BEG] < indent) {
depth[s-BEG] = indent ;
tcopy(&save[s-BEG][0],t) ;
}
120 return 0 ;
} else {
if (!found[s-BEG]) {
found[s-BEG]=1 ;
tcopy(&save[s-BEG][0],t) ;
125 return --remains <= 0 ;
} else
return 0;
}
} else
130 return 0 ;
}
/* Enumération
* t est le tableau des plaques (à un instant donné).
135 * nb est la dernière plaque valide.
* nodes est le tableau des arbres, nodes[i] correspondant à t[i].
all renvoie vrai lorsque poursuivre l'énumération est devenu inutile.
*/
140
int all(num *t, num *nb, node *nodes) {
num *i,*j ;
node *in, *jn ;
145
if (nb-t == 1) { /* cas terminal */
num a=t[0], b=t[1] ;
node *an = nodes, *bn = nodes+1 ;
node w;
150
SETNODE(&w,'+',an,bn) ;
if (pall(a+b,&w,1))
return 1;
155 SETNODE(&w,'*',an,bn) ;
if (pall(a*b,&w,1))
return 1;
if (a > b) {
160 SETNODE(&w, '-', an, bn) ;
if (pall(a-b,&w,1))
return 1;
if (a % b == 0) {
SETNODE(&w, '/', an, bn) ;
165 if (pall(a/b,&w,1))
return 1;
}
} else if (a < b) {
SETNODE(&w, '-', bn, an) ;
170 if (pall(b-a,&w,1))
return 1;
if (b % a == 0) {
SETNODE(&w, '/', bn, an) ;
if (pall(b/a,&w,1))
175 return 1;
}
} else {
w.tag = K ;
w.arg.k = 1 ;
180 if (pall(1,&w,1))
return 1;
}
return 0;
}
185
/* Cas général */
for (i=t, in=nodes ; i < nb ; i++, in++) {
num a = *i ;
node an = *in ;
190
for (j = i+1, jn=in+1; j <= nb ; j++, jn++) {
num b = *j ;
node bn = *jn ;
if ((an.tag != K) || (bn.tag != K) || (a <= b)) {
195
*j = *nb ;
*jn = *(nodes+(nb-t));
if (an.tag != '+') {
/* Inutile de tester (a+b)+c et (a+c)+b, car a+(b+c) l'est */
200 *i = a+b ;
SETNODE(in,'+',&an,&bn) ;
if (pall(*i,in,nb-t) || all(t, nb-1, nodes))
return 1;
}
205 if (an.tag != '*' && a != 1 && b != 1) { /* idem */
*i = a*b ;
SETNODE(in,'*',&an,&bn) ;
if (pall(*i,in,nb-t) || all (t, nb-1, nodes))
return 1;
210 }
if (a != b) {
*i = SUB(a,b) ;
if (a > b)
SETNODE(in,'-',&an,&bn) ;
215 else
SETNODE(in,'-',&bn,&an) ;
if (pall(*i,in,nb-t) || all(t, nb-1, nodes))
return 1 ;
}
220 if (MOD(a,b) == 0 && a != 1 && b != 1) {
*i = DIV(a,b) ;
if (a > b)
SETNODE(in,'/',&an,&bn) ;
else
225 SETNODE(in,'/',&bn,&an) ;
if (pall(*i,in,nb-t) || all(t, nb-1, nodes))
return 1;
}
}
230 *j = b ;
*jn = bn ;
}
*i = a ;
*in = an ;
235 }
return 0 ;
}
int main (int argc, char **argv) {
240 int i;
int nb = argc-1 ;
if (argc > 1 && (strcmp("-o",argv[1]) == 0)) {
nb--;
245 opt = 1 ;
argv++ ;
}
pmax = nb ;
for (i=0 ; i < nb ; i++) {
250 nodes[i].tag = K ;
nodes[i].arg.k = plaque[i] = atoi(argv[i+1]) ;
pall(plaque[i],&nodes[i],pmax) ;
}
255 all(plaque,plaque+nb-1,nodes) ;
for (i=BEG ; i <= END ; i++) {
printf(NUMFORM ":_",i) ;
if (was_found(i)) {
print(&save[i-BEG][0]) ;
260 putchar('\n') ;
} else
printf("?????\n") ;
}
return 0 ;
265 }
|
Programmation « dynamique »
En C
#include<stdio.h>
#include<stdlib.h>
#define NP 16
5 int np;
typedef unsigned int val;
#define FORMAT "%u"
val plaque[NP] ;
10 typedef unsigned int bset;
void pbset(bset s) {
int i ;
15 for (i = np ; i > 0 ; i--) {
putchar(s % 2 ? '+' : '-') ;
s /= 2 ;
}
}
20
/* Ensembles des entiers resultat */
typedef struct iset {
val here;
struct iset *left,*right;
25 unsigned char depth:8 ;
} iset ;
iset* sets[1 << NP];
30 int icard(iset *p) {
if (!p)
return 0;
else {
int r = icard(p->left) ;
35 r++;
return r + icard(p->right) ;
}
}
40 int prof (iset *p) {
if (!p)
return 0 ;
else {
int pl = prof(p->left) ;
45 int pr = prof(p->right) ;
if (pl < pr)
return 1+pr;
else
return 1+pl;
50 }
}
#define K '\0'
typedef struct ival {
55 val me ;
char tag:8 ;
struct ival *g,*d;
} ival ;
60
void pival(ival *t) {
if (t->tag == K)
printf(FORMAT,t->me) ;
else {
65 putchar('(') ;
pival(t->g) ;
putchar(t->tag) ;
pival(t->d) ;
putchar(')') ;
70 }
}
#define NALLOC 1024
ival *vbuff ;
75 int iv ;
ival *alloc_ival(val me, char tag, ival *g, ival *d) {
ival *r ;
80
if (iv == 0) {
vbuff = (ival *)malloc(NALLOC*sizeof(ival)) ;
iv = NALLOC ;
if (vbuff == NULL) {
85 fprintf(stderr,"Plus_de_mémoire\n") ;
exit(2) ;
}
}
r = vbuff ; iv-- ; vbuff++ ;
90 r->me = me ; r->tag = tag ; r->g = g ; r->d = d ;
return r ;
}
95 ival *construct(val k, bset s) ;
ival *csingle(val k, val a, iset *right, bset bl, bset br) {
if (!right)
return NULL ;
100 else {
val b ;
ival *r ;
r = csingle(k, a, right->left, bl, br) ;
105 if (r) return r ;
b = right->here ;
if (k == a+b)
return alloc_ival (k, '+', construct(a, bl), construct(b, br)) ;
110 if (k == a*b)
return alloc_ival (k, '*', construct(a, bl), construct(b, br)) ;
if (a > b) {
if (k == a-b)
115 return alloc_ival (k, '-', construct(a, bl), construct(b, br)) ;
if (b*k == a)
return alloc_ival (k, '/', construct(a, bl), construct(b, br)) ;
} else {
if (k == b-a)
120 return alloc_ival (k, '-', construct(b, br), construct(a, bl)) ;
if (a*k == b)
return alloc_ival (k, '/', construct(b, br), construct(a, bl)) ;
}
return csingle(k, a, right->right, bl, br) ;
125 }
}
ival *cboth(val k, iset *left, iset *right, bset bl, bset br) {
ival *r ;
130
if (!left) return NULL ;
r = cboth(k, left->left, right, bl, br) ;
if (r) return r ;
135
r = csingle(k, left->here, right, bl, br) ;
if (r) return r ;
return cboth(k,left->right, right, bl, br) ;
140 }
ival *csubsets(val k, bset s, bset r, bset rr, bset mask) {
if (s == 0) {
145 if (rr) {
#ifdef DEBUG
putchar('_') ; pbset(r) ;
putchar('_') ; pbset(rr) ;
fflush(stdout) ;
150 #endif
return cboth(k, sets[r], sets[rr], r, rr);
} else
return NULL ;
155 } else {
ival *res ;
while (s % 2 == 0) {
s /= 2 ; mask <<= 1 ;
160 }
res = csubsets(k, s/2,r | mask ,rr, mask << 1) ;
if (res) return res ;
return csubsets(k, s/2, r, rr | mask, mask << 1) ;
165 }
}
ival *construct(val k, bset s) {
bset i=0 ;
170 while (s % 2 == 0) {
s /= 2 ; i++ ;
}
s /= 2 ;
if (s)
175 return csubsets(k, s, 1 << i, 0, 1 << (i+1));
else {
return alloc_ival(plaque[i], K, NULL, NULL) ;
}
}
180
iset *sbuff ;
int is ;
iset *alloc_iset(val here) {
185 iset *r ;
if (is == 0) {
sbuff = (iset *)malloc(NALLOC*sizeof(iset)) ;
is = NALLOC ;
190 if (sbuff == NULL) {
fprintf(stderr,"Plus_de_mémoire\n") ;
exit(2) ;
}
}
195 r = sbuff ; is-- ; sbuff++ ;
r->left = r->right = NULL ;
r->here = here ;
r->depth = 1 ;
return r ;
200 }
unsigned char depth(iset *s) {
return s ? s->depth : 0 ;
205 }
iset *balance(iset *s) {
int hl = depth(s->left) ;
int hr = depth(s->right) ;
210
if (hl-hr > 1) {
iset *l=s->left ;
iset *ll=l->left ;
iset *lr=l->right ;
215 if (depth(lr) <= depth(ll)) {
unsigned char d = 1+depth(lr) ;
s->left = lr ; s->depth = d ;
l->right = s ; l->depth = 1+d ;
return l ;
220 } else {
unsigned char d = depth(ll) ;
s->left = lr->right ; s->depth = d+1 ;
l->right = lr->left ; l->depth = d+1 ;
lr->left = l ; lr->right = s ; lr->depth = d+2 ;
225 return lr ;
}
} else if (hr-hl > 1) {
iset *r = s->right ;
iset *rl = r->left ;
230 iset *rr = r->right ;
if (depth(rl) <= depth(rr)) {
unsigned char d = 1+depth(rl) ;
s->right = rl ; s->depth = d ;
r->left = s ; r->depth = 1+d ;
235 return r ;
} else {
unsigned char d = depth(rr) ;
s->right = rl->left ; s->depth = d+1 ;
r->left = rl->right ; r->depth = d+1 ;
240 rl->left = s ; rl->right = r ; rl->depth = d+2 ;
return rl ;
}
} else {
s->depth = hl > hr ? hl+1 : hr+1 ;
245 return s ;
}
}
iset *insert(val k, iset *s) {
250 if (!s) {
return alloc_iset(k) ;
} else {
val c = s->here ;
if (k < c) {
255 iset *r = insert(k, s->left) ;
if (r) {
s->left = r ;
return balance(s) ;
} else
260 return NULL ;
} else if (k > c) {
iset *r = insert(k, s->right) ;
if (r) {
s->right = r ;
265 return balance(s) ;
} else
return NULL ;
}
return NULL ;
270 }
}
#define BEG 1
#define END 1000
275 ival *res[END-BEG+1];
int remains=END-BEG+1;
bset curset;
280 void print_res(void) {
val i ;
for (i = BEG ; i <= END ; i++) {
printf(FORMAT ":_", i) ;
if (res[i-BEG] == NULL)
285 printf("?????") ;
else
pival(res[i-BEG]) ;
putchar('\n') ;
}
290 }
void record_res(val k) {
if (BEG <= k && k <= END) {
295 if (res[k-BEG] == NULL) {
res[k-BEG] = construct(k, curset) ;
#ifndef PRINT
if (--remains == 0) {
print_res() ;
300 exit(0) ;
}
#endif
}
}
305 }
iset *tinsert(val k, iset *r) {
iset *rr ;
310 record_res(k) ;
rr = insert(k, r) ;
return rr ? rr : r ;
}
315 iset *single(val a, iset *right, iset *r) {
if (!right)
return r ;
else {
val b = right->here ;
320 val k ;
r = single(a, right->left, r) ;
k = a+b ;
325 r = tinsert(k, r) ;
k = a*b ;
r = tinsert(k, r) ;
330 if (a > b) {
k = a-b ;
r = tinsert(k, r) ;
if (a % b == 0) {
335 k = a/b ;
r = tinsert(k, r) ;
}
} else {
k = b-a ;
340
if (k != 0) {
r = tinsert(k, r) ;
}
345 if (b % a == 0) {
k = b/a ;
r = tinsert(k, r) ;
}
}
350 }
return single(a, right->right, r) ;
}
iset *both(iset *left, iset *right, iset *r) {
355 if (!left)
return r;
r = both(left->left, right, r) ;
r = single(left->here, right, r) ;
return both(left->right, right, r) ;
360 }
void subsets(bset s, bset r, bset rr, bset mask) {
365 if (s == 0) {
if (rr) {
s = r | rr ;
#ifdef DEBUG
putchar('_') ; pbset(r) ;
370 putchar('_') ; pbset(rr) ;
fflush(stdout) ;
#endif
curset = s ;
sets[s] = both(sets[r], sets[rr], sets[s]);
375 }
}
else {
while (s % 2 == 0) {
s /= 2 ; mask <<= 1 ;
380 }
subsets(s/2,r | mask ,rr, mask << 1) ;
subsets(s/2,r, rr | mask, mask << 1) ;
}
}
385
void topsubsets(bset s) {
bset i=0 ;
while (s % 2 == 0) {
s /= 2 ; i++ ;
390 }
s /= 2 ;
if (s)
subsets(s, 1 << i, 0, 1 << (i+1));
else {
395 curset = 1 << i ;
sets[curset] = tinsert(plaque[i],sets[curset]) ;
}
}
400
void piset(iset *p, bset s) {
if (p) {
405 piset(p->left, s) ;
printf(FORMAT ":_", p->here);
pival(construct(p->here, s)) ;
putchar('\n') ;
piset(p->right, s) ;
410 }
}
void cnp(int n, int p, bset r, bset mask) {
if (p == 0) {
415 if (r != 0) {
#ifdef PRINT
int ic,in;
pbset(r) ;
fflush(stdout) ;
420 #endif
topsubsets(r) ;
#ifdef PRINT
ic = icard(sets[r]) ;
in = prof(sets[r]) ;
425 printf(":_%d,_%d\n",in,ic) ;
#ifdef DEBUG
piset(sets[r], r) ;
putchar('\n');
#endif
430 #endif
}
} else if (p <= n) {
cnp(n-1, p-1, r | mask, mask << 1) ;
cnp(n-1, p, r, mask << 1) ;
435 }
}
void cardsubsets(int n, int p) {
cnp(n, p, 0, 1) ;
440 }
int main (int argc, char **argv) {
int i;
bset s, full;
445
np = argc-1 ;
full = (1 << np)-1 ;
for (i=0 ; i < np ; i++) {
450 plaque[i] = atoi(argv[i+1]) ;
}
for (i=1 ; i <= np ; i++) {
cardsubsets(np,i) ;
455 }
print_res() ;
return 0;
}
460
465
En Caml
type t = {i : int ; t : term}
and term =
| Const
5 | Op of char * t * t
let rec taille x = match x.t with
| Const -> 1
| Op (_,x,y) -> taille x+ taille y
10 ;;
let rec rev_append xs ys = match xs with
| [] -> ys
| x::rem -> rev_append rem (x::ys)
15
let rev_map f xs =
let rec do_rec f r = function
| [] -> r
| x::xs ->
20 do_rec f (f x::r) xs in
do_rec f [] xs
let rec merge r xs ys = match xs,ys with
25 | [],_ -> rev_append r ys
| _,[] -> rev_append r xs
| x::rxs, y::rys ->
if x.i < y.i then merge (x::r) rxs ys
else if y.i < x.i then merge (y::r) xs rys
30 else
merge (if taille x <= taille y then x::r else y::r)
rxs rys
let rec step r = function
35 | [] -> r
| [xs] -> xs::r
| xs::ys::rem ->
step (merge [] xs ys::r) rem
40 let rec merges xss = match step [] xss with
| [] -> []
| [r] -> r
| r -> merges r
45
let rec app op r xs ys = match xs with
| [] -> merges r
| x::rem ->
50 app
op
(List.map (fun y -> op x y) ys::r)
rem ys
;;
55
let sums xs ys = app (fun x y -> {i=x.i+y.i ; t= Op ('+',x, y)}) [] xs ys
and mults xs ys = app (fun x y -> {i=x.i*y.i ; t= Op ('*',x, y)}) [] xs ys
let tdiff x y = {i=x.i-y.i ; t=Op ('-',x,y)}
60
let diff_end x ys = List.map (fun y -> tdiff y x) ys
let rec diff r x = function
| [] -> r
| y::ys ->
65 if y.i < x.i then diff (tdiff x y::r) x ys
else if x.i=y.i then
merge [] r (diff_end x ys)
else
merge [] r (diff_end x (y::ys))
70
(* x > y *)
let tdiv x y r =
if x.i mod y.i = 0 then
75 {i=x.i/y.i ; t = Op ('/',x,y)}::r
else
r
let div_end x ys =
80 List.fold_right (fun y r -> tdiv y x r) ys []
let rec div r x = function
| [] -> r
| y::ys ->
85 if y.i < x.i then div (tdiv x y r) x ys
else
merge [] r (div_end x (y::ys))
let rec app2 f r xs ys = match xs with
90 | [] -> merges r
| x::rem ->
app2
f
(f [] x ys::r)
95 rem ys
let diffs xs ys = app2 diff [] xs ys
and divs xs ys = app2 div [] xs ys
100 let zyva xs ys =
merge []
(merge [] xs ys)
(merge []
(merge [] (sums xs ys) (mults xs ys))
105 (merge [] (diffs xs ys) (divs xs ys)))
let rec print_item x = match x.t with
| Const -> print_int x.i
| Op (c,x,y) ->
110 print_char '(' ;
print_item x ;
print_char c ;
print_item y ;
print_char ')'
115 ;;
let rec pr_list = function
| [] -> print_newline ()
| x::rem ->
120 print_int x.i ; print_char '=' ;
print_item x ; print_char '\n' ; pr_list rem
;;
125
let rec partitions xs = match xs with
| [] -> []
| [_] -> []
130 | [x ; y] -> [[x],[y]]
| x::rem ->
let p = partitions rem in
List.fold_left
(fun r (l,m) -> (x::l,m)::(l,x::m)::r)
135 [[x],rem] p
;;
let t = Hashtbl.create 107
140 let rec pr_set = function
| [] -> print_newline ()
| x::rem ->
print_int x ; print_char ' ' ; pr_set rem
;;
145
let rec ceb l =
try Hashtbl.find t l
with Not_found ->
let r = match l with
150 | [] -> assert false
| [x] -> [{i=x ; t=Const}]
| s ->
let ps = partitions s in
merges
155 (rev_map
(fun (l,m) ->
let n1 = ceb l and n2 = ceb m in
zyva n1 n2)
ps) in
160 Hashtbl.add t l r ;
r
;;
let plaques = ref []
165 ;;
for i=1 to Array.length Sys.argv-1 do
plaques := !plaques @ [int_of_string Sys.argv.(i)]
done
170 ;;
let rec end_select max = function
| [] -> []
| x::xs ->
175 if x.i > max then []
else
x::end_select max xs
let rec select min max = function
180 | [] -> []
| x::xs ->
if x.i >= min then end_select max (x::xs)
else
select min max xs
185 ;;
pr_list ((ceb !plaques))
;;
190
This document was translated from LATEX by
HEVEA.