KỸ THUẬT ĐẶT LÍNH CANH, CỜ HIỆU
A. ĐẶT LÍNH CANH
Trong lập trình, kỹ thuật đặt lính canh khá cơ bản, chủ yếu áp dụng trong các bài tìm kiếm giá trị lớn nhất hoặc nhỏ nhất, nó đảm bảo được tính chính xác trong thuật toán tổng quát.
Ý tưởng: xét bài toán tìm kiếm giá trị lớn nhất trong một mảng số, đặt biến kết quả bằng giá trị đầu tiên trong mảng (biến này gọi là biến lính canh), xét lần lượt phần tử thứ 2 đến n, nếu có một phần tử nào lớn hơn “lính canh” ban đầu thì thực hiện đổi “lính canh”.
Tại sao nên dùng lính canh?
Lính canh đảm bảo được tính chính xác vì nó chỉ so sánh các phần tử trong mảng với nhau. Nếu như chúng ta đặt biến nhỏ nhất hoặc lớn nhất trong mảng là một con số mặc định, kết quả cuối cùng có thể sẽ sai đó! VD: để tìm max trong mảng, ta đặt biến kết quả mmax = 0, nhưng vô tình mảng chỉ chứa những số nguyên < 0, rõ ràng kết quả cuối cùng mmax = 0 do không có số nào trong mảng > 0 => Sai rồi.
a = [20,5,81,4,32,75,9,15] mmax = a[0] # Biến lính canh # Vòng lặp xét từ phần tử tiếp theo trong LIST for i in range(1,len(a)): # Kiểm tra và thay thế lính canh nếu có phần tử lớn hơn if a[i] > mmax: mmax = a[i] # Đưa ra phần tử lớn nhất trong mảng print(mmax) # 81
B. ĐẶT CỜ HIỆU
Cờ hiệu (hay Flag trong tiếng Anh) để chỉ một biến dùng để đánh dấu kết quả, đa số để lưu lại kết quả cuối cùng trong khi chạy vòng lặp.
Ý tưởng: ta thường dùng biến bool (true, false) để đặt cờ hiệu, ban đầu ta đặt cho lá cờ này một giá trị mặc định, trong suốt vòng lặp, ta sẽ cập nhật lá cờ này.
Nói có vẻ khó hiểu, nhưng thật ra lại rất dễ hình dung, lấy ví dụ về bài toán kiểm tra tính nguyên tố của một số N, làm sao để biết được kết quả cuối cùng – khi mà vòng lặp đã hoàn thành? Cùng xem đoạn code mẫu:N = int(input('Nhập n: ')) #Biến cần kiểm tra tính nguyên tố flag = True # Khai báo cờ hiệu kèm giá trị mặc định (flag = cờ) # Vòng lặp từ 2 đến căn bậc 2 của N for i in range(2,(int(N**0.5))+1): # Chia lấy phần dư (mod) if N % i == 0: # Nếu N chia hết cho i thì đặt cờ hiệu = false flag = False break #Nếu cờ hiệu vẫn là true thì N là số nguyên tố if flag == True: print('N là số nguyên tố!') else: print('N không là số nguyên tố!')Giải thích: gọi flag là cờ để chỉ tính nguyên tố của số N, ban đầu mặc định biến này là true, trong lúc chạy vòng lặp, nếu có bất kì số nào mà N chia hết thì đặt flag = false. Sau khi kết thúc vòng lặp, ta thấy rằng nếu có một số nào đó làm cho cờ hiệu flag chuyển sang false tức đã có một số mà N chia hết => N không là số nguyên tố, ngược lại nếu N không chia hết cho bất kì số nào thì biến flag vẫn giữ nguyên giá trị ban đầu là true => N là số nguyên tố.