PDA

View Full Version : Giải thuật | Các thao tác trên Ma trận



PoPoPoPo
09-10-2006, 10:49 AM
Code các thao tác trên Ma trận vuông.

#include<conio.h>
#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<math.h>
#include<iostream.h>
//=======================================
#define MAXMT 20
#define TRUE 1
#define FLASE 0
//int n;
float A[10][10];
//=======================================
typedef struct
{
int n;//m hang
float A[MAXMT][MAXMT];
}MT;
//========================================
/*
chuong trinh bao gom cac chuc nang chinh
1- Tao moi 1 MT vao file
2- Tim Max(äPtu) cua hang, cot hoac duong cheo
3- Tim hang cua ma tran A[n][n]
4- MT chuyen vi
5- Ma tran nghich dao
6- Tinh dinh thuc
7- Giai He PTTT AX=B
0- thoat
*/
//========================================
void Input_MT(MT *a)
{
// nhap moi vao file
int i,j,m,n;
float k;
FILE *f;
f= fopen("MATRAN.IN","wb");
clrscr();
printf("Co cua MA TRAN A la(n*n) :"); // nhap A
printf("\n n =");
scanf("%d",&n);
a->n=n;
printf("\n Nhap cac he so: \n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
printf("A[%d][%d] = ",i,j);
scanf("%f",&k);
a->A[i][j] = k;
} ;
clrscr();

fwrite(a,sizeof(MT),1,f);

fclose(f);


}
//=============================================
void Input_MT1(MT *a)// load tu tep
{
int i,j,n;
//float k;
FILE *f;
f = fopen("MATRAN.IN","rb");
if(f==NULL)
{
printf("Tep MATRAN.IN khong ton tai");

}
else
{
fread(a,sizeof(MT),1,f);
// hien thi A
n = a->n;
clrscr();
printf("\n Ma tran A [%d * %d]: ",n,n);
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf(" %7.2f",a->A[i][j]);
}

} ;
fclose(f);
}
//=================================================
void display_MT(MT *a)
{
int i,j,n;
n = a->n;
for(i=0;i<n;i++)
{
printf("\n");
for(j=0;j<n;j++)
printf(" %7.2f",a->A[i][j]);
}

}
//================================================
//========================
void timtroi()
{
int n;
int i,j;
float **a;
float max;
float s1,s2,s3,s4;
int dem;

cout<<"Nhap vao co cua ma tran A: n=";
cin>>n;
a=new float*[n];
for(i=0;i<n;i++)

a[i]=new float[n];
max=0;
cout<<"Nhap vao ma tran A";
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
gotoxy(i*6+2,j*2+5);
cin>>a[i][j];
}
s3=s4=0;
//======================
for(i=0;i<n;i++)
{
s1=s2=0;
for(j=0;j<n;j++)
{
s1+=a[i][j];
s2+=a[j][i];
}
s3+=a[i][i];
s4+=a[i][n-i-1];
if(max<s1) {max=s1;dem=i+1;}
if(max<s2) {max=s2;dem=i+n+1;}
}
if(max<s3) {max=s3;dem=n+n;}
if(max<s4) {max=s4;dem=n+n+1;}
if(dem>2*n)
{
cout<<"Duong cheo "<<dem-n-n<<" co tong cac phan tu lon nhat";
}
else
{
if(dem>n)
cout<<"Hang "<<dem-n<<" co tong cac phan tu lon nhat";
else
cout<<"Cot "<<dem<<" co tong cac phan tu lon nhat";
}
cout<<" Gia tri max la "<<max;
getch();
}
//================================================
void MT_chuyenvi(MT *a,MT *b)
{
// sai nhap vao ma tran c khong duoc
int i,j,m,n;

n = a->n ;
b->n =n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{

b->A[j][i] = a->A[i][j];
} ;
display_MT(a);
printf("\nMa tran chuyen vi");
display_MT(b);
}

//==================================================

//================================================== =====

int Dinhthuc_MT(MT *a,float *dthuc,int n)
{ //chuyen ve ma tran tam giac tren
// Ma tran vuong
int i,j,k,h,d;
float tmp,p;
n = a->n;
d =1; // d=1 neu so lan doi cho la chan

if(n == a->n)
{
for(i=0;i<n-1;i++) // vong lap cac buoc khu den n-2 thi dung lai
{ // tim hang co phan tu lon nhat
h=i;
for(k=i+1;k<n;k++) // Duyet tu hang thu i+1
if(fabs(a->A[k][i])>fabs(a->A[h][i])) h=k;

if((a->A[h][i])==0){ printf("\nMa tran suy bien");return 0;}

if(h!=i)// doi hang i va hang h
{
for(j=i;j<n;j++)
{ tmp =a->A[i][j]; a->A[i][j]=a->A[h][j]; a->A[h][j]=tmp; }
d = -d;
}
//bat cac buoc khu
for(k=i+1;k<n;k++)
{
p =(a->A[k][i])/(a->A[i][i]);
for(j=i+1;j<=n;j++) a->A[k][j] = a->A[k][j] - p*(a->A[i][j]);

}

}
// dat cac gia tri duoi duong cheo chinh =0
for(i=1;i<n;i++)
for(j=0;j<i;j++) a->A[i][j] = 0;

tmp = a->A[0][0];
for(i=1;i<n;i++) tmp =tmp*(a->A[i][i]);

*dthuc = d*tmp;//ket qua
}
else {printf("Dau vao sai phai la ma tran vuong"); return 0;}
return 1;
}
//================================================== ======
int HangMT(MT *a)
{
int n;
float dthuc;
n=a->n;
for(int i=2;i<=n;i++)
{
a->n=i;
Dinhthuc_MT(a,&dthuc,i);
if(dthuc==0 ) return(i-1);
}
return(n);
}
//================================================== =====
int MT_Nghichdao(MT *a,MT *b)
{ //phuong phap khu Gauss_Jordan
// dua a ve dang ma tran tren , phia sau se la MT dao
int i,j,k,h,n,n2;
float tmp,p;
n= a->n;
b->n=n;
n2 = 2*n;
// them phan sau de ve ma tran don vi
for(i=0;i<n;i++)
for(j=0;j<n;j++) a->A[i][n+j] = 0; // phan phia sau ==0
for(i=0;i<n;i++) a->A[i][n+i] = 1; // duong cheo chinh phia sau
// vong lap cac buoc khu

for(i=0;i<n;i++)
{
// Tim hang co phan dau lon nhat
h =i;
for(k=i+1;k<n;k++)
if(fabs(a->A[k][i])>fabs(a->A[h][i])) h=k;
if(a->A[h][i]==0) { printf("Ma tran suy bien");return 0;}
if(h!=i) // doi cho i va hang h
{
for(j=i;j<n2;j++)
{tmp = a->A[i][j]; a->A[i][j] =a->A[h][j]; a->A[h][j] = tmp; }
}
// chuyen A[i][i] =1;
tmp = a->A[i][i];
for(j=i;j<n2;j++) a->A[i][j] = a->A[i][j]/tmp;
// tinh lai cac hang
for(k=0;k<n;k++)
{
if(k==i) continue;
p = a->A[k][i];
for(j=i+1;j<n2;j++) a->A[k][j] = a->A[k][j] - p*(a->A[i][j]);
}
}
// dat cac gia tri khong tren duong cheo chinh =0;
for(i=0;i<n;i++)
for(j=0;j<n;j++) { if(i!=j)a->A[i][j]=0; }

// ket qua luu vao ma tran B
for(i=0;i<n;i++)
for(j=0;j<n;j++) b->A[i][j] = a->A[i][n+j];
return 1;

}
//================================================== ===============================
void giai_he()
{

int n,i,j,k;
float tg,max;
clrscr();
printf("\n he phuong trinh co bao nhieu an ? x = ");
scanf("%d",&n);
printf("\n Nhap ma tran mo rong");
for(i=1;i<=n;i++)
for(j=1;j<=n+1;j++)
{
gotoxy(j*6+2,i*2+4);
scanf("%f",&A[i][j]);
}

for(i=1;i<=n;i++)
{
k=i;
max=fabs(A[i][i]);
for(j=i;j<=n;j++)
if(fabs(A[j][i])>max)
{
max=fabs(A[j][i]);
k=j;
}
if(max==0) { printf("he phuong trinh co vo so nghiem");return;}
if(k!=i)
for(j=i;j<=n+1;j++)
{
tg=A[i][j];
A[i][j]=A[k][j];
A[k][j]=tg;
}

tg=A[i][i];

for(j=i;j<=n+1;j++)
A[i][j]=A[i][j]/tg;
for(j=1;j<=n+1;j++)
{
if(j==i) continue;
tg=A[j][i];
for(k=i;k<=n+1;k++)
A[j][k]=A[j][k]-tg*A[i][k];
}

}

printf("\nNghiem cua he la:");
for(i=1;i<=n;i++)
{
printf("\n");
printf(" x[%d] = %g ",i,A[i][n+1]);
}

}
//================================================== ===============


//=================================================
void main()
{
MT a,b,c;
float dthuc;
int T;int n;
char chon;
textmode(C80);
textcolor(YELLOW);
textbackground(BLUE);
window(1,1,80,25);

do
{
clrscr();
printf("\n Tap thao t*c trˆn Ma tran vu“ng") ;
printf("\nÞÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜÜ ÜÜÜÜÜÜÜÜÝ");
printf("\n\n Menu\nÈÍÍÍͼ");
printf("\n1. Tao tap A[N][N]");
printf("\n2. Tim Max(äcacPtu) cua Hang,Cot hoac duong cheo");
printf("\n3. Tim hang cua A[N][N]");
printf("\n4. Tim Chuyen vi cua A[N][N]");
printf("\n5. Tim Det(A)");
printf("\n6. Tim Ngich dao cua A[N][N]");
printf("\n7. Giai he Pt Ax =B");
printf("\n0. Tro ve MENU ch¡nh");
//printf("\n0. Thoat");
printf("\n\nHay chon chuc nang : ");
//===============
chon = getchar();
switch(chon)
{
case '1' :
Input_MT(&a);
Input_MT1(&a);getch(); break;
case '2' :
clrscr();
printf("Tim Max(äPtu) cua Hang,cot hoac duog cheo\n");
timtroi();
break;

case '3' :
clrscr();
printf("\nTim hang Cua A[n][n]");
Input_MT1(&a);T=a.n;
printf("\nHang Cua A = %d",T);
getch();
break;
case '4' :
printf("\nMa tra A la:") ;
MT_chuyenvi(&a,&b);
getch();
break;

case '5': clrscr();
printf("\n Ma tran A:\n");
display_MT(&a);
Dinhthuc_MT(&a,&dthuc,n);
printf("\n-----Ma tran duong cheo------\n");
display_MT(&a);
printf("\n-----------------------------\n");
printf("\n Ket qua : %3.2f",dthuc);
getch(); break;
case '6' : clrscr();
printf("\n Ma tran A:\n");
display_MT(&a);
printf("\n-----Ma tran nghich dao------\n");
MT_Nghichdao(&a,&c);
display_MT(&c);
getch();
break;
case '7':
clrscr();
printf("Giai HePt Tuyen tinh A*X=B");
giai_he();
getch();
break;
}
}while(chon!='0');
}