[LHPIC2425]: Buổi 4

# Nội dung buổi 4 ## Đệ quy ### Fun fact ![image](https://hackmd.io/_uploads/SJkOxsi_Jl.png) ![image](https://i.redd.it/0wap3cp4khm01.jpg) ![image](https://i.imgflip.com/9asmai.jpg) **Trong tự nhiên:** Cây phả hệ cũng là một cấu trúc đệ quy tự nhiên: - Bạn có bố mẹ - Bố mẹ bạn cũng có bố mẹ - Ông bà bạn cũng có bố mẹ - Cứ thế tiếp tục lại lặp.. Hay là cách mọc nhánh của lá cây cũng là đệ quy: - Mỗi cái cây mọc ra một nhánh lớn. - Nhánh đó lại mọc ra các nhánh nhỏ hơn. - Mỗi nhánh nhỏ lại tiếp tục chia nhỏ hơn nữa… - Nếu nhìn từ xa, toàn bộ cây trông như một phiên bản phóng to của một nhánh! **Nhân tạo:** 1. Ta có thể thực nghiệm ngay một thí nghiệm nhỏ để tạo ra đệ quy bằng cách bạn cầm một tấm gương chiếu vào một tấm gương khác 2. Bên cạnh trong đời sống ta có thể thấy một vật được xây dựng trên cơ chế đệ quy đó là búp bê Nga (**Matryoshka**) **** ### Áp dụng vào lập trình Một hàm đệ quy thường có cấu trúc gồm 2 phần: - Trường hợp cơ sở (Base Case): **điều kiện dừng** của một **hàm đệ quy**. Nếu không có nó, hàm sẽ **gọi lại** chính nó vô hạn và gây lỗi **Stack Overflow** + Giải thích lý do cần tồn tại **Base Case**: đệ quy giống như bạn đi xuống một cầu thang **vô hạn**. Nếu không có bậc cuối cùng (trường hợp cơ sở), bạn sẽ **không bao giờ dừng lại!** - Gọi đệ quy: gọi để quy lại chính nó để **chia bài toán lớn** thành bài toán con **** ### Lợi thế, khuyết điểm khi sử dụng đệ quy **Ưu điểm** - **Source code ngắn gọn và dễ hiểu**: Đệ quy giúp giải quyết các bài toán phức tạp một cách **ngắn gọn**, không cần sử dụng **nhiều vòng lặp**. - **Giải quyết bài toán phức tạp có thể tách thành các bài toán con**: Phù hợp với các bài toán có tính chất phân rã (chia nhỏ bài toán thành các phần nhỏ hơn). **Nhược điểm** - **Tràn bộ nhớ** (Stack Overflow): Nếu không có điều kiện dừng chính xác hoặc đệ quy quá sâu, chương trình sẽ gây tràn bộ nhớ. 👉**Nói ngắn gọn**: Đây là lỗi xảy ra khi bạn gọi đệ quy vô hạn hoặc quá nhiều lần mà không dừng lại, làm tràn bộ nhớ ngăn xếp.  - **Hiệu suất kém**: Đệ quy có thể không hiệu quả về mặt thời gian nếu số lần gọi đệ quy rất lớn, dẫn đến việc lặp lại các tính toán không cần thiết. **** ### Bài tập  #### Lời giải ... ## Chia để trị ### Trong thực tế - Ngày xưa, khi xâm lược Việt Nam Pháp đã dùng 1 chính sách rất thâm độc là **chia để trị**. Ví dụ như ở 1 vùng quê nhỏ, có 2 làng là Làng Sen và Làng Tre, 2 làng sống hòa thuận và làm việc cùng nhau. Pháp đến và bắt đầu đối xử bất công với 2 làng để tạo sự chia rẻ. Làng Sen thì được giảm thuế, xây đường còn làng Tre thì bị đánh thuế nặng và chèn ép. Đỉnh điểm là Pháp giết người của Làng Sen rồi đổ cho Làng Tre để đẩy mâu thuẫn của 2 làng từ đó dùng chính mâu thuẫn này để áp chế 2 làng. Nhưng với sự đoàn kết của người Việt hai làng đã ý thức được Pháp chính là kẻ thù chung của cả hai. Từ đó Làng Sen san sẻ đều lợi ích của mình và âm mưu của thực dân Pháp chính thức phá sản. ### Áp dụng vào Lập trình Bài toán lớn được chia thành những bài toán con. Sau khi giải quyết những bài toán con, kết hợp các kết quả ấy để đưa ra đáp án cuối cùng. Thường được cài đặt với đệ quy. ### Ưu điểm, nhược điểm #### Ưu điểm - **Giảm độ phức tạp thời gian**: - **Dùng đệ quy giúp code dễ hiểu hơn**: - **Xử lý được dữ liệu lớn** #### Nhược điểm Bao gồm các nhược điểm của đệ quy. - **Không phải là giải pháp tối ưu cho mọi bài toán** ## Sắp xếp ### Mở đầu - Cho trước mảng $a$ có $n$ phần tử, in mảng theo thứ tự không giảm. - Trong bài viết, mặc định tất cả thuật toán đều sắp xếp theo thứ tự không giảm. - Thông thường, không nhiều bài toán chỉ đơn giản sắp xếp là xong, mà sắp xếp lại dữ liệu là một bước đệm để thực hiện các thuật toán phức tạp hơn trên dữ liệu đã sắp xếp cho dễ thao tác. ### Các thuật toán sắp xếp  #### Comparison-based sorting algorithms (thuật toán dựa trên phép so sánh) Đây là các thuật toán sắp xếp phổ biến mà các bạn có thể đã biết hoặc sẽ được học khi mới bắt đầu. - **Selection sort** - Duyệt qua lần lượt từng phần tử từ $1$ đến $n-1$. - Giả sử đang ở phần tử thứ $i$, tìm phần tử có giá trị nhỏ nhất trong đoạn $[i + 1,n]$ rồi đổi chỗ với phần tử thứ $i$. - Độ phức tạp thời gian: - Tệ nhất: $O(n^2)$. - Trung bình: $O(n^2)$. - Tốt nhất: $O(n^2)$. - **Bubble sort** - Lần lượt bắt đầu từ các vị trí $1$ đến $n-1$. - Giả sử đang bắt đầu ở vị trí $i$, lần lượt duyệt toàn bộ $j$ $\in$ $[i,n - 1]$. - Nếu $a[j] > a[j + 1]$ thì đổi chỗ hai phần tử này. - Độ phức tạp thời gian: - Tệ nhất: $O(n^2)$. - Trung bình: $O(n^2)$. - Tốt nhất: $O(n)$. - **Quick sort** - Giả sử muốn sắp xếp đoạn $[l,r]$ (cả mảng là $[1,n]$). - Chọn một vị trí $p$ bất kỳ thuộc đoạn $[l,r]$. - Duyệt qua các phần tử trong mảng, nếu $a_i < a_p$ thì phần tử thứ $i$ nằm trước $p$, ngược lại nằm sau $p$ (cài đặt chỗ này phải khéo một tí). - Bây giờ mảng đã chia thành 2 nửa ($[l,p - 1]$ và $[p + 1,r])$, dùng chia để trị để tiếp tục sắp xếp 2 nửa này (cài đặt chỗ này phải khéo một tí). - Độ phức tạp thời gian: - Tệ nhất: $O(n^2)$. - Trung bình: $O(n \cdot log_2(n))$. - Tốt nhất: $O(n \cdot log_2(n))$. - **Merge sort** - Giả sử muốn sắp xếp đoạn $[l,r]$. - Chọn vị trí $mid = \frac{(l + r)}{2}$. - Giả sử đoạn $[l,mid]$ và $[mid + 1,r]$ đã được sắp xếp (dùng chia để trị). - Sử dụng 2 con trỏ để ghép 2 mảng con đã sắp xếp thành mảng ban đầu đã sắp xếp (cài đặt chỗ này phải khéo một tí, có dùng mảng phụ). - Độ phức tạp thời gian: - Tệ nhất: $O(n \cdot log_2(n))$. - Trung bình: $O(n \cdot log_2(n))$. - Tốt nhất: $O(n \cdot log_2(n))$. #### Non-comparison-based sorting algorithms (thuật toán không dựa trên phép so sánh) Đây là các thuật toán ít gặp hơn đối với các bạn theo lập trình thi đấu, hầu như ít được chú ý nhưng cũng rất hữu dụng trong một số tình huống đặc biệt. Ta sẽ chỉ đi qua counting sort vì radix sort tương đối phức tạp. - **Counting sort** - Dùng mảng đếm và ghi lại tần số xuất hiện của các phần tử trong mảng gốc, rồi duyệt qua mảng đếm để in các phần tử ra. - Độ phức tạp thời gian: - Tệ nhất: $O(n + k)$. - Trung bình: $O(n + k)$. - Tốt nhất: $O(n + k)$. - Với $k$ là giá trị lớn nhất trong mảng ban đầu. #### Hybrid sorting algorithms (kết hợp 2 thuật toán sắp xếp trở lên) Đây là các thuật toán mạnh thường được cài sẵn trong ngôn ngữ lập trình, ta sẽ chỉ đi qua sơ lược vì việc cài đặt lại chúng là không cần thiết cũng như chắc chắn tốc độ không thể nhanh bằng dùng hàm có sẵn. - **Tim sort** - Kết hợp merge sort và insertion sort. - Là thuật toán sort có sẵn trong Python và Java. - **Intro sort** - Kết hợp quick sort, heap sort và insertion sort. - Là thuật toán sort có sẵn trong C++. - Vì là thuật toán rất mạnh và chủ đề của chúng ta là C++ nên sẽ có một mục riêng cho nó. ### Intro sort - Như đã đề cập bên trên, intro sort là sự kết hợp giữa quick sort, heap sort và insertion sort. - Intro sort tận dụng tốt tốc độ trung bình cao của quick sort, heap sort để xử lý tình huống tệ của quick sort và insertion sort để dùng cho mảng có kích thước nhỏ. - Độ phức tạp thời gian: - Tệ nhất: $O(n \cdot log_2(n))$. - Trung bình: $O(n \cdot log_2(n))$. - Tốt nhất: $O(n \cdot log_2(n))$. - Cách sử dụng trong C++: - Giả sử cần sắp xếp không giảm ***nửa khoảng*** $[l,r)$ trong mảng $a$. - Cú pháp: sort($a + l$, $a + r$). - Với trường hợp sử dụng custom comparator (phép so sánh tự định nghĩa), thì cú pháp là: sort($a + l$, $a + r$, "tên hàm so sánh"). ### Custom comparator C++ - Về bản chất, C++ không có hàm sắp xếp tăng hay giảm, mà dựa theo nguyên lý xác định xem khi nào phần tử $x$ đứng trước phần tử $y$. - Ví dụ như sort không giảm mặc định, ta hiểu rằng phần tử $x$ đứng trước $y$ khi giá trị của $x$ nhỏ hơn giá trị của $y$. - Ví dụ về hàm so sánh: - Giả sử muốn phần tử $x$ đứng trước phần tử $y$ khi giá trị của $x$ lớn hơn giá trị của $y$, mình đặt hàm tên là $cmp$. - Cú pháp: ```cpp! bool cmp(int a,int b){ return a > b; } ``` - Chú ý điều kiện trả về, nếu nó là $true$ có nghĩa là phần tử $a$ sẽ đứng trước phần tử $b$ và ngược lại nếu là $false$. - Cú pháp nếu dùng hàm $cmp$: sort($a + l$,$a + r$,$cmp$). - Không chỉ các kiểu dữ liệu có sẵn như int hay long long, ta hoàn toàn có thể sử dụng lên các struct hoặc các cái khác nâng cao hơn. ### Bài tập ## Tìm kiếm Tìm kiếm là một quy trình hoặc tập hợp các bước có hệ thống để tìm kiếm một phần tử cụ thể trong một cấu trúc dữ liệu như: - Mảng - Danh sách liên kết - Cây - Đồ thị Tùy vào loại dữ liệu và yêu cầu cụ thể mà có nhiều loại thuật toán tìm kiếm khác nhau. ### Linear Search - **Cách hoạt động:** Duyệt qua từng phần tử có trong cấu trúc dữ liệu từ đầu đến cuối đến khi tìm ra phần tử cần tìm hoặc thông báo là không tồn tại - **Điều kiện:** Không có - **Độ phức tạp:** $O(t \cdot n)$ > Vớí $t$ là độ phức tạp cho việc so sánh phần tử hiện tại với phần tử cần tìm - **Ưu điểm:** Đơn giản, dễ hiểu, dễ cài đặt, giải quyết được cho mọi bài toán - **Nhược điểm:** Độ phức tạp lớn - ### Tìm kiếm nhị phân (Binary Search) #### Vấn đề đặt ra Bạn có một quyển sách Ngữ Văn 300 trang siêu dài và bạn muốn tìm một trang cụ thể. Bạn sẽ làm sao? #### Thuật toán ngây thơ Bạn sẽ lần lượt lật từng trang một cho tới khi tìm được trang bạn muốn. #### Cải tiến thuật toán **Nhận xét**: Các trang từ điển được đánh số tăng dần Từ đây, ta có thể chia quyển sách ra thành $2$ nửa, $1$ nửa từ điểm bắt đầu đến vị trí ta chia nửa và $1$ nửa từ vị trí ta chia nửa đến cuối sách. Nếu trang sách mà ta chọn lớn hơn trang sách ta muốn, ta chỉ cần tìm kiếm tiếp trong đoạn từ đầu sách đến vị trí ta chọn và ngược lại. Dễ thấy rằng, nếu vị trí được chọn luôn ở giữa nó sẽ giúp cho việc tìm kiếm nhanh hơn, do số lượng trang ta phải xem xét sẽ luôn được **bỏ bớt phân nửa**. ![bai9-01](https://hackmd.io/_uploads/SJCYwc1YJx.gif) #### Điều kiện để có thể tìm kiếm nhị phân Để có thể thức hiện thuật toán tìm kiếm nhị phân. Ta phải đảm bảo rằng dãy số cần phải **tuyến tính** (có sự tăng hoặc giảm liên tục). #### Một số cách cài đặt thuật toán ```c++=101 int low = -1, high = n + 1; while(low < high - 1){ int mid = (low + high) / 2; if(a[mid] > target){ high = mid; } else{ low = mid; } } cout << low << "\n"; ``` ```c++=101 int answer = 0; for(int i = 31 - __builtin_clz(n); i >= 0; i--){ int base = answer | (1 << i); if(base <= n && a[base] <= target){ answer = base; } } cout << answer << "\n"; ``` ```c++=101 int Dnc(int l, int r, int target){ if(l == r){ return l; } else{ int m = l+r>>1; if(a[m] >= target){ return Dnc(l, m, target); } else return Dnc(m + 1, r, target); } assert(1 == 0); return -1; } ``` #### Một số ứng dụng của tìm kiếm nhị phân Ngoài tìm kiếm nhị phân bình thường, ta có thể sử những ứng dụng khác như tìm kiếm nhị phân trên hàm số. ##### Tìm kiếm nhị phân trên hàm số nguyên ##### Định nghĩa Giả sử chúng ta có một hàm boolean f(x). Thông thường, trong các bài toán như vậy, chúng ta muốn tìm giá trị lớn nhất hoặc nhỏ nhất của x sao cho f(x) trả về true. Tương tự như cách tìm kiếm nhị phân trên một mảng chỉ hoạt động khi mảng đã được sắp xếp, tìm kiếm nhị phân trên đáp án chỉ hoạt động nếu hàm đáp án có tính **tuyến tính**, tức là nó luôn không giảm hoặc luôn không tăng. ##### Ví dụ Có n cuốn sách, cuốn sách thứ i nằm ở vị trí A[i] . Ta muốn lấy ra k cuốn để đọc. Ta nghĩ rằng nếu lấy ra hai cuốn quá gần nhau thì sẽ làm giá sách mất thẩm mĩ. Vậy nên ta muốn tìm cách chọn k cuốn sách sao cho khoảng cách nhỏ nhất giữa hai cuốn sách liên tiếp được lấy ra là lớn nhất có thể. Ví dụ, nếu ta lấy ra những cuốn sách ở vị trí 3 , 10 , 7 , 1 , thì khoảng cách nhỏ nhất giữa hai cuốn sách liến tiếp là 2 , là khoảng cách giữa quyển sách ở vị trí 1 và 3. Trong bài này đầu tiên, ta sắp xếp mảng vị trí sách A theo thứ tự tăng dần. Ta thực hiện tìm kiếm nhị phân trên khoảng cách tối thiểu giữa hai cuốn sách, với giới hạn dưới là 1 và giới hạn trên là A[n−1]−A[0]. Với mỗi giá trị khoảng cách d ở giữa, ta kiểm tra xem có thể chọn được k cuốn sách sao cho khoảng cách giữa mọi cặp liên tiếp trong tập hợp được chọn không nhỏ hơn d hay không. Điều này có thể thực hiện bằng cách tham lam: chọn cuốn sách đầu tiên, sau đó chọn cuốn tiếp theo sao cho cách ít nhất d so với cuốn trước đó. Nếu chọn được ít nhất k cuốn, ta thử tăng d, ngược lại, ta giảm d. Sau khi kết thúc tìm kiếm nhị phân, ta thu được giá trị d lớn nhất thỏa mãn điều kiện. Độ phức tạp của thuật toán là O(nlog(A[n−1]−A[0])). **Code mẫu**: ::: spoiler code ``` c++ #include<bits/stdc++.h> using namespace std; const int maxN = 1e6+12; const int inf = 1e9; int n, k; int a[maxN]; bool check(int m) { int cnt = 1, last = a[1]; for(int i = 1; i <= n; i++){ if(a[i] - last >= m){ last = a[i]; ++cnt; } } if(cnt >= k) return true; else return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); int l = 1, r = inf, ans = 0; while(l <= r){ int mid = (l + r) >> 1; if(check(mid)){ ans = mid; l = mid + 1; } else r = mid - 1; } cout << ans << '\n'; return 0; } ``` ::: ##### Tìm kiếm nhị phân trên hàm số thực Có một số bài yêu toán yêu cầu chúng ta trả ra số thực. Vì vậy chúng ta sẽ chặt với số lần cố định, khoảng 50 lần để có thể cân bằng giữa thời gian và độ chính xác. ```c++=101 double low = 0, high = n; for(int i = 1; i <= 50; i++){ double mid = (low + high) / 2; if(mid....) // check dieu kien { l = mid; } else r = mid; } cout << setprecision(10) << l << "\n"; ```