Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Công Nghệ Thông Tin
Kỹ thuật lập trình
Bài toán dãy con đơn điệu tăng dài nhất
Đang chuẩn bị liên kết để tải về tài liệu:
Bài toán dãy con đơn điệu tăng dài nhất
Uyển Như
132
5
pdf
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Cho dãy số nguyên A = a1, a2, , an. (n ≤ 10000, -10000 ≤ ai ≤ 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2n dãy con. Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. Ví dụ: A = (1, 2, 3, 4, 9, 10, 5, 6, 7, 8). Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7, 8). Dữ liệu (Input) vào từ file văn bản INCSEQ.INP •. | Bài toán dãy con đơn điệu tăng dài nhất Cho dãy số nguyên A a1 a2 . an. n 10000 -10000 ai 10000 . Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2n dãy con. Yêu cầu Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. Ví dụ A 1 2 3 4 9 10 5 6 7 8 . Dãy con đơn điệu tăng dài nhất là 1 2 3 4 5 6 7 8 . Dữ liệu Input vào từ file văn bản INCSEQ.INP Dòng 1 Chứa số n Dòng 2 Chứa n số a1 a2 . an cách nhau ít nhất một dấu cách Kết quả Output ghi ra file văn bản INCSEQ.OUT Dòng 1 Ghi độ dài dãy con tìm được Các dòng tiếp ghi dãy con tìm được và chỉ số những phần tử được chọn vào dãy con đó. INCSEQ.INP INCSEQ.OUT 11 1 2 3 8 9 4 5 6 20 9 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 O 11 1 L 1 11 II II II II II II II O . 7 4- IJ H- sO o Cách giải Bổ sung vào A hai phần tử a0 - và an 1 ro. Khi đó dãy con đơn điệu tăng dài nhất chắc chắn sẽ bắt đầu từ a0 và kết thúc ở an 1. Với V i 0 i n 1. Ta sẽ tính L i độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại ai. 1. Cơ sở quy hoạch động bài toán nhỏ nhất L n 1 Độ dài dãy con đơn điệu tăng dài nhất bắt đầu tại an 1 w. Dãy con này chỉ gồm mỗi một phần tử ro nên L n 1 1. 2. Công thức truy hồi Giả sử với i từ n đến 0 ta cần tính L i độ dài dãy con tăng dài nhất bắt đầu tại ai. L i được tính trong điều kiện L i 1 L i 2 . L n 1 đã biết Dãy con đơn điệu tăng dài nhất bắt đầu từ ai sẽ được thành lập bằng cách lấy ai ghép vào đầu một trong số những dãy con đơn điệu tăng dài nhất bắt đầu tại vị trí aj đứng sau ai. Ta sẽ chọn dãy nào để ghép ai vào đầu Tất nhiên là chỉ được ghép ai vào đầu những dãy con bắt đầu tại aj nào đó lớn hơn ai để đảm bảo tính tăng và dĩ nhiên ta sẽ chọn dãy dài nhất để ghép ai vào đầu để đảm bảo tính dài nhất . Vậy L i được tính như sau Xét tất cả các chỉ số j trong khoảng từ i 1 đến n 1 mà aj ai chọn ra chỉ số jmax có L jmax lớn nhất. Đặt L i L jmax 1. 3. Truy vết Tại bước xây dựng dãy L mỗi khi tính L i L jmax 1 ta đặt T i jmax. Để lưu lại rằng Dãy con dài nhất bắt đầu tại ai sẽ có .
TÀI LIỆU LIÊN QUAN
Bài giảng Thuật toán ứng dụng: Quy hoạch động
Nan giải bài toán đưa đón con
Bài giảng Chương 3: Quy hoạch động
Sáng kiến kinh nghiệm THPT: Sử dụng quy hoạch động đề nâng cao năng lực giải quyết một số vấn đề về dãy con bằng ngôn ngữ lập trình C++
Bài giảng Thuật toán ứng dụng: Quy hoạch động - Trương Xuân Nam
Bài giảng Phân tích thiết kế giải thuật: Dynamic Programming - GV. Hà Đại Dương
Bài giảng Thuật toán ứng dụng: Tiếp cận chia để trị - Trương Xuân Nam
Sáng kiến kinh nghiệm: Một số kinh nghiệm tư duy áp dụng để tìm con đường khai thông nhằm giải quyết bài toán một cách gọn gàng
BÀI TOÁN QUY HOẠCH ĐỘNG ĐIỂN HÌNH.
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ĐH Bách khoa TP. HCM
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.