Tìm kiếm trong Pascal
- Thứ tư - 05/08/2020 09:34
- In ra
- Đóng cửa sổ này
1. TỐNG QUÁTMột trong các nhiệm vụ cơ bản của máy tính là tìm kiếm. Từ một cơ sở dữ liệu cho trước và một đối tượng cho trước ta phải trả lời hai câu hỏi:- Đối tượng có mặt trong cơ sở dữ liệu đó hay không ?- Nếu có thì cho biết vị trí của nó.
Để đơn giản hóa vấn đề ở đây chúng ta chỉ giới hạn vấn đề trong việc tìm một giá trị X (nguyên) xem có nằm trong một dãy các số nguyên hay không ?
Phương pháp tổng quát là đi so sánh X với các phần tử của dãy, nếu việc so sánh cho kết quả TRUE thì việc tìm kiếm thành công.
Có nhiều thuật toán để tìm kiếm, ỏ đây chúng ta chỉ xét 2 thuật toán cơ bản đó là:
- Tìm tuần tự (Sequential Search).
- Tìm nhị phân (Binary Search).
2. TÌM KIẾM TUẦN TỰ TRÊN MỘT DÃY CHƯA CÓ THỨ TỰ
a) Thuật toán
- So sánh từng phần tử của dãy A[1..n] với giá trị x.
- Trong khi đi từ phần tử đầu đến phần tử cuối của dãy:
+ Nếu tìm thấy giá trị x thì thoát ra và thông báo thứ tự của thành phần thứ i thỏa A[i] = x.
+ Nếu sau khi đi hết mà không tìm thấy thì việc tìm kiếm xem như kết thúc với kết quả là 0.
b) Lập trình Pascal
Function Tim (x: integer; A: Array[1..n] of integer);Word; Var i : word;
Begin
i:= 1;
While (i <= n) and not (x = A[i]) do
inc (i);
If i > n then Tim := 0
Else Tim:= i;
End.
3. TÌM KIÊM TUẦN TỰ TRÊN MỘT DÃY ĐÃ CÓ THỨ TỰ
a) Thuật toán
- Thuật toán tìm tuần tự trong trường hợp xấu nhất là tìm không thấy do đó sẽ thực hiện n lần so sánh.
- Giả sử dãy A đã được sắp thứ tự tăng dần ta có thể cải tiến lại thuật toán trên để chạy nhanh hơn như sau:
+ Bắt đầu từ i = 1.
+ Trong khi (i <= n) và (A[i] < x) tăng i.
+ Nếu (i < n và A[i] > x) hay (i > n) thì:
• Không tìm thấy.
Ngược lại thì:
• Giá trị cần tìm ở thành phần thứ i.
b) Lập trình Pascal
Function Tim (x: integer; A: Array[1..n] of Integer): word;
Var i: word;
Begin
i:= 1;
While (i <= n) and (x > A[iJ) do
Inc (i);
If ((i <= n) and (A[i] > x)) or (i > n) then
Tim:= 0
Else
Tim:= i;
End;
• Chú ý:
Nếu dãy được sắp xếp theo thứ tự giảm dần thì ta phải đảo điều kiện trong các biểu thức điều kiện như sau:
While (i <= n) and. (x < A[i])
If ((i <= n) and (A[i] < x)) or (i > n).
4. TÌM KIẾM TUẦN TỰ VỚI LÍNH CANH
a) Thuật toán
- Dùng một lính canh cụ thể là phần tử A[n + 1] có thể đơn giản hóa quá trình tự kiếm tuần tự.
- Trước khi tìm kiếm phần tử có giá trị bằng X trong đoạn dãy A[1..n] ta đặt giá trị đó tại trạm canh bằng lệnh gán:
a[n + 1]:= X;
- Nhờ có lính canh nên câu lệnh lặp:
REPEAT
i:= i + 1
UNTIL
A[i] := x;
luôn luôn được kết thúc một cách tự nhiên, bởi vì trong trường hợp tìm được ta sẽ có A[i] = x với (1 < i < n), còn trong trường hợp giá trị x không có mặt trong mảng A[1..n] thì ta vẫn có:
A[i] := x với i = t + 1
- Việc dùng lính canh đòi hỏi mảng a phải chứa ít ra là n + 1 phần tử.
b) Lập trình Pascal
A[n + 1]:= x; {Đặt lính canh}
I := 0;
Repeat
I := i + 1;
Until A[i]:= x;
If i <= n then writeln(i)
else Writein ('không tìm được');
5. TÌM KIẾM NHỊ PHÂN TRÊN MỘT MẢNG ĐƯỢC SẮP
a) Thuật toán
- Giả sử mảng A[1..n] đã được sắp thứ tự tăng dần.
- Ta chia đôi mảng A xem thành phần ở giữa có giá trị lớn hơn hay nhỏ hơn giá trị x để từ đó xác định nên tiếp tục tìm kiếm trên dãy trên hay dãy dưới. Giả sử chọn được dãy trên, tiếp tục chia đôi dãy trên để tìm kiếm cho đến khi gặp hoặc không thể chia đôi được nữa (nghĩa là không tìm thấy).
Ta dùng 3 biến Low, High, Mid để lưu giữ chỉ số của đầu, cuối, giữa của dãy đang tìm kiếm.
- Ban đầu cho Low:= 1; High:= n.
- Chừng nào High > Low thì thực hiện:
• Mid + (Low + Ligh) Div 2
• Nếu x > A[Mid] thì
Low:= Mid + 1
Ngược lại (x <= A[Mid]
• Nếu x < A[Mid] thì
High:= Mid - 1
Ngược lại (a = A[Mid])
High:= -1
• Nếu High = -1 thì đã tìm thấy x tại thành phần thứ Mid.
Ngược lại không tìm thấy.
b) Lập trình Pascal
Function Tim (x: integer; A: Array[1..n] of integer): word;
Var
Low, High, Mid: integer;
Begin
Low:= 1; High:= n;
While High >= Low do
Begin
Mid:= (High + Low) div 2;
If (A[Mid] < x) then
Low := Mid + 1
else
If (x < x[Mid] then
High := Mid - 1
Else
High:= -1
end;
If high = -1 then Tim:= Mid; else Tim:= 0
Phương pháp tổng quát là đi so sánh X với các phần tử của dãy, nếu việc so sánh cho kết quả TRUE thì việc tìm kiếm thành công.
Có nhiều thuật toán để tìm kiếm, ỏ đây chúng ta chỉ xét 2 thuật toán cơ bản đó là:
- Tìm tuần tự (Sequential Search).
- Tìm nhị phân (Binary Search).
2. TÌM KIẾM TUẦN TỰ TRÊN MỘT DÃY CHƯA CÓ THỨ TỰ
a) Thuật toán
- So sánh từng phần tử của dãy A[1..n] với giá trị x.
- Trong khi đi từ phần tử đầu đến phần tử cuối của dãy:
+ Nếu tìm thấy giá trị x thì thoát ra và thông báo thứ tự của thành phần thứ i thỏa A[i] = x.
+ Nếu sau khi đi hết mà không tìm thấy thì việc tìm kiếm xem như kết thúc với kết quả là 0.
b) Lập trình Pascal
Function Tim (x: integer; A: Array[1..n] of integer);Word; Var i : word;
Begin
i:= 1;
While (i <= n) and not (x = A[i]) do
inc (i);
If i > n then Tim := 0
Else Tim:= i;
End.
3. TÌM KIÊM TUẦN TỰ TRÊN MỘT DÃY ĐÃ CÓ THỨ TỰ
a) Thuật toán
- Thuật toán tìm tuần tự trong trường hợp xấu nhất là tìm không thấy do đó sẽ thực hiện n lần so sánh.
- Giả sử dãy A đã được sắp thứ tự tăng dần ta có thể cải tiến lại thuật toán trên để chạy nhanh hơn như sau:
+ Bắt đầu từ i = 1.
+ Trong khi (i <= n) và (A[i] < x) tăng i.
+ Nếu (i < n và A[i] > x) hay (i > n) thì:
• Không tìm thấy.
Ngược lại thì:
• Giá trị cần tìm ở thành phần thứ i.
b) Lập trình Pascal
Function Tim (x: integer; A: Array[1..n] of Integer): word;
Var i: word;
Begin
i:= 1;
While (i <= n) and (x > A[iJ) do
Inc (i);
If ((i <= n) and (A[i] > x)) or (i > n) then
Tim:= 0
Else
Tim:= i;
End;
• Chú ý:
Nếu dãy được sắp xếp theo thứ tự giảm dần thì ta phải đảo điều kiện trong các biểu thức điều kiện như sau:
While (i <= n) and. (x < A[i])
If ((i <= n) and (A[i] < x)) or (i > n).
4. TÌM KIẾM TUẦN TỰ VỚI LÍNH CANH
a) Thuật toán
- Dùng một lính canh cụ thể là phần tử A[n + 1] có thể đơn giản hóa quá trình tự kiếm tuần tự.
- Trước khi tìm kiếm phần tử có giá trị bằng X trong đoạn dãy A[1..n] ta đặt giá trị đó tại trạm canh bằng lệnh gán:
a[n + 1]:= X;
- Nhờ có lính canh nên câu lệnh lặp:
REPEAT
i:= i + 1
UNTIL
A[i] := x;
luôn luôn được kết thúc một cách tự nhiên, bởi vì trong trường hợp tìm được ta sẽ có A[i] = x với (1 < i < n), còn trong trường hợp giá trị x không có mặt trong mảng A[1..n] thì ta vẫn có:
A[i] := x với i = t + 1
- Việc dùng lính canh đòi hỏi mảng a phải chứa ít ra là n + 1 phần tử.
b) Lập trình Pascal
A[n + 1]:= x; {Đặt lính canh}
I := 0;
Repeat
I := i + 1;
Until A[i]:= x;
If i <= n then writeln(i)
else Writein ('không tìm được');
5. TÌM KIẾM NHỊ PHÂN TRÊN MỘT MẢNG ĐƯỢC SẮP
a) Thuật toán
- Giả sử mảng A[1..n] đã được sắp thứ tự tăng dần.
- Ta chia đôi mảng A xem thành phần ở giữa có giá trị lớn hơn hay nhỏ hơn giá trị x để từ đó xác định nên tiếp tục tìm kiếm trên dãy trên hay dãy dưới. Giả sử chọn được dãy trên, tiếp tục chia đôi dãy trên để tìm kiếm cho đến khi gặp hoặc không thể chia đôi được nữa (nghĩa là không tìm thấy).
Ta dùng 3 biến Low, High, Mid để lưu giữ chỉ số của đầu, cuối, giữa của dãy đang tìm kiếm.
- Ban đầu cho Low:= 1; High:= n.
- Chừng nào High > Low thì thực hiện:
• Mid + (Low + Ligh) Div 2
• Nếu x > A[Mid] thì
Low:= Mid + 1
Ngược lại (x <= A[Mid]
• Nếu x < A[Mid] thì
High:= Mid - 1
Ngược lại (a = A[Mid])
High:= -1
• Nếu High = -1 thì đã tìm thấy x tại thành phần thứ Mid.
Ngược lại không tìm thấy.
b) Lập trình Pascal
Function Tim (x: integer; A: Array[1..n] of integer): word;
Var
Low, High, Mid: integer;
Begin
Low:= 1; High:= n;
While High >= Low do
Begin
Mid:= (High + Low) div 2;
If (A[Mid] < x) then
Low := Mid + 1
else
If (x < x[Mid] then
High := Mid - 1
Else
High:= -1
end;
If high = -1 then Tim:= Mid; else Tim:= 0
Bản quyền bài viết thuộc về Sachgiai.com. Ghi nguồn Sách giải.com khi đăng lại bài viết này.