TAILIEUCHUNG - Sáng tạo trong kỹ thuật và lập trình

Tài liệu dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Sáng tạo trong kỹ thuật và lập trình | Thi HSG Quốc gia 2010 CCKLK Dãy con chung không liền kề dài nhất Cho dãy số nguyên dương x x1 x2 . xn . Dãyy xi1 xi2 . xik được gọi là dãy con không liền kề của dãy x nếu 1 i1 i2-1 . ik-1 n. Cho 2 dãy số nguyên a gồm n phần tử và b gồm m phần tử. Xác định chiều dài k của dãy con chung không liền kề dài nhất của a và b. 2 m n 1000 1 ai bi 10000. 5 6 1 5 3 8 2 2 1 3 4 2 6 2 Giải thích Dòng đầu n m. Từ dòng thứ hai trở đi Dãy số a tiếp đến là dãy số b. k. Thuật toán Quy hoạch động. Gọi d i j là đáp số của bài toán khi xét hai dãy a và b . Ta có Nếu i 0 thì ta quy ước d i j 0 Nếu a i b j thì d i j d i-2 j-2 Nếu a i b j thì d i j max d i-1 j d i j-1 . Để cài đặt ta dùng 3 mảng một chiều x y và z với ý nghĩa x j d i-2 j y j d i-1 j và z j d i j . Khi đó hệ thức trên được viết là Nếu i 0 thì ta quy ước d i j 0 Nếu a i b j thì d i j d i-2 j-2 ứng với z j x j-2 Nếu a i b j thì d i j max d i-1 j d i j-1 ứng với z j max y j z j-1 . Muốn tránh các phép copy dữ liệu từ y sang x từ z sang y và từ x sang z ta chỉ cần tráo đổi các con trỏ mảng. Độ phức tạp O Chương trình Pascal k chieu dai day con chung khong lien ke dai nhat cua hai day so nguyen duong a b const fn gn bl 32 nl 13 10 mn 1001 type int integer mi1 array of int var n m int a b mi1 function Max a b int int begin if a b then Max a else Max b end procedure Doc var i int f text begin assign f fn reset f read f n m writeln n bl m for i 1 to n do read f a i for i 1 to m do read f b i write nl a for i 1 to n do write a i bl write nl b for i 1 to n do write b i bl close f end procedure Ghi k int var g text begin assign g gn rewrite g writeln g k close g end d i j dap so cua bai toan voi a b d i j d i-2 j-2 1 if a i b j Max begin d i j-1 d i-1 j end elsewhere 0 if i 1 j 1 function QHD int var i j v int c array of mi1 x y z t int begin x 1 y 2 z 3 Init i 0 fillchar c x sizeof c x 0 Init i 1 c y 0 0 v 0 for j 1 to m do .

• Kỹ thuật lập trình
• lập trình
• kỹ thuật lập trình
• sáng tạo trong lập trình
• lý thuyết lập trình
• tài liệu lập trình
• kinh nghiệm lập trình
• code lập trình
• kỹ thuật phần mềm
• chương trình lập trình
• lập trình máy tính
• giáo trình lập trình
• lập trình SQL
• giáo trình lập trình SQL
• tài liệu lập trình SQL
• ngôn ngữ lập trình SQL
• tự học lập trình SQL
• Cơ sở lập trình
• Bài giảng cơ sở lập trình
• Ngôn ngữ lập trình
• Bài tập lập trình
• Cấu trúc lặp
• Cú pháp câu lệnhNgôn ngữ lập trình
• thủ thuật lập trình
• lập trình căn bản
• kỹ thuật máy tính
• lập trình hướng đối tượng
• chuyên ngành lập trình
• tổng quan về lập trình
• ngôn ngữ C++
• lập trình C++
• ngôn ngữ lập trình bậc cao
• bài giảng lập trình C++
• ngôn ngữ lập trình C
• phương pháp lập trình cấu trúc
• phép tham chiếu
• lập trình Visual C++
• Lập trình C trên Windows
• phần mềm máy tính
• mẹo lập trình
• Lập trình Windows
• lập trình java
• Lập trình mạng bằng java
• Lập trình song song
• Ôn tập lập trình C++
• Ôn thi lập trình C++
• Cách học lập trình C++
• Tài liệu lập trình C++
• Đề thi lập trình C++
• Ngôn ngữ lập trình C++
• lập trình đối tượng
• phương pháp lập trình
• Lập trình đa luồng làm việc
• Lập trình đa luồng
• Tổng quan lập trình đa luồng
• Kỹ thuật lập trình Windows
• Phương pháp lập trình Windows
• Ngôn ngữ lập trình Windows
• Học lập trình C
• Lập trình mạng
• Kỹ thuật lập trình C
• Lập trình C
• Lập trình Android
• Lập trình Pascal
• Lập trình Visual Basic
• Lý thuyết ngôn ngữ lập trình
• Bài giảng lý thuyết ngôn ngữ lập trình
• Lập trình Mobile
• Tự học lập trình
• Lập trình Web
• Bài giảng lập trình Web
• Lập trình PHP
• Lập trình di động
• Giới thiệu PHP
• Kiểu dữ liệu lập trình PHP
• Mảng trong lập trình
• Chuỗi ký tự lập trình
• lập trình ASP
• ngôn ngữ kịch bản
• Lập trình hợp ngữ
• lập trình tuyến tính
• Giáo trình ngôn ngữ lập trình Java
• Kỹ thuật lập trình Java