Ky thuat dat linh canh trong c la gi

Đề bài: cho mảng số thực a có n số, nhập x từ bàn phím, tìm vị trí xuất hiện đầu tiên của x trong mảng a.

Lời giải:

Thường thì các bạn sẽ sử dụng vòng lặp for để duyệt hết mảng, vòng lặp for như sau:

for (i=0; i
Với mỗi vòng lặp, máy tính phải thực hiện 1 câu lệnh i++, 2 câu lệnh kiểm tra i
Bây giờ ta thêm x vào cuối mảng rồi cài đặt lại vòng lặp như sau:
        a[n] = x; // gan "linh canh" vao cuoi mang
        for (i=0; ; i++)
        {
                if (a[i] == x)
                        break;
        }  
Như vậy, mỗi vòng lặp for đã giảm được 1 câu lệnh kiểm tra, chương trình sẽ chạy nhanh hơn. Đó chính là thuật toán tìm kiếm sử dụng lính canh.
 
Kỹ thuật đặt lính canh dùng khi bạn muốn duyệt qua danh sách và chọn một phần tử có đặc điểm nào đó tùy vào từng trường hợp.



Kỹ thuật này hay dùng để tìm min max, giá trị lớn nhất, nhỏ nhất, số nguyên tố lớn nhất, số nguyên tố nhỏ nhất … của một mảng danh sách.
Đó là các ví dụ thôi chứ không phải là tất cả trường hợp, nếu bạn dùng quen rồi thì sẽ biết lúc nào dùng đến.
 
Hai là, kỹ thuật này áp dụng khi ta có quyền điều khiển data để có thể đặt lính canh như ý mình trên data đó.
Ba là, tác dụng chủ yếu của đặt lính canh là để giảm bớt việc phải xét biên của dữ liệu => với các vòng lặp phức tạp, việc tính toán nhiều thì thêm/bớt một vài thao tác xét biên có tác dụng không nhiều lắm (\lim_{n \to \infty} {n \over {n+k}} = 1). Nên việc phải duplicate data chỉ để thêm lính canh thì cần phải suy nghĩ thật kỹ (a.k.a cần benchmark).
Cuối cùng, lấy ví dụ như bài toán tìm kiếm như trên, nếu dùng tìm tuần tự:
auto find_in(int* a, int n, int v){
    for(int i=0; i> n >> v;
    auto a = std::make_unique(n);
    for (int i=0; i> a[i];
    return find_in(a.get(), n, v);
}
Nếu dùng kỹ thuật lính canh:



auto find_until_found(int* a, int v){
    int i=0;
    while(a[i]!=v) ++i;
    return i;
}

auto find(){
    int n, v;
    std::cin >> n >> v;
    auto a = std::make_unique(n+1);
    for (int i=0; i> a[i];
    a[n]=v; // Đặt lính canh
    auto i = find_until_found(a.get(), v); // Tìm bằng lính canh a[n] bên trên
    if (i==n) return -1;
    return i;
}
Và đây là so sánh độ hiệu quả 2 cách trên: https://gcc.godbolt.org/z/8dMnavTTv
 
Giải pháp của tôi như sau, trước tiên chọn một bạn làm mẫu rồi lần lượt so sánh với các bạn còn lại, nếu bạn nào cao hơn thì đổi chỗ cho bạn làm mẫu đó và người bạn cao hơn, lúc này người bạn cao hơn sẽ đứng làm mẫu. Và cứ như vậy cho đến hết, kết quả là người làm mẫu cuối cùng để canh chính là người cao nhất. Ta gọi đây là kỹ thuật đặt lính canh.
Ví dụ 2: Dùng kỹ thuật đặt lính canh tìm giá trị lớn nhất của 3 số $avà $b và $c.
Cách giải như sau: Khởi tạo một biến $max để chứa giá trị lớn nhất.
Bước 1: Giả sử biến lớn nhất là biến $a, tức là ta gán $max = $a;
Bước 2: So sánh biến $max với $b, nếu $b lớn hơn $max thì ta gán$a1



Bước 3: So sánh biến $max với $c, nếu $c lớn hơn$max thì ta gán $a6
Cuối cùng biến $max chứa giá trị lớn nhất. Sau đây là hàm tìm giá trị lớn nhất:
function tim_max($a, $b, $c)
{
    $max = $a;
    if ($max < $b){
        $max = $b;
    }
    if ($max < $c){
        $max = $c;
    }
    return $max;
}
2. Khi nào nên sử dụng kỹ thuật đặt lính canh
Kỹ thuật đặt lính canh dùng khi bạn muốn duyệt qua danh sách và chọn một phần tử có đặc điểm đặc biệt nào đó.
Kỹ thuật này hay dùng để tìm min max, giá trị lớn nhất, nhỏ nhất, số nguyên tố lớn nhất, số nguyên tố nhỏ nhất … của một mảng danh sách.
Đó là các ví dụ thôi chứ không phải là tất cả trường hợp, nếu bạn dùng quen rồi thì sẽ biết lúc nào dùng đến.
3. Lời kết
Kết thúc bài này tôi hy vọng bạn hiểu được định nghĩa thế nào là kỹ thuật đặt lính canh là quá được rồi. Thực tế thì khi làm web bạn sẽ phải sư dụng kỹ thuật này khá nhiều đấy, Bài tiếp theo tôi sẽ giới thiệu một kỹ thuật khác cũng tương tự đó là kỹ thuật đặt cờ hiệu.
 bổ sung về kĩ thuật đặt cờ hiệu. Kĩ thuật này có nghĩa là ban đầu ta cho đang phất cờ. Nếu gặp 1 điều kiện nào đó thì cờ sẽ hạ xuống. Kĩ thuật này thường dùng để giải quyết các bài toán như đúng sai, xác định số nguyên tố, xác định ...
VD:
void XacDinhSoCHan(int x)
{
int co=1; //co dang phat
if(x%2==1) // dieu kien de ha co xuong
co=0; // ha co xuong ==> ko phai la so chan
if(co==0) // co da ha xuong
printf("%d la so le",x);
else // co chua ha xuong
printf("%d la so chan",x);
}