ỨNG DỤNG THUẬT TOÁN QUAY LUI TRONG GIẢI BÀI TOÁN BẬC THCS TRÊN NGÔN NGỮ LẬP TRÌNH C++

Tóm tắt

Thuật toán quay lui (Backtracking) là một kỹ thuật giải bài toán bằng cách tìm kiếm tất cả các khả năng có thể xảy ra theo từng bước, và loại bỏ (quay lui) những lựa chọn không dẫn đến kết quả đúng. Nghiên cứu này tập trung vào việc ứng dụng thuật toán Quay lui (Backtracking) trong lập trình C++ để bồi dưỡng học sinh giỏi (HSG) môn Tin học cấp THCS. Thực trạng cho thấy nhiều HS gặp khó khăn trong việc tìm ra giải pháp tối ưu, khiến chương trình vượt quá giới hạn thời gian xử lý khi đối mặt với dữ liệu lớn. Mục tiêu chính là giúp HS hiểu rõ khái niệm, bản chất của thuật toán Quay lui và biết cách thiết kế, cài đặt một cách chính xác. Thuật toán Quay lui là một phương pháp vét cạn thông minh, xây dựng bộ nghiệm từng bước và “quay lui” khi không tìm được lời giải, từ đó hạn chế được các nhánh không cần thiết.