Bang hộiTiền mặt: 0 Xu Trò chơiHộp quà giáng sinhThứ Sáu, 15:25:41 - 13/12/2024
Chia sẻ kiến thức ngôn ngữ lập trình C, C++, C#, Java, Python, PHP, JS, SQL ...

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

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

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

#1 » Gửi bài gửi bởi nghiammo1992 » 13/09/2021 10:48 » @523447

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;
}
 
nghiammo1992 ✅
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 Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số đ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ài gửi bởi nghiammo1992 » 13/09/2021 10:56 » @523448

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;
}
 
nghiammo1992 ✅
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 Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số đ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ài gửi bởi nghiammo1992 » 13/09/2021 11:03 » @523449

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 n, int x)
{
    int left = 0;
    int right = n - 1;
    int mid;
    while (left <= right && x >= A[left] && x <= 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: " << n << endl;

    cout << InterpolationSearch(arr, n, -5);

    return 0;
}
Sửa lần cuối: nghiammo1992 03/06/2022 02:50
nghiammo1992 ✅
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 Bang hội: ⚡5/46⚡
Level:
Chủ đề đã tạo: 🩸4141/4141🩸
Tiền mặt:
Ngân hàng:
Nhóm:
Danh hiệu: ⚝⚝⚝Truyền Thuyết⚝⚝⚝
Giới tính:
Ngày tham gia:
Đến từ:
Thiết bị:
Số điện thoại:
(Google Chrome 94.0.460)



Quay về C, C++, C#, Java, Python, PHP, JS, SQL ...

 


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