recherche dans une matrice

Bonsoir,
j'ai une matrice carrée M telle que chaque ligne et chaque colonne est triée dans un ordre croissant (M[1, i] ≤ M[2, i] ≤… ≤ M[n, i] et M[i, 1] ≤ M[i, 2] ≤… ≤ M[i, n], avec i = 1, 2, …, n).
je veux chercher un entier x donné dans la matrice M sachant que la complexité de l'algo est en O(n)
qui peut m'aider svp??

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Fonction recherche (M:Mat ; n,x:Entier):boolean variable i,j:entier ok:boolean Début i<--1 ok<--faux Tant que (i<=n) et non(ok) faire j<--1 Tant que (j<=n) et non(ok) faire si(M[i,j]=x) alors ok<--vrai sinon j<--j+1 FinSi Fin Tantque i<--i+1 Fin Tantque recherche<--ok Fin

---

cette solution est de complexité : O(n²)

merci damosnet pour votre réponse,
je connais cette solution, mais mon problème est que la complexité doit être en O(n).

C'est un exercice ?

Réfléchis un peu, c'est pas si compliqué. Comment tu ferais à la main ?

oui c'est un exercice,
trouver un algorithme n'est pas difficile, mais mon problème est dans la complexité

quelqu'un peut m'aider svp, c'est très urgent???

Si tu devais élargir la dichotomie à une dimension supérieure, qu'est-ce que ça donnerait ?

Salut!
Je crains qu'il n'y ait pas de solution fiable à ton problème. Alors, un petit exemple pour t'expliquer. Je prends la matrice suivante:

Code:

---

1 2 3 4 5 6

101 102 103 104 105 106 102 104 106 108 110 112 103 106 109 112 115 118 104 108 112 116 120 124 105 110 115 120 125 130 106 112 118 124 130 136

---

Les choses suivantes peuvent arriver:

• Si x=73, le problème n'a pas de solution.
• Si x=109, il y a une solution unique: i=j=3.
• Si x=112, il y a quatre solutions: i=2 et j=6; i=3 et j=4; i=4 et j=3; i=6 et j=1; laquelle est la bonne?
• si x=117, le problème n'a pas de solution.

Alors, relis les données de ton problème et, éventuellement, demande à ton prof. un complément d'information.

Jean-Marc Blanc

Citation:

---

Envoyé par FR119492

Alors, relis les données de ton problème et, éventuellement, demande à ton prof. un complément d'information.

---

Étrange comme raisonnement. Pour moi, si un algorithme trouve qu'il n'y a pas de solution au problème qui lui est donné, alors cet algo est viable.

Salut!

Citation:

---

Pour moi, si un algorithme trouve qu'il n'y a pas de solution au problème qui lui est donné, alors cet algo est viable.

---

Dans le monde réel, il y a des ingénieurs à qui leur employeur ou des clients donnent des problèmes à résoudre; il y a aussi des étudiants à qui leurs professeurs donnent des exercices. Dans un cas comme dans l'autre, si on ne trouve pas de solution, c'est un échec. Pour y remédier, il faut demander un complément d'information sur les données du problème et non se résigner à l'absence de solution.
Jean-Marc Blanc

Citation:

---

Envoyé par FR119492

Pour y remédier, il faut demander un complément d'information sur les données du problème et non se résigner à l'absence de solution.

---

Je suis d'accord avec cette phrase. Mais c'est l'homme qui doit effectuer ce travail supplémentaire, pas l'algorithme. Dans un premier temps, on utilise les outils dont on dispose ; si ceux-ci nous apprennent qu'il n'y a pas de solution au problème tel que formulé, alors il faut procéder autrement, utiliser d'autres outils. Mais on est très loin du problème du PO.

Ici, il me semble évident que le PO est un étudiant (qui tarde à répondre) à qui on demande de trouver, s'il existe, l'index d'un entier dans une matrice partiellement triée. Mais effectivement, si cet entier n'existe pas, peut être l'algorithme peut-il retourner des informations supplémentaires. Par exemple, s'il faudra ensuite insérer l'entier recherché dans la matrice, peut être est-ce le moment de calculer à quel endroit celui-ci devra être inséré. Et à la vue des messages du PO, il est encore loin d'y être arrivé :mrgreen:, alors avant de remettre en cause le problème tel que formulé ...

je pense ce code repond bien au pb posé

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

i :=1 j :=n tantque i<=n et j>=1 faire si M[i,j] =x alors retourner (i,j) sinon si M[i,j]<x alors i :=i+1 sinon j :=j-1 fin si fin si fin tantque retourner (-1,-1)

---

Salut, effectivement, on a du O(n). Il est néanmoins possible de faire mieux. :ccool:.