Ma trận là một cấu trúc dữ liệu hai chiều gồm hàng và cột, có thể chứa các giá trị số hoặc dữ liệu khác. Khi muốn giải quyết bài toán sắp xếp các phần tử trong ma trận giảm dần theo từng cột, ta sử dụng nhiều cách sắp xếp khác nhau. Trong bài viết này, chúng ta sẽ tìm hiểu về cách sắp xếp các phần tử trong ma trận giảm dần theo từng cột ngôn ngữ lập trình c++ đơn giản nhất.
1. Bài toán
Bài 23 (TH-CSLT-06): Viết chương trình thực hiện:
a) Nhập ma trận vuông n hàng, n cột các số nguyên (n<=50),
b) Hiện ma trận đó ra màn hình
c) Tính tích hàng k, hàng k nhập từ bàn phím
d) Tìm hàng có tổng các phần tử nhỏ nhất
e) Cho biết có bao nhiêu phần tử âm
f) Sắp xếp các phần tử ma trận giảm dần theo từng cột và hiện ra màn hình ma trận mới
2. Ý tưởng
2.1 Tính tích hàng k
- Khởi tạo biến fun=1, Nhâp k từ bàn phím
- Duyệt mảng, gán biến fun = fun* a[k][j].
2.2 Tìm hàng có tổng các phần tử nhỏ nhất
- Khởi tạo biến min_sum = INT_MAX, sum=0, hang=0;
- Duyệt mảng, tính tổng của từng hàng, so sánh tổng của từng hàng với min_sum. Nếu min_sum>sum thì gán lại min_sum, lưu vị trí hàng.
- Gán lại sum=0, và tính tổng, so sánh hàng tiếp theo.
2.3 Sắp xếp các phần tử ma trận giảm dần theo từng cột và hiện ra màn hình ma trận mới
Để sắp xếp các phần tử ma trận giảm dần theo từng cột thường thì mình sẽ sử dụng thuật toán nổi bọt bubble sort. Đây là thuật toán sắp xếp đơn giản nhất tuy nhiên có độ phức tạp thời gian là O(n^2), với n là số lượng phần tử cần sắp xếp. Trong trường hợp ma trận rất lớn, thuật toán này có thể trở nên rất chậm và không hiệu quả.
Sử dụng thuật toán sắp xếp nổi bọt để sắp xếp các phần tử của cột ma trận 2 chiều kích thước nxn:
- Vòng lặp thứ nhất j duyệt qua tất cả các cột của mảng 2 chiều
- Vòng lặp thứ 2 i để duyệt các tất cả các hàng trong mảng 2 chiều
- Vòng lặp thứ 3 có biến k để duyệt qua tất cả các phần tử của cột hiện tại j. So sánh phần tử thứ a[k][j] với phần tử tiếp theo a[k+1][j], nếu phần tử a[k][j] lớn hơn a[k+1][j] thì tiến hành hoán đổi với biến tạm temp.
- Kết thúc vòng lặp, thực hiện xuất mảng ra màn hình.
3. Code
#include<iostream>
#include<iomanip>
using namespace std;
//a.Nhap mang
void nhapmang(int n, int a[][255]){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<"a["<<i<<"]["<<j<<"]= ";
cin>>a[i][j];
}
}
}
//b. Hien mang
void xuatmang(int n, int a[][255]){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<setw(5)<<a[i][j];
}
cout<<endl;
}
}
//c. Tính tích hàng k, hàng k nhập từ bàn phím.
void tinhtichhangk(int n, int a[][255]){
int k;
double fun=1;
cout<<"Nhap hang can tinh tich k: "; cin>>k;
for(int j=0;j<n;j++){
fun= fun*a[k][j];
}
cout<<" Tich hang "<<k<<" = "<<fun;
}
//d. Tim hang co tong cac phan tu nho nhat
void hangcotongnhonhat(int n, int a[][255]){
int min_sum=INT_MAX, sum=0, hang;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum += a[i][j];
}
if(sum<min_sum){
min_sum=sum;
hang=i;
}
sum=0;
}
cout<<"Hang co phan tu nho nhat la: "<<hang<<" voi tong = "<<min_sum;
}
//e) Cho biết có bao nhiêu phần tử âm
void demphantuam(int n, int a[][255]){
int dem=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]<0){
dem++;
}
}
}
cout<<"So phan tu am trong mang la: "<<dem;
}
//f) Sắp xếp các phần tử ma trận giảm dần theo từng cột và hiện ra màn hình ma trận mới
void sapxepgiamdantheocot(int n, int a[][255]){
for(int j=0;j<n;j++){
for(int i=0;i<n;i++){
for(int k=0;k<n-i-1;k++){
if(a[k][j]>a[k+1][j]){
int temp = a[k][j];
a[k][j]=a[k+1][j];
a[k+1][j]=temp;
}
}
}
}
}
int main(){
int n,a[255][255], chon;
cout<<"Nhap n: "; cin>>n;
do{
cout<<"1. Nhap mang"<<endl;
cout<<"2. Xuat mang"<<endl;
cout<<"3. Tinh tich hang k, hang k nhap vao tu ban phim"<<endl;
cout<<"4. Tim hang co tong cac phan tu nho nhat"<<endl;
cout<<"5. Cho biet co bao nhieu phan tu am"<<endl;
cout<<"6. Sap xep cac phan tu ma tran giam dan theo tung cot"<<endl;
cout<<"Lua chon: "; cin>>chon;
switch(chon){
case 1:{
nhapmang(n,a);
cout<<endl;
break;
}
case 2:{
xuatmang(n,a);
cout<<endl;
break;
}
case 3:{
tinhtichhangk(n,a);
cout<<endl;
break;
}
case 4:{
hangcotongnhonhat(n,a);
cout<<endl;
break;
}
case 5:{
demphantuam(n,a);
cout<<endl;
break;
}
case 6:{
sapxepgiamdantheocot(n,a);
xuatmang(n,a);
cout<<endl;
break;
}
default: exit(0);
}
}while(chon!=0);
}
4. Kết quả
Trên đây là một đoạn mã đơn giản để sắp xếp ma trận giảm dần theo từng cột trong ngôn ngữ C++. Cảm ơn các bạn đã tham khảo trên ttnguyen.net
