Bài tập về dãy con đơn điệu tăng dài nhất năm 2024
|
Điểm: 400 (p) Thời gian: 0.2s Bộ nhớ: 512M Input: bàn phím Output: màn hình Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\). Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1 Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử. Test 1 Input
Output
Cho dãy A gồm n số nguyên, ký hiệu[a0, a1,…, an-1] . Tìm một dãy con đơn điệu tăng dài nhất của dãy A, biết một dãy con của A là dãy có được từ A bằng cách xóa đi một số phân tử của A. Ví dụ: dãy[1, 5, 9, 2, 3, 11, 8, 10, 4] có dãy con đơn điệu tăng dài nhất là [1, 2, 3, 8, 10].
Số dãy con của aChúng ta có thể xem mỗi dãy con a của A tương ứng với một chuỗi nhị phân b độ dài n, trong đó, bi = 0 nghĩa là ai không thuộc a và ngược lại bi = 1 nghĩa là ai thuộc a. Ví dụ nếu A = [1, 3, 2, 3] thì dãy con tương ứng với chỗi nhị phân b = 1010 là [1, 3]. Như vậy, số dãy con của A cũng chính là số chuỗi nhị phân có độ dài n chính là 2n. Mặc dù có thể với 2 chuỗi nhị phân khác nhau sẽ tương ứng với cùng một dãy con (với mảng A = [1, 3, 2, 3], hai chuỗi 1100 và 1001 cùng tương ứng với dãy con [1, 3]), nhưng nếu lập trình bình thường để duyệt tất cả các dãy con của A thì phải duyệt 2n phần tử. Với n = 100 thì có đến 2100≈ 1030 dãy con. Phương án khả thiPhương án duyệt tất cả các dãy con để tìm kết quả tối ưu có độ phức tạp là O(2n), rõ ràng là không khả thi khi n lớn. Có cách nào khác để tìm được dãy con tối ưu mà không phải duyệt tất cả? Chúng ta thử cân nhắc phương pháp Quy hoạch động hay Đệ quy xem thử thế nào, nghĩa là tìm cách chia bài toán ban đầu thành các bài toán con 😕 ###### tags: `exercise` `array` `basic` `fill_in_the_blank` # Dãy Con Tăng Dài Nhất * https://lqdoj.edu.vn/problem/incarr ### Yêu cầu đề - Nhập vào hai mảng a (ban đầu là dãy không giảm) và b (thứ tự bất kì). Có thể thực hiện thao tác sau, xóa một phần tử ở mảng b rồi thêm vào một vị trị bất kì trong mảng a. Sau khi thực hiện tối đa m (số phần tử mảng b) thao tác thì độ dài xâu a là bao nhiêu. Với điều kiện a khi này là dãy tăng dần. ### Hướng dẫn 1. Nhập vào số phần tử và các giá trị của 2 mảng. * Sử dụng các hàm: input(), map(), split(), list(), int(). 2. Thêm các phần tử của mảng b vào mảng a với thứ tự bất kì. 4. Loại bỏ các phần tử trùng lặp trong mảng a để biến mảng từ trạng thái không giảm sang tăng dần. * Gợi ý dùng kiểu dữ liệu set() ### Điền vào chỗ trống * Hãy điền vào chỗ trống (`___`) để hoàn thành bài tập này. ```python # Copyright (c) 2023, Le Duc Phuc Long """ If you don't think twice, you have to code twice. """ n, m = map(int, input().split()) a = ___ b = ___ a = a+b ___ print(___) ``` ### Phần kết * Giải thích thêm về thuật toán: * Như đã nói trong phần hướng dẫn, ta chỉ cần gộp mảng a và mảng b lại, rồi xóa những phần tử trùng lặp là đã có được kết quả bài toán. * Bởi vì sau khi làm bước này ta đã có được một mảng a sau khi đã thêm vào các phần tử của mảng b, đặc biệt là những phần tử trong đó là duy nhất. * Bây giờ nếu ta sắp xếp lại mảng thì sẽ thu được mảng a tăng dần. Nhưng đề chỉ yêu cầu số lượng phần tử của mảng a khi này chứ không quan tâm đến thứ tự nên ta không làm điều đó. * Sau khi hoàn thành chương trình trên, hãy nộp bài ở link được gắn ở đầu bài viết để xem kết quả. * Qua bài tập, hi vọng bạn đã biết thêm được điều gì đó. * Nếu bạn phát hiện sai sót, có thắc mắc, hay bất kì ý kiến đóng góp nào… -> Xin hãy cho tôi biết qua: m.me/phuclong.leduc là một trong những bài toán quy hoạch động kinh điển và được ứng dụng rộng rãi trong việc giải quyết các bài toán về sắp xếp lịch trong thực tế. Bài viết hôm nay chúng ta cùng nhau tìm hiểu về bài toán này, về thuật toán quy hoạch động và cách triển khai nó trong ngôn ngữ lập trình JavaScript nhé. Dãy con tăng dài nhất – Longest Increasing Subsequence (LIS) là một bài toán với mục đích tìm ra dãy con dài nhất có thể của một dãy cho trước, trong đó các phần tử của dãy con đó được sắp xếp theo thứ tự tăng dần. Các phần tử trong dãy con này không nhất thiết phải liền kề hoặc duy nhất. Ví dụ ở hình trên, với đầu vào (input) là một mảng số gồm 8 phần tử thì đầu ra (output) mong muốn của bài toán sẽ là 2 mảng con thỏa mãn yêu cầu cùng độ dài bằng 4. Bài toán dãy con đơn điệu tăng dài nhất có biến thể đơn giản nhất là bài toán dãy con đơn điệu giảm dài nhất và thực tế là 2 bài toán này được xem là một. Ứng dụng của bài toán này trong thực tế có rất nhiều, nhất là trong các vấn đề về sắp xếp và lập lịch. Một ví dụ nổi bật là bài toán bố trí phòng khách sạn như sau: Yêu cầu: Có n khách cùng đặt 1 phòng khách sạn, khách i nhận phòng vào thời điểm A(i) và trả phòng ở thời điểm B(i). Hãy bố trí khách vào phòng đó sao cho phục vụ được nhiều khách nhất có thể. Lưu ý bài toán giả định chỉ có 1 phòng và có thể dễ dàng mở rộng cho nhiều phòng bằng cách sắp xếp lần lượt từng phòng. Chúng ta có thể chuyển yêu cầu trên về bài toán dãy con tăng dài nhất bằng cách sắp xếp các khách đặt phòng theo thời điểm kết thúc B(i) tăng dần. Khách i sẽ được sắp xếp vào phòng sau khách j khi và chỉ khi j < i và B(j) < A(i). Kết quả đầu ra từ thuật toán sẽ cho chúng ta mảng con số lượng khách tối đa có thể đặt được phòng. Bài toán dãy con tăng dài nhất được xếp vào một trong những bài toán quy động động kinh điển, vì thế để giải bài toán này trước tiên chúng ta cùng tìm hiểu về thuật toán này nhé. Phương pháp quy hoạch độngQuy hoạch động là một kĩ thuật thiết kế thuật toán theo kiểu chia bài toán lớn thành các bài toán con, sử dụng lời giải của các bài toán con để tìm lời giải cho bài toán ban đầu giúp chúng ta tối ưu thời gian thực hiện thuật toán. Khác với đệ quy thì quy hoạch động sẽ tính toán lời giải của các bài toán con trước và lưu vào mảng bộ nhớ; tiếp đó dùng lời giải của bài toán con trong mảng đã tính trước đó để giải bài toán theo công thức truy hồi. Thuật toán quy hoạch động gồm 3 bước:
Tham khảo việc làm JavaScript tại Hồ Chí Minh trên TopDev Áp dụng phương pháp quy hoạch động vào bài toán dãy con tăng dài nhất, chúng ta sẽ xác đinh công thức quy hoạch động như sau: Đề bài: Cho dãy số A với n phần tử, yêu cầu tìm ra dãy con tăng dài nhất A(i1), A(i2), … A(ik) thỏa mãn i1 Gọi F(i) là dãy con tăng dài nhất kết thúc ở A(i), ta có công thức đệ quy: F(1) = 1 F(i) = max(F(j) + 1) với j thỏa mãn điều kiện 1<=j Kết quả đầu ra bài toán sẽ là giá trị lớn nhất của trong mảng F. Ví dụ như sau: Mảng A 1 11 2 10 4 5 2 1 Mảng F 1 2 2 3 3 4 2 1 Kết quả đầu ra cho ví dụ trên thì dãy con tăng dài nhất sẽ có độ dài = 4; mảng đầu ra sẽ là [1, 2, 4, 5] Xem việc làm javascript đãi ngộ tốt trên TopDev Triển khai code JavaScriptSource code tham khảo triển khai giải thuật dành cho bài toán dãy con tăng dài nhất bằng JavaScript các bạn có thể tham khảo dưới đây: export default function dpLongestIncreasingSubsequence(sequence) { const lengthsArray = Array(sequence.length).fill(1); let previousElementIndex = 0; let currentElementIndex = 1; while (currentElementIndex < sequence.length) { if (sequence[previousElementIndex] < sequence[currentElementIndex]) { const newLength = lengthsArray[previousElementIndex] + 1; if (newLength > lengthsArray[currentElementIndex]) { lengthsArray[currentElementIndex] = newLength; } } previousElementIndex += 1; if (previousElementIndex === currentElementIndex) { currentElementIndex += 1; previousElementIndex = 0; } } let longestIncreasingLength = 0; for (let i = 0; i < lengthsArray.length; i += 1) { if (lengthsArray[i] > longestIncreasingLength) { longestIncreasingLength = lengthsArray[i]; } } return longestIncreasingLength; } Giá trị trả về longestIncreasingLength là độ dài của dãy con lớn nhất thỏa mãn yêu cầu đề bài. Để lấy ra được giá trị mảng con, chúng ta cần triển khai thêm bước truy vết lấy từng phần tử từ dãy đầu vào theo thứ tự ngược lại của vòng lặp, các bạn có thể tự triển khai thêm nhé. |
