Bang hộiTiền mặt: 0 XuTrò chơiHộp quà giáng sinh

[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

Chia sẻ kiến thức lập trình PHP & MySQL

Các điều hành viên: Mod, Admin, SMod

[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

#1  Gửi bàigửi bởi nghiammo » 13/09/2021 10:48

Thuật toán tìm kiếm tuyến tính (linear search)

Mã: Chọn tất cả
#include <iostream>


using namespace std;


int LinearSearch(int A[], int nint x)
{
    for (
int i 0ni++)
        if (
A[i] == x)
            return 
i;
    return -
1// duyệt hết mảng, không tìm thấy x
}


int main()
{

    
int arr[] {32,71,12,45,-26,80,53,-33,7,99,-5,1,2,3,100};

    
int n sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    
cout << "So luong phan tu trong mang: " << << endl;

    
cout << LinearSearch(arrn, -5);

    return 
0;
}
 
nghiammo
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng: ⚡11/43⚡
Level:
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝Độc Cô Cầu Bại⚝
Giới tính:
Ngày tham gia:
Đến từ:
Điện thoại:
(Google Chrome 94.0.460)

Re: [C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

#2  Gửi bàigửi bởi nghiammo » 13/09/2021 10:56

Thuật toán tìm kiếm nhị phân (binary search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã: Chọn tất cả
#include <iostream>


using namespace std;


int BinarySearch(int A[], int nint x)
{
    
int left 0;
    
int right 1;
    
int mid;
    while (
left <= right)
    {
        
mid = (left right) / 2;
        if (
A[mid] == x)
            return 
mid// tìm thấy x, trả về mid là vị trí của x trong mảng A
        
if (A[mid] > x)
            
right mid 1// Giới hạn khoảng tìm kiếm lại là nửa khoảng trước
        
else if (A[mid] < x)
            
left mid 1// Giới hạn khoảng tìm kiếm lại là nửa khoảng sau
    
}
    return -
1// không tìm thấy x
}

int main()
{

    
int arr[] {-33,-26,-5,1,2,3,7,12,32,45,53,71,80,99,100};

    
int n sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    
cout << "So luong phan tu trong mang: " << << endl;

    
cout << BinarySearch(arrn, -5);

    return 
0;
}
 
nghiammo
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng: ⚡11/43⚡
Level:
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝Độc Cô Cầu Bại⚝
Giới tính:
Ngày tham gia:
Đến từ:
Điện thoại:
(Google Chrome 94.0.460)

Re: [C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

#3  Gửi bàigửi bởi nghiammo » 13/09/2021 11:03

Thuật toán tìm kiếm nội suy (interpolation search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã: Chọn tất cả
#include <iostream>


using namespace std;


int InterpolationSearch(int A[], int nint x)
{
    
int left 0;
    
int right 1;
    
int mid;
    while (
left <= right && >= A[left] && <= A[right])
    {
        
mid left + (right left) * (A[left]) / (A[right] - A[left]);
        if (
A[mid] == x)
            return 
mid;
        if (
A[mid] > x)
            
right mid 1;
        else if (
A[mid] < x)
            
left mid 1;
    }
    return -
1// Không tìm thấy x
}

int main()
{

    
int arr[] {-33,-26,-5,1,2,3,7,12,32,45,53,71,80,99,100};

    
int n sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang

    
cout << "So luong phan tu trong mang: " << << endl;

    
cout << InterpolationSearch(arrn, -5);

    return 
0;
}
 
nghiammo
Hình đại diện của thành viên
Rank: ☀️2/30☀️
Cấp độ:
Tu luyện:
Like:
Online:
Bang hội: Tiếu Ngạo
Xếp hạng: ⚡11/43⚡
Level:
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝Độc Cô Cầu Bại⚝
Giới tính:
Ngày tham gia:
Đến từ:
Điện thoại:
(Google Chrome 94.0.460)



Quay về PHP & MySQL

 


  • Chủ đề tương tự
    Trả lời
    Xem
    Bài viết mới nhất

Ai đang trực tuyến?

Đang xem chuyên mục này: Không có thành viên nào đang trực tuyến1 khách