Các bài thuật toán quen thuộc lớp 8 năm 2024
Có bao giờ bạn phải đau đầu vì để quên chiếc ví ở đâu đó trong nhà mà tìm mãi không thấy? Hay việc các bạn nữ luôn không thể nào tìm thấy bộ quần áo phù hợp để lên phố mặc dù số lượng trang phục xếp nặng trĩu trong tủ quần áo? Cuộc sống chúng ta luôn gắn liền với việc tìm kiếm. Từ một đứa trẻ tò mò tìm kiếm khám phá từng điều thú vị của thế giới đến khi trưởng thành chúng ta phải chật vật tìm kiếm một nửa mảnh ghép còn lại của đời mình, mà ... có nhiều người còn phải chịu thua số phận và đành cam lòng gắn lên mình danh hiệu "FA". Show Đừng nản chí, để giúp bạn giải quyết những vấn đề đó, hôm nay chúng ta sẽ cùng khám phá về thuật toán tìm kiếm trong lập trình - một giải thuật quen thuộc, hữu ích vô cùng trong Tin học mà còn có thể áp dụng ra đời sống, giúp bạn tìm thấy chân ái của đời mình! 2. Bài toán tìm kiếm trong Tin họcCùng so sánh hai sự việc sau đây:
Mục tiêu tìm kiếm trong cả hai bài toán đều đã được xác định, đó là "cục tẩy" và "số 66" (cần tìm thấy số 66 xong mới có được vị trí). Và tập "dữ liệu" của chúng ta có (hay phạm vi tìm kiếm) chính là "những đồ vật trong hộp bút" hoặc "các số trong dãy số đã cho trước". Có thể hiểu, tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp rất nhiều phần tử dựa vào một yêu cầu nào đó. Trong Tin học, với sự giúp đỡ của máy tính, rất nhiều thuật toán tìm kiếm đã ra đời với tính hiệu quả ngày càng tăng cao. Những thuật toán tìm kiếm cơ bản nhất có thể kể đến là Tìm kiếm tuần tự và Tìm kiếm nhị phân. Ngoài ra, áp dụng thêm những cấu trúc dữ liệu trong khi tìm kiếm có thể cho ra những thuật toán có hiệu quả cao hơn nữa. Bài toán tìm kiếm trong Tin học có thể phát biểu như sau: "Cho một dãy gồm nn đối tượng a1,a2,...,ana_1, a_2,..., a_n. Mỗi đối tượng aia_i có một khóa key (1≤i≤n)key \ (1 \le i \le n) gọi là khóa tìm kiếm. Cần tìm kiếm đối tượng có khóa bằng kk cho trước, tức là ai.key=ka_i.key = k". Quá trình tìm kiếm sẽ hoàn thành nếu như có một trong hai trường hợp sau đây xảy ra:
Dưới đây, tôi sẽ trình bày một số thuật toán thông dụng để giải quyết bài toán trên! II. Giải thuật tìm kiếm tuần tự (Sequential Search)Ý tưởngTìm kiếm tuần tự (Sequential Search hay Linear Search) là một giải thuật đơn giản, rất dễ cài đặt. Bắt đầu từ đối tượng a1,a_1, duyệt qua tất cả các đối tượng, cho tới khi tìm thấy đối tượng có khóa mong muốn, hoặc duyệt hết toàn bộ dãy mà không tìm thấy khóa đó. Mô phỏng giải thuật C++:
Đánh giáMặc dù giải thuật Tìm kiếm tuần tự rất đơn giản và dễ cài đặt, tuy nhiên nhược điểm của nó nằm ở độ phức tạp. Trong trường hợp tốt nhất, giải thuật có độ phức tạp là O(1),O(1), nhưng trong trường hợp xấu nhất lên tới O(n)O(n). Vì vậy độ phức tạp tổng quát của giải thuật là O(n),O(n), chỉ phù hợp với những bài toán có kích thước không gian tìm kiếm nhỏ. Ví dụCho một dãy số aa gồm nn số nguyên a1,a2,...,an (1≤n≤1000)a_1, a_2,..., a_n \ (1 \le n \le 1000). Hãy xác định xem số fibonacci thứ k (1≤k≤100)k \ (1 \le k \le 100) có xuất hiện trong dãy số hay không, nếu có thì đưa ra vị trí xuất hiện đầu tiên, ngược lại đưa ra −1-1. Cách giải quyếtTrước tiên, ta dùng vòng lặp để tìm ra số fibonacci thứ k,k, rồi tìm kiếm tuần tự trên dãy số ban đầu để tìm ra vị trí của số fibonacci thứ kk trong dãy. Cài đặt
III. Giải thuật tìm kiếm nhị phânÝ tưởngTrước tiên, không gian tìm kiếm cần được sắp xếp lại theo chiều tăng dần hoặc giảm dần của khóa tìm kiếm (mục tiêu là để tạo ra dãy có tính thứ tự). Giả sử dãy đã được sắp xếp tăng dần theo khóa, giải thuật tìm kiếm nhị phân được thực hiện như sau:
Quá trình tìm kiếm sẽ thất bại nếu như đến một bước nào đó, tập tìm kiếm bị rỗng (l>r)(l > r). Mô phỏng giải thuật C++:
Đánh giáTrong trường hợp tốt nhất, giải thuật Tìm kiếm nhị phân cho ta độ phức tạp O(1)O(1). Còn trong trường hợp xấu nhất, do tập tìm kiếm luôn luôn được chia đôi ra, nên số thao tác chỉ mất O(log2(n))O(\log_2(n)). Vì thế, độ phức tạp tổng quát của giải thuật là O(log(n))O(\log(n)). Tuy nhiên, giải thuật Tìm kiếm nhị phân chỉ có thể thực hiện trên một tập đã sắp xếp, chính vì thế chi phí sắp xếp cũng cần được tính đến. Nếu như dãy số bị thay đổi bởi các thao tác thêm, xóa hay sửa phần tử, thì việc sắp xếp cũng phải thực hiện lại liên tục, từ đó dẫn đến thời gian thực thi bị tăng lên. Hình minh họa dưới đây sẽ thể hiện so sánh tương quan giữa hai giải thuật Sequential Search và Binary Search trong cả ba trường hợp: Tốt nhất, trung bình và xấu nhất: |