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

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

1
516
lượt xem
135
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

Nội dung Text: Kỹ thuật đệ quy và quay lui

  1. 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
  2. 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ố
  3. 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
  4. 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
Đồng bộ tài khoản