Trang chủ » Blog » Coding Dojo » Kata DepthFirstSearch

Kata DepthFirstSearch

bởi CodeGym | 09/12/2023 10:30 | Blog | Coding Dojo

Giới thiệu kata

Cấp độ của Kata: Dễ

Dùng để luyện về Đệ quy

Kata liên quan: KataBreadthFirstSearch

Mô tả bài toán

Depth-first search (tìm kiếm theo chiều sâu) không chỉ là một kĩ thuật AI mà còn là một tiêu chuẩn để duyệt qua các cây (tree – được dùng phổ biến trong khoa học máy tính).

Hướng dẫn

Mức dễ nhất của depth-first search là làm theo hướng function-call stack thay vì hướng stack data structure.

Tránh triển khai một lớp như Graph, Maze hoặc Problem (dù chỉ để làm mocked interface) làm depth-first-searcher để duyệt. Thay vào đó hãy đặt câu hỏi như một “người” dùng (ví dụ: standard in/standard out hoặc theo ngôn ngữ của bạn). Ví dụ: “Các lối ra là gì?” và “Chúng ta đang ở đâu?”. Điều này sẽ tạo ra được các kiểm thử thăm dò rất thú vị. Nếu xây dựng Graph hoặc Maze bằng cách khởi tạo dữ liệu hoặc phân tích một file thì sẽ làm chậm nhóm và mất ý nghĩa của bài Kata.

Tất nhiên, bạn nên giả lập các cuộc hội thoại trong các kiểm thử đơn vị của mình. Điều này chứng tỏ rằng kiểm thử thăm dò có thể được ghi lại trong các kiểm thử tự động có khả năng lặp lại, thứ có giá trị.

Gợi ý các ca kiểm thử

  • One-node graph.
  • Two-node graph.
  • 2×2 maze.
  • Cây nhị phân đầy đủ 2 cấp độ (full two-level binary tree).
  • 3×3 maze.

Nguồn Kata: http://codingdojo.org/kata/DepthFirstSearch/

0 Lời bình

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

11 + 9 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM