Bài học và trò chơi học tập

Đệ quy và quay lui

Các hàm tự gọi chính mình, từ đếm ngược đến bộ giải Sudoku, trên Raspberry Pi 4, với giới hạn độ sâu thực của engine được dạy một cách trung thực.

Khóa học

Đệ quy và quay lui là một khóa Coding trung cấp gồm bảy bài học, sau Python từ số không và Fix the bug. Phần lớn khóa chạy trên bộ Pi hai LED trong thư viện (đỏ ở GPIO17, vàng ở GPIO27), và trùm cuối dùng mô-đun đèn giao thông. Mỗi bước được kiểm tra dựa trên những gì Pi in ra hoặc các chân của nó làm, và mọi con số trong bài học đều là con số chương trình thật sự in ra.

  1. Lời gọi tự gọi chính nó: đếm ngược mà không cần vòng lặp, ngăn xếp lời gọi được vẽ dưới dạng thụt dòng khi cuộn vào và cuộn ra, giai thừa với số nguyên lớn chính xác (25! đầy đủ), một tam giác Sierpinski in dạng chữ, và một LED nhấp nháy năm lần bằng đệ quy.
  2. Trường hợp cơ sở: một cuộc lặn xuống hang không có đáy làm tràn ngăn xếp, một trường hợp cơ sở chặn đứng nó, giới hạn độ sâu được đo (hơi dưới 1.000 lời gọi với một hàm nhỏ), lũy thừa bằng bình phương (2^100 trong 8 lời gọi) và vì sao một đoạn việc tuần tự nên nằm trong vòng lặp.
  3. Tree walks: a cave of tunnels stored as nested tuples, printed as an outline, its 9 rooms counted, its deepest point found, a route to the glow worm grotto by depth-first search, then the Pi's own folders walked with the same pattern.
  4. Hoán vị: mọi thứ tự của một đội, n! đếm tới 720, một tín hiệu người ngoài hành tinh bị xáo trộn được giải mã đối chiếu với một bộ từ, hàng rover được đóng gói theo mẫu chọn-hoặc-bỏ, và kết quả được kiểm tra với itertools.permutations.
  5. Quay lui: N quân hậu với chọn, khám phá, bỏ chọn; mọi nghiệm được đếm từ 4 đến 8 (92 với bàn cờ vua); 15.720 ô được kiểm tra thay vì 16 triệu bàn cờ; LED vàng nhấp nháy mỗi lần quay lui; và thoát khỏi một mê cung hang biển.
  6. Memoization: 21.891 lời gọi của Fibonacci ngây thơ cho fib(20), một từ điển cắt nó xuống 39, functools.lru_cache với số lần trúng và trượt, 601.080.390 lộ trình rover qua một lưới, và 242 cách đổi một đô-la.
  7. Trùm cuối: bộ giải Sudoku: màn kết.

Hồi kết

Trùm cuối dựng một bộ giải Sudoku hoàn chỉnh trong khoảng hai mươi dòng. Nó tải một câu đố thật, viết các luật dưới dạng một hàm và thử trên một ô, rồi giải bảng bằng quay lui: tìm ô trống đầu tiên, thử từng chữ số khớp, giải phần còn lại, và rút chữ số lại nếu thất bại. Một phép kiểm tra độc lập chứng minh mọi hàng, cột và ô vuông đều chứa 1 đến 9 (4.208 lần đặt cho câu đố này), đèn giao thông sáng vàng trong lúc máy nghĩ và xanh khi giải xong, và một bộ canh sẽ quay đèn đỏ cho một câu đố vi phạm luật trước khi bộ giải lãng phí một khoảnh khắc nào vào nó.

Pi engine khác gì ở điểm nào

Pi chạy MicroPython 1.29, không phải CPython, và đệ quy là nơi điều đó thể hiện rõ nhất:

  • Đệ quy quá sâu sẽ phát sinh RuntimeError: maximum recursion depth exceeded, hoặc RuntimeError: pystack exhausted với một hàm có nhiều biến cục bộ. RecursionError, tên của CPython, không được định nghĩa ở đây. Các bài học bắt RuntimeError, cách này chạy được trên cả hai, vì RecursionError của CPython là một loại RuntimeError.
  • Giới hạn là bộ nhớ ngăn xếp, không phải một con số cố định: khoảng 980 lời gọi với một hàm bé, ít hơn với hàm lớn hơn. Ở đây không có sys.setrecursionlimit.
  • Dict không giữ thứ tự các khóa khi đưa vào, nên cây được lưu dưới dạng list và tuple, và os.listdir cùng các tập hợp được sắp xếp trước khi in.
  • str.ljust và str.rjust chưa có, nên việc đệm được tạo bằng " " * count. Số nguyên không có giới hạn kích thước, giống như trong CPython.

Mọi thứ còn lại trong khóa học, functools.lru_cache, itertools và os, chạy đúng như trên một chiếc Pi thật.