1. Bài tập thuật toán tìm kiếm tuyến tính bằng ngôn ngữ lập trình C
Yêu cầu của bài toán là tìm kiếm vị trí xuất hiện của một phần tử có trong mảng số nguyên bằng thuật toán tìm kiếm tuyến tính trong ngôn ngữ lập trình 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 tuyến tính 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 và cách dùng thuật toán tìm kiếm tuyến tính trong C.
Ý tưởng của thuật toán tìm kiếm tuyến tính như sau:
- So sánh phần tử x cần tìm lần lượt với phần tử thứ 1, thứ 2,…thứ n của mảng a cho đến khi gặp được khóa cần tìm, hoặc tìm hết mảng mà không thấy.
Các bước thực hiện yêu cầu của bài tập tìm kiếm vị trí xuất hiện của một phần tử có trong mảng số nguyên bằng thuật toán tìm kiếm tuyến tính trong ngôn ngữ lập trình C như sau:
Bước 1: Ta khỏi tạo hàm Nhap(int a[],int n) dùng để nhập dữ liệu cho mảng. 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 và mỗi lần lặp i tăng lên 1. Trong vòng lặp ta nhập dữ liệu từ bàn phím cho từng phần tử a[i].
Bước 2: Ta khỏi tạo hàm Xuat(int a[],int n) dùng để hiển thị mảng ra màn hình. 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 và mỗi lần lặp i tăng lên 1. Trong vòng lặp ta hiển thị từng phần tử a[i] ra màn hình.
Bước 3: Ta khởi tạo hàm int LinearSearch(int a[],int n,int x) dùng để tìm kiếm vị trí của x trong mảng bằng thuật toán tìm kiếm tuyến tính Linear Search. 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 và mỗi lần lặp i tăng lên 1 dùng để duyệt qua tất cả các phần tử trong mảng; trong vòng lặp ta dùng if với điều kiện a[i]==x nếu thỏa mãn thì trả về i (tìm thấy vị trí của x). Kết thúc lặp ta trả về -1(không tìm thấy x).
Bước 4: Trong hàm main ta khởi tạo mảng tĩnh số nguyên int a[100](có tối đa 100 phần tử), int n và nhận dữ liệu cho biến int n là số phần tử của mảng.
Bước 5: Gọi hàm Nhap(a,n), Xuat(a,n) để hiển nhập và thị mảng vừa nhập.
Bước 6: Khai báo biến int x và nhập dữ liệu cho x (là biến cần tìm). Ta dùng if với điều kiện nếu LinearSearch(a,n,x)==-1 thì thông báo không tìm thấy x; ngược lại hiển thị vị trí của x là LinearSearch(a,n,x) ra màn hình.
Bước 7: Chạy chương trình.
Chương trình giải bài tập tìm kiếm vị trí xuất hiện của một phần tử có trong mảng số nguyên bằng thuật toán tìm kiếm tuyến tính trong ngôn ngữ lập trình C như sau:
#include <stdio.h>
void Nhap(int a[],int n){//ham nhap mang
for(int i=0; i<n; i++){
printf("\nNhap a[%d]=",i);
scanf("%d",&a[i]);
}
}
void Xuat(int a[],int n){//ham xuat mang
for(int i=0; i<n; i++){
printf("%d \t",a[i]);
}
}
int LinearSearch(int a[], int n, int x){//thuat toan tim kiem tuyen tinh
for(int i=0; i<n; i++){
if(a[i]==x){//duyet tung phan tu neu a[i]==x thi tra ve vi tri i
return i;
}
}
return -1;//khong tim thay x
}
int main(){
int a[100];
int n;// so phan tu cua mang
printf("Nhap so phan tu:");
scanf("%d",&n);
Nhap(a,n);
printf("\nMang sau khi nhap la:\n");
Xuat(a,n);
int x;//phan tu x can tim
printf("\nNhap phan tu can tim:");
scanf("%d",&x);
if(LinearSearch(a,n,x)==-1){
printf("Khong tim thay %d trong mang!",x);
}else{
printf("\nVi tri cua %d trong mang la: %d",x, LinearSearch(a,n,x));
}
}
Ví dụ tôi nhập mảng có 5 phần tử: 9,1,4,3,2 và x cần tìm là: 3
Kết quả:
Nhap so phan tu:5 Nhap a[0]=9 Nhap a[1]=1 Nhap a[2]=4 Nhap a[3]=3 Nhap a[4]=2 Mang sau khi nhap la: 9 1 4 3 2 Nhap phan tu can tim:3 Vi tri cua 3 trong mang la: 3
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 vòng lặp để duyệt thông tin của từng phần tử trong C.
- Cách sử dụng thật toán tìm kiếm tuyến tính (Linear Search) trong C.
