Dãy truy hồi

Mức độ: Cơ bản

Nhiều bài đếm không có công thức trực tiếp, nhưng có một quy luật: đáp số của bài lớn tính được từ đáp số của các bài nhỏ hơn. Quy luật đó gọi là công thức truy hồi. Biết lập công thức truy hồi là bước đầu tiên để học quy hoạch động, dạng bài quan trọng bậc nhất trong thi học sinh giỏi.

Ví dụ: tháp Hà Nội

Có n đĩa to nhỏ khác nhau xếp ở cọc A (to dưới, nhỏ trên). Cần chuyển hết sang cọc C, mỗi lần chuyển một đĩa, không bao giờ đặt đĩa to lên đĩa nhỏ, được dùng cọc B làm trung gian. Ít nhất bao nhiêu lần chuyển?

Gọi h(n) là số lần ít nhất. Muốn chuyển đĩa to nhất xuống đáy cọc C thì trước đó n - 1 đĩa nhỏ phải nằm hết ở cọc B. Vậy:

1. Chuyển n - 1 đĩa nhỏ từ A sang B: h(n - 1) lần.
2. Chuyển đĩa to nhất từ A sang C: 1 lần.
3. Chuyển n - 1 đĩa nhỏ từ B sang C: h(n - 1) lần.

h(n) = 2 × h(n - 1) + 1, với h(1) = 1.

n	1	2	3	4	5
h(n)	1	3	7	15	31

Nhìn bảng sẽ đoán được h(n) = 2ⁿ - 1 (một cấp số nhân trừ 1).

Cách lập công thức truy hồi: xét bước cuối

Leo cầu thang n bậc, mỗi bước leo 1 hoặc 2 bậc. Có bao nhiêu cách? Xét bước cuối cùng:

• Bước cuối leo 1 bậc: trước đó đã leo hết n - 1 bậc, có f(n - 1) cách.
• Bước cuối leo 2 bậc: trước đó đã leo hết n - 2 bậc, có f(n - 2) cách.

Hai trường hợp không trùng nhau (quy tắc cộng): f(n) = f(n - 1) + f(n - 2), với f(0) = 1 (đứng yên), f(1) = 1. Đây là dãy Fibonacci.

Ba bước để lập công thức truy hồi:

1. Đặt tên cho đại lượng cần tìm theo kích thước bài toán: f(n) = số cách với n bậc.
2. Xét bước cuối (hoặc phần tử cuối, đĩa to nhất…), chia trường hợp.
3. Viết giá trị ban đầu cho các n nhỏ nhất.

Tính từ dưới lên, đừng gọi đệ quy thẳng

Viết hàm đệ quy theo đúng công thức f(n) = f(n - 1) + f(n - 2) thì f(n - 2) bị tính lại nhiều lần, số lần gọi hàm tăng theo cấp số nhân (xem bài Đệ quy). Cách đúng: tính lần lượt f(0), f(1), f(2), … và lưu vào mảng, mỗi giá trị chỉ tính một lần.

Python

n = int(input())
f = [0] * (n + 2)
f[0], f[1] = 1, 1
for i in range(2, n + 1):
    f[i] = f[i - 1] + f[i - 2]      # mỗi giá trị chỉ tính một lần
print(f[n])                          # n = 10 in ra 89

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> f(n + 2);
    f[0] = 1;
    f[1] = 1;
    for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];   // mỗi giá trị chỉ tính một lần
    cout << f[n] << endl;                                      // n = 10 in ra 89
    return 0;
}

Lưu ý: dãy truy hồi thường tăng rất nhanh. f(90) đã gần 4,6 × 10¹⁸, sát giới hạn long long. Khi n lớn hơn, đề sẽ yêu cầu chia lấy dư; khi n tới 10¹⁸ thì dùng lũy thừa ma trận.

Quy hoạch động: truy hồi trên bảng

Robot đi từ góc trên trái đến góc dưới phải của lưới, mỗi bước sang phải hoặc xuống dưới, không đi vào ô cấm. Gọi f[i][j] là số đường đi tới ô (i, j). Xét bước cuối: robot đến (i, j) từ ô bên trên hoặc ô bên trái:

f[i][j] = f[i - 1][j] + f[i][j - 1] (bằng 0 nếu (i, j) là ô cấm).

Đây vẫn là công thức truy hồi, chỉ là theo hai chiều. Quy hoạch động chính là: chia bài thành bài nhỏ, lập công thức truy hồi, tính lần lượt và lưu kết quả.

Luyện tập

Gồm 20 bài, chia thành 3 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Truy hồi bậc một

Bài 1. Tháp Hà Nội

Nhập n (1 ≤ n ≤ 62). In ra số lần chuyển đĩa ít nhất để chuyển n đĩa của tháp Hà Nội.

Ví dụ: nhập 3 thì in ra 7.

Kiểm tra: nhập 20.

Xem đáp số

1048575

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Dãy Collatz

Từ số nguyên dương n, lặp lại: nếu n chẵn thì chia đôi, nếu n lẻ thì thay bằng 3n + 1, cho tới khi n = 1. Nhập n (n ≤ 10¹²), in ra số bước.

Ví dụ: nhập 6 thì in ra 8.

Kiểm tra: nhập 27.

Xem đáp số

111

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Dãy Collatz dài nhất

Nhập n (n ≤ 10⁶). Trong các số từ 1 đến n, số nào có dãy Collatz (bài 2) nhiều bước nhất? In ra số đó và số bước (nếu nhiều số cùng nhiều bước nhất thì in số nhỏ nhất).

Ví dụ: nhập 10 thì in ra 9 19.

Kiểm tra: nhập 1000.

Xem đáp số

871 178

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Bài toán Josephus

n người đứng thành vòng tròn, đánh số 1 đến n. Bắt đầu từ người số 1, đếm 1, 2, …, k; người được đếm đến k bị loại, rồi đếm tiếp từ người kế tiếp. Nhập n, k (n, k ≤ 10⁶), in ra số thứ tự người còn lại cuối cùng.

Ví dụ: nhập 5 2 thì in ra 3.

Kiểm tra: nhập 41 3.

Xem đáp số

31

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Cắt bánh pizza

Cắt một chiếc bánh tròn bằng n nhát dao thẳng (n ≤ 10⁹). Được nhiều nhất bao nhiêu miếng?

Ví dụ: nhập 3 thì in ra 7.

Kiểm tra: nhập 10.

Xem đáp số

56

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Gửi tiết kiệm

Bạn An có x đồng. Cuối mỗi tháng, tiền được cộng lãi r% (làm tròn xuống đến đồng) rồi An gửi thêm m đồng. Nhập x, r, m, T (x, m ≤ 10⁹, 1 ≤ r ≤ 10, T ≤ 10¹², chắc chắn đạt được). Sau ít nhất bao nhiêu tháng số tiền ≥ T?

Ví dụ: nhập 1000 10 0 2000 thì in ra 8.

Kiểm tra: nhập 5000000 1 500000 50000000.

Xem đáp số

61

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Truy hồi bậc hai

Bài 7. Lát gạch 2 × n

Lát kín một hình chữ nhật 2 × n bằng các viên gạch 1 × 2 (được xoay). Nhập n (1 ≤ n ≤ 85), in ra số cách lát.

Ví dụ: nhập 3 thì in ra 3.

Kiểm tra: nhập 10.

Xem đáp số

89

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Cầu thang có bậc hỏng

Cầu thang n bậc (n ≤ 10⁵), mỗi bước leo 1 hoặc 2 bậc, không được dẫm vào các bậc hỏng. Dòng đầu có n, k; dòng thứ hai có k số thứ tự bậc hỏng (từ 1 đến n - 1). In ra số cách leo lên bậc n chia lấy dư cho 10⁹ + 7.

Ví dụ:

Nhập	In ra
5 1 2	2

Kiểm tra: nhập

12 3
3 6 9

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Lát gạch 3 × n

Lát kín hình chữ nhật 3 × n bằng gạch 1 × 2. Nhập n (n chẵn, 2 ≤ n ≤ 60), in ra số cách lát.

Ví dụ: nhập 2 thì in ra 3.

Kiểm tra: nhập 8.

Xem đáp số

153

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Không có ba số 1 liền nhau

Nhập n (n ≤ 70). Đếm các dãy nhị phân độ dài n không có ba chữ số 1 đứng liền nhau.

Ví dụ: nhập 3 thì in ra 7.

Kiểm tra: nhập 10.

Xem đáp số

504

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Xâu không có hai chữ A liền nhau

Nhập n (1 ≤ n ≤ 35). Đếm các xâu độ dài n chỉ gồm các chữ A, B, C mà không có hai chữ A đứng liền nhau.

Ví dụ: nhập 2 thì in ra 8.

Kiểm tra: nhập 5.

Xem đáp số

164

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Tô màu vòng tròn

Có n ô xếp thành vòng tròn (n ≥ 3, n ≤ 60). Tô mỗi ô bằng một trong 3 màu sao cho hai ô kề nhau khác màu (ô cuối kề ô đầu). Có bao nhiêu cách tô?

Ví dụ: nhập 3 thì in ra 6.

Kiểm tra: nhập 6.

Xem đáp số

66

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Dãy Jacobsthal

Dãy a₁ = 1, a₂ = 1, a_n = a_{n - 1} + 2a_{n - 2}. Nhập n (n ≤ 62), in ra a_n.

Ví dụ: nhập 5 thì in ra 11.

Kiểm tra: nhập 10.

Xem đáp số

341

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Quy hoạch động đơn giản

Bài 14. Đường đi trên lưới có ô cấm

Dòng đầu có m, n (m, n ≤ 1000). m dòng tiếp theo là lưới gồm . và # (ô cấm). Robot đi từ ô (1, 1) đến ô (m, n), mỗi bước sang phải hoặc xuống dưới, không vào ô cấm. In ra số đường đi chia lấy dư cho 10⁹ + 7.

Ví dụ:

Nhập	In ra
3 3 ... .#. ...	2

Kiểm tra: nhập

4 5
.....
..#..
.#...
.....

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Nhặt nhiều quà nhất

Dòng đầu có m, n (m, n ≤ 1000). m dòng tiếp theo mỗi dòng n số tự nhiên: số quà ở mỗi ô. Đi từ ô (1, 1) đến ô (m, n), mỗi bước sang phải hoặc xuống dưới, nhặt hết quà ở các ô đi qua. Nhặt được nhiều nhất bao nhiêu quà?

Ví dụ:

Nhập	In ra
2 3 1 3 1 1 5 1	10

Kiểm tra: nhập

4 4
1 3 1 2
2 1 5 1
4 2 1 3
0 6 2 1

Xem đáp số

18

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Tam giác số

Dòng đầu là n (n ≤ 1000). n dòng tiếp theo, dòng thứ i có i số nguyên. Đi từ đỉnh xuống đáy, mỗi bước xuống số ngay dưới hoặc dưới bên phải. Tìm tổng lớn nhất của các số trên đường đi.

Ví dụ:

Nhập	In ra
3 1 2 3 4 5 6	10

Kiểm tra: nhập

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Xem đáp số

30

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Ếch nhảy tốn ít sức nhất

Có n hòn đá (n ≤ 10⁵), hòn thứ i cao h_i. Con ếch ở hòn 1, mỗi lần nhảy tới hòn i + 1 hoặc i + 2, tốn sức bằng chênh lệch độ cao |h_i - h_j|. Ít nhất tốn bao nhiêu sức để tới hòn n? Dòng đầu là n, dòng hai là các độ cao.

Ví dụ:

Nhập	In ra
4 10 30 40 20	30

Kiểm tra: nhập

8
5 2 8 6 4 9 1 7

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Số cách đổi tiền

Dòng đầu có n, k (n ≤ 10⁵, k ≤ 100). Dòng thứ hai có k mệnh giá tiền khác nhau. Có bao nhiêu cách đổi n đồng thành các tờ tiền (mỗi mệnh giá dùng bao nhiêu tờ cũng được, không tính thứ tự)? In ra kết quả chia lấy dư cho 10⁹ + 7.

Ví dụ:

Nhập	In ra
5 3 1 2 5	4

Kiểm tra: nhập

20 4
2 3 5 10

Xem đáp số

16

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Ít tờ tiền nhất

Dòng đầu có n, k (n ≤ 10⁵, k ≤ 100). Dòng thứ hai có k mệnh giá khác nhau. Đổi n đồng thành ít tờ tiền nhất có thể. In ra số tờ, hoặc -1 nếu không đổi được.

Ví dụ:

Nhập	In ra
11 3 1 2 5	3

Kiểm tra: nhập

30 3
1 15 25

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Dãy con tăng dài nhất

Dòng đầu là n (n ≤ 5000). Dòng thứ hai có n số nguyên. Tìm độ dài dãy con tăng ngặt dài nhất (chọn các phần tử theo đúng thứ tự xuất hiện, không cần liền nhau).

Ví dụ:

Nhập	In ra
6 5 2 8 6 3 6	3

Kiểm tra: nhập

10
3 10 2 1 20 4 6 7 15 9

Xem đáp số

5

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.