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

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

Và bài test cuối cùng: Sudoku