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 i10 --- 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....
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 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ố 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 (n7. 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
