Chủ đề nổi bật

Bài 14: Thuật toán tìm kiếm tuyến tính trong php

Trong bài thuật toán sắp xếp nổi bọt tôi đã nói nếu một danh sách được sắp xếp có thứ tự thì việc tìm kiếm trên danh sách đó rất là nhanh, và để ...

Trong bài thuật toán sắp xếp nổi bọt tôi đã nói nếu một danh sách được sắp xếp có thứ tự thì việc tìm kiếm trên danh sách đó rất là nhanh, và để chứng minh điều đó thì bắt đầu từ bài này chúng ta sẽ tìm hiểu hai thuật toán đó là tìm kiếm tuyến tính và tìm kiêm nhị phân, từ đó bạn sẽ hiểu nguyên do nếu một mảng được sắp xếp sẵn thì thời gian tìm kiếm sẽ nhanh hơn.

Trong 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

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

BẢNG MÃ KÍCH HOẠT KHÓA HỌC RẤT RẺ

Mình đã sưu tầm các mã giám giá rất rẻ và đăng nó ơ trong bài viết này, bạn hãy vào tham khảo để xem cần kháo nào thì hãy chọn cho riêng mình nhé, Lưu ý la chỉ có tại code24h.com, bạn sẽ không thể tìm thấy ở chỗ khác.

Xem Ngay

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:

$mang = array(321,312,3,4,5,45,56,5,7,6,787,8,7,2);
 
$can_tim = 67;
 
for ($i = 0; $i < count($mang); $i++){ // duyệt qua từng phần tử của mảng
    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
        echo 'Số ' . $can_tim . ' có nằm trong mảng tại ví trí thứ ' . $i;
        break;
    }

Giải có dùng hàm:

// hàm kiểm tra
function kiem_tra($mang, $can_tim)
{
    for ($i = 0; $i < count($mang); $i++){ // duyệt qua từng phần tử của mảng
        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
            return true; // và không cần làm gì trong hàm này nữa, trả về là đúng luôn
        }
    }
    return false; // sau khi lặp hết mà ko có thì return về false
}
 
// ---------------------- chương trình chính
// Cho mảng
$mang = array(321,312,3,4,5,45,56,5,7,6,787,8,7,2);
 
// biến cần tìm
$can_tim = 67;
 
// gọi hàm và xuất kết quả
if (kiem_tra($mang, $can_tim)){
    echo 'Số ' . $can_tim . ' có nằm trong mảng';
}

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

// Hàm tìm các số chia hết cho 3
function tim_so_chia_het_cho_3($mang)
{
    foreach ($mang as $key => $val){
        if ($val % 3 == 0){
            echo 'Ví trí thứ ' . $key . '<br/>';
        }
    }
}
 
// Chương trình chính
//-----------------------------------------------
// Lặp từ 1 đến 100 để gán giá trị vào mảng
$mang = array();
for ($i = 1; $i <= 100; $i++){
    $mang[$i] = $i;
}
 
// Gọi hàm để xuất ra vị trí chia hết cho 3
tim_so_chia_het_cho_3($mang);

3. Lời kết

Kết thúc bài học này hy vọng các bạn không lúng túng khi gặp một bài toán tìm kiếm nữa nhé, nếu có gặp hãy nhớ đến thuật toán tìm kiếm tuyến tính tại code24h.com laugh. 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 KẾ SAU
BÀI KẾ TIẾP

Nguồn: code24h.com

Bài liên quan
Mới nhất

Danh sách các múi giờ (Timezones) trong PHP

- Múi giờ (timezones) thường được sử dụng trong các hàm xử lý ngày tháng & thời gian. - Dưới đây là danh sách đầy đủ các múi giờ được hỗ trợ trong ngôn ngữ lập trình PHP. 1) Africa Africa/Abidjan Africa/Accra Africa/Addis_Ababa Africa/Algiers 2) America ...

Các hàm dùng để quản lý thư mục trong PHP

Hàm Mô tả chức năng chdir() chroot() closedir() dir() getcwd() opendir() readdir() rewinddir() scandir() ...

Danh sách tất cả các hàm xử lý chuỗi trong PHP

Hàm Mô tả chức năng addcslashes() Thêm một dấu gạch chéo ngược () phía trước các ký tự được chỉ định addslashes() Thêm một dấu gạch chéo ngược () phía trước các ký tự là dấu nháy kép, dấu nháy đơn và dấu gạch chéo ngược trong chuỗi bin2hex() Chuyển một chuỗi các ký tự ...

Cách khai báo và sử dụng hàm (function) trong PHP

1) Hàm là gì !? - Hàm là một tập hợp gồm nhiều câu lệnh, các câu lệnh này được sắp xếp theo một thứ tự xác định để xây dựng thành một chức năng cụ thể và mỗi hàm sẽ có một cái tên. Ví dụ Đoạn mã bên dưới, chúng ta có một hàm tên là GioiThieuBanThan. Hàm này gồm ba câu lệnh với ...

Vòng lặp for & foreach trong PHP

1) Vòng lặp là gì !? - Trong PHP, vòng lặp là một loại cú pháp giúp ta lặp lại việc thực thi một đoạn mã nhiều lần. - Ví dụ, nếu tôi muốn hiển thị lên màn hình 100 dòng chữ "Lập Trình Web" thì đáng ra phải gõ 100 câu lệnh echo "<p>Lập Trình Web</p>"; . Tuy nhiên, với việc sử ...

Lệnh điều kiện if ... else trong PHP

"Nếu bạn học tốt môn lập trình web thì bạn sẽ có thể thiết kế được website" - Câu trên được chia làm hai vế: Vế thứ nhất: "Nếu bạn học tốt môn lập trình web" Vế thứ hai: "Bạn sẽ có thể thiết kế được website" - Trong cuộc sống, ta gọi vế thứ nhất là điều kiện, vế thứ hai là một điều ...

Danh sách tất cả các hàm xử lý mảng trong PHP

Hàm Mô tả chức năng array_change_key_case Đổi tên của tất cả các phần tử trong mảng về dạng chữ in hoa hoặc chữ thường array_chunk array_column array_combine array_count_values array_diff array_diff_assoc array_diff_key ...

Danh sách các hàm xử lý tập tin hệ thống trong PHP

Hàm Mô tả chức năng basename() Trả về tên tập tin từ một đường dẫn chgrp() Thay đổi nhóm người dùng của tập tin được chỉ định chmod() Thiết lập quyền hạn của các nhóm người dùng trên tập tin được chỉ định chown() Thay đổi chủ sở hữu của một tập tin copy() Sao ...

Danh sách tất cả các hàm xử lý ngày tháng trong PHP

Hàm Mô tả chức năng checkdate Kiểm tra xem một ngày được xác định có hợp lệ hay không date date_add date_create date_create_from_format data_create_immutable data_create_immutable_from_format date_date_set date_default_timezone_get ...

Vòng lặp while & do while trong PHP

1) Vòng lặp while trong PHP - Trước khi nêu khái niệm "vòng lặp while là gì?" thì tôi có một ví dụ để giúp bạn có thể hình dung sơ qua về vòng lặp while. - Bạn đưa ra một điều kiện, nếu điều kiện đó là sai thì kết thúc, còn nếu đúng thì một đoạn mã sẽ được thực thi và bạn tiếp tục quay ...