Hàm tự tạo và đệ quy
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Ước, bội, ƯCLN, BCNN
- Chủ đề
- hàmđệ quy
- Trạng thái
Kiến thức cơ bản
Hàm tự tạo
Một hàm là một nhóm các câu lệnh cùng nhau thực hiện một nhiệm vụ. C++ cung cấp nhiều hàm có sẵn như sqrt, __gcd,... và chúng ta cũng có thể tự tạo các hàm như:
// Hàm trả về số lớn hơn trong hai số a và b
int maxOf(int a, int b) {
if (a > b) return a;
return b;
}
maxOf là tên hàm tự tạo (user-defined function); int là kiểu kết quả trả về, (int a, int b) là tham số. Trong thân hàm, lệnh return trả kết quả và kết thúc hàm.
Các điều cần nhớ khi sử dụng các hàm tự tạo trong lập trình:
- Hàm phải được viết trước chỗ gọi nó (thường viết phía trên hàm main);
- Tên hàm nên nói lên việc hàm làm, mỗi hàm chỉ nên làm một việc. Hàm giúp chia bài lớn thành các bước nhỏ, dễ kiểm tra từng bước và dùng lại nhiều lần.
- Biến cục bộ (local variable) là biến khai báo trong hàm, chỉ dùng được trong hàm đó; mỗi lần gọi hàm sẽ có biến mới. Biến toàn cục (global variable) khai báo bên ngoài mọi hàm, hàm nào cũng dùng được (dùng khi cần lưu dữ liệu chung).
Nếu thêm dấu & trước tên tham số (truyền theo tham chiếu), hàm làm việc trực tiếp trên biến gốc thay vì giá trị (truyền theo giá trị). Dấu & rất hữu ích khi cần hàm thay đổi biến (như hoán đổi hai số) và khi truyền vector để không phải sao chép cả vector (chậm khi vector lớn).
Ví dụ hàm swapVal để đổi giá trị trực tiếp trên 2 biến a, b.
// có & : a, b chính là biến gốc
void swapVal(int &a, int &b) {
int tmp = a; a = b; b = tmp;
}
Kiểu dữ liệu trả về của hàm swapVal là void (không kiểu), nên không cần lệnh return giá trị. Trường hợp muốn kết thức sớm dùng lệnh return;.
Hàm đệ quy
Đệ quy là khi một hàm tự gọi lại chính nó. Hãy tưởng tượng búp bê gỗ Nga Matryoshka:
- Mở búp bê cỡ lớn n, bên trong thấy con búp bê cỡ n-1.
- Mở tiếp búp bê cỡ n-1 bên trong thấy búp bê cỡ n-2.
- Cứ mở mãi cho đến khi chạm tới con búp bê bé nhất (búp bê tí hon đặc ruột) không thể mở được nữa.
- Sau khi chạm đáy, ta bắt đầu đóng nắp tính từng con lại từ nhỏ đến lớn.
Một hàm đệ quy luôn có hai phần:
- Trường hợp cơ sở (điểm dừng): bài toán nhỏ nhất mà ta trả lời được ngay (búp bê cuối cùng). Không có điểm dừng thì hàm gọi mãi không dừng và chương trình bị lỗi.
- Bước đệ quy: đưa bài toán về một bài toán nhỏ hơn cùng loại (gọi lại chính nó với đầu vào nhỏ hơn), rồi dùng kết quả đó để tính ra kết quả của bài toán hiện tại.
Ví dụ với giai thừa, n! = 1.2...(n-1).n. Dưới góc nhìn đệ quy thì n! = n.(n - 1)!, và 0! = 1 là điểm dừng.
long long factorial(int n) {
if (n == 0) return 1; // điểm dừng: 0! = 1
return n * factorial(n - 1); // bước đệ quy: n! = n.(n-1)!
}
Lưu ý khi viết đệ quy:
- Luôn viết điểm dừng trước, sau đó mới viết bước đệ quy.
- Mỗi lần gọi phải làm bài toán nhỏ hơn (ví dụ n - 1), nếu không sẽ không bao giờ đến điểm dừng.
- Nếu gọi lồng quá nhiều tầng (khoảng vài trăm nghìn tầng) thì chương trình cũng bị lỗi vì hết chỗ chứa các lời gọi đang chờ.
- Hãy luôn thử với số nhỏ (n = 0, 1, 2, 3) và chạy tay để kiểm tra điểm dừng và công thức.
Luyện tập
Bài 1. Mật mã đối xứng
Một số được gọi là đối xứng nếu đọc xuôi hay đọc ngược đều giống nhau (ví dụ 12321). Hãy viết một hàm trả về giá trị đúng/sai (kiểu bool) cho biết số n có đối xứng hay không, rồi dùng hàm đó để trả lời.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 109) | |
|---|---|---|
| Đầu ra | In ra YES nếu n là số đối xứng, ngược lại in ra NO | |
| Test | Input | Output |
| 12321 | YES | |
| 1200 | NO | |
Bài 2. Trọng tài thể thao
Hãy tìm thời gian nhỏ nhất và lớn nhất của các vận động viên trong một cuộc thi chạy.
| Đầu vào | Dòng 1: số nguyên dương n (1 ≤ n ≤ 105) Dòng 2: n số nguyên là thời gian chạy của các bạn (1 ≤ a[i] ≤ 109) | |
|---|---|---|
| Đầu ra | In ra hai số: thời gian nhỏ nhất và lớn nhất cách nhau khoảng trắng | |
| Test | Input | Output |
| 5 12 45 7 89 23 | 7 89 | |
- Gợi ý: viết hàm
void min_max(const vector<ll> &a, ll >nn, ll >ln)để giải bài toán.
Bài 3. Giai thừa
Giai thừa của n, viết là n!, là tích 1.2...n, quy ước 0! = 1. Em hãy tính n! bằng hàm đệ quy theo công thức n! = n. (n-1)!
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 20) | |
|---|---|---|
| Đầu ra | In ra giá trị của n! | |
| Test | Input | Output |
| 5 | 120 | |
| 20 | 2432902008176640000 | |
Bài 4. Lũy thừa bằng đệ quy
Hãy tính an bằng hàm đệ quy, dựa vào nhận xét an = a.an-1 và a0 = 1.
| Đầu vào | Hai số nguyên a, n (1 ≤ a ≤ 10; 0 ≤ n ≤ 18) | |
|---|---|---|
| Đầu ra | In ra giá trị của an | |
| Test | Input | Output |
| 2 10 | 1024 | |
| 10 18 | 1000000000000000000 | |
Bài 5. Dãy Fibonacci
Dãy Fibonacci (0, 1, 1, 2, 3, 5, 8, ...) bắt đầu bằng F0 = 0, F1 = 1, các số sau bằng tổng hai số đứng ngay trước nó: Fn = F(n-1) + F(n-2). Hãy tính Fn bằng hàm đệ quy.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 30) | |
|---|---|---|
| Đầu ra | In ra giá trị Fn | |
| Test | Input | Output |
| 10 | 55 | |
| 30 | 832040 | |
Bài 6. Đọc ngược bằng đệ quy
Máy đọc sách bị lỗi và đọc từ ký tự cuối về ký tự đầu. Hãy dùng hàm đệ quy để in chuỗi theo thứ tự ngược lại.
| Đầu vào | Một chuỗi s (|s| ≤ 1000) gồm chữ cái và chữ số, không có dấu cách | |
|---|---|---|
| Đầu ra | In ra chuỗi s theo thứ tự ngược lại dùng hàm đệ quy | |
| Test | Input | Output |
| hello | olleh | |
Bài 7. Leo cầu thang
Bạn Hùng muốn leo lên đỉnh cầu thang có n bậc. Mỗi bước bạn ấy có thể bước lên 1 bậc hoặc 2 bậc. Hỏi Hùng có bao nhiêu cách khác nhau để leo lên đúng đỉnh cầu thang (n bậc)? Ví dụ n = 3 có 3 cách: (1, 1, 1), (1, 2), (2, 1).
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 30) | |
|---|---|---|
| Đầu ra | Số cách leo lên n bậc cầu thang | |
| Test | Input | Output |
| 4 | 5 | |
| 10 | 89 | |
Bài 8. Tháp Hà Nội
Có 3 cọc đánh số 1, 2, 3 và n chiếc đĩa có kích thước khác nhau xếp chồng ở cọc 1, đĩa nhỏ nằm trên đĩa lớn. Mỗi lần chỉ được chuyển một đĩa trên cùng sang cọc khác và không được đặt đĩa lớn lên đĩa nhỏ. Hãy chuyển toàn bộ n đĩa sang cọc 3 với số lần chuyển ít nhất và in ra các bước chuyển.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 10) | |
|---|---|---|
| Đầu ra | Dòng 1: số lần chuyển ít nhất Các dòng tiếp theo: mỗi dòng gồm hai số a, b nghĩa là chuyển đĩa trên cùng của cọc a sang cọc b, theo đúng thứ tự thực hiện. | |
| Test | Input | Output |
| 3 | 7 1 3 1 2 3 2 1 3 2 1 2 3 1 3 | |
- Gợi ý: chuyển n-1 đĩa sang cọc phụ (2), chuyển đĩa lớn nhất sang cọc 3, rồi thực hiện bài toán nhỏ hơn: chuyển n-1 đĩa từ cọc 2 sang cọc 3 với cọc phụ là 1.
Bài tập tự luyện
Bài 1. Chênh lệch nhiệt độ
Một trạm khí tượng ghi lại nhiệt độ của n ngày. Hãy viết các hàm tìm giá trị lớn nhất và nhỏ nhất của dãy (truyền vector bằng tham chiếu), rồi in ra hiệu của chúng.
| Đầu vào | Dòng 1: số nguyên dương n (1 ≤ n ≤ 105) Dòng 2: n số nguyên là nhiệt độ từng ngày ghi nhận (|a[i]| ≤ 109) | |
|---|---|---|
| Đầu ra | Một số nguyên: giá trị lớn nhất trừ giá trị nhỏ nhất. | |
| Test | Input | Output |
| 5 3 -7 10 4 0 | 17 | |
Bài 2. Số có nhiều ước nhất
Viết một hàm đếm số ước của một số để giải bài toán: Trong các số từ 1 đến n, hãy tìm số có nhiều ước dương nhất, nếu có nhiều số cùng có số ước nhiều nhất thì chọn số nhỏ nhất.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 105) | |
|---|---|---|
| Đầu ra | In ra số tìm được và số lượng ước của nó cách nhau một dấu cách | |
| Test | Input | Output |
| 10 | 6 4 | |
| 100 | 60 12 | |
Bài 3. Gốc của một số
Từ một số n, ta cộng các chữ số của nó lại để được số mới; nếu số mới vẫn có từ hai chữ số trở lên thì lại cộng các chữ số của số đó, cho đến khi số còn lại có một chữ số. Chữ số cuối cùng đó gọi là gốc của n. Ví dụ 9875 → 29 → 11 → 2, nên gốc của 9875 là 2.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 1018) | |
|---|---|---|
| Đầu ra | In ra gốc của n | |
| Test | Input | Output |
| 9875 | 2 | |
| 1000000000000000000 | 1 | |
Bài 4. Xâu nhị phân không có hai số 1 liền nhau
Một xâu nhị phân là xâu chỉ gồm các ký tự 0 và 1. Có bao nhiêu xâu nhị phân độ dài n mà không có hai ký tự 1 đứng cạnh nhau? Ví dụ n = 3 có 5 xâu: 000, 001, 010, 100, 101.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 30) | |
|---|---|---|
| Đầu ra | Số lượng xâu thỏa mãn | |
| Test | Input | Output |
| 3 | 5 | |
| 5 | 13 | |
Bài 5. Liệt kê xâu nhị phân
Hãy liệt kê tất cả các xâu nhị phân có độ dài n theo thứ tự từ điển (từ nhỏ đến lớn), mỗi xâu trên một dòng.
| Đầu vào | Một số nguyên dương n (1 ≤ n ≤ 10) | |
|---|---|---|
| Đầu ra | Các xâu nhị phân độ dài n, mỗi xâu 1 dòng | |
| Test | Input | Output |
| 3 | 000 001 010 011 100 101 110 111 | |
- Gợi ý: xây dựng xâu từng ký tự, mỗi vị trí có hai lựa chọn là 0 hoặc 1, rồi gọi đệ quy cho vị trí tiếp theo.
Bài 6. Tổ hợp
Số cách chọn k phần tử từ n phần tử, ký hiệu C(n, k), thỏa công thức C(n, k) = C(n - 1, k - 1) + C(n - 1, k), với C(n, 0) = C(n, n) = 1. Hãy tính C(n, k).
| Đầu vào | Hai số nguyên n, k (0 ≤ k ≤ n ≤ 20) | |
|---|---|---|
| Đầu ra | In ra giá trị C(n, k) | |
| Test | Input | Output |
| 5 2 | 10 | |
Bài 7. Chia nhóm quà tặng
Có n món quà, món thứ i có giá trị a[i]. Hãy đếm xem có bao nhiêu cách chọn ra một số món quà (ít nhất một món) sao cho tổng giá trị đúng bằng S. Hai cách chọn khác nhau nếu có ít nhất một món quà khác nhau (các món có cùng giá trị vẫn được tính là khác nhau).
| Đầu vào | Dòng 1: số nguyên dương n, s (1 ≤ n ≤ 20; 1 ≤ s ≤ 2000) Dòng 2: n số nguyên (1 ≤ a[i] ≤ 100) | |
|---|---|---|
| Đầu ra | Số cách chọn có tổng bằng s | |
| Test | Input | Output |
| 3 5 5 5 5 | 3 | |
| 4 7 1 2 3 4 | 2 | |
- Gợi ý: với mỗi món quà có hai lựa chọn là chọn hoặc không chọn.
Bài 8. Lũy thừa nhanh
Hãy tính an chia lấy dư cho m, với n rất lớn.
| Đầu vào | Một dòng gồm 3 số nguyên a, n, m (1 ≤ a, m ≤ 109; 0 ≤ n ≤ 1018) | |
|---|---|---|
| Đầu ra | Phần dư của an khi chia cho m | |
| Test | Input | Output |
| 2 10 1000 | 24 | |
| 2 1000000000000000000 1000000007 | 719476260 | |
- Gợi ý: an = an/2.an/2 khi n chẵn, a.an/2.an/2 khi n lẻ, lấy dư sau mỗi phép nhân.