A voir également:
- Matrie de 10 000 000 d éléments environ
- Clé windows 10 gratuit - Guide
- Windows 10 gratuit - Guide
- Mon pc s'allume mais ne démarre pas windows 10 - Guide
- Windows 10 iso - Guide
- Licence windows 10 - Guide
24 réponses
Bonsoir
Si ta matrice est à 2 dimensions, et que chaque dimension est de 20, la taille est de 20 * 20 = 400, ce qui me semble beaucoup plus raisonnable.
Tu dis que tu es débutant, je doute qu'on t'ait demandé de traiter une matrice gigantesque.
Si ta matrice est à 2 dimensions, et que chaque dimension est de 20, la taille est de 20 * 20 = 400, ce qui me semble beaucoup plus raisonnable.
Tu dis que tu es débutant, je doute qu'on t'ait demandé de traiter une matrice gigantesque.
Simple suggesion :
Si tu ne dois garder que les lignes qui ont au moins deux chiffres de différence, autant le faire au fur et à mesure du remplissage du tableau !
Si tu ne dois garder que les lignes qui ont au moins deux chiffres de différence, autant le faire au fur et à mesure du remplissage du tableau !
mamiemando
Messages postés
33081
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 avril 2024
7 749
20 oct. 2008 à 13:30
20 oct. 2008 à 13:30
Bon j'ai compris le sujet ^^ Idée que je propose : plutôt que de créer la liste de toutes les arrangements possibles et de l'élaguer en plusieurs itération ce qui sera :
- lent (mauvais se complexité d'un point de vu algorithmique)
- coûteux en mémoire
.... ne serait il pas possible de créer directement la matrice finale. Il suffit pour cela étant donné un arrangement x et un nombre de différence minimal fixé N, de générer le plus petit arrangement supérieur y présentant au moins N différences avec x.
On peut pour cela intelligemment utilisé un mécanisme d'addition (+) et de modulo (%). Je pense que dans ton exemple tu as dû te craquer car il y a des colonnes successives qui ne diffère que d'un élément. Voici ce que je te propose :
Quelques précisions :
- val_max désigne la borne supérieure stricte (par exemple 4 si les valeurs autorisées sont 1,2,3)
- le pointeur swap permet de transvaser instantanément suivant dans courant et évite une recopie du vecteur, ce qui accélère le programme.
- dans la fonction qui incrémente l'arrangement, on pourrait éviter de faire un appel récursif, ce qui serait plus élégant et moins coûteux.
- l'assertion ne sert en pratique à rien, c'est juste que pendant la phase de développement, c'est bien de mettre des filets de sécurité.
Est-ce que ça te convient ?
Bonne chance
- lent (mauvais se complexité d'un point de vu algorithmique)
- coûteux en mémoire
.... ne serait il pas possible de créer directement la matrice finale. Il suffit pour cela étant donné un arrangement x et un nombre de différence minimal fixé N, de générer le plus petit arrangement supérieur y présentant au moins N différences avec x.
On peut pour cela intelligemment utilisé un mécanisme d'addition (+) et de modulo (%). Je pense que dans ton exemple tu as dû te craquer car il y a des colonnes successives qui ne diffère que d'un élément. Voici ce que je te propose :
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
void afficher_arrangement(
unsigned *arrangement,
unsigned taille
){
unsigned i;
for(i=0;i<taille;++i) printf("%i ",arrangement[i]);
printf("\n");
}
void init_arrangement(
unsigned *arrangement,
unsigned taille
){
unsigned i;
for(i=0;i<taille;++i) arrangement[i] = 1;
}
unsigned comparer_arrangements(
unsigned *courant,
unsigned *suivant,
unsigned taille
){
unsigned i,cpt = 0;
for(i=0;i<taille;++i){
if(courant[i] != suivant[i]) ++cpt;
}
return cpt;
}
int incrementer_arrangement(
unsigned *arrangement,
unsigned taille,
unsigned position,
unsigned val_max
){
assert(position < taille);
++arrangement[position];
if(arrangement[position] % val_max == 0){
if(position == 0) return 0;
arrangement[position] = 1;
return incrementer_arrangement(arrangement,taille,position-1,val_max);
}
return 1;
}
/**
* \param courant L'arrangement courant
* \param suivant L'arrangement suivant
* \param taille Le nombre de chiffre dans les arrangements
* \param nb_differences_min Le nombre de différences minimal
* \param val_max La valeur maximale figurant dans un arrangement
* \return 1 Si on a trouvé un suivant, 0 sinon
*/
int calculer_arrangement_suivant(
unsigned *courant,
unsigned *suivant,
unsigned taille,
unsigned nb_differences_min,
unsigned val_max
){
unsigned i,nb_diff = 0,ret;
for(i=0;i<taille;++i) suivant[i] = courant[i];
while(nb_diff < nb_differences_min){
ret = incrementer_arrangement(suivant,taille,taille-1,val_max);
if(ret == 0) return 0;
nb_diff = comparer_arrangements(courant,suivant,taille);
}
return 1;
}
int main(){
unsigned i;
const unsigned taille = 3;
const unsigned val_max = taille + 1;
const unsigned nb_differences_min = taille - 1;
unsigned *courant = (unsigned *)malloc(sizeof(unsigned)*taille);
init_arrangement(courant,taille);
unsigned *suivant = (unsigned *)malloc(sizeof(unsigned)*taille);
unsigned *swap;
afficher_arrangement(courant,taille);
while(calculer_arrangement_suivant(courant,suivant,taille,nb_differences_min,val_max)){
// printf("****************************\n");
// afficher_arrangement(courant,taille);
afficher_arrangement(suivant,taille);
swap = courant;
courant = suivant;
suivant = swap;
}
free(courant);
free(suivant);
return 0;
}
ce qui donne :
(mando@aldur) (~) $ gcc -W -Wall plop.c (mando@aldur) (~) $ ./a.out 1 1 1 1 2 2 1 3 1 2 1 1 2 2 2 2 3 1 3 1 1 3 2 2 3 3 1
Quelques précisions :
- val_max désigne la borne supérieure stricte (par exemple 4 si les valeurs autorisées sont 1,2,3)
- le pointeur swap permet de transvaser instantanément suivant dans courant et évite une recopie du vecteur, ce qui accélère le programme.
- dans la fonction qui incrémente l'arrangement, on pourrait éviter de faire un appel récursif, ce qui serait plus élégant et moins coûteux.
- l'assertion ne sert en pratique à rien, c'est juste que pendant la phase de développement, c'est bien de mettre des filets de sécurité.
Est-ce que ça te convient ?
Bonne chance
char x[20][10000000];, ça passe en visual C++. Du moins au niveau compilation et link.
Sinon, faire un voire quelques malloc pour réserver la mémoire nécessaire, et ensuite "bricoler" avec pour gérer tout ça, pas très difficile mais lourd.
-> mamiendo : la logique de ton algorithme m'échappe complètement. 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... ??? L'initialisation val_max=taille+1 me semble bien arbitraire (val_max=4 suffit...) Et la boucle comparer_arrangements gagnerait à avoir une sortie dès qu'on a une différence de 2.
Sinon, faire un voire quelques malloc pour réserver la mémoire nécessaire, et ensuite "bricoler" avec pour gérer tout ça, pas très difficile mais lourd.
-> mamiendo : la logique de ton algorithme m'échappe complètement. 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... ??? L'initialisation val_max=taille+1 me semble bien arbitraire (val_max=4 suffit...) Et la boucle comparer_arrangements gagnerait à avoir une sortie dès qu'on a une différence de 2.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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. Entre deux lignes consécutives oui, mais je ne vois pas où Onedream parle de lignes consécutives. Qu'en dis-tu, Onedream ?
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 ?
même remarque pour nb_differences_min = taille - 1, tout aussi arbitraire.
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 !
<ital>il y en a trois il faut réécrire le code<ital> Non, là ou j'ai dit 2 il suffit d'utiliser ta variable nb_differences_min
Chez moi, ça se lit en ligne et entre deux lignes consécutives il y a bien deux digits qui diffèrent. Entre deux lignes consécutives oui, mais je ne vois pas où Onedream parle de lignes consécutives. Qu'en dis-tu, Onedream ?
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 ?
même remarque pour nb_differences_min = taille - 1, tout aussi arbitraire.
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 !
<ital>il y en a trois il faut réécrire le code<ital> Non, là ou j'ai dit 2 il suffit d'utiliser ta variable nb_differences_min
désolé pour le retard; car j ai pas d internet chez moi.
je viens de lire vos msg et le programme de mamiemando et franchement je n ai rien compris car il est compliqué pour moi; je vais le relire plusieurs fois pour essayer de le comprendre car je ss pas fort en pointeur il me bloque :).
j ai pas donné l énoncé du probléme au début car j ai peur qu il y aurais personne qui va me comprendre; mais quand j ai vu que vous me suivez et que vous êtes fort en programmation voici le probléme:
le probleme en général c de saisir un nombre n et saisir un nombre que je vais l appeler : dim
ensuite remplir une matrice qui sera de cette forme A[dim][n^dim]
n^dim=n puissance dim
et cette matrice sera rempli par les chifrres: 0,1,2,3,4,....,n
cad si n=4 et dim =18 la matrice sera de la taille A[18][4^18]
ensuite saisir un vecteur par example B[de 1 jusqu à dim][1] en suite saisir le nbre minimal de différence(diff) entre les colonnes et le vecteur saisi
et en résultat afficher un tableau résultant qui regroupe des colonnes qui ont un nombre de différence supérieur ou égale au nombre saisi(diff)
et voila mon programme mais comme je vous ai dit il y a certain beug comme la taille qui n est pas acceptée car pour un dim= 18 pour une base ternaire n=3 ou quaternaire n=4 sa se bloque
et encore pour la différence je vois qu il y a en résultat certaine colonne qui se répétent ou que que la différence est inférieure a la différence demandée
#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{ clrscr();
long int a,b,n,dim,dim2,j,diff,m,x,w,d,di;
long int k,i,i1,e,jm;
long int A[10][500];
printf("donner la puissance n-ieme de la matrice :"); scanf ("%ld",&n);
printf("donner la dimension de la matrice :"); scanf ("%ld",&dim);
e=pow(n,dim);
printf ("\n %ld puissance %ld = %ld\n",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(n,m-1);
w=pow(n,dim-m);
k=pow(n,dim-m+1);
for(i=0;i<x;i++)
for(j=1;j<w+1;j++)
for(i1=1;i1<n+1;i1++)
{ A[m][j+i*k+(i1-1)*w]=i1;
}
}
printf("\n la matrice est :");
for(k=1;k<e+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]);}
}
//saisir le nombre de difference entre les lignes
do { printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>dim);
// traitement sur les differences 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<e+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();
}
remarque je l ai pas encore testé et en plus la saisie du vecteur je l ai pas encore fais; c pour demain et merci de votre aide.
je viens de lire vos msg et le programme de mamiemando et franchement je n ai rien compris car il est compliqué pour moi; je vais le relire plusieurs fois pour essayer de le comprendre car je ss pas fort en pointeur il me bloque :).
j ai pas donné l énoncé du probléme au début car j ai peur qu il y aurais personne qui va me comprendre; mais quand j ai vu que vous me suivez et que vous êtes fort en programmation voici le probléme:
le probleme en général c de saisir un nombre n et saisir un nombre que je vais l appeler : dim
ensuite remplir une matrice qui sera de cette forme A[dim][n^dim]
n^dim=n puissance dim
et cette matrice sera rempli par les chifrres: 0,1,2,3,4,....,n
cad si n=4 et dim =18 la matrice sera de la taille A[18][4^18]
ensuite saisir un vecteur par example B[de 1 jusqu à dim][1] en suite saisir le nbre minimal de différence(diff) entre les colonnes et le vecteur saisi
et en résultat afficher un tableau résultant qui regroupe des colonnes qui ont un nombre de différence supérieur ou égale au nombre saisi(diff)
et voila mon programme mais comme je vous ai dit il y a certain beug comme la taille qui n est pas acceptée car pour un dim= 18 pour une base ternaire n=3 ou quaternaire n=4 sa se bloque
et encore pour la différence je vois qu il y a en résultat certaine colonne qui se répétent ou que que la différence est inférieure a la différence demandée
#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{ clrscr();
long int a,b,n,dim,dim2,j,diff,m,x,w,d,di;
long int k,i,i1,e,jm;
long int A[10][500];
printf("donner la puissance n-ieme de la matrice :"); scanf ("%ld",&n);
printf("donner la dimension de la matrice :"); scanf ("%ld",&dim);
e=pow(n,dim);
printf ("\n %ld puissance %ld = %ld\n",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(n,m-1);
w=pow(n,dim-m);
k=pow(n,dim-m+1);
for(i=0;i<x;i++)
for(j=1;j<w+1;j++)
for(i1=1;i1<n+1;i1++)
{ A[m][j+i*k+(i1-1)*w]=i1;
}
}
printf("\n la matrice est :");
for(k=1;k<e+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]);}
}
//saisir le nombre de difference entre les lignes
do { printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>dim);
// traitement sur les differences 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<e+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();
}
remarque je l ai pas encore testé et en plus la saisie du vecteur je l ai pas encore fais; c pour demain et merci de votre aide.
j ai oublié de mentionné que toto a raison car pour le résultat de mamiemando, pour
1 1 1 si je la compare avec 1 3 1 et 2 1 1et 3 1 1 il n ont pour différence que 1 il ne doivent pas etre ds le resultat final si on a 1 1 1
pour le 1 2 2 avec 2 2 2 et 3 2 2 ils n ont que 1 pour la difference
pour le 1 3 1 avec 2 3 1 et 3 3 1 même chose
pour le 2 1 1 avec 2 3 1 et 3 1 1 même chose
pour le 2 2 2 avec 3 2 2
2 3 1 avec 3 3 1
3 1 1 avec 3 3 1
j espére que j ai bien expliqué
1 1 1 si je la compare avec 1 3 1 et 2 1 1et 3 1 1 il n ont pour différence que 1 il ne doivent pas etre ds le resultat final si on a 1 1 1
pour le 1 2 2 avec 2 2 2 et 3 2 2 ils n ont que 1 pour la difference
pour le 1 3 1 avec 2 3 1 et 3 3 1 même chose
pour le 2 1 1 avec 2 3 1 et 3 1 1 même chose
pour le 2 2 2 avec 3 2 2
2 3 1 avec 3 3 1
3 1 1 avec 3 3 1
j espére que j ai bien expliqué
toto> est ce que sa marche en visual c++ la déclaration char[20][10000000] seulement pour les caractéres et pas pour int?
mamiemando>merci de votre programme mais j ai trouvé des difficultés pour le comprendre car comme je vous ai dis je ss débutant en programmation surtout au niveau des pointeurs et le grop probleme est que ma matrice est dynamique je dois la resoudre avec les pointeurs mais les pointeurs me bloquent énormément.
le programme que j ai fait jusqu a ce moment:
#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{ clrscr();
long int a,b,n,dim,dim2,j,diff,m,x,w,d,di;
long int k,i,i1,e,jm;
long int A[20][500];
printf("donner la puissance n-ieme de la matrice :"); scanf ("%ld",&n);
printf("donner la dimension de la matrice :"); scanf ("%ld",&dim);
e=pow(n,dim);
printf ("\n %ld puissance %ld = %ld\n",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(n,m-1);
w=pow(n,dim-m);
k=pow(n,dim-m+1);
for(i=0;i<x;i++)
for(j=1;j<w+1;j++)
for(i1=1;i1<n+1;i1++)
{ A[m][j+i*k+(i1-1)*w]=i1;
}
}
printf("\n la matrice est :");
for(k=1;k<e+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]);}
}
//saisir le vecteur qu on veux comparer
printf("\nEntrer le vecteur qu on veux comparer:\n");
for(m=1;m<dim+1;m++)
{ printf(" A[%ld][0]=",m); scanf("%ld",&A[m][0]);
}
printf("\n le vecteur qu on veux comparer qvec est:\n");
for(m=1;m<dim+1;m++)
{ printf(" A[%ld][0]=%ld",m,A[m][0]);
}
//saisir le nombre de difference entre les lignes
do { printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>dim);
// traitement sur les differences entre les lignes
// je ne retiens que les lignes qui ont une difference >= di
int i2;
for(i2=1;i2<10;i2++)
{ for(i=0;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=0;k<e+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]);}
}
printf("\n le vecteur qu on veux comparer qvec est:\n");
for(m=1;m<dim+1;m++)
{ printf(" A[%ld][0]=%ld",m,A[m][0]);
}
getch();
}
mais il y a encore quelques erreurs:
1- la taille quand elle dépasse 7 (dim=7) sa marche pas sachant que j ai 2046 en ram et 2 ghz en processeur
2- pour le vecteur que je saisi pour le comparer avec ma matrice je l ai mis ds le tableau au debut pour la colonne 0
mais il y a un probleme pour la dim=6 je trouve que mon vecteur a changé mais pr dim<6 sa marche bien.
mamiemando>merci de votre programme mais j ai trouvé des difficultés pour le comprendre car comme je vous ai dis je ss débutant en programmation surtout au niveau des pointeurs et le grop probleme est que ma matrice est dynamique je dois la resoudre avec les pointeurs mais les pointeurs me bloquent énormément.
le programme que j ai fait jusqu a ce moment:
#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{ clrscr();
long int a,b,n,dim,dim2,j,diff,m,x,w,d,di;
long int k,i,i1,e,jm;
long int A[20][500];
printf("donner la puissance n-ieme de la matrice :"); scanf ("%ld",&n);
printf("donner la dimension de la matrice :"); scanf ("%ld",&dim);
e=pow(n,dim);
printf ("\n %ld puissance %ld = %ld\n",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(n,m-1);
w=pow(n,dim-m);
k=pow(n,dim-m+1);
for(i=0;i<x;i++)
for(j=1;j<w+1;j++)
for(i1=1;i1<n+1;i1++)
{ A[m][j+i*k+(i1-1)*w]=i1;
}
}
printf("\n la matrice est :");
for(k=1;k<e+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]);}
}
//saisir le vecteur qu on veux comparer
printf("\nEntrer le vecteur qu on veux comparer:\n");
for(m=1;m<dim+1;m++)
{ printf(" A[%ld][0]=",m); scanf("%ld",&A[m][0]);
}
printf("\n le vecteur qu on veux comparer qvec est:\n");
for(m=1;m<dim+1;m++)
{ printf(" A[%ld][0]=%ld",m,A[m][0]);
}
//saisir le nombre de difference entre les lignes
do { printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>dim);
// traitement sur les differences entre les lignes
// je ne retiens que les lignes qui ont une difference >= di
int i2;
for(i2=1;i2<10;i2++)
{ for(i=0;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=0;k<e+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]);}
}
printf("\n le vecteur qu on veux comparer qvec est:\n");
for(m=1;m<dim+1;m++)
{ printf(" A[%ld][0]=%ld",m,A[m][0]);
}
getch();
}
mais il y a encore quelques erreurs:
1- la taille quand elle dépasse 7 (dim=7) sa marche pas sachant que j ai 2046 en ram et 2 ghz en processeur
2- pour le vecteur que je saisi pour le comparer avec ma matrice je l ai mis ds le tableau au debut pour la colonne 0
mais il y a un probleme pour la dim=6 je trouve que mon vecteur a changé mais pr dim<6 sa marche bien.
toto> est ce que sa marche en visual c++ la déclaration char[20][10000000] seulement pour les caractères et pas pour int?
char[20][10000000] prend 4 fois moins de place que int [20][10000000]. Je ne sais pas quel compilateur tu utilises, mais c'est probablement pareil sur le tien.
Ton tableau actuel n'a que 500 lignes A[20][500]. Pourquoi prendre des long int pour stocker des tout petits entiers alors que tu cherches à économiser la mémoire?
Dès que dim=6 pour n=3, tu as besoin de 3^6=729 lignes. Ton tableau ne suffit plus. Mais comme il est malgré tout 'assez grand', tu 'tapes' encore dedans, mais plus forcément au bon endroit. Regarde la liste des vecteurs générés, tu verras que tu retombes sur les mêmes au bout d'un moment et que la liste ne finit pas par 333333.
Par contre, pour dim=7, tu sors du tableau et c'est le plantage complet.
Tout ceci est normal avec ton code tel qu'il est écrit.
Maintenant, si tu veux une proposition sérieuse de solution, donne nous les valeurs max de n et dim. Et si tu réponds n=3 et dim=20, je te signale que ça fait environ 3 10^9 lignes de chacune 20 nombres. Si on compte 2 bits par nombre, ça fait 15 Goctets. Il va falloir un certain temps pour créer ce fichier (je ne parle plus de mémoire centrale). Mais le balayer 3 milliards de fois environ comme le demande ta méthode actuelle (j'ignore s'il y en a une meilleure), ça me laisse rêveur...
char[20][10000000] prend 4 fois moins de place que int [20][10000000]. Je ne sais pas quel compilateur tu utilises, mais c'est probablement pareil sur le tien.
Ton tableau actuel n'a que 500 lignes A[20][500]. Pourquoi prendre des long int pour stocker des tout petits entiers alors que tu cherches à économiser la mémoire?
Dès que dim=6 pour n=3, tu as besoin de 3^6=729 lignes. Ton tableau ne suffit plus. Mais comme il est malgré tout 'assez grand', tu 'tapes' encore dedans, mais plus forcément au bon endroit. Regarde la liste des vecteurs générés, tu verras que tu retombes sur les mêmes au bout d'un moment et que la liste ne finit pas par 333333.
Par contre, pour dim=7, tu sors du tableau et c'est le plantage complet.
Tout ceci est normal avec ton code tel qu'il est écrit.
Maintenant, si tu veux une proposition sérieuse de solution, donne nous les valeurs max de n et dim. Et si tu réponds n=3 et dim=20, je te signale que ça fait environ 3 10^9 lignes de chacune 20 nombres. Si on compte 2 bits par nombre, ça fait 15 Goctets. Il va falloir un certain temps pour créer ce fichier (je ne parle plus de mémoire centrale). Mais le balayer 3 milliards de fois environ comme le demande ta méthode actuelle (j'ignore s'il y en a une meilleure), ça me laisse rêveur...
oui j ai remarqué que quand dim>7 et n=3 je sors de ma declaration A[20][500] mais quand je déclare une taile plus grande et suffaisante il me donne erreur: size array so long
pour le compilateur que j utilise j ai c version 3.5
pour votre remarque de ma déclaration du tableau long int vous avez complétement raison je dois récrifier pour int .
on se limite a la raille max dim=16 et n=3 si c possible et merci
pour le compilateur que j utilise j ai c version 3.5
pour votre remarque de ma déclaration du tableau long int vous avez complétement raison je dois récrifier pour int .
on se limite a la raille max dim=16 et n=3 si c possible et merci
je viens de faire un programme et j ai fais quelques progrés car je me ss arrivé a une taille avancée un peu :
dim=10 pour n=3
en declarant ma matrice comme caractére: char A[11][5500]
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';
}
}
dim=10 pour n=3
en declarant ma matrice comme caractére: char A[11][5500]
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';
}
}
merci toto de votre suivi
votre remarque de déclaration de caractére prends d espace mémoire m a aidé à trouver un truc pour ne pas rester bloquer; je declare ma matrice comme caractére et sa me donne encore plus d éléments ds ma matrice
char A[11][5700] et ds le remplissage de la matrice je me ss limité à 5700 lignes mais j aimerais que sa soit le 1/3 de la matrice cad la derniére ligne sera
1 3 3 3 3 3 3 3 3 3 ( mais ma derniere ligne est 1 1 3 2 3 2 2 1 1 2)
la ligne suivante sera
2 1 1 1 1 1 1 1 1 1
et la je peux l avoir en remplaçant par ceci(pour avoir le second 1/3)
A[m][col1]='2';
A[m][col2]='1';
A[m][col3]='3';
pour le troisiéme 1/3 je ferai ceci ;
A[m][col1]='3';
A[m][col2]='1';
A[m][col3]='2';
j espére que vous allez me comprendre ; si c possible de traduire ce programme en visual c++ j en serai trés reconnaissant juste pour arriver a déclarer 13 ou 14 cologne A[14][5 000 000] car la sa fait plus de 20 jours que je ss ds la boucle je ne sais quoi faire sa ma parait difficile le visual c++.
voici le programme:
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
long int b,dim,j,diff,m,x,w,d;
long int k,i,e,di,jm,dim2,col1,col2,col3;
char A[11][5700];
printf("donner la dimension de la matrice :"); scanf ("%ld",&dim);
e=pow(3,dim);
printf ("\n 3 puissance %ld = %ld\n",dim,e); scanf ("%ld",&b);
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++)
{ if (((j+i*k)<5700)||((j+i*k+w)<5700)||((j+i*k+2*w)<5700))
{ col1=j+i*k;
col2=j+i*k+w;
col3=j+i*k+2*w;
A[m][col1]='1';
A[m][col2]='2';
A[m][col3]='3';
}
}
}
e=5699;
do {
printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>dim);
// traitement sur les differences 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",e);
for(k=0;k<e+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(" %c",A[m][k]);}
}
getch();
}
votre remarque de déclaration de caractére prends d espace mémoire m a aidé à trouver un truc pour ne pas rester bloquer; je declare ma matrice comme caractére et sa me donne encore plus d éléments ds ma matrice
char A[11][5700] et ds le remplissage de la matrice je me ss limité à 5700 lignes mais j aimerais que sa soit le 1/3 de la matrice cad la derniére ligne sera
1 3 3 3 3 3 3 3 3 3 ( mais ma derniere ligne est 1 1 3 2 3 2 2 1 1 2)
la ligne suivante sera
2 1 1 1 1 1 1 1 1 1
et la je peux l avoir en remplaçant par ceci(pour avoir le second 1/3)
A[m][col1]='2';
A[m][col2]='1';
A[m][col3]='3';
pour le troisiéme 1/3 je ferai ceci ;
A[m][col1]='3';
A[m][col2]='1';
A[m][col3]='2';
j espére que vous allez me comprendre ; si c possible de traduire ce programme en visual c++ j en serai trés reconnaissant juste pour arriver a déclarer 13 ou 14 cologne A[14][5 000 000] car la sa fait plus de 20 jours que je ss ds la boucle je ne sais quoi faire sa ma parait difficile le visual c++.
voici le programme:
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
long int b,dim,j,diff,m,x,w,d;
long int k,i,e,di,jm,dim2,col1,col2,col3;
char A[11][5700];
printf("donner la dimension de la matrice :"); scanf ("%ld",&dim);
e=pow(3,dim);
printf ("\n 3 puissance %ld = %ld\n",dim,e); scanf ("%ld",&b);
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++)
{ if (((j+i*k)<5700)||((j+i*k+w)<5700)||((j+i*k+2*w)<5700))
{ col1=j+i*k;
col2=j+i*k+w;
col3=j+i*k+2*w;
A[m][col1]='1';
A[m][col2]='2';
A[m][col3]='3';
}
}
}
e=5699;
do {
printf("\nEntrer le nombre de difference entre les lignes :");
scanf("%ld",&di);
}
while (di>dim);
// traitement sur les differences 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",e);
for(k=0;k<e+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(" %c",A[m][k]);}
}
getch();
}
Il n'y a rien à traduire pour pouvoir compiler sous visual C++. J'ai copié-collé ton programme et il n'y a pas d'erreur de syntaxe, juste quelques warnings pour les conversion de type (utilisation de pow avec des entiers, mauvaise manip. Des erreurs d'arrondi peuvent donner des résultats faux, il vaut mieux faire le calcul sur des entiers)
Par contre, pour ce qui est de la logique... En traitant le tableau par tiers, tu ne pourras pas répondre au problème : comment comparer une combinaison avec une autre déjà effacée ?
Par contre, pour ce qui est de la logique... En traitant le tableau par tiers, tu ne pourras pas répondre au problème : comment comparer une combinaison avec une autre déjà effacée ?
oui sous visual c++ il me donne erreur de conversion de type et si je la traite avec des entiers il va accepter 3^10 car c est long int
pour le decoupe de la matrice je ne vais effacer ma matrice resultante du premier 1/3 et la mettre ds une autre matrice B[][] comme sa je libererai de la mémoire pour le traitement suivant
c une façon de trouver une solution.
si vs avez d autres idées j en ss reconnaissant.
pour le decoupe de la matrice je ne vais effacer ma matrice resultante du premier 1/3 et la mettre ds une autre matrice B[][] comme sa je libererai de la mémoire pour le traitement suivant
c une façon de trouver une solution.
si vs avez d autres idées j en ss reconnaissant.
mamiemando
Messages postés
33081
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 avril 2024
7 749
15 oct. 2008 à 18:32
15 oct. 2008 à 18:32
Si chaque case ne peut prendre que 4 valeurs il serait logique d'utiliser des "short int" et idéalement d'utiliser seulement 2 bits (soit avec une structure contenant deux bool (pardon pour ce jeu de mot douteux)).
Le type bool n'existe pas en C mais en C++ et n'occupe qu'un bit, il peut prendre les valeurs true (1) ou false (0).
Au niveau de ta matrice si elle est creuse (beaucoup de 0), il faut éviter d'allouer toutes les cases et utiliser une structure de matrice creuse (listes chaînée pour chaque ligne et colonne qui s'entrecroisent). En C++ ça se fait immédiatement avec des std::map. Tu peux faire un truc dans ce genre :
Le type bool n'existe pas en C mais en C++ et n'occupe qu'un bit, il peut prendre les valeurs true (1) ou false (0).
Au niveau de ta matrice si elle est creuse (beaucoup de 0), il faut éviter d'allouer toutes les cases et utiliser une structure de matrice creuse (listes chaînée pour chaque ligne et colonne qui s'entrecroisent). En C++ ça se fait immédiatement avec des std::map. Tu peux faire un truc dans ce genre :
#include <map>
class value_t{
protected:
bool x;
bool y;
public:
value_t(bool x0=false,bool y0=false):x(x0),y(y0){}
explicit value_t(unsigned x){set_value(x);}
inline void set_value(unsigned x0){
switch(x0){
case 0: x = 0; y = 0; break;
case 1: x = 0; y = 1; break;
case 2: x = 1; y = 0; break;
case 3: x = 1; y = 1; break;
default: throw;
}
}
inline unsigned get_value() const {
if (!x && !y) return 0;
if (!x && y) return 1;
if (x && !y) return 2;
// if (!x && !y)
return 3;
}
inline value_t & operator=(unsigned x0){
set_value(x0);
return *this;
}
};
typedef std::map<unsigned,std::map<unsigned,value_t> > sparse_matrix_t;
int main(){
sparse_matrix_t m;
m[25][48] = 2;
return 0;
}
Bonne chance
mamiemando
Messages postés
33081
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 avril 2024
7 749
16 oct. 2008 à 02:16
16 oct. 2008 à 02:16
toto > apparemment (et si j'ai bien compris) sa matrice est de taille 20 * 10000000 apparemment, et chaque case peut prendre 4 valeurs.
onedream > est-ce une matrice creuse ? Es-tu sûre qu'une telle matrice soit la meilleure façon de stocker les informations (que cherches-tu à faire ?). Je te préviens tout de suite qu'en C c'est beaucoup plus compliqué qu'en C++ car il faut coder une structure d'arbre ou de liste chaînée (si la matrice est creuse).
onedream > est-ce une matrice creuse ? Es-tu sûre qu'une telle matrice soit la meilleure façon de stocker les informations (que cherches-tu à faire ?). Je te préviens tout de suite qu'en C c'est beaucoup plus compliqué qu'en C++ car il faut coder une structure d'arbre ou de liste chaînée (si la matrice est creuse).
mamiendo > J'ai bien compris, c'est ce qu'a écrit onedream. Mias il dit aussi que sa matrice a 3^20 éléments, ce qui est contradictoire. D'autre part, comme il ne parle que de 3 (et non pas 4 comme le suggère son "quaternaire") valeurs 1,2,3, on peut imaginer que les 3^20 sont simplement le nombre de vecteurs différents de 20 éléments qu'on lui a demandé de générer, pas forcément de mettre dans un tableau.
Bref, j'aimerais bien voir l'énoncé exact du problème soumis à onedream, car je doute qu'un prof demande à un débutant de programmer un tableau qui ne "rentre" pas directement dans les capacités d'un compilateur normal.
Bref, j'aimerais bien voir l'énoncé exact du problème soumis à onedream, car je doute qu'un prof demande à un débutant de programmer un tableau qui ne "rentre" pas directement dans les capacités d'un compilateur normal.
mamiemando
Messages postés
33081
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
27 avril 2024
7 749
16 oct. 2008 à 10:14
16 oct. 2008 à 10:14
Oui je suis d'accord avec toi.
Mais à la limite peu importe qu'il ait mal quantifié la taille occupée. Son problème reste qu'il n'arrive pas à allouer un tableau car celui-ci est trop volumineux en mémoire.
Il faut donc revoir les données qu'il stocke en mémoire (est-ce utile de stocker toute la matrice en mémoire, peut-il exploiter la notion de matrice creuse, etc...). Et pour cela comme tu l'as dit il faudrait l'énoncé exact ;-)
Mais à la limite peu importe qu'il ait mal quantifié la taille occupée. Son problème reste qu'il n'arrive pas à allouer un tableau car celui-ci est trop volumineux en mémoire.
Il faut donc revoir les données qu'il stocke en mémoire (est-ce utile de stocker toute la matrice en mémoire, peut-il exploiter la notion de matrice creuse, etc...). Et pour cela comme tu l'as dit il faudrait l'énoncé exact ;-)
peu importe qu'il ait mal quantifié la taille occupée.
Je crois au contraire que ce genre d'incohérence est très révélateur. En tant que membre très actif de ce forum, tu sais bien que les difficultés viennent très souvent des énoncés. Combien de fois t'es-tu rendu compte au bout de 10 échanges qu'il y avait incompréhension dès le départ ?
Il est bien sûr possible que onedream ait réellement besoin de ce qu'il demande, mais j'aimerais aimé en être sûr avant d'y consacrer trop d'énergie.
Je crois au contraire que ce genre d'incohérence est très révélateur. En tant que membre très actif de ce forum, tu sais bien que les difficultés viennent très souvent des énoncés. Combien de fois t'es-tu rendu compte au bout de 10 échanges qu'il y avait incompréhension dès le départ ?
Il est bien sûr possible que onedream ait réellement besoin de ce qu'il demande, mais j'aimerais aimé en être sûr avant d'y consacrer trop d'énergie.
