14/04/2016 03:29:29 PM

Bài viết sưu tầm

Giải bài toán Cổ bằng phương pháp tìm tiếm nhị phân
Mở rộng phương pháp tìm kiếm nhị phân
 
Trong các bài toán Tin học, có những bài toán không chỉ đơn thuần tìm vị trí của 
 
khóa X trong một dãy đối tượng được sắp xếp mà có thể là tìm phần tử có khóa 
 
nhỏ nhất lớn hơn X (hoặc tìm phần tử có khóa lớn nhất nhỏ hơn X). Khi đó vẫn sử 
 
dụng tìm kiếm nhị phân nhưng cần cải tiến một chút trong hàm tìm kiếm này.
 
Ví dụ: dùng tìm kiếm nhị phân để tìm phần tử có giá trị nhỏ nhất lớn hơn X trong 
 
dãy phần tử đã sắp xếp tăng dần.
 
Function TK_NP(x:Longint): Longint;
 
Var    L, R, Mid: Longint;
 
Begin
 
L := 1; R := N;
 
while (L <= R) do
 
Begin
 
Mid := (L + R) div 2;
 
if (K[Mid] <= X) then L := Mid + 1
 
else R := Mid – 1;
 
End; 
 
exit(L);
 
End;
 
Tương tự, ta có thể tìm phần tử lớn nhất nhỏ hơn giá trị X.
 
Bài toán áp dụng
 
Bài 1. Bài toán cổ
 
"Vừa gà vừa chó
 
Bó lại cho tròn
 
Ba mươi sáu con
 
Một trăm chân chẵn
 
Hỏi có bao nhiêu gà bao nhiêu chó?"
 
Bài toán cổ này chúng đã biết cách giải từ thời cấp 1. Hôm nay chúng ta cùng đi 
 
quyết bài toán tổng quát với số con gà và con chó, số chân gà và chân con chó tùy 
 
Yêu cầu: Cho biết tổng số con gà và con chó là M, tổng số chân là N. Hãy xác 
 
định số lượng con gà và con chó.
 
Dữ liệu vào: Đọc từ file CHICKDOG.INP chứa hai số nguyên dương M, N (2 ≤ 
 
M, N ≤ 1015; N/4 < M < N/2)
 
Kết quả: Ghi ra file CHICKDOG.INP chứa hai số nguyên là số con gà và con chó, 
 
nếu không có nghiệm thì in -1.
 
Ví dụ:
 
CHICKDOG.INP CHICKDOG.OUT 
 
36 100 22 14 
 
Hướng dẫn:
 
Cách 1:
 
Thử số lượng con chó từ 1 đến N/4. Nếu số chân phù hợp thì lấy kết quả và kết 
 
thúc.
 
Function Timcho:Int64;
 
Begin
 
For x:=1 To N Div 4 Do
 
Exit(-1);
 
End;
 
If x*4+(M-x)*2 = N) Then Exit(x;)
 
Độ phức tạp là O(N)
 
Cách 2: 
 
Sử dụng thuật toán nhị phân tìm số chó như sau:
 
d:=1;c:=N Div 4;
 
Trong khi d ≤ c thì
 
- g:=(d+c) Div 2;
 
- Nếu g*4+(M-g)*2 = N thì số chó là g và kết thúc
 
- Nếu g*4+(M-g)*2 > N thì số chó quá lớn thì chặt nhị phân trong đoạn d đến 
 
c=g-1
 
- Nếu g*4+(M-g)*2 < N thì số chó quá nhỏ thì chặt nhị phân trong đoạn 
 
d=g+1 đến c
 
Function Timcho:Int64;
 
Begin
 
d:=1;c:=N Div 4;
 
While d<=c Do
 
Begin
 
g:=(d+c) Div 2;
 
If g*4+(M-g)*2=N Then Exit(g);
 
If g*4+(M-g)*2>N Then c:=g-1
 
Else d:=g+1;
 
End;
 
Exit(-1);
 
End;
 
Độ phức tạp là O(LogN)

» Tin mới nhất:

» Các tin khác:

Hôm nay, ngày

26/11/2024

Tuần học:

17

Sinh viên tiêu biểu

Số lượt truy cập: 9090896