Câu hỏi:
20/04/2023 716Thay 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?
Siêu phẩm 30 đề thi thử THPT quốc gia 2024 do thầy cô VietJack biên soạn, chỉ từ 100k trên Shopee Mall.
Quảng cáo
Trả lời:
Để tìm số lần lật thẻ nhiều nhất để tìm ra thẻ in số K trong dãy A = {0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67} với phương pháp lật thẻ từ đầu đến cuối và quyết định lật tiếp theo dựa trên số ghi trên thẻ so với số K, ta có thể giả sử trường hợp xấu nhất là K nằm ở đầu dãy hoặc ở cuối dãy.
Nếu K nằm ở đầu dãy, ta sẽ cần lật tất cả các thẻ từ đầu đến khi lật thẻ in số K (lật tối đa 11 lần), sau đó lật thẻ in số K (1 lần), tổng cộng là 12 lần.
Nếu K nằm ở cuối dãy, ta sẽ cần lật tất cả các thẻ từ đầu đến cuối dãy trước khi lật thẻ in số K (lật tối đa 11 lần), sau đó lật thẻ in số K (1 lần), tổng cộng là 12 lần.
Vậy số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là 12 lần.
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
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 2:
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 3:
Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.
Câu 4:
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 5:
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.
Câu 6:
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.
về câu hỏi!