VD về thuật toán chặt nhị phân, đệ quy, quai lui VD code chỉ chọn 1 trong 3 : Cpp, Pascal, Python Nl : cán mốc 300, ợp vv

`***` Chặt nhị phân (tìm kiếm nhị phân):

`+` Chặt nhị phân là thuật toán tối ưu dùng để kiểm tra xem một số nguyên `k` nào đó có nằm trong một mảng `a` nào đó đã được sắp xếp tăng dần hay không.

`+` Cấu trúc của thuật toán tìm kiếm nhị phân:

`-` tb = (l+r)/2

`-` Nếu a[tb] = k thì trả về true (có phần tử k trong mảng)

`-` Nếu a[tb] > k thì đặt r = tb-1 (vì mảng a đã được sắp xếp tăng dần nên nếu ai > k thì ai+1, ai+2, ... đều sẽ lớn hơn k)

`-` Nếu a[tb] < k thì đặt l = tb+1 (vì mảng a đã được sắp xếp tăng dần nên nếu ai < k thì ai-1, ai-2, ... đều sẽ bé hơn k)

`+` Như vậy, độ phức tạp của thuật toán chặt nhị phân chỉ có O(log(n))

`+` Code ví dụ hàm tìm kiếm nhị phân:

bool binary_search(int l, int r, int k)
{
    while (l<=r)
    {
        tb = (l+r)/2;
        if (a[tb] == k) return true;
        if (a[tb] > k) r = tb-1;
        else l = tb+1;
    }
    return false;
}

//Khi gọi hàm tìm kiếm nhị phân, ta đặt l=chỉ số bắt đầu, r=chỉ số kết thúc, k=giá trị cần tìm.

//Lưu ý a phải được sắp xếp trước khi gọi hàm tìm kiếm.

$\\$

`***` Đệ quy:

`+` Về cơ bản, đệ quy chỉ là một hàm tự gọi lại chính nó.

`+` Một số lưu ý khi sử dụng đệ quy:

`-` Phải có ít nhất một điều kiện để kết thúc việc gọi đệ quy.

`-` Không lạm dụng đệ quy vì đệ quy chiếm rất nhiều bộ nhớ.

`-` Đối với C++: Gọi đệ quy tối đa 4000 lần (có thể nhiều hơn hoặc ít hơn tùy vào bộ nhớ), nếu gọi quá sẽ dễ bị tràn stack.

`-` Đối với Python: Chế độ mặc định cho phép gọi đệ quy tối đa 1000 lần, có thể gọi nhiều hơn tùy vào việc chỉnh sửa hệ thống (sys).

`+` Code ví dụ đệ quy:

//Bài toán tính n!

int dequy(int n)
{
    if (n==1) return 1;
    return n*dequy(n-1);
}

$\\$

`***` Quay lui:

`+` Quay lui là một thuật toán vét cạn.

`+` Một số lưu ý khi sử dụng quay lui:

`-` i là chỉ số, j là các giá trị có thể gán tại i `->` Độ phức tạp O(`j^i`)

`-` Như bạn thấy, độ phức tạp là quá lớn, vì vậy thuật toán này chỉ có thể sử dụng trong một vài trường hợp cụ thể.

`+` Ví dụ vế quay lui:

//Bài toán in ra tất cả dãy nhị phân có độ dài n

void quaylui(int i, int n, string &s)
{
    for (char j:{'0','1'})
    {
        s[i] = j;
        if (i==n-1) cout << s << endl;
        else quaylui(i+1,n,s);
    }
}

//i luôn = 0, n là độ dài dãy nhị phân, s là xâu chứa kết quả (s được khai báo có độ dài  là n).

$\\$

`@Daoanhviet96`