Numerical-CPP

Tôi học theo một khoá học khác trên Udemy về Numerical computation with CPP

2 Linear search¶

Nhiệm vụ:

Nhập một dãy số vào list của vector
Kiểm tra 1 con số có trong list này không

#include <iostream>
#include <vector>

using namespace std;


// Định nghĩa

void fillVector(vector<int>& newMyVector) // tạo function với argument là reference của một vector (array) có định dạng là integer // sử dụng & để nó pass by reference chứ không cần phải copy dữ liệu của array
{
    int input;
    cout << "Please type in the numbers and stop with (-1): " << endl;
    cin >> input; // Nhập dữ liệu và ấn Enter
    while (input != -1) {
        newMyVector.push_back(input); // add dữ liệu vào vị trí cuối vector
        cin >> input;// tiếp tục nhập thêm
    };
};

void printVector(const vector<int>& newMyVector)
{
    cout << "The existing number are: ";
    for (int i = 0; i < newMyVector.size(); i++) {
        cout << newMyVector[i] << " ";
    }
    cout << endl;
};

// Checking number already exists
bool searchVector(int enteredNumber, vector<int>& newMyVector)
{
    for (size_t i = 0; i < newMyVector.size(); i++)
    {
        if (enteredNumber == newMyVector[i]) {
            return true;
        }
    }
    return false; // mặc định return false
}

int main()
{
    vector<int> myVector;
    fillVector(myVector);
    printVector(myVector);
    int myNumber{ 0 };
    cout << "Please write a check number: " << endl;
    cin >> myNumber;
    if (searchVector(myNumber, myVector)) {
        cout << "The number already exist" << endl;
    }
    else
    {
        cout << "Your number is not in the list" << endl;
    }

    return 0;
}

3 Binary Search¶

Bài toán:

Vẫn kiểm tra một số có trong list như bài toán trên
Nhưng bổ sung thêm yêu cầu sắp xếp list trước khi check
Sau đó sử dụng Binary search algorithm

Để sort thì cần sử dụng 2 vòng lặp, nếu tìm được Min thì đổi vị trí của index i (vòng lặp lớn) và vị trí của index j

3.1 Sort¶

void sortVector(vector<int>& newMyVector) //sắp xếp
{
    int minIndex = 0;
    int minElement = 0;
    for (size_t i = 0; i < newMyVector.size(); i++)
    {
        minElement = newMyVector[i]; // reset
        minIndex = i;

        for (size_t j = i+1; j < newMyVector.size(); j++)
        {// xác định vị trí Min trong mỗi vòng lặp
            if (newMyVector[j] < minElement) {
                minIndex = j;
                minElement = newMyVector[j];
            };
        }

        // Đổi vị trí của Min và vị trí của value tại i index
        int temp = newMyVector[i]; // tạo một biến trung gian
        newMyVector[i] = minElement;
        newMyVector[minIndex] = temp;
    }

}

3.2 Binary search algorithm¶

Sử dụng Binary search sẽ giúp cho kết quả nhanh hơn rất nhiều lần so với Linear search, vì nó chỉ cắt dữ liệu ra làm đôi, chứ không so sánh lần lượt từng dữ liệu

// Checking number already exists, sử dụng binary search
bool binarySearchVector(int enteredNumber, vector<int>& newMyVector)
{
    //Nguyên tắc của binary search là chia đôi ra để tìm tuỳ theo biến nhỏ hơn hay lớn hơn
    // Tạo ba vị trí
    int lowIndex{ 0 };
    int midIndex{ 0 };
    int highIndex = newMyVector.size() - 1;
    while (lowIndex < highIndex)// nếu low bằng high index thì 2 điểm này trùng nhau, tức là không còn mid point nữa
    {
        midIndex = (lowIndex + highIndex) / 2;
        if (newMyVector[midIndex] == enteredNumber)
        {
            return true;
        }
        else if (newMyVector[midIndex] > enteredNumber)
        {
            highIndex = midIndex-1; // - 1 rất quan trọng
        }
        else
        {
            lowIndex = midIndex+1;
        }

    };

    return false; // mặc định return false
}

4 Degree to radian¶

5 Recursive function - factorial¶

Tạo functions trong function. Có ích trong các bài toán như n! = n(n-1)(n-2)…

#include <iostream>

using namespace std;
// recursive function
int counter(int number) //factorial function, giai thừa
{
    if (number <= 0 || number == 1) 
    {
        return 1;
    }else
    {
        return (number *= counter(number - 1)); //number = number*counter(numer -1)
    }
};

Trong function chúng ta cần return chính function này để nó tính lại thêm 1 lần nữa. Tức là function counter khi return cũng đặt counter bên trong. Tuy nhiên phải có một hàm if phía trước nó để biết khi nào dừng lại.

Nếu nhập 5! thì 5 sẽ thuộc vào else, nó sẽ lấy 5x4, sau đó kết quả này là 20x3,..

6 Euler number (recursive function vs loop)¶

Tính số Euler. Thực tế giá trị của Euler number là 2.71828… con số này được Leonhard Euler giới thiệu vào năm 1748, được viết tắt là \(e\)

Số \(e\) thường được dùng trong tính toán population growth hoặc decay rate. Ngoài ra nó cũng được dùng nhiều trong các bài toán kinh tế.

Công thức tính Euler number:

\[
e = 1 + \frac{1}{1} + \frac{1}{1\times2} + \frac{1}{1\times2\times3} + \frac{1}{1\times2\times3\times4}+...+\frac{1}{n!}
\]

6.1 Sử dụng recursive method¶

Sẽ áp dụng cách sử dụng function trong function để tính factorial của n! như trong bài toán 5.

6.2 Sử dụng interative method¶

Backlinks¶

No other pages link to this page.

Created : Apr 17, 2022