Đề tài Các phép toán thực hiện trên ma trận thực

CHƯƠNG I : ĐẶT VẤN ĐỀ I MỤC ĐÍCH CỦA ĐỢT THỰC TẬP Qua đợt thực tập này sẽ tạo điều kiện để sinh viên nghiên cứu sâu hơn về một số vấn đề được giới thiệu trên lớp học.Qua đó nâng cao khả năng sử dụng ngôn ngữ lập trình,làm quen dần với việc giải quyết các bài toán ứng dụng . II ĐỀ TÀI THỰC TẬP 1 . Tên đề tài : Các phép toán thực hiện trên ma trận thực 2 . Nội dung và yêu cầu của đề tài : Nội dung : Xây dựng chương trình thực hiện các phép toán trên ma trận thực: cộng ,trừ,nhân hai ma trận : tính định thức ma trận vuông bằng cách dùng công thức hoán vị,từ đó tìm hạng của ma trận vuông C. det C = cc …..c Trong đó p là hoán vị p = của n số tự nhiên liên tiếp đầu tiên Yêu cầu : Nhập xuất dữ liệu từ file và từ bàn phím .Kết quả lưu ra file và hiển thị được ra màn hình . Mỗi ma trận kích thước m*n được lưu trên một file với cấu trúc : Dòng 1 : m n Dòng 2 : hàng thứ 1 của ma trận ……………………………… Dòng m+1 : hàng thứ m của ma trận Có một hàm sinh ra ma trận ngẫu nhiên với kích thước tùy ý, kết quả lưu ra file. Khi tìm hạng của ma trận A ,hiển thị được ma trận con cấp cao nhất có định thức khác 0 bằng mầu khác với phần còn lại của A. Tính toán được trên ma trận kích thước lớn với thời gian chấp nhận được(200*200). Hiển thị được các kết quả trung gian khi có yêu cầu (ma trận ,biểu thức tính toán…) III . CÁC NHIỆM VỤ CỤ THỂ ĐẶT RA TRONG ĐỀ TÀI Ngoài các nội dung chính thực hiện trên ma trận thực :cộng ,trừ ,nhân hai ma trận,tính định thức ma trận vuông dùng công thức hoán vị và tìm hạng của ma trận vuông ,để giải quyết đề tài một cách trọn vẹn ta còn phải tạo dữ liệu vào cho chương trình thông qua file văn bản và tạo giao diện(menu) cho chương trình .Như vậy với đề tài này thì các nhiệm vụ đặt ra là : Tạo dữ liệu đầu vào ( Tạo file lưu trữ các thông tin về ma trận) Thực hiện các phép toán trên ma trận thực : Cộng hai ma trận. Trừ hai ma trận . Tích hai ma trận . Tính định thức của ma trận vuông. Tính hạng của ma trận vuông. Tạo giao diện cho chương trình CHƯƠNG II : XÂY DỰNG CHƯƠNG TRÌNH Với mục đích và yêu cầu của bài toán trong đề tài thì chương trình sẽ thực hiện các công việc như sau : Thực hiện các phép toán trên ma trận thực. Tính định thức của ma trận vuông bằng cách dùng công thức hoán vị,từ đó tìm hạng của ma trận . Tuy nhiên để hoàn thiện đề tài thì ta phải tạo đươc các ma trận bất kỳ và ma trận vuông .Nhưng để tạo được ma trận thì ta cần phải nhập vào số liệu do vậy ta phải thêm bước tạo file để sử dụng trong chương trình .Hơn nữa sau khi tạo ma trận và thực hiện các phép toán trên ma trận thì để tiện sử dụng và kiểm tra thì ta cần ghi chúng vào các file sau đó tiến hành đọc chúng khi có yêu cầu . Như vậy khi thực hiện chương trình thì gồm các bước chính sau : Tạo ma trận từ file và từ bàn phím . Thực hiện các phép toán trên ma trận thực và ghi vao file . Tinh định thức của ma trận vuông bằng cách dùng công thức hoán vị,từ đó tìm hạng của ma trận và ghi vào file. Hiển thi ra màn hình các kết quả khi có yêu cầu . Với các yêu cầu như trên thì chương trình sẽ bao gồm 7 phần tương ứng với 8 mục đầu trong menu chính của chương trình : Nhập ma trận . Nhập ma trận ngẫu nhiên . Nhập ma trận từ file Tổng ma trận . Hiệu ma trận . Tích ma trận . Định thức và hạng ma trận . Hiển thị file . _Exit . A. CÁC HÀM VÀ THỦ TỤC TRONG CHƯƠNG TRÌNH Chương trình bao gồm các hàm sau : void nhapmatran ( ) ; void matranngaunhien ( ) ; void matrannhaptufile ( ) ; void tong ( ) ; void hieu ( ) ; void tich ( ) ; void dinhthuc ( int n1 ) ; void hang ( ); void tongmatran ( ) ; void hieumatran ( ) ; void tichmatran ( ); void dinhthucvahangmatran ( ) ; void hienthifile ( ) ; Trong đó các hàm được xây dựng theo cấu trúc sau : Chương trình chính sẽ gọi là main ( ) Từ hàm main se gọi đến 1 trong 7 hàm : nhapmatran , matranngaunhien , tongmatran , hieumatran , tichmatran , dinhthucvahangmatran , hienthifile . . Nhapmatran : Hàm này làm việc theo một trong hai cách : + Nhập ma trận từ file : Gọi hàm tạo file mình đã tạo sẵn: “Input.txt” ; Gọi hàm nhập ma trận từ file: Matrannhaptufile ( ); + Nhập ma trận với dữ liệu nhập từ bàn phím: Gọi hàm tạo ma trận : Nhapmatran ( ) ; Hàm Matrannhaptufile ( ); sẽ lấy file có sẵn ở hàm tạo file có trước “Input.txt” để tạo dữ liệu đầu vào một cách ngẫu nhiên cho chương trình tùy theo sụ lựa chọn Hàm Nhapmatran ( ); sẽ tạo file với dữ liệu nhập từ bàn phím Trong hàm nhapmatran ( );ta xây dựng 3 ma trận sử dụng cho toàn bộ chương trình :ma trận A ,B và ma trận vuông C với dữ liệu lấy một cách ngẫu nhiên từ bàn phím và lưu chúng vào file . Trong hàm Matrannhaptufile ( ); ta cũng xây dựng tương tự 3 ma trận A,B,C với dữ liệu lấy từ file. 2 . Matranngaunhien : Hàm này tạo ma trận A,B và ma trận vuông C một cách ngẫu nhiên ,lưu chúng vào file và sử dụng cho toàn bộ chương trình. Để tạo được như vậy ta sử dụng hàm rand ( ); 3 .Tongmatran : Hàm tongmatran ( ); sẽ đưa ra tổng của hai ma trận cùng cấp và để thực hiện điều này thì nó phải gọi hàm tong ( ); .Hàm tong ( ); này sẽ đưa cho ta một thủ tục để tính tổng của hai ma trận cùng cấp và kết quả là ma trận cùng cấp (trong chương trình thì đó là ma trận E ) . 4 .Hieumatran : Hàm hieumatran ( ); sẽ đưa ra hiệu của hai ma trận cùng cấp và để thực hiện điều này thì nó phải gọi hàm hieu ( ); .Hàm hieu ( ); sẽ đưa ra một thủ tục để tính hiệu của hai ma trận cùng cấp ,kết quả là ma trận cùng cấp (trong chương trình thì là ma trận F) 5 . Tichmatran : Hàm tichmatran ( );sẽ đưa ra tích của hai ma trận và để thực hiện điều này thì nó phải gọi hàm tich ( ); Hàm tich ( );sẽ đưa ra một thủ tục để tính tích của hai ma trận ( trong chương trình thì đó là ma trận D).Nhưng trong hàm tichmatran ( ); thi ta phải kiểm tra điều kiện để tồn tại tích của hai ma trận A và B . 6 . Dinhthucvahangmatran : Hàm dinhthucvahangmatran ( ); sẽ đưa ra định thức và hạng của ma trận vuông C . Trong hàm này thì nó gọi hàm dinhthuc ( ); và hàm hang ( ); Hàm dinhthuc ( ); sẽ đưa ra thủ tục để tính định thức và hàm hang ( ); sẽ đưa ra thủ tục để tính hạng nhưng sau khi đã xây dựng được hàm dinhthuc(); của ma trận vuông C. 7 . Hienthifile : Hàm hienthifile ( ); dùng để hiện thị tất cả các file đã tạo và sử dụng trong suốt quá trình làm việc : + Hiển thị file chứa toàn bộ các ma trận đã được nhập vào (đó là ma trận A,B,C) . +Hiển thị file chứa toàn bộ quá trình thiết lập để tính và hiện thị ra được kết quả của tích ma trận (ma trận D), tổng ma trận(ma trận E), hiệu ma trận(ma trận F), định thức ma trận và hạng của ma trận. ******************************************************* B . SƠ ĐỒ THUẬT TOÁN Trong đề tài này để xây dựng và hoàn thiện chương trình thì ta phải xây dựng sơ đồ thuật toán với mục đích : Tránh những lỗi logic khi thực hiện chương trình. Giúp cho người đọc dễ dàng hiểu được code của chương trình. Để giải quyết được các yêu cầu trong đề tài này thì ta cần làm : 1 . Tạo dữ liệu để sử dụng trong suốt chương trình .(nhapmatran) Dữ liệu đầu vào chính là xây dựng hai ma trận bất kỳ A[m][n], B[p][q] và ma trận vuông C[n1][n1] .Việc xây dựng 3 ma trận này tương tự như nhau là đều sử dụng hai vòng lặp for.Tuy nhiên có hai cách để xây dựng chúng :Thiết lập ma trận với số liệu lấy nhập bàn phím và thiết lập ma trận một cách ngẫu nhiên : 1.1 Ma trận với số liệu nhập từ bàn phím Ví dụ với ma trận A :Ta dùng hai biến i ( chỉ số hàng ) và j ( chỉ số cột ) Cho i chạy từ 1 tới m và j chạy từ 1 tới n for ( i=1 ; i<=m ; i++) for ( j=1 ; f<=n ; j++ ) printf ( “ \ n A[%d][%d] = “ , i , j ) ; scanf ( “%f “ , &t ) ; A[ i ][ j ] =t ; 1.2 Ma trận tạo ngẫu nhiên Ví dụ với ma trận A : for ( i=1 ; i<=m ; i++) for ( j=1 ; f<=n ; j++ ) A[ i ][ j ] =rand ( ) ; Sau khi tạo được bằng một trong hai cách ta phải in được các ma trận đó ra màn hinh : Ta cũng sử dụng hai vòng lặp for : Ví dụ với ma trận A : printf ( “Ma tran A \ n “ ) ; printf ( “ %d %d “ , m , n ) ; for ( i=1 ; i<=m ; i++ ) { printf ( “ \n “ ) ; for ( j=1 ; j<=n ; j++ ) printf ( “ % 10.2 f “ , A[ i ][ j ] ) ; } 1.3 Ma trận đọc từ file Đầu tiên ta phải tạo được dữ liệu đầu vào tức là ta xây dựng file “Input.txt”, khai báo sâu kiểu chr msg [25] . Ta sử dụng hàm fgets để đọc dữ liệu và sử dụng hàm atoi ( hàm chuyển ký tự thành số ) ví dụ như m = atoi(msg) .Sau đó ta hiển thị ra bằng cách sử dụng hai vòng lặp for : Với ma trận A : for ( i = 1 ; i <=m ; i++ ) { for ( j = 1 ; j<=n ; j++ ) { fgets ( msg , 25 , stream ); aij=atoi ( msg ); printf ( "A[%d][%d]=%d " , i , j , aij ); } printf ( " \ n \ r " ); } 2. Các phép toán thực hiện trên ma trận thực ( ma trận đã được nhập ). 2.1. Tổng ma trận ( tongmatran ) : Với hai ma trận bất kỳ đã được nhập A[m][n] và B[p][q] thì ta xây dựng công thức tổng quát tính tổng của hai ma trận này. Tuy nhiên trước đó ta phải kiểm tra xem có tồn tại tổng của hai ma trận này không ( để tồn tại tổng thì hai ma trận này cùng cấp ) Tức là : ( ( m==p )&&( n==q ) ) + Nếu điều kiện này được thỏa mãn thì ta tiến hành tính tổng của hai ma trận này ( giả sử ma trận tổng là E[m][n] ). Ta dùng hai biến chạy i (1<=i<=m )và j (1<=j<=n ) , ma trận tổng E[ i ][ j ] = A[ i ][ j ] + B[ i ][ j ] Ta minh họa bằng thuật toán: for ( i=1 ; i<=m ; i++) for ( j=1 ; f<=n ; j++ ) { E[ i ][ j ] = A[ i ][ j ] + B[ i ][ j ] } Sau đó ta hiển thị ma trận lên màn hình for ( i=1 ; i<=m ; i++) { for ( j=1 ; f<=n ; j++ ) printf ( “%10.2f “ , E[ i ][ j ] ) ; } + Nếu điều kiện này không thỏa mãn thì không tồn tại tổng. Ta minh họa thuật toán tính tổng bằng sơ đồ giải thuật : BEGIN NHẬP MA TRẬN TỔNG MA TRẬN END m=p&n=q 2.2 Hiệu ma trận ( hieumatran ) Với hai ma trận bất kỳ đã được nhập A[m][n] và B[p][q] thì ta xây dựng công thức tổng quát tính hiệu của hai ma trận này. Tuy nhiên trước đó ta phải kiểm tra xem có tồn tại hiệu của hai ma trận này không: if ( ( m==p )&&( n==q ) ) + Nếu điều kiện này được thỏa mãn thì ta tiến hành tính hiệu của hai ma trận này ( giả sử ma trận hiệu là F[m][n] ). Ta dùng hai biến chạy i (1<=i<=m )và j (1<=j<=n ) , ma trận hiệu F[ i ][ j ] = A[ i ][ j ] - B[ i ][ j ] Ta minh họa bằng thuật toán: for ( i=1 ; i<=m ; i++) for ( j=1 ; f<=n ; j++ ) { F[ i ][ j ] = A[ i ][ j ] - B[ i ][ j ] } Sau đó ta hiển thị ma trận hiệu lên màn hình for ( i=1 ; i<=m ; i++) { for ( j=1 ; f<=n ; j++ ) printf ( “%10.2f “ , F[ i ][ j ] ) ; } + Nếu điều kiện này không thỏa mãn thì không tồn tại hiệu. Ta minh họa thuật toán tính hiệu bằng sơ đồ giải thuật : BEGIN NHẬP MA TRẬN HIỆU MA TRẬN END m=p&n=q 2. 3 Tích ma trận ( tichmatran ) Với hai ma trận bất kỳ đã được nhập A[ m ][ n ] và B[ p ][ q ] thì ta xây dựng công thức tổng quát tính tích của hai ma trận này. Tuy nhiên trước đó ta phải kiểm tra xem có tồn tại tích của hai ma trận này không ( để tồn tại tích của hai ma trận A và B thì hàng của ma trận A phải bằng cột của ma trận B Tức là : ( n==p ) + Nếu điều kiện này được thỏa mãn thì ta tiến hành tính tích của hai ma trận này ( giả sử ma trận tích là D[ m ][ q ] ). Ta dùng hai biến chạy i (1<=i<=m )và j (1<=j<=q ) , Sau đó ta gán D[ i ][ j ] =0 và lấy hàng i của ma trận A nhân với cột j của ma trận B . Để làm được điều này ta dùng biến trung gian k ( 1<=k<=n ) ma trận tích là : D[ i ][ j ] = A[ i ][ k ] * B[ k ][ j ] Ta minh họa thuật toán như sau : for ( i=1 ; i<=m ; i++) for ( j=1 ; f<=q ; j++ ) { D[ i ][ j ] = 0; for (k=1 ; k<=n ; k++ ) D[ i ][ j ] + = A[ i ][ k ] * B[ k ][ j ] } Sau đó ta hiển thị ma trận tích lên màn hình for ( i=1 ; i<=m ; i++) { for ( j=1 ; f<=q ; j++ ) printf ( “%10.2f “ , D[ i ][ j ] ) ; } + Nếu điều kiện này không thỏa mãn thì không tồn tại tích . Ta minh họa thuật toán tính tích bằng sơ đồ giải thuật : BEGIN NHẬP MA TRẬN TÍCH MA TRẬN END n==p 2.4 Hạng và định thức của ma trận vuông ( dinhthucvahangmatran ) Theo yêu cầu của đề tài thì ta phải tìm được định thức của ma trận vuông C[n1][n1] trước sau đó mới suy ra hạng . Trước hết ta tìm định thức của ma trận : Ta dùng kiểu boolean : đặt done=0 ( FALSE ) Nếu như đúng while ( ! done ) thì thuật toán sẽ như sau: + Nếu có phần tử trên đường chéo chính bằng không ( C[ i][j ]==0 ) ta đặt giá trị đó là max=0 và m1=i ( gán hàng i là hàng m1) Dùng một biền phụ k cho biến này chạy (k=i+1 ; k<n1 ; k++ ) Nếu max < trị tuyệt đối của phần tử C[ k ][ i ] thì hàng m1 trở thành hàng k và max = fabs ( C[ k ][ i ] ) Nếu ( m1! = i ) thì ta hoán đổi hàng i và hàng m1và giá trị của định thức d=-d. Nếu ( m1 == i ) thì ma trận lúc này suy biến done lúc này=1 và d=0 Ta minh họa bằng thuật toán như sau if(C[ i ][ i ]==0) { max = 0; m1 = i; for ( k = i+1 ; k<n1 ; k++ ) if ( max < fabs ( C[ k ][ i ] ) ) { m1 = k; max = fabs ( C[ k ][ i ] ); } if ( m1 != i ) { d = -d; for ( j = i+1 ; j<n1 ; j++ ) { c = C[ i ][ j ]; C[ i ][ j ] = C[m1][ j ]; C[m1][ j ] = c; /* doi hang i va hang m1 */ } } if ( m1==i ) { done = 1; printf("\n Ma tran la suy bien!\n"); d= 0 ; } } + Nếu phần tử trên đường chéo chính khác không thì ta tiến hành làm như sau : +1 Chia tất cả các phần tử ở hàng thứ i cho C[ i ][ i ] . Để đơn giản ta đặt c = C[ i ][ i ] sau đó nhân các phần tử còn lại ở hàng thứ i với c. Cho (i+1<j<n1) thì C[ i ][ j ] = C[ i ][ j ]*c; +2 Tiến hành khử hàng :Ta dùng biến trung gian k ( k chạy từ i+1 tới n1 ) sau đó tiến hành khử hàng thứ k theo quy tắc hình chữ nhật C[ k ][ j ] = C[ k ][ j ] - C[ i ][ j ] * C[ k ][ i ] Và cho tất cả các phần tử ở cột thứ i bằng 0 tức là : C[ k ][ i ] = 0 Minh họa như sau If ( C[ i ][ i ] != 0) { c=1/C[ i ][ i ]; for( j = i+1 ; j<n1 ; j++ ) C[ i ] [j ] = C[ i ][ j ] * c; for( k = i+1 ; k<n1 ; k++) { for ( j = i+1 ; j<n1 ; j++ ) C[ k ][ j ] = C[ k ][ j ] - C[ i ][ j ] * C[ k ][ i ]; C[ k ][ i ] = 0; } Sau đó cho i tăng :Nếu ( i>=n1 ) thì cho i chạy từ 0 tới n1 và định thức lúc này chính là tích của các phần tử trên đường chéo chính tức là : d = d * C[ i ][ i ] Ta minh họa như sau If ( i>= n1 ) { for ( i=0 ; i<n1 ; i++ ) d = d * C[ i ][ i ]; printf ( “ \ n Dinh thuc cua ma tran = %8.3 f \ n " , d ); } Sau khi đã tính được định thức của ma trận ta đi tìm hạng của ma trận này. Trước hết ta khai báo một kiểu boolean : enum BOOLEAN {false=0,true} t1; Như ta đã biết hạng của ma trận dạng bậc thang bằng số hàng khác không của nó và theo cách tính định thức trên thì ta đã biến đổi ma trận C[n1][n1] thành dạng bậc thang nên ta sẽ tim hạng thông qua số hàng khác không của ma trận hình thang này : Đặt t1 lúc đầu là true tức là các phần tử hàng khác không và gán i = n1-1 Trong khi xảy ra ( t1 ) thì sau đó ta làm như sau : Cho j chạy từ i đến n1. Để cho tiện ta đặt một biến trung gian tg = C[ i ][ j ] Nếu t1 = false ( các phần tử trên hàng i bằng không ) thi ta tiến hành giảm i xuống và cứ như thế kiểm tra đến khi nào t1=true.và hạng ma trận là : i+2 ( do ban đầu ta gán i = n1-1 va sau đó lại giảm i nên hạng ma trận là i+2 ) Ta minh họa như sau : t1 = true; i = n1-1; do { for(j=i;j<n1;j++) { tg=C[i][j]; if(tg) t1=false; } i--; } while(t1); printf("\n Hang ma tran=%d",i+2); CHƯƠNG III : MÃ NGUỒN #include #include #include #include #define UP 72 #define DOWN 80 #define ENTER 28 typedef double mt [20][20]; const int a=9; const int x=20; const int y=12; const int w=40; const int donvi_h=1; const char*title[]={ "1.Nhap ma tran", "2.Ma tran ngau nhien", "3.Ma tran doc tu file", "4.Tong hai ma tran", "5.Hieu hai ma tran", "6.Tich hai ma tran", "7.Dinh thuc va hang ma tran", "8.Hien thi file", "9.Exit" }; int _exit=0; int m , n , n1 , p , q , k , i , j , aij , bij , cij , m1 ; mt A,B,C,D,E,F; FILE*stream; char msg[25]; float t,tg; enum BOOLEAN {false=0,true} t1; /*******************************************/ void nhapmatran() { clrscr(); stream=fopen("C:\\output.txt","w"); printf("\n vao so hang m, so cot n cua ma tran A\n"); fprintf(stream,"\n vao so hang m, so cot n cua ma tran A\n"); printf("m="); fprintf(stream,"m="); scanf("%d",&m); fprintf(stream,"%d",m); printf("n="); fprintf(stream," n="); scanf("%d",&n); fprintf(stream,"%d",n); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { printf("\n A[%d][%d]=",i,j); fprintf(stream,"\n A[%d][%d]=",i,j); scanf("%f", &t); fprintf(stream,"%f",t); A[i][j]=t; } printf("\n\r"); printf("\n vao so hang p, so cot q cua ma tran B\n"); fprintf(stream,"\n vao so hang p, so cot q cua ma tran B\n"); printf("p="); fprintf(stream,"p="); scanf("%d",&p); fprintf(stream,"%d",p); printf("q="); fprintf(stream," q="); scanf("%d",&q); fprintf(stream,"%d",q); for(i=1;i<=p;i++) for(j=1;j<=q;j++) { printf("\n B[%d][%d]=",i,j); fprintf(stream,"\n B[%d][%d]=",i,j); scanf("%f",&t); fprintf(stream,"%f",t); B[i][j]=t; } printf("\n\r"); printf("\n vao cap cua ma tran vuong C\n"); fprintf(stream,"\n vao cap cua ma tran vuong C\n"); printf("n1="); fprintf(stream,"n1="); scanf("%d",&n1); fprintf(stream,"%d",n1); for(i=0;i<n1;i++) for(j=0;j<n1;j++) { printf("\n C[%d][%d]=",i,j); fprintf(stream,"\n C[%d][%d]=",i,j); scanf("%f",&t); fprintf(stream,"%f",t); C[i][j]=t; } printf("\n\r"); printf("Ma tran A\n"); fprintf(stream,"\n Ma tran A\n"); printf(" %d %d",m,n); fprintf(stream," %d %d",m,n); for(i=1;i<=m;i++) { printf("\n"); fprintf(stream,"\n"); for(j=1;j<=n;j++) { printf("%10.4f",A[i][j]); fprintf(stream,"%10.4f",A[i][j]); } } printf("\n\n\r"); printf("Ma tran B\n"); fprintf(stream,"\n Ma tran B\n"); printf(" %d %d",p,q); fprintf(stream," %d %d",p,q); for(i=1;i<=p;i++) { printf("\n"); fprintf(stream,"\n"); for(j=1;j<=q;j++) { printf("%10.4f",B[i][j]); fprintf(stream,"%10.4f",B[i][j]); } } printf("\n\n\r"); printf("Ma tran C\n"); fprintf(stream,"\n Ma tran C\n"); printf(" %d %d",n1,n1); fprintf(stream," %d %d",n1,n1); for(i=0;i<n1;i++) { printf("\n"); fprintf(stream,"\n"); for(j=0;j<n1;j++) { printf("% 10.4f",C[i][j]); fprintf(stream,"% 10.4f",C[i][j]); } } printf("\n\n\r"); fclose(stream); printf("\n\r NHAP MA TRAN THANH CONG .PRESS...") ; getch(); } /**************************************************/ void matranngaunhien() { clrscr(); stream=fopen("C:\\output.txt","a"); printf("\n vao so hang m, so cot n cua ma tran A\n"); fprintf(stream,"\n vao so hang m, so cot n cua ma tran A\n"); printf("m="); fprintf(stream,"m="); scanf("%d",&m); fprintf(stream,"%d",m); printf(" n="); fprintf(stream," n="); scanf("%d",&n); fprintf(stream,"%d",n); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { A[i][j]=rand(); } printf("\n vao so hang p, so cot q cua ma tran B\n"); fprintf(stream,"\n vao so hang p, so cot q cua ma tran B\n"); printf("p="); fprintf(stream,"p="); scanf("%d",&p); fprintf(stream,"%d",p); printf(" q="); fprintf(stream," q="); scanf("%d",&q); fprintf(stream,"%d",q); for(i=1;i<=p;i++) for(j=1;j<=q;j++) { B[i][j]=rand(); } cprintf("\n\r"); printf("\n Vao cap cua ma tran C\n"); fprintf(stream,"\n Vao cap cua ma tran C\n"); printf("n1="); fprintf(stream,"n1="); scanf("%d",&n1); fprintf(stream,"%d",n1); for(i=1;i<=n1;i++) for(j=1;j<=n1;j++) { C[i][j]=rand(); } cprintf("\n\r"); printf("\n Ma tran A\n"); fprintf(stream,"\n Ma tran A\n"); printf(" %d %d",m,n); fprintf(stream," %d %d",m,n); for(i=1;i<=m;i++) { printf("\n"); fprintf(stream,"\n"); for(j=1;j<=n;j++) { printf("%10.3f",A[i][j]); fprintf(stream,"%10.3f",A[i][j]); } } printf("\n\n\r"); printf("\n Ma tran B\n"); fprintf(stream,"\n Ma tran B\n"); printf(" %d %d",p,q); fprintf(stream," %d %d",p,q); for(i=1;i<=p;i++) { printf("\n"); fprintf(stream,"\n"); for(j=1;j<=q;j++) { printf("%10.3f",B[i][j]); fprintf(stream,"%10.3f",B[i][j]); } } printf("\n\n\r"); printf("\n Ma tran C\n"); fprintf(stream,"\n Ma tran C\n"); printf(" %d %d",n1,n1); fprintf(stream," %d %d",n1,n1); for(i=1;i<=n1;i++) { printf("\n"); fprintf(stream,"\n"); for(j=1;j<=n1;j++) { printf("%10.3f",C[i][j]); fprintf(stream,"%10.3f",C[i][j]); } } fclose(stream); } /**********************************************/ void doctufile() { clrscr(); /* open file for update */ stream=fopen("C:\\Input.txt","r"); /* read m string from the file */ fgets(msg,25,stream); m=atoi(msg); /* atoi chuyen ky tu thanh so */ printf(" m=%d",m); fprintf(stream," m=%d",m); /* read n string from the file */ fgets(msg,25,stream); n=atoi(msg); printf(" n=%d\n",n); /* display the string */ for(i=1;i<=m;i++) { for (j=1;j<=n;j++) { fgets(msg,25,stream); aij=atoi(msg); printf("A[%d][%d]=%d ",i,j,aij); } printf("\n\r"); } printf("\n"); /* read p string from the file */ fgets(msg,25,stream); p=atoi(msg); /* atoi chuyen ky tu thanh so */ printf(" p=%d",p); /* read q string from the file */ fgets(msg,25,stream); q=atoi(msg); printf(" q=%d\n",q); /* display the string */ for(i=1;i<=p;i++) { for (j=1;j<=q;j++) { fgets(msg,25,stream); bij=atoi(msg); printf("B[%d][%d]=%d ",i,j,bij); } printf("\n\r"); } printf("\n"); /* read n1 string from the file */ fgets(msg,25,stream); n1=atoi(msg); /* atoi chuyen ky tu thanh so */ printf(" n1=%d\n\r",n1); /* display the string */ for(i=1;i<=n1;i++) { for (j=1;j<=n1;j++) { fgets(msg,25,stream); cij=atoi(msg); printf("C[%d][%d]=%d ",i,j,cij); } printf("\n\r"); } fclose(stream); printf("\n\r Nhap xong.PRESS..."); getch(); } /**********************************************/ void tong() { clrscr(); /* open a file for update */ stream=fopen("C:\\output.txt","a"); printf("\n tong hai ma tran\n"); fprintf(stream,"\n tong hai ma tran\n"); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { E[i][j]=A[i][j]+B[i][j]; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { printf("%10.4f",E[i][j]); fprintf(stream,"%10.4f",E[i][j]); } printf("\n"); fprintf(stream,"\n"); } fclose(stream); } /************************************************/ void hieu() { clrscr(); /* open a file for update */ stream=fopen("C:\\output.txt","a"); printf("\n hieu hai ma tran\n"); fprintf(stream,"\n hieu hai ma tran\n"); for(i=1;i<=m;i++) for(j=1;j<=n;j++) { F[i][j] = A[i][j]-B[i][j]; } for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { cprintf("%12.4f",F[i][j]); fprintf(stream,"%12.4f",F[i][j]); } printf("\n"); fprintf(stream,"\n"); } fclose(stream); } /************************************************/ void tich() { clrscr(); /* open a file for update */ stream=fopen("C:\\output.txt","a"); printf("\n tich hai ma tran\n"); fprintf(stream,"\n tich hai ma tran\n"); for(i=1;i<=m;i++) for(j=1;j<=q;j++) { D[i][j]=0; for(k=1;k<=n;k++) D[i][j]+=A[i][k]*B[k][j]; } for(i=1;i<=m;i++) { for(j=1;j<=q;j++) { printf("%15.3f",D[i][j]); fprintf(stream,"%15.3f",D[i][j]); } printf("\n"); fprintf(stream,"\n"); } fclose(stream); } /*************************************************/ void dinhthuc(int n1) { double i=0,done=0; float max,c, d=1; stream=fopen("C:\\output.txt","a"); printf("\n tinh dinh thuc ma tran\n"); fprintf(stream,"\n tinh dinh thuc ma tran\n"); while(!done) { if(C[i][i]==0) { max=0; m1=i; for(k=i+1;k<n1;k++) if(max<fabs(C[k][i])) { m1=k; max=fabs(C[k][i]); } if(m1!=i) { d=-d; for(j=i+1;j<n1;j++) { c=C[i][j]; C[i][j]=C[m1][j]; C[m1][j]=c; /* doi hang i va hang m1 */ } } if(m1==i) { done=1; printf("\n Ma tran la suy bien!\n"); fprintf(stream,"\n Ma tran la suy bien!\n"); d=0; } } if(C[i][i]!=0) { c=1/C[i][i]; for(j=i+1;j<n1;j++) C[i][j]=C[i][j]*c; for(k=i+1;k<n1;k++) { for(j=i+1;j<n1;j++) C[k][j]=C[k][j]-C[i][j]*C[k][i]; C[k][i]=0; } } printf("\n lan khu hang %d",i); fprintf(stream,"\n lan khu hang %d",i); for(k=0;k<n1;k++) { printf("\n"); fprintf(stream,"\n"); for(j=0;j<n1;j++) { printf("%10.4f",C[k][j]); fprintf(stream,"%10.4f",C[k][j]); } } i++; if(i>=n1) done=1; } if(i>=n1) { for(i=0;i<n1;i++) d=d*C[i][i]; printf("\n Dinh thuc cua ma tran=%-10.4f\n",d); fprintf(stream,"\n Dinh thuc cua ma tran=%-10.4f\n",d); } fclose(stream); } /**********************************************/ void HANG() { stream=fopen("C:\\output.txt","a"); t1=true; i=n1-1; do { for(j=i;j<n1;j++) { tg=C[i][j]; if(tg) t1=false; } i--; } while(t1); printf("\n Hang ma tran=%d",i+2); fprintf(stream,"\n Hang ma tran=%d",i+2); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); fprintf(stream,"\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); getch(); fclose(stream); } /**********************************************/ void tongmatran(void) { stream=fopen("C:\\output.txt","a"); if((m==p)&&(n==q)) { tong(); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); } else { printf("\n\n\n khong ton tai tong !"); fprintf(stream,"\n\n\n khong ton tai tong !"); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); } getch(); fclose(stream); } /********************************************/ void hieumatran(void) { stream=fopen("C:\\output.txt","a"); if((m==p)&&(n==q)) { hieu(); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); } else { printf("\n\n\n khong ton tai hieu !"); fprintf(stream,"\n\n\n khong ton tai hieu !"); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); } getch(); fclose(stream); } /*********************************************/ void tichmatran(void) { stream=fopen("C:\\output.txt","a"); if(n==p) { tich(); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); } else { printf("\n\n\n khong ton tai tich !"); fprintf(stream,"\n\n\n khong ton tai tich !"); printf("\n BAM PHIM BAT KY DE TRO RA ! PRESS..."); } getch(); fclose(stream); } /***********************************************/ void dinhthucvahangmatran() { clrscr(); stream=fopen("C:\\output.txt","a"); dinhthuc(n1); HANG(); getch(); fclose(stream); } /***********************************************/ void hienthifile() { FILE*f; char str[255]; int l=0; f=fopen("C:\\output.txt","rt"); while(!feof(f)) { fgets(str,255,f); printf("\n\r%s",str); l=l+1; if(l % 1==0) { getch(); } } fclose(f); getch(); } /**********************************************/ void Window(int x, int y, int w, int h, int color) { textbackground(color); window(x,y, x + w, y + h); clrscr(); } /*********************************************/ void Interface() { Window(1, 1, 79, 24, GREEN); textcolor(RED); gotoxy(23,2); cprintf("TRUONG DAI HOC BACH KHOA HA NOI"); gotoxy(28,3); cprintf("KHOA TOAN TIN UNG DUNG"); gotoxy(31,4); cprintf("---*---*---*---"); gotoxy(18,6); cprintf("CAC PHEP TOAN THUC HIEN TREN MA TRAN THUC"); gotoxy(15,8); cprintf("Sinh vien thuc hien : BUI VAN BANG"); gotoxy(15,9); cprintf("MSSV : 20030180 "); gotoxy(15,10); cprintf("Lop : TOAN TIN_2 -K48"); gotoxy(32,25); cprintf("HA NOI-2006"); } /**********************************************/ void Menu() { int h=donvi_h*a +2; Window(x,y,w, h, BLACK); } /**********************************************/ void Tao_Menu(int chon) { int h = donvi_h*a + 2; Window(x, y, w, h, CYAN); for(i = 0; i< a; i++) { if(i == chon) { textcolor(RED); } else { textcolor(WHITE); } gotoxy(5, 2+i); cprintf("%s\r\n",title[i]); } } /*************************************************/ void ham1(void) { clrscr(); Window(1,1,79,24,CYAN); nhapmatran(); getch(); Interface(); Menu(); } /************************************************/ void ham2(void) { clrscr(); Window(1,1,79,24,CYAN); matranngaunhien(); getch(); Interface(); Menu(); } /***********************************************/ void ham3(void) { clrscr(); Window(1,1,79,24,CYAN); doctufile(); getch(); Interface(); Menu(); } /**********************************************/ void ham4(void) { clrscr(); Window(1,1,79,24,CYAN); tongmatran(); getch(); Interface(); Menu(); } /***********************************************/ void ham5(void) { clrscr(); Window(1,1,79,24,CYAN); hieumatran(); getch(); Interface(); Menu(); } /**********************************************/ void ham6(void) { clrscr(); Window(1,1,79,24,CYAN); tichmatran(); getch(); Interface(); Menu(); } /**********************************************/ void ham7(void) { clrscr(); Window(1,1,79,24,CYAN); dinhthucvahangmatran(); getch(); Interface(); Menu(); } /**********************************************/ void ham8(void) { clrscr(); Window(1,1,79,24,CYAN); hienthifile(); getch(); Interface(); Menu(); } /*************************************************/ void Key(int pos) { switch(pos) { case 0: ham1(); break; case 1: ham2(); break; case 2: ham3(); break; case 3: ham4(); break; case 4: ham5(); break; case 5: ham6(); break; case 6: ham7(); break; case 7: ham8(); break; case 8: _exit = 1; break; } } /***************************************************/ int ReadKey() { int key; while (bioskey(1) == 0); key = bioskey(0)>>8; return key; } /***************************************************/ int main(void) { int i, j = 0; char ch; textmode(C80); Interface(); Menu(); while(!_exit) { Tao_Menu(j); i = ReadKey(); switch(i) { case UP: j--; if(j==-1) { j = 8; } break; case DOWN: j++; if(j==9) { j=0 ; } break; case ENTER: Key(j); break; } } return 0; } /***********************THE_END********************/ CHƯƠNG IV : ĐÁNH GIÁ THUẬT TOÁN VÀ CHƯƠNG TRÌNH I . ĐÁNH GIÁ THUẬT TOÁN Trong chương trinh ta có sử dụng thuật toán là : duyệt tuần tự các phần tử trên đường chéo chính của ma trận C và khi tính hạng ta cũng sử dụng phương pháp duyệt để tìm các hàng khác không. Ta đánh giá độ phức tạp tính toán như sau : 1.1 Duyệt các phần tử trên đường chéo chính. Đối với giải thuật này chính là phép di chuyển con trỏ dùng để duyệt và so sánh với 0 .Nếu tìm được phần tử bằng không thì thuật toán dừng và kết luận . Do duyệt tuần tự nên số phép dịch chuyển bằng số phép so sánh . Giả sử ma trận là cấp n thì sẽ có n lần duyệt danh sách : + Trong trường hợp tốt nhất :( phần tử đầu tiên C[ 1 ][ 1 ] = 0 ) Tại bất cứ lần duyệt nào cũng chỉ làm một phép so sánh. Độ phức tạp tính toán trong trường hợp này là : T(n) = O(1). + Trong trường hợp xấu nhất :(duyệt đến tận phần tử cuối C[ n ][ n ]=0) Tổng số phép so sánh :n Độ phức tạp tính toán : T(n) = O(n) + Trong trường hợp trung bình : ( Coi các phần tử có xác suất xuất hiện là số không tại các vị trí là như nhau ) Tức là số phép so sánh trung bình lúc này là n/2. Độ phức tạp tính toán là : T(n) = O(n) 1.2 Phương pháp duyệt từng hàng để tìm hạng Số bước duyệt trong giải thuật này phụ thuộc vào ma trận được nhập.Quá trình duyệt là xuất phát từ phần tử A[ n ][ n ].( giả sử ma trận cấp n) + Trong trường hợp tốt nhất :( phần tử đầu tiên C[ n ][ n ] = 0 ) Ta chỉ cần làm một phép so sánh. Độ phức tạp tính toán trong trường hợp này là : T(n) = O(1). + Trong trường hợp xấu nhất : (ta phải duyệt đến hàng đầu tiên của ma trận ) Tại lần duyệt thứ i cần làm i phép so sánh. Tổng số lượng phép so sánh : = Độ phức tạp tính toán là : T(n) = O(n) + Trong trường hợp trung bình :( Các phần tử có xác suất xuất hiện tại các vị trí là như nhau như vậy tại bước thứ i cần so sánh i/2 lần Tổng số phép so sánh là : = Độ phức tạp tính toán là : T(n) = O(n) II . ĐÁNH GIÁ CHƯƠNG TRÌNH Chương trình đã giải quyết được các vấn đề mà đề tài yêu cầu, tạo được giao diện để sử dụng và cho phép sử dụng nhiều dạng dữ liệu để đánh giá chương trình một cách toàn diện. Sau khi cho chạy thử với bộ dữ liệu đầu vào khác nhau thì thu được một số đánh giá sau : Tốc độ : Ma trận nhập vào với kích thước lớn ( <=.15 ) thì việc tính toán cộng , trừ nhân hai ma trận là không lâu lắm .Tốc độ tính toán trong giải thuật tính định thức và tìm hạng của ma trận với kích thước nhỏ là không lâu lắm.Tuy nhiên việc hiển thị ra file trên fỏm của C thì phải tiến hành cắt các trường thông tin nên hiển thị file chậm hơn so với Pascal. Điều này không phải do giải thuật mà do việc xử lý trên file text. Độ tin cậy : Chương trình cho kết quả đúng với nhiều dữ liệu đầu vào khác nhau nhưng chỉ với các ma trận có kích thước (<=15).Tuy nhiên với ma trận có kích thước lớn thì em chưa xử lý được. Trong quá trình tính định thức của ma trận vuông thì việc tính toán cũng chỉ áp dụng được với các ma trận có kích thước nhỏ(<=7),nếu ma trận có kích thước lớn thì tính toán sẽ gặp sai số và ảnh hưởng đến kết quả cũng như hạng của ma trận Lời tựa : Trong quá trình làm đề tài này dù em đã cố gắng rất nhiều nhưng cũng không thể tránh khỏi những thiếu xót và một số vấn đề chưa giải quyết được .Em rất mong sự giúp đỡ của cô giáo để hoàn thiện chương trình này hơn. TÀI LIỆU THAM KHẢO Giáo trình Phương pháp tính ( Tác giả : Dương Thùy Vĩ ) Giải tích số ( Tác giả : Lê Trọng Vinh ) Toán cao cấp - Tập 1 ( Đại số và hình giải tích ) Tác giả : Nguyễn Đình Trí ( chủ biên) Tạ Văn Đĩnh- Nguyễn Hồ Quỳnh