Một robot di chuyển trên trục số. Hệ thống lưu lại chuỗi lệnh gồm: R (di chuyển sang phải

Câu hỏi số 977637:

Vận dụng

Một robot di chuyển trên trục số. Hệ thống lưu lại chuỗi lệnh gồm: R (di chuyển sang phải một đơn vị) và L (di chuyển sang trái một đơn vị). Hãy:

a) Trình bày ý tưởng xác định vị trí cuối cùng của robot.

b) Thiết kế chương trình theo phương pháp làm mịn dần.

c) Phân tích độ phức tạp của thuật toán.

Quảng cáo

Xem lời giải

Câu hỏi:977637

Phương pháp giải

Sử dụng một biến nguyên để quản lý tọa độ hiện tại của robot trên trục số, khởi tạo từ vị trí gốc.

Giải chi tiết

a) Ý tưởng: Coi vị trí bắt đầu của robot là 0. Duyệt lần lượt qua từng ký tự trong chuỗi lệnh: nếu gặp lệnh R thì tăng vị trí lên 1 đơn vị, nếu gặp lệnh L thì giảm vị trí đi 1 đơn vị. Giá trị cuối cùng của biến vị trí chính là tọa độ cần tìm.

b) Thiết kế chương trình theo phương pháp làm mịn dần:

- Bước 1: Nhập chuỗi lệnh S từ bàn phím.

- Bước 2: Khởi tạo biến vitri = 0.

- Bước 3: Sử dụng vòng lặp duyệt từng ký tự c trong chuỗi S. Nếu c bằng R thì vitri = vitri + 1, ngược lại nếu c bằng L thì vitri = vitri - 1.

- Bước 4: Thông báo giá trị vitri ra màn hình.

c) Phân tích độ phức tạp:

- Độ phức tạp thời gian: O(n) với n là độ dài của chuỗi lệnh do robot chỉ cần duyệt qua chuỗi một lần duy nhất.

- Độ phức tạp không gian: O(1) do chỉ sử dụng một vài biến đơn giản để lưu trữ tọa độ.

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòng- Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.