Một Số Giải Thuật Cơ Bản Phần 1 | I Like Programming

Đây là các loại bài về Cấu Trúc dữ liệu cơ bản mà mình sẽ viết chia sẽ với các bạn .Loạt bài này nói về Các giải thuật cơ bản,bao gồm:các giải thuật tìm kiếm trên mảng số và Các giải thuật sắp xếp. Chúng tar bắt đầu tìm hiểu về giải thuật tìm kiếm.(các giải thuật cài đặt trên C/C++)

I Giải thuật tìm kiếm trên mảng số  1. Tìm kiếm tuyến tính (Linear Search) 

 Ý tưởng: 

-Thuật toán tiến hành so sánh x lần lượt với các phần tử thứ 1, thứ 2,… của mảng a cho đến khi gặp phần tử có khóa cần tìm, hoặc đã tìm hết mảng mà không thấy x.

 Ví dụ: Cho dãy số sau:

5 3 6 8 9 1 2

–>Tìm phần tử có giá trị x = 9, x= 10 ??? Minh họa ví dụ 

Xét dãy số A có 7 phần tử:

5 3 6 8 9 1 2 Tìm x = 9 Tìm x = 10.Tương tự (Các bạn tự làm thử nhé)

 Cài đặt 

Mã nguồn :  int LinearSearch (int a[], int n, int x) { for(int i=0;i<n;i++) if(a[i]==x) return i;          // trả về vị trí của x trong a return - 1; // trả về -1 báo là không có x trong a }

2. Thuật toán tìm kiếm nhị phân (Binary Search)

 Ý tưởng

– Giả sử dãy số a đã có thứ tự tăng.

– Tại mỗi bước tiến hành so sánh x với phần tử nằm vị trí giữa của dãy tìm kiếm hiện hành, dựa vào kết quả so sánh này để quyết định giới hạn dãy tìm ở bước kế tiếp là nửa trên hay nửa duới của dãy tìm kiếm hiện hành.

 Ví dụ:

– Cho dãy a có 7 phần tử: 3 4 6 8 9 10 13

– Tìm x = 10 và x = 2 ???

 Minh họa ví dụ

– Cho dãy số a: 3 4 6 8 9 10 13

tìm x= 10.

Mã nguồn :  Cài đặtint BinarySearch (int a[], int n, int x) { int left = 0, right = n- 1; while(left<=right) { int mid = (left + right)/2; if(a[mid] == x) return mid; else if( a[mid]<x)               left = mid+1; else                        right = mid- 1; } return – 1;

Bài Tập Làm Cho Quen: *Bài tập lý thuyết

 Cho dãy số sau: 7 9 13 17 27 30 31 35 38 40 a. Tìm x= 17, x=35, x=40 b. Tìm x = 23, x=10, x=36  Cho dãy ký tự Z R L K H F E C A a. Tìm x = R, x = C b. Tìm x = D, x = Q

*Bài tập thực hành 

Cho mảng 1 chiều a chứa n số nguyên. Viết chương trình thực hiện các

yêu cầu sau:

1. Viết hàm nhập/xuất mảng a.

2. Tìm max/min của a.

3. Đếm số phần tử chẵn/lẻ trong a.

4. Tìm kiếm phần tử x trong a theo 2 dạng ( trả về vị trí/xuất câu thông

báo) với giải thuật tìm kiếm tuyến tính/ tìm kiếm nhị phân.

5. Tìm trên a có bao nhiêu phần tử x. Đến đây cơ bản là xong 2 giải thuật tìm kiếm cơ bản.Chúng tar cùng nhau thảo luận nhé.Phần tiếp theo là các giải thuật sắp xếp,mình sẽ viết nó ở phần sau(Phần 2) Phần 2: II CÁC GIẢI THUẬT SẮP XẾP

(Các thuật toán minh họa sắp xếp dãy không tăng trên mảng 1 chiều chứa dữ liệu là các số nguyên)

– Sắp xếp là quá trình xử lý một danh sách các phần tử để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đó dựa trên nội dung thông tin lưu trữ tại mỗi phần tử. +Các phương pháp sắp xếp thông dụng

2.1. Sắp xếp đổi chỗ trực tiếp – Interchange Sort

2.2. Sắp xếp chọn trực tiếp – Selection Sort

2.3. Sắp xếp chèn trực tiếp – Insertion Sort

2.4. Sắp xếp Nổi bọt – Bubble Sort

Phần tiếp theo sẽ được viết trong thời gian sớm nhất. Hy vọng giúp ít cho các bạn.

Tác giả : Trần Thanh Nhã

Share this:

• Twitter
• Facebook

Like Loading...

Related