Ha Hoang's Blog

Loạt bài Quy hoạch động cơ bản mình trình bày ở đây nhằm mục đích định rõ các bước tư duy cụ thể để đưa ra được thuật toán Quy hoạch động cho một bài toán. Sản phẩm của quá trình lập luận, suy nghĩ gồm có: định nghĩa hàm trạng thái mô tả một trạng thái chung của bài toán; một công thức Quy hoạch động thể hiện việc tính toán các trạng thái sau nhờ một vài trạng thái trước đó; một số bài toán cơ sở làm tiền đề cho việc tính các trạng thái sau và một phương án lưu trữ giá trị các trạng thái nhằm mục đích đưa ra kết quả cuối cùng hoặc truy vết tìm một phương án hợp lí. Bài này sẽ bàn về một bài Quy hoạch động điển hình "Dãy con tăng dài nhất" . Có thể bạn đã đọc, thấy bài này ở nhiều nơi rồi, ở bài viết này mình một lần nữa phân tích theo 5 bước cụ thể để các bạn mới học có thể tiếp cận một cách dễ dàng hơn. Tóm tắt bài Dãy con tăng dài nhất (LIQ) : Cho dãy gồm N phần tử a[i] với i từ 1 tới N; Hãy tính độ dài của dãy con tăng đơn điệu dài nhất. Một dãy con tăng đơn điệu là một dã...

Frog2 là một bài tập Quy hoạch động cơ bản dạng dễ . Bài này được nằm trong loạt bài mẫu nhằm giúp các bạn định hướng cách nghĩ để có thể đưa ra một thuật toán Quy hoạch động . Ở đó bao gồm các bước tư duy nhằm định nghĩa một hàm Quy hoạch động (hàm trạng thái), một công thức Quy hoạch động, các bài toán cơ sở, bảng phương án và các lưu ý khi tính bảng phương án. Bài Frog 2 có thể tóm tắt như sau: Có N hòn đá được đánh số từ 1 tới N. Hòn đá thứ i có độ cao h_i. Ban đầu chú ếch ở hòn đá 1. Chú liên tục thực hiện một loạt hành động sau: Nếu chú đang ở hòn đá i, chú có thể nhảy tới các hòn đá i+1, i+2,..., i+K và chi phí cho bước nhảy đó là |H_i - H_j| với j là hòn đá mà chú ếch nhảy tới. Hỏi chi phí tối thiểu để chú ếch nhảy từ hòn đá đầu đến hòn đá thứ N? Nếu đã làm bài Frog 1 rồi thì bạn sẽ nhận thấy ngay Frog 2 là bài khá tương tự bài Frog 1. Như vậy, cách nghĩ và cách phân tích để đưa ra phương án Quy hoạch động cũng tương tự bài Frog 1. Bạn có thể thực hành nghĩ lại theo các chỉ dẫ...

Bài FROG 1 là một bài tập Quy hoạch động cơ bản, nằm trong danh sách các bài tập thuộc kì thi DP Contest tại Atcoder. Hôm nay chúng ta cùng nhau phân tích cách nghĩ để giải bải Frog 1 bằng Quy hoạch động . Mục đích là muốn thực hành lại các bước tư duy thuật toán theo mô hình Quy hoạch động đã được trình bày ở một bài viết trước. Tóm tắt bài FROG 1: Có N hòn đá được đánh số từ 1 tới N. Ban đầu chú ếch ngồi ở hòn đá 1. Tại hòn đá i, chú ếch có thể nhảy tới hòn đá (i+1) hoặc (i+2); và chú sẽ mất chi phí là |h[i]-h[j]| với j là hòn đá đích mà chú ếch nhảy tới. Hãy tìm chi phí tối thiểu để chú ếch có thể nhảy tới hòn đá N? Ở giai đoạn ban đầu làm quen với Quy hoạch động, ta xem xét các bài toán có dấu hiệu giải được bằng phương pháp QHĐ trước để học cách phân tích (tư duy Quy hoạch động), nên tạm thời ta sẽ bỏ qua bước xác định xem bài toán liệu có thể giải được bằng phương pháp QHĐ. Định nghĩa hàm Quy hoạch động: Bài toán yêu cầu tính chi phí tối thiểu để nhảy tới hòn đá N, ta gọi F(n) ...

VSTEPS là một bài tập Quy hoạch động cơ bản , phù hợp cho các bạn luyện tập tư duy ở giai đoạn đầu khi đang làm quen với mô hình thiết kế thuật toán Quy hoạch động.  Như mình đã chia sẻ các bước suy nghĩ để xây dựng thuật toán Quy hoạch động cho một bài toán theo trình tự các bước, dưới đây là vận dụng phương pháp vào bài VSTEPS - SPOJ. Đề bài VSTEPS  được tóm tắt như sau: Một cầu thang N bậc được đánh số từ 1 tới N. Lucky có thể đi lên 1 hoặc 2 bậc. Tuy nhiên một số bậc thang bị hỏng và không thể bước chân lên được. Bậc thang 1 luôn không thủng và là vị trí đứng ban đầu của Lucky. Hỏi có bao nhiêu cách để Lucky leo hết được cầu thang? Định nghĩa hàm Quy hoạch động : bài toán yêu cầu tìm số cách để leo được lên bậc thứ N, như vậy ta gọi F(n) là số cách tới được bậc thang thứ N. Số cách này chỉ phụ thuộc vào N mà thôi. Tìm công thức Quy hoạch động : Ta giả sử đang đứng ở bậc thứ i, khi đó có hai trường hợp: Nếu bậc thứ i bị thủng --> Không có cách nào tới được bậc i đó -...

Theo kinh nghiệm dạy học của cá nhân mình, các chiến lược thiết kế thuật toán là những nội dung nâng cao, là các nội dung khó đối với nhiều giáo viên cũng như học sinh.  Giả sử giai đoạn lập trình cơ bản, các học sinh có khả năng sử dụng ngôn ngữ lập trình nào đó để biểu diễn các thuật toán cơ bản tốt rồi, học sinh có thể vận dụng tư duy để đưa ra thuật toán cho các bài toán cơ bản rồi. Vậy mà khi chuyển qua nội dung các chuyên đề nâng cao là đa số học sinh bị tụt lại 😆 Và trên thực tế, số lượng này không hề nhỏ. Vậy điều gì làm cho nội dung này là một nội dung quá khó, không thể học được với nhiều học sinh? Đối với các học sinh giỏi về Quy hoạch động, chắc là các HS đội tuyển Quốc Gia, Quốc Tế thì họ nghĩ thế nào về chủ đề này? Người ta có thấy chủ đề này "dễ" ngay từ đầu không? Và con đường để họ giỏi về nội dung này là gì? Nếu mình theo con đường đó, mình có giỏi được như họ không? Hihi, câu trả lời tôi nghĩ sẽ rất chung chung, đại khái là đọc sách chuyên đề QHĐ, đại khái...

Việc chấm bài tự động trên các trang chấm bài online rất phổ biến ở nhiều nơi, cả ở nước ngoài cũng như Việt Nam. Nhưng ở khu vực mình dạy học, chấm bài tự động như là một "đặc sản" riêng của lớp chuyên Tin học. Mình nghĩ, việc sử dụng công cụ chấm bài tự động để hỗ trợ giáo viên và học sinh trong dạy và học lập trình rất hữu ích kể cả giai đoạn lập trình cơ bản. Bởi thế, mình đã biên soạn lại các bài tập trong SGK Cánh Diều để có thể chấm tự động, đồng thời đưa lên trang này để các HS có thể sử dụng để thực hành.  Sử dụng hệ thống chấm bài tự động có nhiều lợi ích. Một là, có thể giúp giảm bớt gánh nặng đối với giáo viên trong các giờ thực hành . Giờ thực hành, giáo viên ngoài việc chuẩn bị các nội dung thực hành, giao cho các nhóm học sinh ở từng máy, rồi quan sát, hỗ trợ học sinh ở từng máy, từng bài tập,... rất nhiều việc khiến giáo viên "kiệt sức" ở mỗi giờ thực hành. Mà mỗi giáo viên, một buổi dạy 4, 5 tiết; một tuần 4,5 buổi :( Nếu không dùng công cụ chấm tự...