Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Répondre
Résumé de la discussion (messages les plus récents en premier)
- golguup
- 19-12-2011 22:58:13
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!)
- José
- 19-12-2011 22:20:53
hello,
Je vais tenter voir ce que ca donne ..
Je sors mon compilateur :-)
Merci bcp.
José
- Golgup
- 18-12-2011 22:47:33
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..
- José
- 18-12-2011 21:12:38
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é
- José
- 18-12-2011 12:58:14
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é