TIN HỌC 11
Bài 13
BÀI TẬP MẢNG MỘT CHIỀU
B. CÁC VÍ DỤ
Bài 1. Tìm phần tử lớn nhất của dãy số nguyên (với n<=250 và A[i]<=500). Nếu dãy có nhiều phần tử có cùng giá trị thì đưa ra phần tử có giá trị lớn nhất đầu tiên
INPUT: Nhập số nguyên dương N và dãy gồm N số
nguyên dương a1,a2,…aN
OUTPUT: Giá trị lớn nhất của dãy và chỉ số tương
ứng của nó (csMax)
THUẬT TOÁN TÌM MAX
1
5
2
3
4
7
THUẬT TOÁN THỂ HIỆN BẰNG PASCAL
B1. Nhập n và dãy a1…aN
Write(‘nhap so luong phan tu’);
Readln(N);
For i:=1 to N do
Begin
Write(‘phan tu ’,i);
readln(a[i]);
End;
B2. Max← a[1], i ←1;
Max:=a[1]; csMax:=1;
B3. Nếu i>N thì đưa ra Max rồi kt
B4.
B41. Nếu a[i]>Max thì Max ←a[i]
B42. i ←i+1 quay lại B3
For i:=2 to N do
if a[i]>Max then
begin
Max:=a[i]; csMax:=I
end;
THUẬT TOÁN SẮP XẾP BẰNG TRÁO ĐỔI (Exchange Sort)
Ví dụ 2:
Input: Số nguyên dương N (N<=250) và dãy A gồm N số nguyên dương A1, A2,…,AN, mỗi số đều không vượt quá 500
Output: Dãy số A đã được sắp xếp thành dãy không giảm
A
CHO DÃY SỐ SAU: 3 2 9 7 6
Giả sử:
Mỗi phần tử trong dãy được xem như là một bọt nước
Trọng lượng của bọt nước thứ i là giá trị của A[i]
Lượt 1
i chạy từ đầu dãy đến vị trí [cuối dãy -1]
Khi a[i]>a[i+1] tức bọt nước bên trên nặng hơn bọt nước bên dưới, bọt nước trên chìm xuống và bọt nước bên dưới nổi lên (tráo đổi vị trí)
Sau lượt 1 bọt nước nặng nhất sẽ chìm về cuối đáy
Lượt 2
i chạy từ đầu đến vị trí [cuối dãy -1] bỏ qua phần tử cuối cùng
Sau lượt thứ 2 bọt nước nặng thứ 2 sẽ chìm về đáy
Quá trình duyệt tráo đổi được lặp đi lặp lại cho đến khi duyệt chỉ còn 2 phần tử và dãy được sắp xếp
NHẬN XÉT: ĐƯA RA ĐOẠN LỆNH SẮP XẾP
Số phần tử ở các lần duyệt (j) sẽ giảm từ n xuống 2 phần tử
Việc giảm dần giá trị các lần duyệt cho phép loại ra các giá trị lớn nhất ở cuối dãy thể hiện bằng cấu trúc Pascal ra sao?
for j:=N downto 2 do
NHẬN XÉT: ĐOẠN CHƯƠNG TRÌNH TRÁO ĐỔI
Tại mỗi lần duyệt
(ứng với mỗi lần duyệt của j)
- Cho i chạy từ 1 đến số phần tử -1
Nếu A[i]>A[i+1] thì
Tráo đổi A[i] với A[i+1]
thông qua trung gian (tg)
for i:=1 to j-1 do
if A[i]>A[i+1] then
begin
tg:=A[i];
A[i]:=A[i+1];
A[i+1]:=A[i];
end;
CHƯƠNG TRÌNH PASCAL HOÀN CHỈNH
Type
arrInt=array[1..250] of integer;
Var
N, i , j , t : integer; A: arrInt;

Khai báo mảng 1 chiều
Nhập giá trị cho các phần tử mảng
Sắp xếp mảng
In ra mảng 1 chiều sau khi sắp xếp
Begin
write(‘nhap so luong phan tu cua day, N= ’);
readln(N);
for i:=1 to N do
begin
write(‘nhap phan tu thu’,i);
readln(A[i]);
end;

for j:=N downto 2 do
for i:=1 to j-1 do
if A[i] > A[i+1] then
begin
t:=A[i]; A[i]:=A[i+1]; A[i+1]:=t;
end;

writeln(‘day duoc sap xep la’);
for i:=1 to N do write(A[i]:4);
End.

CỦNG CỐ
Quá trình duyệt các phần tử trong mảng thường sử dụng cấu trúc gì? Tại sao?
Quá trình hoạt động của 2 vòng lặp lồng nhau như thế nào?