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ó nên lập kế hoạch nghề nghiệp (18/04/2025)
- Xử lý ngoại lệ (18/04/2025)
- Cấu trúc KPA của CMM (18/04/2025)
- EIGRP-redistribute static (18/04/2025)
- EIGRP with authentication (18/04/2025)
» Các tin khác:
- Sửa đổi cơ sở dữ liệu (05/04/2016)
- Xóa cơ sở dữ liệu trong SQL Server (05/04/2016)
- Backbone framework (02/04/2016)
- Sử dụng bản mẫu xác định yêu cầu phần mềm (17/03/2016)
- Các loại yêu cầu phần mềm (17/03/2016)
- Giới thiệu semantic ui framework (17/03/2016)
- Giới thiệu về Phaser framewrok (17/03/2016)
- Cấu hình và đăng nhập vào hệ thống OpenStack Autopilot Canonical - Phần 2 (16/03/2016)
- Cài đặt OpenStack Private Cloud với OpenStack Autopilot Canonical - Phần 1 (16/03/2016)
- Giới thiệu về lý thuyết phân vùng ngẫu nhiên của Kingman (16/03/2016)
