1. Bài tập thuật toán tìm kiếm nhị phân bằng ngôn ngữ lập trình C
Bài tập: Một sinh viên gốm thuộc tính là: mã sinh viên(MaSV), tên sinh viên(TenSV), lớp(Lop) và điểm tổng kết(DTK). Yêu cầu của bài tập là hiển thị tất cả các sinh viên có cùng số điểm là x ra màn hình bằng thuật toán tìm kiếm nhị phân trong C.
Đối với bài tập này chúng ta sẽ sử dụng các kiến thức như sau: nhập và xuất dữ liệu cơ bàn trong ngôn ngữ lập trình C, cách sử dụng mảng trong ngôn ngữ lập trinh C, cách sử dụng vòng lặp for để duyệt các phần tử trong mảng, cách dùng thuật toán tìm kiếm nhị phân trong C và các thuật toán sắp xếp trong C.
2. Lời giải
Để thực hiện bài toán này chúng ta cần có kiến thức cơ bản về ngôn ngữ lập trình C, nhập xuất dữ liệu cơ bàn trong ngôn ngữ lập trình C, cách sử dụng mảng trong ngôn ngữ lập trinh C, cách sử dụng vòng lặp for để duyệt các phần tử trong mảng, cách dùng thuật toán tìm kiếm nhị phân trong C và các thuật toán sắp xếp trong C.
Ý tưởng của thuật toán tìm kiếm nhị phân như sau:
- Thuật toán tìm kiếm nhị phân dựa trên phương pháp chia để trị để tìm kiếm phần tử.
- Giả xử ta xét mảng có thứ tự tăng, khi ấy ta có ai-1<ai<ai+1.
- Nếu x>ai thì x chỉ có thể xuất hiện trong đoạn [ai+1 , an-1 ].
- Nếu x<ai thì x chỉ có thể xuất hiện trong đoạn [a0 , ai-1 ].
- Ý tưởng của giải thuật là tại mỗi bước ta so sánh x với phần tử đứng giữa trong dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này mà ta quyết định giới hạn dãy tìm kiếm ở nữa dưới hay nữa trên của dãy tìm kiếm hiện hành.
Lưu ý: Thuật toán tìm kiếm tuyến tính chỉ áp dụng được với các dãy đã được sắp xếp.
Các bước thực hiện yêu cầu của bài tập hiển thị tất cả các sinh viên có cùng số điểm là x ra màn hình bằng thuật toán tìm kiếm nhị phân trong C như sau:
Bước 1: Ta khai báo một cấu trúc struct SinhVien gồm có: int MaSV(mã sinh viên); char TenSV[50](tên sinh viên); char Lop[50](lớp); float DTK(điểm tổng kết).
Bước 2: Ta khỏi tạo hàm void Nhap(SinhVien sv[], int n) dùng để nhập dữ liệu từ bàn phím thông tin của sinh viên. Trong hàm ta sử dụng vòng for bắt đầu từ int i=0, kết thúc khi i<n và mỗi lần i tăng lên 1 để nhập dữ liệu cho từng sinh viên từ sv[0] đến sv[n-1], trong vòng for thì nhập vào dữ liệu của sinh viên.
Bước 3: Ta khởi tạo hàm void Xuat(SinhVien sv[], int n) dùng để hiển thị dữ liệu của sinh viên ra màn hình. Trong hàm ta sử dụng vòng for bắt đầu từ int i=0, kết thúc khi i<n và mỗi lần i tăng lên một để hiển thị dữ liệu của từng sinh viên từ sv[0] đến sv[n-1] ra màn hình, trong vòng for in dữ liệu của sinh viên ra màn hình.
Bước 4: Ta khỏi tạo hàm void BubleSort(SinhVien sv[], int n) dùng để sắp xếp thứ tự các sinh viên theo điểm bằng thật toán nổi bọt – Buble Sort bạn cũng có thể sử dụng các thuật toán sắp xếp khác(vì thuật toán tìm kiếm chỉ sử dụng được với các dãy đã sắp xếp). Trong hàm ta dùng vòng lặp for bắt đầu từ int i=0, kết thúc khi i<n-1 và mỗi lần lặp i tăng lên 1. Trong vòng lặp for i ta dùng vòng lặp for bắt đầu từ int j=n-1, kết thúc khi j>i và mỗi lần lặp j giảm đi 1 (duyệt từ cuối mảng về vị trí thứ i thỏa mãn j>i). Trong vòng for j ta dùng if với điều kiện nếu a[j]<a[j-1] thỏa mãn thì đổi chỗ a[j] cho a[j-1] qua biến int tg. Kết thúc lặp ta gọi hàm Xuat(a,n) để hiển thị mảng đã sắp xếp ra màn hình.
Bước 5: Ta khởi tạo hàm int BinarySearch(SinhVien sv[], int n, int x) dùng để tìm kiếm vị trí của sinh viên có điểm là x muốn tìm bằng thuật toán tìm kiếm nhị phân – Binary Search. Trong hàm ta khai báo biến int left=0, right=n-1 là điểm bắt đầu và kết thúc của dãy sinh viên và biến int mid là biến dùng để gán vị trí giữa của mảng. Tiếp theo ta dùng vòng lặp do while với điều kiện left<=right (nếu còn phần tử trong dãy hiện hành); trong đó ta gán mid=(left+right)/2 và dùng if với điều kiện sv[mid].DTK==x thoản mãn thì trả về vị trí mid ngược lại nếu sv[mid].DTK < x thì ta gán left = mid + 1 ngược lại ta gán right = mid-1. Kết thúc lặp ta trả về -1(Không tìm thấy sinh viên có điểm là x).
Bước 6: Ta khởi tạo hàm void HienThi(SinhVien sv[], int n, int x) dùng để hiển thị các sinh viên có điểm là x ra màn hình. Trong hàm ta khai báo biến int pos = BinarySearch(sv,n,x) và dùng if với điều kiện nếu pos==-1 thỏa mãn thì in ra màn hình không có sinh viên cần tìm; ngược lại ta khai báo biến int t=pos cùng với vòng while với điều kiện t>=0 && sv[t].DTK==x nếu đúng ta in thông tin của sinh viên thứ t ra màn hình và giảm t đi 1 (tìm kếm ở bên trái vị trí pos). Tương tự để tìm kiếm ở vị trí bên phải pos ta khai báo biến int p=pos+1 cùng với vòng lặp while với điều kiện p<=n-1 && sv[p].DTK==x nếu đúng ta in thông tin của sinh viên thứ p ra màn hình và tăng p lên 1.
Bước 7: Trong hàm main ta khởi tạo biến SinhVien sv[100] (mảng sv kiểu dữ liệu SinhVien có tối đa 100 phần tử), biến int n (số lượng sinh viên) và nhập dữ liệu từ bàn phím và cho n.
Bước 8: Ta gọi hàm Nhap(sv,n), Xuat(sv,n) và BubleSort(sv,n) để hiển thị danh sách sinh viên ra màn hình.
Bước 9: Khai báo biến float x là điểm cần tìm và nhập dữ liệu vào cho x và gọi hàm HienThi(sv,n,x) để hiển thị sinh viên có điểm là x cần tìm.
Bước 10: Chạy chương trình.
Chương trình giải bài tập hiển thị tất cả các sinh viên có cùng số điểm là x ra màn hình bằng thuật toán tìm kiếm nhị phân trong C như sau:
#include <stdio.h>
struct SinhVien{
char MaSV[50];
char TenSV[50];
char Lop[50];
float DTK;
};
void Nhap(SinhVien sv[], int n){// ham nhap thong tin sinh vien
for(int i=0; i<n; i++){
printf("\nNhap thong tin sinh vien thu %d:",i);
printf("\nNhap ma sinh vien:");
fflush(stdin);//xoa bo dem
gets(sv[i].MaSV);
printf("\nNhap ten sinh vien:");
fflush(stdin);//xoa bo dem
gets(sv[i].TenSV);
printf("\nNhap lop:");
fflush(stdin);//xoa bo dem
gets(sv[i].Lop);
printf("\nNhap diem tong ket:");
scanf("%f", &sv[i].DTK);
}
}
void Xuat(SinhVien sv[], int n){//ham hien thi thong tin sinh vien
printf("\n-----THONG TIN SINH VIEN----\n");
printf("MaSV \t TenSv \t\t Lop \t DTK \n");
for(int i=0; i<n; i++){
printf("%s \t %s \t %s \t %f \n",sv[i].MaSV, sv[i].TenSV,sv[i].Lop,sv[i].DTK);
}
}
void BubleSort(SinhVien sv[], int n){//thuat toan sap xep noi bot
for(int i=0;i<n-1;i++){
for(int j=n-1;j>i;j--){
if(sv[j].DTK<sv[j-1].DTK){
SinhVien tg = sv[j];
sv[j]=sv[j-1];
sv[j-1]=tg;
}
}
}
printf("\n-----Danh sach sinh vien sau khi sap xep la----\n");
Xuat(sv,n);
}
int BinarySearch(SinhVien sv[], int n, int x){//thuat toan tim kiem nhi phan
int left=0, right=n-1;// left = 0 la vi tri dau mang, right = n-1 la vi tri cuoi mang
int mid;//phan tu dung de gan vi tri giua mang
do{
mid=(left+right)/2;
if (sv[mid].DTK==x)//neu vi tri giua mang co DTK = x thi tra ve mid
return mid;
else if (sv[mid].DTK < x)//neu neu vi tri giua mang co DTK < x thì left = mid + 1
left = mid + 1;
else
right = mid-1;//neu neu vi tri giua mang co DTK > x thì right = mid-1
}while(left<=right);//neu con phan tu trong day hien hanh
return -1;//khong co phan tu can tim
}
void HienThi(SinhVien sv[], int n, int x)//hien thi sinh vien muon tim
{
int pos = BinarySearch(sv,n,x);
if (pos==-1)
printf("Khong co sinh vien can tim!");
else{
printf("-------------------------------");
printf("\nSinh vien co diem can tim la:\n");
//in cac vi tri ben trai cua pos neu co cung gia tri x
int t = pos;
while(t>=0 && sv[t].DTK==x){
printf("\n-------------------------------\n");
printf("\nMa sinh vien: %s",sv[t].MaSV);
printf("\nTen sinh vien: %s",sv[t].TenSV);
printf("\nLop: %s",sv[t].Lop);
printf("\nDiem tong ket: %f",sv[t].DTK);
t--;
}
//in cac vi tri ben phai cua pos neu co cung gia tri x
int p = pos+1;
while(p<=n-1 && sv[p].DTK==x){
printf("\n-------------------------------\n");
printf("\nMa sinh vien: %s",sv[p].MaSV);
printf("\nTen sinh vien: %s",sv[p].TenSV);
printf("\nLop: %s",sv[p].Lop);
printf("\nDiem tong ket: %f",sv[p].DTK);
p++;
}
}
}
int main(){
SinhVien sv[100];// khai bao mang sv kieu SinhVien co toi da 100 phan tu
int n; // khai bao so sinh vien
printf("Nhap so sinh vien:");
scanf("%d",&n);
Nhap(sv,n);
Xuat(sv,n);
BubleSort(sv,n);
float x;
printf("\nNhap diem can tim:");
scanf("%f",&x);
HienThi(sv,n,x);
}
Kết quả như sau:
Nhap so sinh vien:3 Nhap thong tin sinh vien thu 0: Nhap ma sinh vien:01 Nhap ten sinh vien:Nguyen Van A Nhap lop:CNTT1 Nhap diem tong ket:9 Nhap thong tin sinh vien thu 1: Nhap ma sinh vien:02 Nhap ten sinh vien:Dinh Van B Nhap lop:CNTT2 Nhap diem tong ket:7 Nhap thong tin sinh vien thu 2: Nhap ma sinh vien:03 Nhap ten sinh vien:Chu Minh C Nhap lop:CNTT3 Nhap diem tong ket:9 -----THONG TIN SINH VIEN---- MaSV TenSv Lop DTK 01 Nguyen Van A CNTT1 9.000000 02 Dinh Van B CNTT2 7.000000 03 Chu Minh C CNTT3 9.000000 -----Danh sach sinh vien sau khi sap xep la---- -----THONG TIN SINH VIEN---- MaSV TenSv Lop DTK 02 Dinh Van B CNTT2 7.000000 01 Nguyen Van A CNTT1 9.000000 03 Chu Minh C CNTT3 9.000000 Nhap diem can tim:9 ------------------------------- Sinh vien co diem can tim la: ------------------------------- Ma sinh vien: 01 Ten sinh vien: Nguyen Van A Lop: CNTT1 Diem tong ket: 9.000000 ------------------------------- Ma sinh vien: 03 Ten sinh vien: Chu Minh C Lop: CNTT3 Diem tong ket: 9.000000 --------------------------------
3. Tổng kết
Sau khi làm bài tập này các bạn cần phải hiểu và nắm được những kiến thức sau:
- Cách nhập xuất cơ bản trong ngôn ngữ lập trình C.
- Cách sử dụng hàm trong C.
- Cách sử dụng struct trong C.
- Cách sử dụng vòng lặp để duyệt thông tin của từng sinh viên trong C.
- Cách nhập và hiển thị thông tin sinh viên trong C.
- Cách sử dụng thuật toán sắp xếp BubleSort trong C.
- Cách sử dụng thuật toán tìm kiếm nhị phân trong C.
