Discussion :

[devdébuto]

bonsoir! je voudrais savoir comment chercher un tableau d'entiers à une dimension s'il existe ou non dans une matrice.

[Emmanuel Delahaye]

bonsoir! je voudrais savoir comment chercher un tableau d'entiers à une dimension s'il existe ou non dans une matrice.

C'est une question d'algorithme, pas de C...

Si le tableau n'est pas trié, une recherche lineaire s'impoe.

Si il est trié, une recheche dichotomique est possible (en C, bsearch()).

[devdébuto]

Si le tableau n'est pas trié, une recherche lineaire s'impoe.

Je voudrais savoir comment se fait le recherche linéaire.

[devdébuto]

je veux mettre à chaque fois le contenu du tableau dans la matrice aprés avoir fait une permutation aléatoire et vérifier s'il existe ou non dans la matrice.
Voici ce que j'ai écrit:

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
	ligne=0;
		do
		{
		/*générer un nouveau tableau T*/
		i=rand()%n;
		do
		{
			j=rand()%n;}
		while(i==j);
		aux=t[i];
		t[i]=t[j];
		t[j]=aux;
		/*chercher T dans la matrice m*/
		j=0;stop=0;
		while(j<ligne && stop==0)
		{	different=0;
			i=0;
			while(i<n && different==0)
			{	
				if(t[i]!=m[ligne][i])
					different=1;
				else
					i++;
			}
			if(different==1)
				j++;
			else
				stop=1;
		}
 
 
		if(stop==0)
		{
			/*ajouter t dans m*/
			for(j=0;j<n;j++)
				m[ligne][j]=t[j];
				ligne++;
		}
 
		}
		while(ligne<fact(n));

Le problème c'est que je n'ai pas obtenu le bon résultat.Si vous pouvez me corriger?

[Emmanuel Delahaye]

Si le tableau n'est pas trié, une recherche lineaire s'impoe.

Je voudrais savoir comment se fait le recherche linéaire.

Tu parcours le tableau jusqu'à trouver ce que tu cherches... C'est un peu le B.A. BA de l'informatique non ? Tu n'as jamais fais d'algorithmique, même la plus élémentaire ?

[devdébuto]

Tu parcours le tableau jusqu'à trouver ce que tu cherches.

Je crois que vous ne m'avez pas bien compris.Ce que je veux:c'est verifier l'existence d'un tableau dans un matrice.Si vous pouvez jeter un coup d'oeil sur ce que j'ai fait un peu plus haut.

[reggae]

En C ça fait qqch du genre:

Code :

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

1
2
3
4
5
6
7
8
9
 
for(int i=0; i<nombre_element;i++)
{
   if(tableau[i]  ==  ce_que_tu_cherches)
   { 
   std::cout << "trouve en position " << i;
   }
   else{}
}

Bon c'est pas super mais ça te montre le principe
PS:code pas vérifié

[Emmanuel Delahaye]

En C ça fait qqch du genre:

Code :

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

1
2
 
   std::cout << "trouve en position " << i;

Hum ...

[devdébuto]

Je sais comment trouver si une valeur existe ou non dans un tableau.
Voilà par ex:

Code :

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

1
2
3
4
5
6
7
8
9
i=0;
trouve=0;
while(i<n && trouve==0)
{     
      if(t[i]==val)
       trouve=1;
    else
     i++;
}

if(trouve) printf("valeur trouvée");
else printf(".....");
Mon problème c'est comme faire la corrspondance avec les matrices.
S'il vous plait,j'ai besoin de votre aide.

[Emmanuel Delahaye]

Tu parcours le tableau jusqu'à trouver ce que tu cherches.

Je crois que vous ne m'avez pas bien compris.Ce que je veux:c'est verifier l'existence d'un tableau dans un matrice.

L'existence d'un tableau ? Si c'est une matrice codée avec un tableau de pointeurs, on peut supposer que si un des pointeurs est NULL, le tableau n'existe pas...

Si vous pouvez jeter un coup d'oeil sur ce que j'ai fait un peu plus haut.

Incomplet. Ne compile pas. Merci de poster un code complet mais réduit au minimum montrant le problème.

[devdébuto]

voici mon code:

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<stdlib.h>
void main()
{
	int fact(int n);
	int t[100],m[1000][100],i,j,aux,different,stop,ligne,n;
 
	do
	{
		printf("Donner le nombre d'entiers à entrer:\n");
		scanf("%d",&n);
	}
	while(n<=0 || n>100);
		printf("Le nombre de combinaisons est %d\n",fact(n));
	for(i=0;i<n;i++)
	{
		printf("Donner le %d%s element ",(i+1),(i)?"eme":"er");
		scanf("%d",&t[i]);
	}
 
	ligne=0;
		do
		{
		/*générer un nouveau tableau T*/
		i=rand()%n;
		do
		{
			j=rand()%n;}
		while(i==j);
		aux=t[i];
		t[i]=t[j];
		t[j]=aux;
		/*chercher T dans la matrice m*/
		j=0;stop=0;
		while(j<ligne && stop==0)
		{	different=0;
			i=0;
			while(i<n && different==0)
			{	
				if(t[i]!=m[j][i])
					different=1;
				else
					i++;
			}
			if(different==1)
				j++;
			else
				stop=1;
		}
 
 
		if(stop==0)
		{
			/*ajouter t dans m*/
			for(j=0;j<n;j++)
				m[ligne][j]=t[j];
				ligne++;
		}
 
 
		}
		while(ligne<fact(n));
 
 
	/*affichage des combinaisons*/
	for(j=0;j<fact(n);j++)
	{
		for(i=0;i<n;i++)
			printf("%d",m[i][j]);
		printf("-");
	}
}
int fact(int n)
{
	int i;int f;
	f=1;
	for(i=1;i<=n;i++)
		f=f*i;
	return f;
}

[Emmanuel Delahaye]

voici mon code:

• On a pas déjà dit 3000 fois que main() retournait int ?
• On ne met pas une declaration de fonction dans un bloc.
• La première fois qu'on lit la matrice m, elle n'est pas initialisé...

Si je comprends bien, ta méthode pour trouver les combinaisons est le pseudo-hasard ?

Si j'ai bien compris, tu prends une liste de n valeurs, et tu les melanges autant de fois qu'il faut pour trouver une combinaison originale ? Techniquement, ça devrait marcher, mais il est probable que le temps d'exécution augmente exponentiellement avec le nombre d'éléments à combiner...

Pas sûr que ce soit très efficace...

Pour comparer deux tableaux, on compare chaque éléments des tableaux ...

[fearyourself]

Encore ton probleme de permutations?

A part les remarques d'Emmanuel:

On a pas déjà dit 3000 fois que main() retournait int ?
On ne met pas une declaration de fonction dans un bloc.
La première fois qu'on lit la matrice m, elle n'est pas initialisé...

Lesquels tu pourrais commencer a prendre note quand meme, ce n'est pas la premiere fois qu'on te le dit je crois...

Ton algorithme bien que pas tres intelligent/rapide a l'avantage d'etre assez simple pour qu'on puisse voir qu'il marchera. La seule erreur que tu as dans ton code est ici:

Code :

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

1
2
 
printf("%d",m[i][j]);

ou il faudrait mettre:

Code :

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

1
2
 
printf("%d",m[j][i]);

Et oui, t'as inverse les indices...


EDITION: Une bonne page sur les permutations se trouve [url]http://www.bearcave.com/random_hacks/permute.html[/url... Avec un moindre effort, tu pourrais modifier le premier programme donne pour qu'il fasse ce que tu veux et de facon beaucoup plus rapide...

Jc