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) ? ... ?