Bài giảng Môn Tin học lớp 11 - Kỹ thuật đệ quy và quay lui

Kỹ thuật đệ quy và quay lui
1. Dùng dữ liệu thay cho xử lý: mảng bool, mảng bit ... đánh dấu ứng cử viên đã dùng.
2. Dùng hàng rào giới hạn vùng xử lý: đặc trưng là bài mã đi tuần dùng ma trận (n+2)*(n+2) để dễ xử lý hơn.
3. Dùng câu lệnh IF để dễ dàng giới hạn dừng đệ quy: đặc biệt có ích khi xử lý bài map với dữ liệu mảng 2 chiều (IF i>10 ---> Tăng i, đưa j về 1 và exit). Đặt câu lệnh này trước quá trình đệ quy, với ý nghĩa là "điểm mốc" của đệ quy.
4. Đặt cờ báo đã tìm ra kết quả, chấm dựt sự đệ quy cũng như quay lui để tránh lãng phí thời gian "trả về các giá trị" trong chương trình quay lui.
Cấu trúc 1 thủ tục đệ quy:
begin
IF quá giới hạn OR tìm thấy THEN exit;
IF hết dòng THEN 
xuống dòng;
khởi tạo cột =1;
exit;
IF chưa sử dụng AND thỏa điều kiện
Gán vào;
Đánh dấu đã sử dụng;
Đệ quy bước kế tiếp;
Gỡ bỏ giá trị đã gán;
end;
Các bài tập:
1. Số hạng thứ k: 
Dãy số nguyên n<=30k ptử và số nguyên dương k<=n. Chỉ ra số hạng lớn thứ k trong dãy (có k số ko bé hơn nó và n-k số ko lớn hơn nó).
NumK.inp
NumK.out
4 2 
10
1
10
11
8
2. Phân số tối giản:
Xét tập cá phân số tối giản có giá trị nằm trong đoạn [0,1] và có mẫu số <=N. Các phân số này có thể đc sắp xếp theo thứ tự tăng dần. Với N cho trước, tập có phân số khác nhau thỏa điều kiện trên là 1 tập hữu hạn. Các phân số trong tập này đc đánh số thứ tự từ 1, như vậy mỗi phân số tương ứng một số thứ tự duy nhất. Ví dụ với N=6 tập có 11 phân số tối giản được sắp theo thứ tự: 
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
Theo dãy trên, phân số có thứ tự 3 là 1/4, phân số 3/5 có thứ tự là 7.
Yêu cầu: Cho trước N, xác định số thứ tự của phân số p/q hoặc ngược lại, cho số thứ tự của phân số hãy xác định phân số.
Dữ liệu vào từ Fraction.inp
_ N<500
Các dòng kế:
Ghi số 0: kết thúc file
Ghi số 1: tiếp theo là 2 số nguyên ko âm p, q thể hiện yêu cầu tìm STT phân số p/q
Ghi số 2: tiếp theo là số nguyên dương K thể hiện yêu cầu tìm phân số có STT là K.
Kết quả xuất ra Fraction.out gồm nhiều dòng, mỗi dòng ghi câu trả lời cho 1 dòng yêu cầu của input.
Fraction.inp
Fraction.out
5
7
1 3 5 
1 4 
2 3 
0
3. Tam giác Sierpinski
4. Lát gạch 
5. Chia tam giác: 
Trên 1 lưới ô vuông độ dài cạnh là 1, người ta thiết lập 1 đa giác lồi D gồm n đỉnh (n<=20), mỗi đỉnh đc xác định bằng cặp tọa độ (x,y) (|x|, |y|<=100).
Một tam giác đc gọi là cơ sở của D nếu có các đỉnh là đỉnh của D hoặc là điểm trên lưới nằm trong D và có diện tích =1/2.
Yêu cầu: lập trình chia D thành các tam giác cơ sở.
Dữ liệu vào từ Triangle.inp:
_ n<=20
_ Tọa độ mỗi đỉnh đa giác
Kết quả xuất ra Triangle.out:
_ M: số tam giác chia được (0: ko chia đc).
M dòng kế, mỗi dòng 6 số là tọa độ 3 đỉnh mỗi tam giác 
Triangle.inp
Triangle.out
4
9
0 0 
0 2 0 3 1 3 
0 3
0 2 1 3 1 2 
2 3 
0 2 1 2 0 1 
1 0 
1 1 1 2 0 1 
1 1 0 0 0 1 
1 1 0 0 1 0 
2 3 1 3 1 2 
2 3 1 1 1 2 
2 3 1 1 1 0 
6. Chuỗi nhị phân: 
Một chuỗi gồm toàn '0' và '1' là chuỗi nhị phân. Một đoạn liện tiếp k ký tự của chuỗi là chuỗi con độ dài k.
Yêu cầu: Cho trước k<16. Xác định chuỗi nhị phân dài nhất sao cho mỗi chuỗi con k chỉ xuất hiện 1 lần.
Dữ liệu vào từ Binstr.inp gồm 1 dòng chứa số k.
Kết quả ra file Binstr.out gồm 2 dòng: dòng đầu là độ dài chuỗi, dòng sau là chuỗi nhị phân tìm được.
Binstr.inp
Binstr.out
3
10
0001110100
7. Xây dựng chuỗi K:
Xét dãy số S gồm N ký số. Các sổ nguyên tạo thành dãy là các số từ 1 đến K cho trước. Một đoạn các ký số liên tiếp nhau của S là một dãy con. Hãy xây dựng S sao cho ko có 2 dãy con giống nhau đứng kề nhau.
Dữ liệu vào từ StringK.inp gồm một dòng chứ 2 số nguyên dương N<=30 và K<=5.
Kết quả ra file StringK.out gồm 1 dòng chứ N ký tự là các ký số của dãy tìm được. Nếu ko tìm đc in ra -1.
StringK.inp
StringK.out
6 3 
121312
8. Vòng số nguyên tố
Một vòng tròn chứ n vòng tròn nhỏ (n chẵn). Các vòng tròn nhỏ đc đánh số từ 1 đến n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ 1 đến n vào các vòng tròn nhỏ sao cho tổng của 2 số trên 2 vòng tròn nhỏ liên tiếp là số nguyên tố. Vòng tròn nhỏ số 1 luôn được ghi số 1.
Dữ liệu vào từ file Ring.inp chứa số n chẵn (2<n<20) 
Kết quả ra file Ring.out:
_ K: số cách điền số tìm đc 
K dòng tiếp theo mỗi dòng ghi một cách điền.
Ring.inp
Ring.out
6
2
1 4 3 2 5 6 
1 6 5 2 3 4 
Ring.inp
Ring.out
8
4
1 2 3 8 5 6 7 4 
1 2 5 8 3 4 7 6 
1 4 7 6 5 8 3 2 
1 6 7 4 3 8 5 2 
9. Map
Và bài test cuối cùng: Sudoku