Với giải Khởi động trang 89 Tin học lớp 11 Kết nối tri thức chi tiết trong Bài 19: Bài toán tìm kiếm giúp học sinh dễ dàng xem và so sánh lời giải từ đó biết cách làm bài tập Tin học 11. Mời các bạn đón xem:
Giải bài tập Tin học lớp 11 Bài 19: Bài toán tìm kiếm
Khởi động trang 89 Tin học 11: 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?
Lời giải:
Bạn An không chắc chắn xác định được thẻ nào in số K nếu An chỉ lật từng thẻ từ đầu đến cuối một cách tuần tự. Trong trường hợp xấu nhất, thẻ in số K có thể nằm ở vị trí cuối cùng của bộ thẻ, khiến An phải lật qua tất cả các thẻ trước đó trước khi tìm ra thẻ in số K. Tuy nhiên, có một cách khác để tìm ra thẻ in số K nhanh hơn, bạn An có thể làm theo các bước sau:
- Lật thẻ ở giữa bộ thẻ để xem giá trị số in trên đó.
- So sánh giá trị số in trên thẻ với số K:
- Nếu giá trị số in trên thẻ bằng số K, thì trò chơi kết thúc và thẻ đó chính là thẻ in số K.
- Nếu giá trị số in trên thẻ lớn hơn số K, thì thẻ in số K nằm ở một vị trí trước đó trong bộ thẻ. Tiếp tục tìm kiếm trong nửa đầu của bộ thẻ từ đầu đến vị trí thẻ vừa lật.
- Nếu giá trị số in trên thẻ nhỏ hơn số K, thì thẻ in số K nằm ở một vị trí sau đó trong bộ thẻ. Tiếp tục tìm kiếm trong nửa sau của bộ thẻ từ vị trí thẻ vừa lật đến cuối.
Lặp lại các bước trên cho đến khi tìm thấy thẻ in số K hoặc đã lật hết tất cả các thẻ trong bộ thẻ. Với cách làm như vậy, An sẽ tìm ra thẻ in số K trong số lượt lật thẻ ít hơn so với phương pháp tìm lần lượt, đặc biệt là khi số lượng thẻ là lớn.
Xem thêm lời giải bài tập Tin học lớp 11 Kết nối tri thức hay, chi tiết khác:
Khởi động trang 89 Tin học 11: 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?...
Hoạt động 1 trang 89 Tin học 11: Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả năng các kết quả có thể tìm được của bài toán:...
Câu hỏi 1 trang 90 Tin học 11: Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau...
Câu hỏi 2 trang 90 Tin học 11: Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau...
Hoạt động 2 trang 90 Tin học 11: Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát...
Câu hỏi 1 trang 91 Tin học 11: Cho dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86]. Thuật toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử có giá trị bằng 47 trong dãy?...
Câu hỏi 2 trang 91 Tin học 11: Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?...
Câu hỏi 3 trang 91 Tin học 11: Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ...
Hoạt động 3 trang 91 Tin học 11: Cho trước một đây số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dây các phần từ đã sắp xếp...
Câu hỏi 1 trang 93 Tin học 11: Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần từ có giá trị bằng 34?...
Câu hỏi 2 trang 93 Tin học 11: Cho dãy A= {0, 4, 9, 10, 12,14, 17, 18, 20, 31, 34, 67}. Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phân tử có giá trị bằng 34?...
Câu hỏi 3 trang 93 Tin học 11: Thay vị lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu Tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lạt tiếp thẻ ở ngay bên trái hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?...
Luyện tập 1 trang 93 Tin học 11: Em hãy chỉnh sửa thuật toán tìm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phân tử bằng giá trị cần tìm...
Luyện tập 2 trang 93 Tin học 11: Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần...
Vận dụng 1 trang 93 Tin học 11: Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn...
Vận dụng 2 trang 93 Tin học 11: Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết thương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh...
Xem thêm các bài giải SGK Tin học lớp 11 Kết nối tri thức hay, chi tiết khác: