Forum de mathématiques - Bibm@th.net

José

Invité

Trouver la valeur la + proche d'une valeur donnée à partir de Nvaleurs

Bonjour,

Je cherche un methode qui trouve la valeur la plus proche d'une valeur en utilisant de 1 à N valeurs ( avec N = 1 à 100 )
ex : Comment trouver la valeur la plus proche de 100 à partir des valeurs suivantes 20 33 16 3 6 26 9 13 43 10.

C'est une espece de "le compte est presque bon"

Si vous avez des pistes, faites m'en part.
D'avance merci pour vos retours
José

José

Invité

Re : Trouver la valeur la + proche d'une valeur donnée à partir de Nvaleurs

Re-bonjour,

J'ai une solution -> J'itere sur toutes les combinaisons possibles  ( exp N ).  Je fais un 'force brut'.
mais c'est tres couteux en temps de calcul et  ca bloque tres rapidement qd N devient grand.  Qd N > 20, c'est plus tres utilisable.

Je cherche une solution plus subtile et qui puisse etre utilisée avec N compris entre 20 et 50.

José

Golgup

Membre actif

Inscription : 09-07-2008

Messages : 574

Re : Trouver la valeur la + proche d'une valeur donnée à partir de Nvaleurs

Je crois que j'ai trouvé mieux! mais je n'ai pas essayé de voir encorE la complexité?

L'algorithme (récursif) consiste à réduire la séquence à chaque itération:

Ont peut borner Vr (car V borné entre Vr et Vr+1):

[tex]\left(1+V\right)+\frac{1}{N}\sum^{N}_{k=1}\left|V-{V}_{k}\right|\,>\,{V}_{r}\,>\,\left(V-1\right)-\frac{1}{N}\sum^{N}_{k=1}\left|V-{V}_{k}\right|[/tex]

La première chose à faire est de trier la suite , ça ce fait très rapidement (tris par tas en nlogn), ensuite, on réduit la suite à chaque itération (on dichotomise ).

Par exemple, soit la suite [1, 7, 3, 12, 21, 8, 30, ]  on recherche l’élément le plus proche de 17:

première étape:  tri;  [1, 3, 7, 8, 12, 21, 30, ]

deuxième etape: reduction 1 , les calculs donnent  [tex]28>{V}_{r}>6[/tex]

troisième etape: supression de tous les element plus petits que 6 ainsi que ceux plus grands que 28 , nouvelle liste:  [7, 8, 12, 21, ] (continuer tant qu'il reste plus de un element dans la liste..

quatrieme etape: reduction 2 , les calculs donnent  [tex]25>{V}_{r\,}>9[/tex] , nouvelle liste:  [ 12, 21, ]

cinquieme etape: reduction 3 , on a [tex]22>{V}_{r}>12[/tex] , nouvelle liste:  [ 21, ]

il reste un élément dans la liste, 21, retourner 21.

Ici le tri sert à ne pas avoir a parcourir la liste en entier a chaque fois, ( pour voir si la condition de suppression est vérifiée) , car on s’arrête une fois qu'on trouve un élément supérieur (selon borne sup) ou inférieur (selon borne inf) a la nouvelle borne.

José, je serait curieux de voir ce que ça donne sur les liste ou tu as tester la force brute! Mais je pense que tu peux largement l'utiliser pour des liste de 50 et beaucoup plus..

Dernière modification par Golgup (18-12-2011 23:16:55)

José

Invité

Re : Trouver la valeur la + proche d'une valeur donnée à partir de Nvaleurs

hello,

Je vais  tenter voir ce que ca donne ..
Je sors mon compilateur :-)

Merci bcp.
José

golguup

Invité

Re : Trouver la valeur la + proche d'une valeur donnée à partir de Nvaleurs

Non, je crois que je n'ai pas répondu a la question: (j'ai mal compris le problème) , il s'agit de calculer a partir des opérations +-*/ un entier de référence grâce aux entiers de la liste?!  ou bien de rechercher l’élément de la liste le plus proche de la valeur de référence (car dans ce cas ce n'est pas exponentiel mais linéaire!)