Tiếp nối trong nội dung bài trước, bài viết này mình sẽ hướng dẫn bạn một số kỹ thuật cơ bản trên mảng một chiều. Đây là những kỹ thuật rất hay được sử dụng để thao tác trên mảng một chiều và là kỹ thuật đầu tiên mà mình muốn giới thiệu trong bài viết này “kỹ thuật đặt lính canh”
Kỹ thuật đặt lính canh là gì?
Ý tưởng
Sở dĩ gọi là “đặt lính canh” vì kỹ thuật này có ý tưởng như sau:
Tìm người lính cao nhất trong tiểu đội được xếp thành một hàng. Thông thường, để tìm người cao nhất thì chúng ta sẽ lấy một người lính ra làm chuẩn. Tất nhiên là bạn có thể lấy bất kỳ người nào ra để làm chuẩn, nhưng để cho tiện thì lấy người lính đứng ở vị trí đầu trong hàng luôn nhé. Lúc này, bạn sẽ lần lượt so sánh người lính làm chuẩn với từng người còn lại trong hàng. Trong qua trình so sánh, nếu bạn thấy có người khác cao hơn người lính làm chuẩn thì chúng ta sẽ thay thế người lính làm chuẩn bằng người cao hơn này. Cứ lặp đi lặp lại việc so sánh và thay thế này cho đến hết, lúc này người lính làm chuẩn cuối cùng sẽ là người cao nhất.
Để dễ hiểu hơn, bạn hãy theo dõi hình ảnh mô phỏng cho ý tưởng này như sau:
Kỹ thuật đặt lính canh được sử dụng trong trường hợp nào?
Với ý tưởng như trên, có lẽ bạn đã phần nào hiểu được vì sao gọi là “kỹ thuật đặt lính canh” rồi đúng không nào? Đây là kỹ thuật dù là rất cơ bản nhưng lại quan trọng trong kỹ thuật lập trình, thường được áp dụng cho các dạng toán như:
- Tìm kiếm một giá trị/vị trí của một phần tử nào đó trong không gian cho trước.
- Liệt kê các giá trị thỏa mãn theo điều kiện nào đó.
Áp dụng kỹ thuật đặt lính canh trong mảng một chiều
Sau khi nắm được ý tưởng của kỹ thuật này thì bây giờ là lúc để chúng ta tiến hành thực nghiệm. Và để minh hoạ, mình sẽ xây dựng chương trình tìm giá trị lớn nhất trong mảng một chiều các số nguyên.
Trong phần này, mình sẽ chỉ xây dựng hàng tìm giá trị lớn nhất để minh hoạ thôi nhé. Còn những hàm khác như nhập mảng / xuất mảng thì bạn hãy tự làm lại dựa trên kiến thức của bài học trước.
Minh hoạ kỹ thuật đặt lính canh
Dưới đây là hàm mà mình xây dựng để minh hoạ cho kỹ thuật này, bạn hãy cùng xem và phân tích thử xem sao nhé.
Phân tích
Đoạn code minh hoạ ở trên, mình xây dựng một hàm có tên là MaxSearch. Hàm này có 02 tham số đầu vào là mảng a và biến n. Trong đó:
- Mảng a: là mảng chứa các phần tử có giá trị là số nguyên.
- Biến n: là số lượng phần tử các số nguyên có trong mảng a.
Đầu tiên, bạn hãy quan sát dòng số 3. Tại dòng này mình khai báo một biến số nguyên có tên là _maxElement. Đây chính là biến lính canh được sử dụng để làm chuẩn, vì vậy ban đầu mình gán luôn cho biến này giá trị của phần tử đầu tiên trong mảng a (là phần tử a[0]).
Vì chúng ta đang thao tác trên mảng một chiều, nên ở đây mình sử dụng vòng lặp for (dòng 5) để duyệt qua lần lượt các phần tử trong mảng a. Với mỗi lần duyệt qua một phần tử trong mảng a, mình sẽ thực hiên so sánh (dòng 6) giá trị của phần tử lính canh với giá trị của phần tử hiện tại trong mảng. Nếu phần tử hiện tại trong mảng có giá trị lớn hơn giá trị của phần tử lính canh thì sẽ cập nhật lại giá trị mới cho phần tử lính canh (dòng 7). Mục đích của việc cập nhật giá trị là để phần tử lính canh luôn giữ giá trị lớn nhất ở thời điểm hiện tại để làm chuẩn cho các lần so sánh sau.
Cứ như vậy, khi kết thúc vòng lặp thì chúng ta chắn chắn sẽ xác định được giá trị lớn nhất trong mảng chính là giá trị mà phần tử lính canh đang nắm giữ. Và đây cũng chính là tư tưởng chủ đạo của kỹ thuật này.
Tổng kết
Đây là bài viết mở đầu cho chuỗi các bài viết về kỹ thuật cơ bản trong thao tác mảng. Kỹ thuật đặt lính canh nghe tên thì có thể hơi “ghê gớm” nhưng thực chất nó rất cơ bản và dễ hiểu. Vì vậy mình hy vọng bài viết này sẽ là tư liệu để hỗ trợ cho các bạn mới học lập trình được dễ dàng hơn.
Bạn muốn học lập trình hãy liên hệ ngay với Mỹ Vân để được nhận ưu đãi từ học viện nhé
Không có nhận xét nào:
Đăng nhận xét