Discussion :

[lautrec1]

Bonjour,

Je (re)code un solveur de mots mêlés en C. C'est mon 3è code. J'ai implémenté un algo (ésotérique) pour les deux premiers codes (+-350 lignes)
On m'a proposé un algo plus élégant qui est nettement plus court.

La taille des données max est M=50 et N=25.

Voilà ce que j'obtiens, le 3è algo (l'élégant) me fait dépasser la capacité de mémoire de mon win XP. Les pointeurs sont codés sur 16bits. A l'analyse, c'est logique, puisque la mémoire allouée est de l'ordre de (1,5*sizeof(char)+sizeof(int))*(M+N)*(M.N) (--> 515.625, plus grand que 2^16)

Les codes non élégants requièrent (8*sizeof(int)+sizeof(char))*M*N (-->41250, sous 2^16).

Je me dis que Win XP est deprecated, mais je me demande aussi :que penser d'un code qui résoud une grille de 50*25 caractères pour un problème linéaire mais qui ne tourne pas sur une machine de 2006 ????

Voilà quelle approche privilégier ?

Bien à vous,

[Invité]

salut,

500kB c'est rien, change plutot ta datastructure.
Au lieu d'allouer sur un espace contigu, fais plutot plein de petites alloc!

[lautrec1]

Au lieu d'allouer sur un espace contigu

J'ai surtout changé le compilo. Mon TurboC++ (1991) travaille en 16 bits
Avec gcc les adresses utilisables sont de 32 bts.

Mon problème est de choisir l'algo et il s'agit d'un compromis élégance-complexité

Maintenant, je dois choisir entre deux alternatives:
pour une grille rectangulaire de taille M*N, il faut trouver K mots.

1 codée et validée) # if : M*N*(8*K+32)
2 élégante en construction) # if : M*N*(8*K + 6*(M+N))

Ah oui, le but de l'affaire est d'avoir un code pédagogique. Quelle option choisir ?

[droggo]

Toe,

Si c'est pour être pédagogique, la solution est particulièrement simple : diminuer la taille de la matrice.

D'autre part, pourquoi persister à utiliser un compilateur qui ne connaît que le 16 bits ?

(Tant que tu y es, tu pourrais virer XP et remettre MS-DOS )

[lautrec1]

D'autre part, pourquoi persister à utiliser un compilateur qui ne connaît que le 16 bits ?

En effet, j'utilise GCC depuis quelques heures. Vive les 32bits. (Quelques minutes après mon post, je me suis rendu compte de l'erreur )

Comment réduire la taille de la matrice ? Chaque élément est pertinent.

Ex de grille M=N=8:

EELLERIG
TTNBPBSM
ERTEEAEE
GOCERRHH
UEIDLUEC
OAIAABMM
RNNLNTAA
ELLIPROT

k mots à trouver:

bar
raie
plie
tanche
merlan
murene
rouget
ablette
sardine
eperlan
girelle
torpille