Discussion :

[sm1z2000]

Bonjour,

J'ai besoin de votre aide pour realiser un algorithme qui me permettra d'approcher une valeur donnee. J'explique:
J'ai des liste de valeurs du type:
n: est la valeur max que je peux atteindre.
si n=4 alors
(1)
...
(4)

(2 3)
(2 4)
...
(4 4)

(2 3 3)
...
(4 4 4)

sachant que les membres doivent rester dans l'ordre croissant tq: (2 3 4)
(3 3 3) ou (2 4 4)
Voila pour plus d'infos n'hesitez pas a me demander des questions.
Merci

[pseudocode]

Pour être bien sur d'avoir compris:

Tu cherches une suite croissante d'entiers positifs a1,...,an (1<=ai<=n) tels que, pour un valeur X donnée, la distance D = abs( a1*a2*...*an - X) soit minimale ?

[sm1z2000]

Effectivement.
c'est une bonne formulation du probleme.
Mais il faut que le length de la liste soit bon car:

dans le cas ou 4 est la capacite max on a (4 4) et (2 2 2) qui donne le meme resultat 8.
donc en fait a (4 4) on passe a (2 3 3)
et puis a (4 4 4) on passe a (2 3 3 4) et ainsi de suite.
Et en plus de ca il trouve l'algo pour le cas n...

Merci pour l'aide en tt cas.

[pseudocode]

Et si tu décomposais ta valeur donnée "X" en facteurs premiers.

Ca permettrait de voir si tu peut l'atteindre de manière exacte avec les entiers dont tu disposes. Si ce n'est pas le cas, tu peux ensuite tester "X-1" et "X+1", et ainsi de suite.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
valeurs possibles: 1,2,3,4
valeur a atteindre X=21 
 
D=0
21 = 3 * 7 --> fail
 
D=1
20 = 2^2 * 5 --> fail
22 = 2 * 11 --> fail
 
D=2
19 = 19 --> fail
23 = 23 --> fail
 
D=3
18= 2 * 3^2 --> ok  (2,3,3)
24= 2^3 * 3 --> ok  (2,2,2,3)
 
Meilleur choix : (2,3,3)

[sm1z2000]

C'est une idee, mais le soucis est que la valeur approchee doit etre = ou superieur a la valeur a atteindre..
De plus dans ce cas (2,2,2,3)=24 < (4,4,4)=64 donc pas possible
puisque: ou 4 = a la valeur max
(1)
(2)
(3)
(4)

(2 3)=5
(2 4)=6
(3 4)=12
(4 4)

(2 3 3)=18
(2 3 4)=24
(3 3 3)=27
(2 4 4)=32
(3 3 4)=36
(3 4 4)=48
(4 4 4)=64
...ainsi de suite

[pseudocode]

C'est une idee, mais le soucis est que la valeur approchee doit etre = ou superieur a la valeur a atteindre..

Bah il suffit de tester uniquement X, X+1, X+2, ...

De plus dans ce cas (2,2,2,3)=24 < (4,4,4)=64 donc pas possible
puisque: ou 4 = a la valeur max

j'ai rien compris a cette remarque.

Tu veux dire que (2,2,2,3) n'est pas une solution car la liste contient trop de valeurs ? Ou alors que tu préfères la forme plus compacte (2,3,4) ? ... ?

[sm1z2000]

Oui on peut que incrementer mais pour des valeurs superieurs a (4 4 4 4 4)=1024 ca devient complique de trouver les facteurs premiers.

Pour la 2eme question, je voulais dire que: qd j'atteins la valeur max ici 4^n je rajoute un nouvel "etage" a ma liste(je veux dire par etage le length)
(1)
(2)
(3)
(4) -->4^1 on rajoute une longueur

(2 3)=5
(2 4)=6
(3 4)=12
(4 4)-->4^2 on rajoute une longueur

(2 3 3)=18
(2 3 4)=24
(3 3 3)=27
(2 4 4)=32
(3 3 4)=36
(3 4 4)=48
(4 4 4)=64-->4^3 on rajoute une longueur

Je ne sais pas si j'ai ete assez precis?

[pseudocode]

Oui on peut que incrementer mais pour des valeurs superieurs a (4 4 4 4 4)=1024 ca devient complique de trouver les facteurs premiers.

Tu n'as pas vraiment à trouver tous les facteurs, mais juste a vérifier si ta valeur X est décomposable par les facteurs dont tu disposes (les valeurs de 1 à n)

X=22 et L=(2,3,4)=(2,3,2^2)
22 divisible par 3 : non
22 divisible par 2 : oui, reste 11
11 divisible par 3 : non
11 divisible par 2 : non
donc X ne peut pas se décomposer avec des facteurs 2 et 3

Pour la 2eme question, je voulais dire que: qd j'atteins la valeur max ici 4^n je rajoute un nouvel "etage" a ma liste(je veux dire par etage le length)

hum... ca m'a l'air juste d'un jeu d'écriture. Toutes tes listes peuvent s'écrire sous forme d'une liste de taille N, sous réserve de mettre des "1" au début.

(1) = (1,1,1)
(2) = (1,1,2)
(3) = (1,1,3)
(4) = (1,1,4)

(2 3) = (1,2,3)
(2 4) = (1,2,4)
(3 4) = (1,3,4)
(4 4) = (1,4,4)

...

[sm1z2000]

Pour l'idee de la decomposition en facteur premier, ca m'a l'air d'etre une bonne idee. Je vais essaye de voir s'il ny a pas de probleme avec.

Sinon pour le jeu d'ecriture que j'utilise est:
On a un arbre de buffer et a chaque noued on a une divergence donnee qui depend de la capacite max du buffer a diverger.Ici ds notre cetait 4 ainsi:
(2 4) veut dire qu'on a un 1er buffer qui va diverger de 2(cad 2 branche ou de fil) ensuite a chaqu'une des deux branches il y aura un buffer qui va diverger de 4 ce qui donne 8 fil en sortie.
De plus pour des raisons physiques les divergences doivent etre ordonnees ds l'ordre croissant dans la liste.

[sm1z2000]

Bonjour,
J'ai developpe l'idee sur les facteurs premier, mais le probleme est par rapport au length de ma liste car par exemple dans le cas 37 sorties(avec divergences max =3), ca me donne la liste:
(2 2 2 2 2 2)=64 alors que moi je veux (2 3 3 3)=54
Voici mon code, trLargestExp me donne la puissance de l'element premier,Depth c le length max ici 3:

procedure( trPF( aNumber divisor Depth)
let( ( ; locals

result
exp
( num aNumber )
)
while( num > 1 && divisor > 1
when( ( exp = trLargestExp( num divisor )) > 0

(for i 1 exp
result=cons(divisor result))
;result = cons( list( divisor exp ) result )
num = num / divisor ** exp
) ; when
divisor-- ;;; try next divisor
) ; while
result
) ; let
) ; procedure


Merci pour l'aide en tout cas

[pseudocode]

Avant de continuer, quels sont les ordres de grandeurs de tes valeurs : nombre de facteurs, valeurs a atteindre, longueur max de la séquence ?

Si ces valeurs sont assez faibles, il vaut peut etre mieux aller vers des algos plus classiques d'exploration (genre branch and bound)