Discussion :

[valentin03]

Bonjour,
J'ai un tableaux de 7 valeurs entre 1 et 13 non trié. (index "ind" de 1 à 7)
J'ai une valeur x entre 1 et 13
Je voudrais prendre dans le tableau [A] la plus faible valeur supérieure à x.
Suis-je obligé de trier [A] avant ou y a t-il moyen de s'en passer, et si oui comment (en pseudo code svp)
Merciiiii.

[balkany]

Non tu n'es pas obligé, et tu ne devrais pas le faire si tu n'en as pas besoin, car c'est une opération dont le coût est en général en O(nlog(n)), alors qu'ici ce que tu veux faire est en O(n).

[valentin03]

Non tu n'es pas obligé, et tu ne devrais pas le faire si tu n'en as pas besoin, car c'est une opération dont le coût est en général en O(nlog(n)), alors qu'ici ce que tu veux faire est en O(n).

Si je ne trie pas il va me sortir la première valeur supérieure qu'il va trouver, mais pas la plus faible du tableau.
Tu ne m'aide pas des masses.

[balkany]

Fais un effort : c'est pas bien compliqué de stocker cette valeur et de la comparer à celles qui sortiront ensuite…

[valentin03]

Fais un effort : c'est pas bien compliqué de stocker cette valeur et de la comparer à celles qui sortiront ensuite…

C'est sûr que quand on sait faire, tout est facile et rien n'est compliqué.
Mais bon, faut savoir faire, et là ça fait un moment que je mets des instructions dans tous les sens et pour l'instant, j'en suis à trier, vu qu'autrement j'y arrive pô mais comme le tableau est "soudé" à d'autres c'est la panique des index.
Au secours les bonnes âmes...

[balkany]

Je ne sais pas si c'est du pseudo-code correct, mais voilà :

Code :

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

1
2
3
4
5
6
y = INF
Pour i = 0; i < longueur (A); i = i + 1
  Si x < A[i] et A[i] < y
    y = A[i]
  FinSi
FinPour

Et si tu ne peux ou ne veux pas initialiser y avec une valeur « infinie », tu peux découper la boucle en deux temps :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Pour i = 0; i < longueur (A); i = i + 1
  Si x < A[i]
    y = A[i]
    Interruption
  FinSi
FinPour
 
Pour j = i; j < longueur (A); j = j + 1
  Si x < A[j] et A[j] < y
    y = A[j]
  FinSi
FinPour

[Flodelarab]

Bonjour

Et si tu ne peux ou ne veux pas initialiser y avec une valeur « infinie »

Ce n'est pas une question anodine. On cherche une solution dont on n'a pas prouvé l'existence. "y" doit donc prendre la valeur que doit retourner l'algorithme en cas d'absence de solution.

[balkany]

Oui, j'ai laissé ce point de côté : à valentin03 de savoir comment il veut identifier la possible non existence d'une solution (on peut aussi affecter un booléen dans la première boucle du second code).

[valentin03]

Je ne sais pas si c'est du pseudo-code correct, mais voilà :

Code :

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

1
2
3
4
5
6
y = INF
Pour i = 0; i < longueur (A); i = i + 1
  Si x < A[i] et A[i] < y
    y = A[i]
  FinSi
FinPour

Et si tu ne peux ou ne veux pas initialiser y avec une valeur « infinie », tu peux découper la boucle en deux temps :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Pour i = 0; i < longueur (A); i = i + 1
  Si x < A[i]
    y = A[i]
    Interruption
  FinSi
FinPour
 
Pour j = i; j < longueur (A); j = j + 1
  Si x < A[j] et A[j] < y
    y = A[j]
  FinSi
FinPour

J'ai interprété ton "interruption" comme une sortie de la boucle
Et ça a l'air de fonctionner, un gros merci.
Pour les non-solutions je devrais pouvoir m'en sortir, sinon, je reviendrai.
Merci beaucoup.

[valentin03]

J'ai interprété ton "interruption" comme une sortie de la boucle
Et ça a l'air de fonctionner, un gros merci.
Pour les non-solutions je devrais pouvoir m'en sortir, sinon, je reviendrai.
Merci beaucoup.

Pour le premier algo, si je mets pour Y une valeur supérieure au nombre le plus grand du tableau ça fonctionne aussi. mais est-ce que ça va gérer les non solutions et si oui comment ?

[balkany]

Le truc c'est que le tableau n'est pas connu d'avance, et qu'on ne veut pas avoir à le parcourir une première fois pour savoir quel est le plus grand élément, afin d'initialiser y avec une valeur plus grande encore.
D'où le recours à une constante connue à priori dans le langage, comme INF en matlab (si je me souviens bien), mais elle n'existe pas forcément partout.

À partir de là, si en sortie du programme y vaut INF, c'est qu'il n'y avait pas de solution.
Sinon, tu peux aussi initialiser y à x, et de même, si y vaut x en sortie, c'est qu'il n'y avait pas de solution.

Ou encore, tu peux initialiser un booléen à FAUX et le faire passer à VRAI dans la première boucle, comme je disais plus haut :

Code :

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

1
2
3
4
5
6
7
8
existenceSolution = FAUX
Pour i = 0; i < longueur (A); i = i + 1
  Si x < A[i]
    y = A[i]
    existenceSolution = VRAI
    Interruption
  FinSi
FinPour

Après ça dépend du langage pour savoir comment tu récupères le booléen et y, c'est pour ça que je n'aime pas beaucoup le pseudo-code…

+++

Ceci dit, j'imagine qu'il faut rajouter quelque chose comme

Code :

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

Renvoyer y et existenceSolution

sans se soucier de savoir comment on les renvoie…

[disedorgue]

Balkany a raison, dans ce genre de situation, le pseudo-code n'est pas adapté, car si on considère les langages qui ne créent par exemple la case du tableau que l'on initialise, on peut facilement faire un tri implicite au remplissage du tableau et donc connaitre aussi les extrêmes.

[valentin03]

Balkany a raison, dans ce genre de situation, le pseudo-code n'est pas adapté, car si on considère les langages qui ne créent par exemple la case du tableau que l'on initialise, on peut facilement faire un tri implicite au remplissage du tableau et donc connaitre aussi les extrêmes.

Pour ce cas la grandeur du tableau est connue et les nombres sont connus Tous les algos ne sont transcrivables en pseudo code, mais là ça va très bien, c'est plus clair que dans un langage à la syntaxe inconnue.
Je mets "résolu" si j'y arrive

[Flodelarab]

Conceptuellement, on renvoie un pointeur. Un pointeur vers la solution si elle existe, et un pointeur nul, sinon. Je ne crois pas qu'il y ait la nécessité de considérer 2 objets différents (un pour la faisabilité et un pour la solution).

Le pseudo-code s'intéresse aux actions. Pas au format des données. N'est-ce pas ? (je n'en sais rien).

transcrivables

Aïe. Du verbe "transcriver" ? "Transcriptible", par exemple ? Comme pour les verbes inscrire, écrire, réécrire, transcrire. exemple: CD réinscriptible.

[valentin03]

@: Flodelarab:
Les "non solution" je les traiterai plus loin. (l'usine à gaz est en bonne voie, pour l'instant tout fonctionne, pourvu que ça dure...).
Le pseudo code, c'est très merveilleux.
Le "Transcriptible", le correcteur me l'a souligné en vermicelle rouge; alors j'ai tenté...Autre...Et j'ai encor'raté.

[balkany]

Le wiktionnaire donne transcrivable comme synonyme populaire de transcriptible : https://fr.wiktionary.org/wiki/transcrivable
Mais hunspell ne semble effectivement apprécier ni l'un, ni l'autre

[Flodelarab]

Le wiktionnaire est l'aspirateur à n'importe quelle ânerie.
https://fr.wiktionary.org/wiki/transcriptible

[balkany]

Bah je trouve pas tant que ça en fait.
Ils ont leurs critères d'acceptabilité, comme tous les sites de la fondation wikimedia : https://fr.wiktionary.org/wiki/Wikti...s_entr%C3%A9es
Ce ne sont certes pas ceux de l'académie française, mais ça ne me semble pas si absurde (rapide lecture pour la première fois : ça me rappelle wikipédia (forcément), où j'ai un peu contribué par le passé).
Mais bon, on s'écarte probablement pas mal du sujet

[valentin03]

Je crains que nous ne devions nous soumettre à l'implacable logique de Flodelarab qui a cassé la baraque avec un imparable: "transcriver".