Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++
Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++. Đây là một trong những thuật toán tìm kiếm được sử dụng nhiều nhất, bởi nó nhanh hơn và chính xác hơn bất kì thuật toán tìm kiếm nào.
Trước khi đi vào tìm hiểu thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++, chúng ta hãy xem khái niệm về nó đã nhé. Sau đó mình sẽ giải thích thuật toán và kèm theo ví dụ minh họa cho các bạn tham khảo.
Tìm kiếm nội suy (Interpolation Search) là gì?
Thuật toán tìm kiếm nội suy (Interpolation Search) là sự cải tiến của thuật toán tìm kiếm nhị phân (Binary Search). Tuy nhiên nó linh động hơn rất nhiều so với tìm kiếm nhị phân.
Nói một cách dễ hiểu hơn, tìm kiếm nhị phân chia nữa mảng bắt đầu từ đầu mảng đến cuối mảng. Tìm kiếm nội suy (Interpolation Search) sẽ tìm ra phần tử gần giá trị tìm kiếm nhất và bắt đầu tìm từ đó.
Như vậy thời gian tìm kiếm nhanh hơn và phạm vi tìm kiếm được thu hẹp hơn rất nhiều.
Ví dụ: Mình có một mảng Number = {4, 5, 6, 7, 10}. Bây giờ cần tìm giá trị 7 trong mảng Number.
- Nếu sử dụng thuật toán tìm kiếm nhị phân thì bắt đầu tìm từ số 4 (đầu mảng).
- Đối với tìm kiếm nội suy (Interpolation Search) thì nó sẽ so sánh và bắt đầu tìm từ cuối, vì như vậy sẽ nhanh hơn.
Ví dụ thực tế: Giả sử chúng ta muốn tìm kiếm bạn Tâm trong danh sách lớp. Chúng ta ưu tiên tìm từ cuối danh sách thay vì tìm từ đầu danh sách. Như vậy sẽ nhanh hơn rất nhiều.
Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++
Bởi vì thuật toán tìm kiếm nội suy (Interpolation Search) được cải tiến từ thuật toán tìm kiếm nhị phân, nên về cơ bản khá giống nhau. Mảng cần được sắp xếp trước khi tìm kiếm nhé.
Dưới đây là thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++, các bạn hãy xem qua rồi mình giải thích ngay bên dưới nhé.
int InterPolationSearch(int arr[], int n, int x)
{
int left = 0;
int right = n-1;
while (left <= right && x >= arr[left] && x <= arr[right])
{
double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
int val2 = (right-left);
int Search = left + val1*val2;
if (arr[Search] == x)
return Search;
if (arr[Search] < x)
left = Search + 1;
else
right = Search - 1;
}
return -1;
}Trong thuật toán này, chúng ta thay đổi công thức tìm phần tử ở giữa khác một chút so với thuật toán tìm kiếm nhị phân như sau.
Tìm kiếm nhị phân:
Search = left + (right - left) * 1/2
Tìm kiếm nội suy:
Search = left + (X- T[left]) * (right – left) / (T[right] – T[left])
Giải thích thuật toán:
- Sau khi xác định được phần tử giữa (middle), ta so sánh với giá trị cần tìm. Nếu bàng nhau thì trả về vị trí rồi thoát vòng lặp.
- Nếu Search < x thì tăng left lên 1 đơn vị rồi quay lại vòng lặp.
- Nếu Search > x thì giảm right xuống một đơn vị rồi quay lại vòng lặp.
Bây giờ mình sẽ thực hiện một ví dụ cụ thể sử dụng thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++. Chương trình được viết bằng hai ngôn ngữ C và C++, các bạn có thể tham khảo nhé.
Chương trình C:
#include <stdio.h>
#include <stdbool.h>
void sort_numbers_ascending(int number[], int count)
{
int temp, i, j, k;
for (j = 0; j < count; ++j)
{
for (k = j + 1; k < count; ++k)
{
if (number[j] > number[k])
{
temp = number[j];
number[j] = number[k];
number[k] = temp;
}
}
}
printf("Các số sau khi được sắp xếp tăng dần: ");
for (i = 0; i < count; ++i)
printf("%d ",number[i]);
}
int InterPolationSearch(int arr[], int n, int x)
{
int left = 0;
int right = n-1;
while (left <= right && x >= arr[left] && x <= arr[right])
{
double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
int val2 = (right-left);
int Search = left + val1*val2;
if (arr[Search] == x)
return Search;
if (arr[Search] < x)
left = Search + 1;
else
right = Search - 1;
}
return -1;
}
int main(void) {
int n,x, result;
do{
printf("Nhập vào số lượng phần tử của mảng: ");
scanf("%d", &n);
if(n <= 0) printf("Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n");
}while(n <= 0);
int a[n];
//nhập các phần tử mảng
for(int i=0; i<n; i++){
printf("Nhập vào phần tử a[%d]: ",i);
scanf("%d",&a[i]);
}
sort_numbers_ascending(a,n);
printf("\nNhập giá trị x cần tìm: ");
scanf("%d", &x);
result = InterPolationSearch(a, n, x);
if(result == -1) printf("\nKhông tìm thấy giá trị %d trong mảng.\n",x);
else printf("\nĐã tìm thấy giá trị %d tại vị trí %d",x,result);
printf("\n----------------------------\n");
printf("Chương trình này được đăng tại codehow.net");
return 0;
}Kết quả:
Chương trình C++:
#include <iostream>
using namespace std;
void sort_numbers_ascending(int number[], int count)
{
int temp, i, j, k;
for (j = 0; j < count; ++j)
{
for (k = j + 1; k < count; ++k)
{
if (number[j] > number[k])
{
temp = number[j];
number[j] = number[k];
number[k] = temp;
}
}
}
cout<<"Các số sau khi được sắp xếp tăng dần: ";
for (i = 0; i < count; ++i)
cout<< number[i]<<" ";
}
int InterPolationSearch(int arr[], int n, int x)
{
int left = 0;
int right = n-1;
while (left <= right && x >= arr[left] && x <= arr[right])
{
double val1 = (double) (x - arr[left]) / (arr[right]-arr[left]);
int val2 = (right-left);
int Search = left + val1*val2;
if (arr[Search] == x)
return Search;
if (arr[Search] < x)
left = Search + 1;
else
right = Search - 1;
}
return -1;
}
int main() {
int n,x, result;
do{
cout << "Nhập vào số lượng phần tử của mảng: ";
cin >> n;
if(n <= 0) cout<<"Vui lòng nhập số lượng phần tử lớn hơn 0!!!\n";
}while(n <= 0);
int a[n];
//nhập các phần tử mảng
for(int i=0; i<n; i++){
cout << "Nhập vào phần tử a[" << i << "]: ";
cin >> a[i];
}
sort_numbers_ascending(a,n);
cout<<"\nNhập giá trị x cần tìm: ";
cin>>x;
result = InterPolationSearch(a, n, x);
if(result == -1) cout<<"Không tìm thấy giá trị "<<x<<" trong mảng.\n";
else cout<<"Đã tìm thấy giá trị "<<x<<" tại vị trí "<<result;
cout<<"\n----------------------------\n";
cout<<"Chương trình này được đăng tại codehow.net";
}Kết quả:
Như vậy là chúng ta đã cùng nhau tìm hiểu về thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++. Các bạn hãy luyện tập thật nhiều để sử dụng các thuật toán một cách thành thạo nhé. Chúc các bạn thành công !!!!
