Matrie de 10 000 000 d éléments environ

Fermé
onedream - 15 oct. 2008 à 17:58
 onedream - 11 nov. 2008 à 19:38
Bonjour,
je s débutant en language de programmation, et je ss entrain de faire un programme en c mais le probleme la déclaration de ma matrice je m explique :
ma matrice est quaternaire et de 2 dimensions c a d je la rempli avec des nombres 1,2,3
si j entre une dimension 20 par example ma matrice va etre de 3^20(3 puissance 20)éléments.
comment déclarer ma matrice : int M[20][10 000 000]
mais il me donne une erreur comme quoi la taille est trop grande.
et merci d avance
A voir également:

24 réponses

mamiemando Messages postés 33093 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2024 7 752
16 oct. 2008 à 12:33
C'est vrai, tu as raison.
Merci pour le compliment au passage ;-)
-1
bonjour et merci pour l aide,
oui c à base de 3 j ai fais une erreur.
le probléme consisteà faire entrer la puissance ensuite faire remplir la matrice par que des 1,2,3 de telle sorte que chaque ligne soit différente de l autre.
ensuite saisir le nombre minimalde différence que doit avoir entre les lignes et les faire afficher ds un fichier.
j ai fais le programme et je ss proche du résultat mais il y a des erreurs:
1- quand la puissance dépasse la puissance 7 sa marche plus.
2- il y a une erreur pour le traitement de la différence entre les lignes.
voici mon code :



#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{ clrscr();
long int a,b,dim,dim2,j,diff,m,x,w,d,di;
long int k,i,e,jm,A[14][500];
printf("donner la dimension (puissance) de la matrice :"); scanf ("%ld",&dim);

e=pow(3,dim);
printf ("\n 3 puissance %ld = %ld\n",dim,e);
printf ("\nle nombre d element de la matrice est :%ld",e);

// remplissage de la matrice par des 1,2,3
// de telle sorte que chaque ligne soit differente de l autre

for(m=1;m<dim+1;m++)
{ x=pow(3,m-1);
w=pow(3,dim-m);
k=pow(3,dim-m+1);
for(i=0;i<x;i++)
for(j=1;j<w+1;j++)
{ A[m][j+i*k]=1;
A[m][j+i*k+w]=2;
A[m][j+i*k+2*w]=3;
}
}

//saisir le nombre de difference minim entre les lignes

do { printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>=dim);
// traitement sur les difference entre les lignes
// je ne retiens que les lignes qui ont une difference >= di

int i2;
for(i2=1;i2<10;i2++)
{ for(i=1;i<e+1;i++)
{diff=0;jm=i;
for(j=i+1;j<e+1;j++)
{ diff=0;
for(m=1;(m<dim+1)&&(diff<di);m++)
// une fois la difference >= di je sors de la boucle m
{ if(A[m][i]!=A[m][j])
{ diff=diff+1;
if (diff>=di)
{ jm=jm+1;dim2=jm;
for(d=1;d<dim+1;d++)
{ A[d][jm]=A[d][j];
}
}


}
}
}e=jm;dim2=jm;
}
}
printf("\n le nombre de lignes resultantes est :%ld",dim2);
for(k=1;k<dim2+1;k++)
{printf("\n"); // pour voir les resultats
if(k%40==0){ printf("\n appuyer sur touche....!\n");scanf("%ld",&b);}
for(m=1;m<dim+1;m++)
{ printf(" %ld",A[m][k]);}
}

getch();

}

fin du programme...
***************************************************************************************
remarque: je tiens à remercie infiniment char sniper qui m a aidé pour la formule de remplissage , je viens de la vérifier sa marche:
for(m=1;m<dim+1;m++)
{ x=pow(3,m-1);
w=pow(3,dim-m);
k=pow(3,dim-m+1);
for(i=0;i<x;i++)
for(j=1;j<w+1;j++)
{ A[m][j+i*k]=1;
A[m][j+i*k+w]=2;
A[m][j+i*k+2*w]=3;
}
}
0
mamiemando Messages postés 33093 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2024 7 752
17 oct. 2008 à 00:45
J'ai rien compris à l'énoncé en ce qui me concerne, quelques petits exemples sont les bienvenus.
-1
je te remercie de votre attention, je te donne 2 example:
si je donne la puissance =2
les éléments de la matrice = 3^2=9 elements
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
si je donne le nombre de différence minimale que doit avoir entre les lignes résultantes= 2
je vais avoir comme résultat :
je garde la ligne 1 1 et je fais la comparaison avec les autres lignes et je ne garde que les lignes qui ont une différence supérieur ou égale 2 :
1 1
2 2
2 3
3 2
3 3
ensuite je garde la la 1 ere ligne et la 2eme 1 1 et 2 2 et je compare la 2eme ligne 2 2 avec les autre lignes de la matrice , j aurais :
1 1
2 2
3 3
donc le résultat finale est :
1 1
2 2
3 3
***********************
2émé example :
pour la puissance =3
nbre d elements sera =3^3=27 elements
ma matrice sera :
je vais inverser les lignes et les colones pour optimiser:
1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3
1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3 1 1 1 2 2 2 3 3 3
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
si je fais entrer le nbre minimale entre les (mnt ce sont les colonnes)=2
je fixe la 1 ere colonne 1 1 1 et je la fais comparer avec les autres et je ne retiens que ceux qui ont une difference
supérieure a 2, donc j aurais:
1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3
1 2 2 3 3 1 1 2 2 2 3 3 3 1 1 2 2 2 3 3 3 matrice résultante1
1 2 3 2 3 2 3 1 2 3 1 2 3 2 3 1 2 3 1 2 3
ensuite je garde la 1 erer et la 2eme je compare les autres colonnes de ma matrice résultante1 avec la 2 eme colonne, j aurais comme résultat:
1 1 2 2 2 2 2 2 3 3 3 3 3 3 3
1 2 1 1 2 2 3 3 1 1 2 2 3 3 3 matrice resultante2
1 1 2 3 1 3 1 2 2 3 1 3 1 2 3
ensuite je garde les 3 premieres colonnes 1 1 1 et 1 2 1 et 2 1 2 et je compare les autres colones de la matrice resultantes2 avec la 3 eme colonne qui est 2 1 2, j aurais:
1 1 2 2 2 2 3 3 3 3 3 3
1 2 1 2 2 3 1 2 2 3 3 3 resultante3
1 1 2 1 3 1 3 1 3 1 2 3
ensuite je garde les 4 premiere colonnes et je compare les autres qui restent de la resultante3 avec la 4eme colonne qui est:2 2 1, jaurais:
1 1 2 2 2 3 3 3 3 3
1 2 1 2 3 1 2 3 3 3 resultante4
1 1 2 1 1 3 3 1 2 3
je garde les 5 premiere et je compare le reste de la resultante5 avec la 5 eme colonne : 2 3 1, j aurais:
1 1 2 2 2 3 3 3 3
1 2 1 2 3 1 2 3 3 resultante5
1 1 2 1 1 3 3 2 3
je garde les 6 premiere colonnes je compare le reste de resultante5 avec la 6 eme colonne: 3 1 3, j aurais:
1 1 2 2 2 3 3
1 2 1 2 3 1 3
1 1 2 1 1 3 2
et ce sera le resultat final car si je compare entre les colonnes de ma resultante je vois que chaque colonne différe de l autre avec au moins 2 element, le resultat final est:
1 1 2 2 2 3 3
1 2 1 2 3 1 3
1 1 2 1 1 3 2
***************************************************
j espére que je me suis fais comprendre si vous voulez d autres explications je ss la; mon probleme c que je dois remplir une matrice 3^20 elements mais pour la puissance 7 sa marche pour le remplissage mais pour la différence sa marche pas ensuite pour une puissance superieure a 7 sa marche pas pour moi.
et merci d avance.
0
mamiemando Messages postés 33093 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2024 7 752
20 oct. 2008 à 17:27
-> mamiemando : la logique de ton algorithme m'échappe complètement.

Il consiste simplement à compter, et quand on observe un nombre de différences suffisants entre le dernier nombre retenu et celui auquel on est rendu, on extrait ce nouveau nombre, qui servira de référence pour trouver le suivant.

Les résultats de onedream me semblaient corrects à une faute de frappe près (répétée il est vrai) dans la deuxième colonne (lire 122 au lieu de 121). Alors que dans les tiens, on lit 111 et 211, 111 et 131, 211 et 231, etc... ???

Chez moi, ça se lit en ligne et entre deux lignes consécutives il y a bien deux digits qui diffèrent. C'est ce que j'ai compris de l'exercice en tout cas.

L'initialisation val_max=taille+1 me semble bien arbitraire (val_max=4 suffit...)

Oui sauf que si tu fais varier la taille du problème toutes les variables sont correctement initialisée comme j'ai fait

Et la boucle comparer_arrangements gagnerait à avoir une sortie dès qu'on a une différence de 2.

Non, car ça dépend du problème qu'on résout. Dans l'exemple il parle dès qu'on a deux différences en sort, mais le jour ou il y en a trois il faut réécrire le code. Je suis d'accord qu'on gagnerait un peu en efficacité en faisant une boucle for qui s'interrompt dès que le seuil de différences est atteint.

Bonne chance
-1
mamiemando Messages postés 33093 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2024 7 752
20 oct. 2008 à 19:40
Il consiste simplement à compter etc... j'avais bien compris, mais le fait qu'un nombre soit acceptable ou non ne dépend pas QUE du dernier retenu, mais aussi de la liste des précédents.
Chez moi, ça se lit en ligne et entre deux lignes consécutives il y a bien deux digits qui diffèrent.


C'est moi qui ait mal compris si ce n'est pas pour deux arrangements consécutifs :-)

Ceci dit, la méthode que je propose fournit un premier "ménage" qui permet d'élaguer le nombre d'arrangements candidats. Mais dans ce cas je pense qu'il doit exister plusieurs sous-ensembles d'arrangements admissibles distincts.

Oui sauf que si tu fais varier la taille du problème toutes les variables sont correctement initialisée comme j'ai fait C'est bien sûr une bonne idée de mettre val_max en variable, ce que je voulais dire c'est que dans l'énoncé, il n'a jamais été question que cette val_max ait un quelconque rapport avec la taille. Pourquoi taille+1 plutôt que taille +2 ou +3 ? Sinon parce que c'est la "bonne" valeur pour faire un test rapide sur 3 éléments ?

C'est justement pour ca que j'ai séparé les variables. Dans l'énoncé il n'y a pas de précision à ce sujet, mais :
- dans l'exemple, pour un arrangement à trois éléments les valeurs possibles sont 1,2,3
- et pour un arrangement à deux éléments 1 et 2.

Mon code ne force en rien à respecter cette contrainte justement car il est facile d'initialiser différemment val_max et taille.

D'ailleurs, si nb_differences_min valait toujours taille - 1, ça voudrait dire au maximum deux chiffres communs entre deux combinaisons. Il n'y aurait pas besoin d'un gros tableau !

Justement dans mon code il n'y a pas de tableau qui stocke les combinaisons trouvées. Mais si comme tu le penses la "distance" d'un arrangement dépend de l'ensemble des prédécesseurs il faut effectivement les tous stocker. La différence fondamentale entre l'approche proposée au départ par Onedream est qu'au lieu de restreindre petit à petit un ensemble d'arrangement, je le construis au fur et à mesure ce qui est beaucoup moins coûteux en mémoire (on ne stocke que des arrangements "pertinents").

Rien n'empêche ensuite d'utiliser la méthode de onedream pour restreinte ce jeu d'arrangements candidats pour que ceux-ci présentent suffisamment de différence deux à deux.
-1