Ne garder que les valeurs d'une certaine distance dans un tableau

**Sylvain255** · 08/10/2022, 19h17

Bonjour,
j'explique mon problème : j'ai un tableau à une dimension avec des valeurs réelles. Je voudrais ne garder que certaines valeurs de façon à ce que l'écart entre chacune des valeurs soit supérieur à un certain seuil delta. Il faut garder le maximum de valeurs. Je n'y arrive pas. Merci de m'aider.
Edit : plus avant dans le problème, un second tableau indicé comme le premier permet de choisir les valeurs à garder car il peut y avoir plusieurs valeurs à garder : soit garder prioritairement les valeurs du premier tableau dont les valeurs dans le second tableau au même indice sont les plus proche d'une certaine valeur V ou deuxième algorithme garder prioritairement les valeurs du premier tableau dont les valeurs dans le second tableau au même indice sont les plus grandes

Bien cordialement

**dourouc05** · 08/10/2022, 21h33

Je ne suis pas sûr d'avoir bien compris ta demande. Je vois deux interprétations possibles :
- garder les éléments s'ils sont assez distants des éléments avant et après : si |x[i-1] - x[i]| ≥ δ et |x[i] - x[i + 1]| ≥ δ, alors on garde la valeur en i ;
- garder les éléments assez distants par rapport à une valeur fixe V : si |V - x[i]| ≥ δ, alors on garde i.

**tbc92** · 08/10/2022, 23h47

Comme Dourouc05, je n'ai pas compris la question.
Mais sur le cas 1, qui me paraît à peu près clair, je ne suis pas d'accord avec la solution proposée.
Si l'écart mini est de 10 par exemple, et qu'on a 50 valeurs espacées de 3 en 3 par exemple, la solution proposée gardera uniquement les 2 valeurs extrêmes.

L'autre piège très courant à éviter quand on parcourt une liste, et qu'on doit supprimer des éléments, c'est qu'il faut parcourir la boucle à partir de la fin. Sinon, dès qu'on a commencé à supprimer des lignes, on croit traiter une certaine ligne, et on en traite une autre.

Code :

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

1
2
3
Pour i = taille_tableau -1 à 1 pas -1
 si tablo(i) > tablo(i+1) - ecart_minimum alors supprimerligne(i)
fin

**Sylvain255** · 09/10/2022, 11h55

Bonjour dourouc c'est la première version

je pense que l'algo de tbc marche à condition de trier le tableau avant, oui si je devais reformuler la question je ne veux garder que les éléments du tableau qui ont un écart minimum de delta

**Sylvain255** · 09/10/2022, 13h11

non cet algo ne fonctionne pas !
en voici un exemple : [2,4,6,8,10,12,14,16,18,20,22,24,26,28,30]
l'écart minimum est 3
cet algo va supprimer toutes les valeurs alors qu'il faut en garder par exemple 30-26=4

**tbc92** · 09/10/2022, 13h54

L'algo que je propose fonctionne, si effectivement les données sont triées auparavant.

Etape 1 : Je compare 28 avec 30, l'écart est trop faible, je supprime 28 ; le tableau contient dorénavant 2 4 6 8 10 12 14 16 18 20 22 24 26 30
Etape 2 : Je compare 26 avec le nombre suivant, c'est à dire 30 (et non 28, il a été supprimé), l'écart est suffisant, je ne fais rien.
Etape 3 : Je compare 24 avec le nombre suivant, c'est à dire 26, l'écart est insuffisant, je supprime 24

Etc etc.
Je ne duplique pas le tableau en 'gardant' les valeurs qui m'intéressent (garder= recopier dans ce contexte)
Je manipule uniquement le tableau de données en supprimant les données en trop.

**Sylvain255** · 09/10/2022, 13h56

ah ok super merci en fait j'avais modifié ta condition en :
abs(t[i+1]-t[i])<seuil
car je n'avais pas compris

**tbc92** · 09/10/2022, 14h40

Tu peux ajouter abs() ... mais ça ne change rien. Il faut effectivement que le tableau soit déjà trié.

**Guesset** · 11/10/2022, 12h19

Bonjour,

Il n'y a pas unicité de la solution.

1 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 Problème avec exclusion si d < 3
_ 2 _ 6 _ 10 __ 14 __ 18 __ 22 __ 26 __ 30 Solution 1 <-
1 _ 4 _ 8 __ 12 __ 16 __ 20 __ 24 __ 28 __ Solution 2 ->
1 _ 4 _ 8 __ 12 __ 16 __ 20 __ 24 __ __ 30 Solution 2' ->
1 _ 4 _ 8 __ 12 __ 16 __ 20 __ __ 26 __ 30 Solution 2" ->

Je pense, mais ne l'ai pas démontré que les solutions montantes et descendantes sont de même longueur. Si elles sont identiques cela va de soi. Si elles sont entrelacées elles sont mécaniquement de même longueur (pas nécessairement n/2). Et le mix des deux types se compose d'une partie commune et d'une partie entrelacée (mais il reste à confirmer que le passage entre les 2 parties d'induit pas de différence).

Salutations

**tbc92** · 11/10/2022, 12h52

Tout à fait, il y a des solutions en pagaille.
Les 2 solutions montantes et descendantes sont faciles à implémenter, et sont forcément optimales.

Si on était en dimension 2 ou plus, ce serait beaucoup plus compliqué, pardon, beaucoup moins simple.

**Sylvain255** · 11/10/2022, 14h52

j'en ai parlé à un prof de fac qui me dit qu'on peut aller en indice croissant plutôt qu'en indice décroissant ? Est-ce vrai et si non avez-vous un exemple détaillé que je puisse lui montrer qu'il a tort

**tbc92** · 11/10/2022, 15h09

On peut évidemment aller en indice croissant, mais il faut être beaucoup plus prudent. Le code est un peu plus compliqué, mais c'est un exercice intéressant à faire.

En pratique, si je voulais avoir en résultat la 2ème proposition de Guesset, je trierais les données par ordre décroissant, et je garderais la boucle comme actuellement (avec des valeurs absolues).
Mais un parcours en montant est possible aussi. C'est juste plus compliqué.

**Sylvain255** · 11/10/2022, 15h10

oui je sais j'ai déjà été confronté au problème, mais avez-vous un exemple à dérouler où l'on voit que c'est plus compliqué que je lui montre ?

**tbc92** · 11/10/2022, 15h50

Cherche un peu.

Tout ceci m'a l'air d'un exercice scolaire, et on t'a déjà beaucoup aidé.

Montrer que le code 'basique' ne fonctionne pas, c'est facile : tu fais le programme, et tu vois que c'est faux.
Montrer que le code 'corrigé' fonctionne : C'est à ton ami prof de le faire, puisqu'il te dit que ça fonctionne. Ou c'est à toi de le trouver pour vérifier qu'il a raison.

Eventuellement, montre lui le code simple proposé ici, et demande lui de faire un truc aussi simple, et correct, en parcourant le tableau dans l'ordre croissant.
Forcément, sa solution sera plus compliquée.
Un petit peu plus compliquée, il y a juste une ou 2 instructions à ajouter.
C'est cet exercice là que ton (ami) prof te demande de faire.

**Sylvain255** · 11/10/2022, 15h57

voilà après une petite réflexion :

exemple :

[1,2,3,5,7,9]
écart : 2
on garde 1
on supprime 2
[1,3,5,7,9]
tous les indices suivants sont décalés de -1

programme par ordre croissant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
i=1
n=taille_tableau -1
faire
 si tablo(i)-tablo[i-1] <ecart_minimum alors 
	supprimerligne(i)
	n=n-1
 sinon
	i=i+1
 finsi
jusqu'à i>=n	
fin

vous validez ?

en effet c'est plus compliqué que par ordre décroissant, en fait mon prof me disait que c'était plus simple par ordre croissant

**tbc92** · 11/10/2022, 16h48

Selon les cas, on fait i=i+1 ou n=n-1 ... ça, c'est bien.
La condition de sortie : jusqu'à i>= n : j'ai toujours du mal, est-ce que c'est bon, est-ce qu'il faut mettre n+1, ou n-1 ; il faut se concentrer, et prendre une feuille de papier... Je ne suis pas sûr mais je pense que ce n'est pas bon.

Je préfère TantQue , plutôt que jusqu'à, je trouve que c'est plus facile, mais c'est certainement différent selon chacun. C'est une question d'habitude.

**Sylvain255** · 11/10/2022, 16h50

ah oui tant que i<=n alors

**Guesset** · 11/10/2022, 20h54

Bonjour,

Comme l'écrit tbc92, attention aux indices.

En partant de i = 1, je présume que cela suppose un tableau de 1 à taille_tableau (par exemple possible en Pascal). Or n = taille_tableau - 1. Il manque l'élément Tablo[taille_tableau] soit Tablo[n+1].

Si le tableau (type C, C++ etc.) commence à 0, le dernier élément sera à taille_tableau - 1 soit n. Il manque l'élément Tablo[0] car i commence à 1.

Si on accepte d'avoir un tableau résultat en plus du tableau source, les deux sens sont aussi simples l'un que l'autre.

Si on veut trouver toutes les solutions, y compris les solutions mixtes c'est un peu plus délicat. Je vois bien une solution avec 3 tableaux résultants Rup, Rdn, Rmixt. Mais il y a peut être plus simple. Remarque : les deux solutions montante et descendante peuvent déjà être un mixte c'est à dire avoir une partie commune.

Salutations