Discussion :

[amal1410]

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??

[damosnet]

Code :

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

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²)

[amal1410]

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

[davcha]

C'est un exercice ?

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

[amal1410]

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

[amal1410]

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

[prgasp77]

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

[FR119492]

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 :

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

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

[prgasp77]

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.

[FR119492]

Salut!

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

[prgasp77]

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é , alors avant de remettre en cause le problème tel que formulé ...

[amal1410]

je pense ce code repond bien au pb posé

Code :

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

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)

[prgasp77]

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