Ha Hoang's Blog

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ự...

Theo yêu cầu cần đạt môn Tin học 2018 cho thấy, việc dạy học lập trình chú trọng nhiều tới kĩ năng thực hành. Ngay từ những bài đầu tiên học sinh đã có được trải nghiệm viết được một vài chương trình đơn giản hoàn chỉnh. Bởi thế, thời lượng dành cho các hoạt động thực hành trên máy là rất nhiều.  Việc dạy học phần thực hành khiến giáo viên rất vất vả. Có lẽ, hiệu quả dạy học lập trình đa số không đạt như kì vọng là do tổ chức thực hành chưa được tốt. Hoạt động học tập trong các giờ thực hành đòi hỏi học sinh làm việc thực sự theo nhóm nhỏ (tối đa 02 học sinh/ máy tính), rất cục bộ. Trong giờ thực hành giai đoạn đầu học lập trình, phần nặng nhất đối với giáo viên lại không nằm ở nội dung thực hành mà ở các hoạt động quan sát, hỗ trợ kịp thời các nhóm học sinh gặp vướng mắc. Thường giáo viên chỉ đủ thời gian hỗ trợ một vài nhóm nhỏ. Không có thời gian xem xét, giúp đỡ các nhóm khác là nguyên nhân chính gây ra việc học sinh rơi vào trạng thái "bơ vơ", không biết làm thế nào tiếp...