Skip to content

Numerical-CPP

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

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 đị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;
}

Bài toán:

  • Vẫn kiểm tra một số có trong list như bài toán trên
  • Nhưng bổ sung thêm yêu cầu sắp xếp list trước khi check
  • Sau đó sử dụng Binary search algorithm

Để sort thì cần sử dụng 2 vòng lặp, nếu tìm được Min thì đổi vị trí của index i (vòng lặp lớn) và vị trí củ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++)
        {// xác định vị trí Min trong mỗi vòng lặp
            if (newMyVector[j] < minElement) {
                minIndex = j;
                minElement = newMyVector[j];
            };
        }

        // Đổi vị trí của Min và vị trí của value tại i index
        int temp = newMyVector[i]; // tạo một biến trung gian
        newMyVector[i] = minElement;
        newMyVector[minIndex] = temp;
    }

}

3.2 Binary search algorithm

Sử dụng Binary search sẽ giúp cho kết quả nhanh hơn rất nhiều lần so với Linear search, vì nó chỉ cắt dữ liệu ra làm đôi, chứ không so sánh lần lượt từng dữ liệu

// Checking number already exists, sử dụng binary search
bool binarySearchVector(int enteredNumber, vector<int>& newMyVector)
{
    //Nguyên tắc của binary search là chia đôi ra để tìm tuỳ theo biến nhỏ hơn hay lớn hơn
    // Tạo ba vị trí
    int lowIndex{ 0 };
    int midIndex{ 0 };
    int highIndex = newMyVector.size() - 1;
    while (lowIndex < highIndex)// nếu low bằng high index thì 2 điểm này trùng nhau, tức là không cò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 trọng
        }
        else
        {
            lowIndex = midIndex+1;
        }

    };

    return false; // mặc định return false
}

4 Degree to radian

5 Recursive function - factorial

Tạo functions trong function. Có ích trong các bài toá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 chúng ta cần return chính function này để nó tính lại thêm 1 lần nữa. Tức là function counter khi return cũng đặt counter bên trong. Tuy nhiên phải có một hàm if phía trước nó để biết khi nào dừng lại.

Nếu nhập 5! thì 5 sẽ thuộc vào else, nó sẽ lấy 5x4, sau đó kết quả này là 20x3,..

6 Euler number (recursive function vs loop)

Tính số Euler. Thực tế giá trị của Euler number là  2.71828… con số này được Leonhard Euler giới thiệu vào năm 1748, được viết tắt là \(e\)

Số \(e\) thường được dùng trong tính toán population growth hoặc decay rate. Ngoài ra nó cũng được dùng nhiều trong các bài toán kinh tế.

Công thức tí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ử dụng recursive method

Sẽ áp dụng cách sử dụng function trong function để tính factorial của n! như trong bài toán 5.

6.2 Sử dụng interative method

No other pages link to this page.



Created : Apr 17, 2022