← Thư viện hoạt động

Hoạt động

Đoán trước, đo sau: nhân đôi n thì chi phí tăng mấy lần?

Sinh viên dự đoán rồi tự đo tỉ số T(2n)/T(n) để nhận ra bậc tăng của một đoạn mã.

  • 15 phút
  • Vai AI: Không dùng AI
  • Pha 5E: Explore
  • Bậc học: Đại học
  • Trụ cột: Wonder · Tò mò, Systems · Hệ thống
  • ARCS: Thu hút, Tự tin

Các bước

  1. Cho đoạn mã hai vòng lặp lồng nhau: i từ 0 tới n−1, j từ i+1 tới n−1, mỗi lần chạy đếm một phép so sánh.
  2. Chưa chạy. Mỗi bạn ghi dự đoán: nhân đôi n thì số phép so sánh tăng gấp mấy lần, 2, 4 hay 8? Cả lớp giơ tay theo lựa chọn.
  3. Chạy với n = 10, 20, 40 và điền bảng. Kết quả đúng là 45, 190, 780.
  4. Tính T(20)/T(10) và T(40)/T(20). Các tỉ số lần lượt là 4,22 và 4,11, đang tiến dần về 4.
  5. Rút quy tắc. Hỏi tiếp: một vòng lặp thì tỉ số là bao nhiêu? Ba vòng lặp thì sao?

Cách kiểm tra bạn thật sự hiểu

Đưa một đoạn mã mới có ba vòng lặp lồng nhau. Bạn dự đoán tỉ số trước khi chạy và giải thích vì sao. Với n = 10, 20, 40 số phép tính là 120, 1 140, 9 880, tỉ số gần 8 và đang tiến về 8.

Lưu ý khi dạy

Nếu lớp có máy, cho các bạn tự viết đoạn mã đếm. Không có máy thì thầy cô đọc sẵn bảng kết quả sau khi lớp đã dự đoán.

Liên quan

Bài học trên JoyBell