Ở bài này chúng ta sẽ tìm hiểu thuật toán tìm kiếm tuyến tính trước.
Nội dung bìa học như sau:
- Tìm kiếm tuyến tính là gì?
- Các ví dụ tìm kiếm tuyến tính.
Nội dung
1. Tìm kiếm tuyến tính là gì?
Tìm kiếm tuyến tính (hay tìm kiếm tuần tự). Là một thuật toán tìm kiếm một phần tử cho trước nằm trong một danh sách (có thể là mảng). Bằng cách duyệt lần lược các phần tử và so sánh cho đến khi tìm thấy phần tử đó.
Giả sử có mảng $a gồm 50 phần tử. Giờ tìm xem số 50 có nằm trong mảng không thì ta sẽ dùng vòng lặp for để duyệt lần lược 50 phần tử đó. Và so sánh xem có phần tử nào bằng 50 không. Nếu có thì trả kết quả là tìm thấy và dừng vòng lặp. Ngược lại nếu lặp hể cả 50 phần tử mà vẫn không có thì sẽ trả kết quả là không tìm thấy.
Tìm kiếm tuyến tính tuần tự là một giải thuật rất đơn giản và dễ cài đặt. Giải thuật này tỏ ra khá là nhanh đối với những dữ liệu có kích thước nhỏ vừa phải chưa được sắp thứ tự.
2. Ví dụ tìm kiếm tuyến tính
Trong phần này chúng ta sẽ làm các ví dụ tìm kiếm tuyến tính trong php. Qua đó các bạn sẽ hiểu được ý tưởng của nó.
Ví dụ 1: Cho mảng $mang = array(321,312,3,4,5,45,56,5,7,6,787,8,7,2); .Hãy viết hàm kiểm tra số 67 có nằm trong mảng không?.
Chúng ta sẽ giải bài toán bằng hai cách không dùng hàm và có dùng hàm.
Giải không dùng hàm:
1:$mang = array(321,312,3,4,5,45,56,5,7,6,787,8,7,2);.
2:
3: $can_tim = 67;.
4:
5: for ($i = 0; $i < count($mang); $i++){ // duyệt qua từng phần tử của mảng.
6: if ($mang[$i] == $can_tim){ // và so sánh xem có bằng số 67 không, nếu có thì xuất ra màn hình và dừng vòng lặp.
7: echo 'Số ' . $can_tim . ' có nằm trong mảng tại ví trí thứ ' . $i;.
8: break;
9: }
Giải có dùng hàm:
ảnh minh họa
1: // hàm kiểm tra
2: function kiem_tra($mang, $can_tim).
3: {
4: for ($i = 0; $i < count($mang); $i++){ // duyệt qua từng phần tử của mảng.
5: if ($mang[$i] == $can_tim){ // và so sánh xem có bằng số 67 không, nếu có thì xuất ra màn hình.
6: return true; // và không cần làm gì trong hàm này nữa, trả về là đúng luôn.
7: }
8: }
9: return false; // sau khi lặp hết mà ko có thì return về false.
10: }
11:
12: // ———————- chương trình chính.
13: // Cho mảng.
14: $mang = array(321,312,3,4,5,45,56,5,7,6,787,8,7,2);.
15:
16: // biến cần tìm
17: $can_tim = 67;.
18:
19: // gọi hàm và xuất kết quả.
20: if (kiem_tra($mang, $can_tim)){
21: echo 'Số ' . $can_tim . ' có nằm trong mảng';
22: }.
Ví dụ 2: Cho một mảng gồm các phần tử từ 1 đến 100. Hãy tìm vị trí các số chia hết cho 3 trong dãy.
ảnh minh họa
Trong bài học tiếp theo chúng ta sẽ học về kỹ thuật đặt lính canh trong PHP.
Bài 15: Kỹ thuật đặt lính canh ở trong PHP
Nội dung bài học bao gồm:
- Kỹ thuật đặt lính canh là gì?
- Khi nào nên sử dụng kỹ thuật này.
1. Kỹ thuật đặt lính canh là gì?
Chúng ta sẽ phân tích một ví dụ trong thực tế như sau.
Ví dụ 1: Tôi muốn tìm người cao nhất trong lớp học.
Trước tiên chọn một bạn làm mẫu rồi lần lượt so sánh với các bạn còn lại. Nếu bạn nào cao hơn thì đổi chỗ cho bạn làm mẫu đó và người bạn cao hơn. Lúc này người bạn cao hơn sẽ đứng làm mẫu. Và cứ như vậy cho đến hết. Kết quả là người làm mẫu cuối cùng để canh chính là người cao nhất. Đây được gọi là kỹ thuật đặt lính canh.
Ví dụ 2: Dùng kỹ thuật đặt lính canh tìm giá trị lớn nhất của 3 số $avà $b và $c.
Cách giải các bước như sau: Khởi tạo một biến $max để chứa giá trị lớn nhất.
1: Giả sử biến lớn nhất là biến $a, tức là ta gán $max = $a;.
2: So sánh biến $max với $b, nếu $b lớn hơn $max thì ta gán$max = b;.
3: So sánh biến $max với $c, nếu $c lớn hơn$max thì ta gán $max = c;.
Cuối cùng biến $max chứa giá trị lớn nhất. Sau đây là hàm tìm giá trị lớn nhất:
ảnh minh họa
2. Khi nào thì nên sử dụng kỹ thuật đặt lính canh?
Kỹ thuật đặt lính canh dùng khi các bạn muốn duyệt qua danh sách và chọn một phần tử có đặc điểm đặc biệt nào đó.
Kỹ thuật này hay được dùng để tìm min max. Giá trị lớn nhất, nhỏ nhất, số nguyên tố lớn nhất, số nguyên tố nhỏ nhất … của một mảng danh sách.
Đó là các ví dụ thôi chứ không phải là tất cả trường hợp. Nếu bạn dùng quen rồi thì sẽ biết lúc nào dùng đến.
Ở bài tiếp theo tôi sẽ giới thiệu một kỹ thuật khác cũng tương tự đó là kỹ thuật đặt cờ hiệu.
Bài 16: Kỹ thuật đặt cờ hiệu bên trong PHP
Nội dung chính
- Kĩ thuật đặt cờ hiệu là gì?
- Khi nào sử dụng kĩ thuật đặt cờ hiệu
1. Kỹ thuật đặt cờ hiệu là gì?
Tương tự bài trước mình sẽ đưa ra một ví dụ thực tế để các bạn dễ hình dung.
Ví dụ 1: Quy trình của đội bóng trước khi ra sân.
Giả sử có một đội bóng trước khi ra sân thi đấu. Các bác sỹ kiểm tra sức khỏe của từng người. Nếu một trong những cầu thủ ra sân có sử dụng chất kích thích. thì cả đội bóng sẽ không được thi đâu và sẽ bị kỉ luật. Cách làm như sau: tôi sẽ duyệt qua từng người và kiểm tra. Chỉ cần có 1 cầu thủ thôi là kết luận đc đội bóng này không đủ điều kiện. Đây gọi là kỹ thuật đặt cờ hiệu.
Ví dụ 2: Kiểm tra xem các số từ 1 đến 1000 có số nào chia hết cho 40 không?
Giải bài này tôi sẽ dùng kỹ thuật đặt cờ hiệu lặp từ 1 cho -> 1000 rồi chia lấy dư cho 40. Chỉ cần có một số chia hết cho 40 là tôi có thể quyết định rằng số chia hết cho 40 trong khoảng từ 1 đến 1000.
Sau đây là hàm có sử dụng kỹ thuật này.
2. Khi nào sử dụng kỹ thuật đặt cờ hiệu
Kỹ thuật đặt cờ hiệu dùng để duyệt mảng danh sách và kiểm tra từng phần tử để đưa ra kết quả cuối cùng.
Kỹ thuật này thường dùng để kiểm tra các dữ liệu đầu vào trước khi lưu vào hệ thống. Kiểm tra một số tồn tại trong danh sách không. Kiểm tra trong danh sách có số nguyên tố không, … Đây là một vài ví dụ thôi chứ thực tế bạn có thể dùng nó cho nhiều trường hợp lắm.
Các bạn thấy kỹ thuật này cũng khá là ngắn gọn phải không nào. Bài tiếp theo ta sẽ tìm hiểu một thuật toán sắp xếp. Không phải là thuật toán sắp xếp nổi bọt mà là thuật toán sắp xếp chọn.
Bài 17: Thuật toán sắp xếp chọn trong PHP
Nội dung bao gồm:
- Ý tưởng thuật toán sắp xếp chọn
- Tìm kiếm phần tử lớn nhất, nhỏ nhất
- Sắp xếp chọn tăng dần
- Sắp xếp chọn giảm dần
1. Ý tưởng thuật toán sắp xếp chọn
Với thuật toán nổi bọt thì ý tưởng là với mỗi phần tử sẽ lặp hết các phần tử phía sau, nếu phần tử nào không đứng đúng vị trí thì hoán vị ngay lập tức. Với thuật toán sắp xếp chọn trong PHP thì lại khác. Ý tưởng như sau: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng, tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1, sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí. Tiếp tục thao tác như vậy cho các vị trí tiếp theo.
Sắp xếp chọn tăng dần theo các bước sau:
1: Duyệt từ vị trí thứ 1 đến vị trí cuối cùng. Tìm vị trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 1. Sau đó loại vị trí số 1 ra khỏi danh sách sắp xếp vì nó đã được đặt đúng vị trí
2: Duyệt từ vị trí số 2 đến vị trí cuối cùng, tìm ví trí phần tử nhỏ nhất sau đó hoán vị với vị trí số 2, sau đó loại vị trí số 2 ra khỏi danh sách sắp xếp vì đã đặt đúng vị trí
Bước n: Cứ như vậy cho đến vị trí phần tử cuối cùng, lúc này chỉ còn 1 phần tử nên coi như nó đã sắp xếp
Giải thuật mô tả bằng hình:
ảnh minh họa
Sắp xếp chọn giảm dần:
Tương tự như sắp xếp tăng dần, vẫn duyệt n bước với điều kiện hoán vị. Ngược lại là tìm vị trí phần tử lớn nhất và hoán vị với vị trí thứ n.
2. Tìm kiếm phần tử lớn nhất, nhỏ nhất
Thuật toán sắp xếp chọn có sử dụng thuật toán tìm kiếm giá trị lớn nhất, nhỏ nhất trong mảng nên tôi sẽ mở ra một phần nhỏ này dành cho những bạn chưa rành gì về kỹ thuật lập trình.
Để tìm giá trị nhỏ nhất, lớn nhất chúng ta sẽ dùng kỹ thuật đặt lính canh kết hợp với tìm kiếm tuyến tính, nghĩa là lúc đầu sẽ chọn phần tử thứ nhất làm lính cầm canh, sau đó duyệt các phần tử còn lại, phần tử nào lớn hơn nếu tìm MAX hoặc nhỏ hơn nếu tìm MIN thì thay thế cho lính canh đã chọn. Sau khi lặp hết các phần tử thì lính canh chính là vị trí lớn nhất, nhỏ nhất.
Bài giải: Tìm phần tử nhỏ nhất:
ảnh minh họa
Bài giải: Tìm phần tử lớn nhất:
ảnh minh họa
3. Sắp xếp chọn trong PHP tăng dần
ảnh minh họa
4. Sắp xếp chọn trong PHP giảm dần
ảnh minh họa
0 Lời bình