Kỹ thuật đệ quy và quay lui

Chia sẻ: Cao Chi Chinh | Ngày: | Loại File: DOC | Số trang:5

Thêm vào BST

Báo xấu

595
lượt xem 137
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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
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 (n
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