Programme en c
Résolu
Bonjour,
pour pouvoir faire mon prog en C, j'ai besoin d'une methode pour identifier une erreur de position entre 2 matrices :
a b c a b d
d e f g
f g h c e h
ici on erreur(a)=0, erreur(b)=0, erreur(c)=4(2lignes et 2 colonnes)
ou encore erreur(f)=1(1 ligne de difference), etc...
la solution a l'arrache est de faire un char table[9][9] et d'identifier un a un les espacements mais je recherche un methode plus courte et plus intelligente
quelqu'un a t il une idee?
merci d'avance
PS : le but du puzzle est de deplacer les lettres de la matrice1 grace a l'espace pour retrouver la matrice 2
pour pouvoir faire mon prog en C, j'ai besoin d'une methode pour identifier une erreur de position entre 2 matrices :
a b c a b d
d e f g
f g h c e h
ici on erreur(a)=0, erreur(b)=0, erreur(c)=4(2lignes et 2 colonnes)
ou encore erreur(f)=1(1 ligne de difference), etc...
la solution a l'arrache est de faire un char table[9][9] et d'identifier un a un les espacements mais je recherche un methode plus courte et plus intelligente
quelqu'un a t il une idee?
merci d'avance
PS : le but du puzzle est de deplacer les lettres de la matrice1 grace a l'espace pour retrouver la matrice 2
A voir également:
- Programme en c
- Programme demarrage windows - Guide
- Mettre en veille un programme - Guide
- Message programmé iphone - Guide
- Programme word gratuit - Guide
- Cette action ne peut pas être réalisée car le fichier est ouvert dans un autre programme - Guide
4 réponses
La méthode "brutale" à le mérite d''être simple et rapide à implémenter.
Méthode que je te propose :
- tu parcours les deux matrices en référençant pour chaque lettre leur position dans les deux matrices.
- une fois cette structure de comparaison construite, pour chaque lettre stockée dans cette structure, tu calcules la distance de hamming entre les deux positions d = |x -x'| + |y - y'| (ce que tu as appelé erreur).
Je ne sais pas si tu as fait un peu de complexité mais concrètement en informatique on évalue les performances d'une approche ainsi : un programme est dit en O(n) si son temps de calcul croît linéairement avec n un paramètre du programme.
Posons H la hauteur de la matrice et L sa largeur.
Dans la méthode brutale :
On parcourt la première matrice (O(L.H)) et à rechercher ce caractère dans la seconde matrice. Cette recherche étant en O(L.H) et effectuée pour chaque lettre de la première matrice, la complexité du programme est O(L^2.H^2).
Dans la méthode que je te propose :
L'avantage c'est tu ne parcours les deux matrices qu'une fois (O(L.H + L.H) soit O(L.H)), puis tu parcours la structure de comparaison pour afficher les distances de hamming. Cette structure contenant L.H éléments le parcours se fait en (O(L.H)). Du coup programme en O(L.H).
Maintenant posons n=L=H (matrice carrée d'ordre n). Dans la première approche le programme est en O(n^4), et dans la seconde en O(n^2). Conclusion : si n est petit cette différence de complexité sera probablement imperceptible. Si par contre n est grand il faut clairement privilégier la seconde approche.
Bonne chance
Méthode que je te propose :
- tu parcours les deux matrices en référençant pour chaque lettre leur position dans les deux matrices.
- une fois cette structure de comparaison construite, pour chaque lettre stockée dans cette structure, tu calcules la distance de hamming entre les deux positions d = |x -x'| + |y - y'| (ce que tu as appelé erreur).
Je ne sais pas si tu as fait un peu de complexité mais concrètement en informatique on évalue les performances d'une approche ainsi : un programme est dit en O(n) si son temps de calcul croît linéairement avec n un paramètre du programme.
Posons H la hauteur de la matrice et L sa largeur.
Dans la méthode brutale :
On parcourt la première matrice (O(L.H)) et à rechercher ce caractère dans la seconde matrice. Cette recherche étant en O(L.H) et effectuée pour chaque lettre de la première matrice, la complexité du programme est O(L^2.H^2).
Dans la méthode que je te propose :
L'avantage c'est tu ne parcours les deux matrices qu'une fois (O(L.H + L.H) soit O(L.H)), puis tu parcours la structure de comparaison pour afficher les distances de hamming. Cette structure contenant L.H éléments le parcours se fait en (O(L.H)). Du coup programme en O(L.H).
Maintenant posons n=L=H (matrice carrée d'ordre n). Dans la première approche le programme est en O(n^4), et dans la seconde en O(n^2). Conclusion : si n est petit cette différence de complexité sera probablement imperceptible. Si par contre n est grand il faut clairement privilégier la seconde approche.
Bonne chance
ok je crois ke g compris, sauf ke sur les 9 erreurs a trouver yen a 2 ki sont fausses
voila mon code :
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define TAILLE 3
//Arguments d'entree//
int main(int argc,char*argv[]) {
int i=0;
int j=0;
printf("Parametres d'entree : ");
printf("argc =%d\n\n",argc);
for (i=0;i<argc;i++){
printf("argv[%d]=%s\n",i,argv[i]);
}
printf("\n");
//-------------------------------------------------------
//recuperation du puzzle de depart//
char matrix1[TAILLE][TAILLE];
for (i=0;i<3;i++){
for (j=0;j<3;j++){
matrix1[i][j]=argv[1][i*TAILLE+j];
}
}
//-------------------------------------------------------
//affichage du puzzle de depart//
printf("Puzzle de depart : \n\n");
for(i=0; i<3; i++) {
for(j=0; j<3; j++){
printf("%c ", matrix1[i][j]);
}
printf("\n");
}
//-------------------------------------------------------
//recuperation du puzzle d'arrivee//
char matrix2[TAILLE][TAILLE];
for (i=0;i<3;i++){
for (j=0;j<3;j++){
matrix2[i][j]=argv[2][i*TAILLE+j];
}
}
//-------------------------------------------------------
//affichage du puzzle d'arrivee//
printf("Puzzle d'arrivee : \n\n");
for(i=0; i<3; i++){
for(j=0; j<3; j++){
printf("%c ", matrix2[i][j]);
}
printf("\n");
}
printf("\n\n");
//-------------------------------------------------------
//comparaison des deux matrices//
char temp1[9];
char temp2[9];
short c=0;
for(i=0;i<3;i++){
for(j=0; j<3; j++){
temp1[i*TAILLE+j]=matrix1[i][j];
temp2[i*TAILLE+j]=matrix2[i][j];
}
}
for (i=0; i<9; i++){
for (j=0; j<9; j++){
if (temp1[i]==temp2[j]){
c++;
}
}
}
if (c<9){
printf("les 2 matrices ne contiennent pas les memes elemens");
}else{
//-------------------------------------------------------
//Calcul des erreurs//
int k=0;
int l=0;
int erreur[9];
for (i=0; i<9; i++){
erreur[i]=0;
}
for (i=0; i<=2; i++){
for (j=0; j<=2; j++){
k=0;l=0;
while (matrix1[i][j]!=matrix2[k][l] && k<=2){
l++;
if (l==2){k++;l=0;}
}
erreur[i*TAILLE+j]=(k+l)-(i+j);
}
}
//-------------------------------------------------------
//Affichage des erreurs//
for (i=0; i<9; i++){
printf("erreur(%c)=%d\n",temp1[i],erreur[i]);
}
}
printf("\n\n");
printf("fin\n");
return 0;
}
alors si je rentre
a b c f b c
d e f d e
g h a g h
jai comme erreurs
a:2,b:0,c:1,d:1,e:1
f:3,g:1,h:0, :3
alors ke on devrait avoir h:1 et c:0
merci de me dire ce que tu en penses
voila mon code :
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define TAILLE 3
//Arguments d'entree//
int main(int argc,char*argv[]) {
int i=0;
int j=0;
printf("Parametres d'entree : ");
printf("argc =%d\n\n",argc);
for (i=0;i<argc;i++){
printf("argv[%d]=%s\n",i,argv[i]);
}
printf("\n");
//-------------------------------------------------------
//recuperation du puzzle de depart//
char matrix1[TAILLE][TAILLE];
for (i=0;i<3;i++){
for (j=0;j<3;j++){
matrix1[i][j]=argv[1][i*TAILLE+j];
}
}
//-------------------------------------------------------
//affichage du puzzle de depart//
printf("Puzzle de depart : \n\n");
for(i=0; i<3; i++) {
for(j=0; j<3; j++){
printf("%c ", matrix1[i][j]);
}
printf("\n");
}
//-------------------------------------------------------
//recuperation du puzzle d'arrivee//
char matrix2[TAILLE][TAILLE];
for (i=0;i<3;i++){
for (j=0;j<3;j++){
matrix2[i][j]=argv[2][i*TAILLE+j];
}
}
//-------------------------------------------------------
//affichage du puzzle d'arrivee//
printf("Puzzle d'arrivee : \n\n");
for(i=0; i<3; i++){
for(j=0; j<3; j++){
printf("%c ", matrix2[i][j]);
}
printf("\n");
}
printf("\n\n");
//-------------------------------------------------------
//comparaison des deux matrices//
char temp1[9];
char temp2[9];
short c=0;
for(i=0;i<3;i++){
for(j=0; j<3; j++){
temp1[i*TAILLE+j]=matrix1[i][j];
temp2[i*TAILLE+j]=matrix2[i][j];
}
}
for (i=0; i<9; i++){
for (j=0; j<9; j++){
if (temp1[i]==temp2[j]){
c++;
}
}
}
if (c<9){
printf("les 2 matrices ne contiennent pas les memes elemens");
}else{
//-------------------------------------------------------
//Calcul des erreurs//
int k=0;
int l=0;
int erreur[9];
for (i=0; i<9; i++){
erreur[i]=0;
}
for (i=0; i<=2; i++){
for (j=0; j<=2; j++){
k=0;l=0;
while (matrix1[i][j]!=matrix2[k][l] && k<=2){
l++;
if (l==2){k++;l=0;}
}
erreur[i*TAILLE+j]=(k+l)-(i+j);
}
}
//-------------------------------------------------------
//Affichage des erreurs//
for (i=0; i<9; i++){
printf("erreur(%c)=%d\n",temp1[i],erreur[i]);
}
}
printf("\n\n");
printf("fin\n");
return 0;
}
alors si je rentre
a b c f b c
d e f d e
g h a g h
jai comme erreurs
a:2,b:0,c:1,d:1,e:1
f:3,g:1,h:0, :3
alors ke on devrait avoir h:1 et c:0
merci de me dire ce que tu en penses
voila la solution :
//Fonctio de calcul des erreurs//
int calcul_erreur(char matrix1[3][3],char matrix2[3][3])
{
int i=0;
int j=0;
int k=0;
int l=0;
int erreur[9];
for (i=0; i<9; i++){
erreur[i]=0;
}
for (i=0; i<3; i++){
for (j=0; j<3; j++){
for (k=0; k<3; k++){
for (l=0;l<3; l++){
if(matrix1[i][j]==matrix2[k][l]){
erreur[i*TAILLE+j]=abs(k-i)+abs(l-j);
}
}
}
}
}
}
//Fonctio de calcul des erreurs//
int calcul_erreur(char matrix1[3][3],char matrix2[3][3])
{
int i=0;
int j=0;
int k=0;
int l=0;
int erreur[9];
for (i=0; i<9; i++){
erreur[i]=0;
}
for (i=0; i<3; i++){
for (j=0; j<3; j++){
for (k=0; k<3; k++){
for (l=0;l<3; l++){
if(matrix1[i][j]==matrix2[k][l]){
erreur[i*TAILLE+j]=abs(k-i)+abs(l-j);
}
}
}
}
}
}