Solutions of Operations on number

Select solution language

Terence Created at 1 likes

💡 Ý tưởng giải bài toán (bằng BFS): Ta cần tìm số thao tác tối thiểu để biến số nguyên dương n thành m, với mỗi thao tác là: - Nhân n với 2. - Trừ n đi 1. Vì mỗi thao tác tạo ra một số mới, bài toán này giống như việc di chuyển trên một đồ thị trạng thái, trong đó mỗi đỉnh là một số nguyên dương, và các cạnh thể hiện thao tác biến đổi giữa chúng. ✅ Mục tiêu: Tìm số bước ít nhất để đi từ n đến m. Đây là bài toán điển hình của tìm đường đi ngắn nhất, nên BFS (Breadth-First Search) là lựa chọn tối ưu. 🔍 Chi tiết thuật toán: Dùng hàng đợi (queue) để duyệt BFS từ số n. Mỗi bước, ta có thể: Trừ đi 1 (n - 1) Nhân đôi (n * 2) Đánh dấu các số đã duyệt để tránh lặp vô hạn. Nếu tại một bước nào đó ta đến được m, thì số bước đã đi chính là số thao tác tối thiểu cần tìm. ⚠ Giới hạn: Ta chỉ cần xét đến các số không vượt quá 2 * m, vì vượt hơn thì sẽ không có lợi (càng xa m hơn). BFS đảm bảo ta đến m với số bước ít nhất.