Kata DepthFirstSearch

21/04/2017 | Blog, Coding Dojo | 0 Lời bình

Trang chủ » Blog » Coding Dojo » Kata DepthFirstSearch

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

Tạo và sử dụng USER FUNCTION

Tạo và sử dụng USER FUNCTION

Với các vấn đề mà các FUNCTION không giải quyết được. Thì chúng ta phải tự tạo ra một FUNCTION để sử dụng, hay còn gọi là USER FUNCTION.

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

GỌI NGAY

098 953 44 58

Nhận tư vấn, định hướng 1-1

Điền và gửi thông tin cá nhân để được tư vấn miễn phí về các chương trình học.

2 + 12 =