Em đã biết thiết lập cấu trúc dữ liệu đóng vai trò quan trọng khi giải quyết trong các bài toán thực tế trên máy tính. Trong các bài toán thực tế sau em sẽ thiết lập cấu trúc dữ liệu như thế nào?
Chỉnh sửa lại chương trình của Nhiệm vụ 1 để bổ sung chức năng: a) Thông báo điểm đầu tiên và điểm cuối cùng trong danh sách. b) Cho phép người dùng tra cứu đầu điểm thứ n với quy ước n bắt đầu từ 1 ứng với điểm đầu tiên, nếu n lớn hơn tổng số đầu điềm hoặc nhỏ hơn 1, cần thông báo không hợp lệ và yêu cầu người dùng nhập lại.
Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số ghi trên thẻ. Mỗi người chơi mỗi lần chỉ được lật một thẻ để xem giá trị số in trên đó. Nếu giá trị số in trên thẻ bằng bằng số k cho trước thì trò chơi kết thúc. Bạn An đã chơi bằng cách lật lần lượt từng thẻ từ đầu đến cuối. Theo em, An có chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?
Chỉnh sửa lại chương trình của Nhiệm vụ 3 để cho phép chương trình có thể tìm kiếm điểm số trên danh sách điểm số được sắp xếp theo thứ tự giảm dần.
Bài học trước cho em thấy việc tìm kiếm trên một dãy đã sắp xếp nhanh hơn với việc tìm kiếm tuần tự. Vì vậy bài toán tìm kiếm liên quan mật thiết đến bài toán sắp xếp. Bài toán sắp xếp cơ bản có dạng như sau: Cho dãy A gồm n phần tử: A[0],A[1],….,A[n-1] (1) Cần sắp xếp dãy A theo thứ tự tăng dần: A[0] ≤≤A[1]≤≤ ... ≤≤A[n-1] (2) Em hãy trình bày ý tưởng của mình để giải bài toán sắp xếp với dãy có bốn phần tử.
Trong bài 21, em đã được học cách triển khai thuật toán sắp xếp để sắp xếp các phần tử trong danh sách theo thứ tự tăng dần. Nếu cần sắp xếp theo thứ tự ngược lại thì câu lệnh so sánh tương ứng trong vòng lặp sẽ cần thay đổi như thế nào?
Trong các bài trước em đã học cách thiết kế thuật toán cho một số bài toán như bài toán tìm kiếm, bài toán sắp xếp và thiết lập chương trình thực hiện thuật toán đó. Một bài toán có nhiều thuật toán khác nhau và do đó có thể có nhiều chương trình khác nhau cùng giải quyết một bài toán. Hãy thảo luận và trả lời các câu hỏi sau: Làm thế nào để biết trong các thuật toán giải cùng một bài toán thì thuật toán nào là tốt nhất? Có những tiêu chí nào để đánh giá tính “tối ưu” của một thuật toán?
Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?
Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?
Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Tất cả các thiết kế chương trình đó có điểm nào chung? Theo em, để thiết kế một thuật toán đúng giải một bài toàn cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.
Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ hình cây để mô tả phương pháp này không?
Em sẽ thiết kế chương trình như thế nào? Trao đổi với bạn về cách thiết kế chương trình sao cho hợp lí nhất.
Trong bài 28, em đã biết tầm quan trọng và ý nghĩa của việc thiết kế chương trình theo mô đun. Mỗi mô đun chính là một chương trình con được xác định khi phân tích thiết kế bài toán lớn. Mỗi mô đun được viết một cách độc lập, có thể sử dụng lại như các thư viện và có thể chia sẻ trong nhóm làm việc. Trong bài tập thực hành này em sẽ được tự mình thiết kế chương trình cho một bài toán hoàn chỉnh theo mô đun.
Em hãy tìm thêm các ví dụ thực tế của mô hình danh sách liên kết.
T LẬP THƯ VIỆN CHƯƠNG TRÌNH Khởi động trang 143 Tin học 11: Trong bài 30, em đã tìm hiểu ý nghĩa và cách thiết lập thư viện chương trình. Em có thể thấy xung quanh em, đặc biệt là trong các lĩnh vực khoa học tự nhiên như Toán học, Vật lí và Hóa học, thường xuất hiện nhiều vấn đề hoặc nhiệm vụ tính toán mang tính tổng quát. Em hãy triển khai thuật toán cho các vấn đề như vậy thành các thư viện để có thể sử dụng lại nhiều lần cũng như làm toàn bộ chương trình có cấu trúc trong sáng, rõ ràng, dễ p