Discussion :

[Ignarde]

Bonsoir, j'aimerai écrire un programme C qui rechercherait un entier dans un tableau d'entiers de dimension 2 (càd n*n quoi^^)dans lequel les nb sont rangés dans l'ordre croissant en ligne et en colonne, pour l'algo, j'ai pensé prendre la case du milieu de la dernière colonne du tableau et d'utiliser la méthode "diviser pour régner" pour determiner si l'entier recherché est dans la moitié supérieure ou inférieure de mon tableau.
J'élimine ainsi les lignes au fur et à mesure et au final, j'applique à nouveau "diviser pour régner" sur la ligne isolée.

L'algo me semble bon et j'aimerai justement le vérifier en écrivant un programme C correspondant, et je voudrais savoir comment faire pour "sélectionner tout une partie d'un tableau de dimension 2"...
je ne sais pas si c'est assez clair ^_^'...merci pour les réponses!

Petite info : Je dois obligatoirement utiliser "diviser pour régner"...

[snake264]

Propose nous ta version écrite de ton algo écrit en C et on dira si c'est bon ou non

[Ignarde]

hum...je tiens à prévenir que le programme est trèès tordu...^^'..et qu'il est sans doute aussi bourré d'erreur...-_-'

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
    #include <stdio.h>
    #include <stdlib.h>
 
   typedef struct couple {
           int x;
           int y;
           }Couple;
 
Couple rechercherX (int nb_colonnes, int nb_lignes, int x, int tab[][nb_lignes], int* d, int* f){
           int  i, j, m;
 
           Couple position;
           position.x=0;
           position.y=0; 
 
           if ((nb_lignes==1)&&(nb_colonnes==1)){
              if (tab[0][0]==x){
                 position.x=1;
                 position.y=1;
                 return position;
              }
           }
 
           if ((nb_lignes!=1)&&(nb_colonnes!=1)){
               i=nb_colonnes;
               j=nb_lignes/2;
 
               if (tab[i][j]==x){
                 position.x=i;
                 position.y=j;
                 return position;
               }else{
                     if (tab [i][j]>x){
                        rechercherX (nb_colonnes, j, x, tab, *(tab), *(tab+(nb_colonnes*j)));
                     }else{
                        rechercherX (nb_colonnes, nb_lignes-j, x, tab, *(tab+(j*nb_colonnes)+1), *(tab+(nb_colonnes*nb_colonnes)));
                     }
                }
             }
 
            if (nb_lignes==1){
              m=nb_colonnes/2;
 
              if (tab [m][j]==x){
                 position.x=m;
                 position.y=j;
                 return position;
              }else{
                    if (tab [m][j]<x){
		               rechercherX (nb_colonnes-m-1, 1, x, tab, *(tab+(j*nb_colonnes+m+1)), *(tab+(nb_colonnes*j)));
                    }else{                   
                       rechercherX (m-1, 1, x, tab, *(tab+(j*nb_colonnes)+1), *(tab+(j*nb_colonnes+m)));
                    }                     
              }
            }
 
	      return position;
}

[Ignarde]

Rebonjour! ^^
Zappons complètement le programme précédent...
J'en ai écris un autre qui prend un tableau T[n][n] avec n pair et dont les entiers sont rangés dans l'ordre croissant en ligne et en colonne.
Seulement, il ne me renvoie pas le bon résultat et je ne comprend pas pourquoi, est-ce que quelqu'un pourrait me dire où ça coince?
Merci! ^_^

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
 
#include <stdio.h>
 
   typedef struct coordonnee {
           int x;
           int y;
           }Coordonnee;
 
 
Coordonnee rechercherX (int x, int taille, int tab[][taille], int lig_deb, int col_deb, int lig_fin, int col_fin){
           int m;
           Coordonnee position;
 
           if ((taille==1)&&(tab[lig_deb][col_deb]!=x)){
               position.x=-1;
               position.y=-1;
               return position;
           }  
 
           if ((taille==1)&&(tab[lig_deb][col_deb]==x)){
               position.x=lig_deb;
               position.y=col_deb;
               return position;
           }  
 
           if ((taille%2)==0){
              m=(taille-1)/2;
              if ((tab[lig_deb][col_deb]<=x)&&(x<=tab[lig_deb+m][col_deb+m])){
                  rechercherX (x, taille/2, tab, lig_deb, col_deb, lig_deb+m, col_deb+m);
              }
              if ((tab[lig_deb][col_deb+m+1]<=x)&&(x<=tab[lig_deb+m][col_deb+col_fin])){
                  rechercherX (x, taille/2, tab, lig_deb, col_deb+m+1, lig_deb+m, col_deb+col_fin);
              }
              if ((tab[lig_deb+m+1][col_deb]<=x)&&(x<=tab[lig_fin][col_deb+m])){
                  rechercherX (x, taille/2, tab, lig_deb+m, col_deb, lig_fin, col_deb+m);
              }
              if ((tab[lig_deb+m+1][col_deb+m+1]<=x)&&(x<=tab[lig_fin][col_fin])){
                  rechercherX (x, taille/2, tab, lig_deb+m+1, col_deb+m+1, lig_fin, col_fin);                                
              }
           }
}
 
int main(){
     int T[4][4]={{10,12,16,18},
                  {11,16,40,46},
                  {22,57,59,60},
                  {40,80,82,85}}; 
 
     Coordonnee p=rechercherX (60, 4, T, 0, 0, 3, 3);
     printf ("La position de 60 (qui est (2,3)) est : (%d, %d).\n", p.x, p.y);
     system("PAUSE");
     return 0;
}

et ça me renvoie :
La position de 60 (qui est (2,3)) est : (2009091650,4200032).

[diogene]

La première chose à faire est

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
....
              if ((tab[lig_deb][col_deb]<=x)&&(x<=tab[lig_deb+m][col_deb+m])){
                  position = rechercherX (x, taille/2, tab, lig_deb, col_deb, lig_deb+m, col_deb+m);
              }
              if ((tab[lig_deb][col_deb+m+1]<=x)&&(x<=tab[lig_deb+m][col_deb+col_fin])){
                  position =rechercherX (x, taille/2, tab, lig_deb, col_deb+m+1, lig_deb+m, col_deb+col_fin);
              }
              if ((tab[lig_deb+m+1][col_deb]<=x)&&(x<=tab[lig_fin][col_deb+m])){
                  position =rechercherX (x, taille/2, tab, lig_deb+m, col_deb, lig_fin, col_deb+m);
              }
              if ((tab[lig_deb+m+1][col_deb+m+1]<=x)&&(x<=tab[lig_fin][col_fin])){
                  position =rechercherX (x, taille/2, tab, lig_deb+m+1, col_deb+m+1, lig_fin, col_fin);                                
              }
           }
 return position;
}

Mais il reste des erreurs dans le code, car si certaines le sont, toutes les réponses ne sont pas correctes

[Ignarde]

d'accord, j'en prend note, seulement, le résultat ne sera pas renvoyé par les 2 premiers "if"?

[Ignarde]

Vous pouvez clore ce topic, j'ai résolu mon problème!^^
Merci!