TAILIEUCHUNG - 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 •. | 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 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 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 đó. 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ó .

Uyển Như 126 5 pdf

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Tổng quan về ứng dụng công nghệ thông tin - truyền thông trong giáo dục

3 401 8

Mô tả công việc Giám đốc công nghệ thông tin

2 390 0

Luận văn: Tính toán hiệu quả chuyển giao công nghệ thông tin thông qua thị trường tin học

76 278 3

Công nghệ thông tin và ứng dụng công nghệ thông tin trong dạy học

8 386 15

Chương trình giáo dục Đại học theo học chế tín chỉ ngành: Công nghệ thông tin

28 289 0

Quyết định 995/QĐ-BTC năm 2013

5 277 0

Bài giảng Chương 2 - Thiết kế và quản lý dự án Công nghệ thông tin - PGS.TS Nguyễn Văn Định

26 310 1

Bài giảng Đại cương Công nghệ thông tin và truyền thông - ThS. GV. Phạm Quang Quyền

118 287 3

Giáo trình Tiếng Anh chuyên ngành Công nghệ thông tin

47 1247 85

Ebook Tìm hiểu Luật Công nghệ thông tin và các Nghị định hướng dẫn thi hành - NXB Bưu điện

74 359 6

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 461847 55

Giới thiệu :Lập trình mã nguồn mở

14 22528 57

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10867 529

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10030 445

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9491 104

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8245 1124

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8207 423

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7860 2220

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 6648 253

Vật lý hạt cơ bản (1)

29 5756 85

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 4

47 245 1 20-04-2024

Trading Strategies Profit Making Techniques For Stock_3

23 181 0 20-04-2024

extremetech Hacking Firefox phần 7

46 186 0 20-04-2024

Magnetic Bearings Theory and Applications phần 2

14 170 0 20-04-2024

TƯƠNG QUAN GIỮA MÔ HỌC, GIẢI PHẪU VÀ HÌNH ẢNH CỦA CÁC KHỐI U PHẦN PHỤ

3 167 0 20-04-2024

Management and Services Part 1

10 155 0 20-04-2024

Báo cáo nghiên cứu khoa học " KẾT QUẢ NGHIÊN CỨU BƯỚC ĐẦU VỀ THIÊN ĐỊCH CHÂN KHỚP TRÊN CÂY THANH TRÀ Ở THỪA THIÊN HUẾ "

7 173 0 20-04-2024

MySQL Basics for Visual Learners PHẦN 9

15 183 0 20-04-2024

Posted prices versus bargaining in markets_7

23 154 0 20-04-2024

THE ANTHROPOLOGY OF ONLINE COMMUNITIES BY Samuel M.Wilson and Leighton C. Peterson

19 138 0 20-04-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7860 2220

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 5608 1330

Ebook Chào con ba mẹ đã sẵn sàng

112 3752 1229

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 5256 1127

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8245 1124

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3474 641

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10867 529

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3670 524

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4024 513

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4105 478