Bài 11:
MẢNG MỘT CHIỀU
(tiết 2)
1. Bài toán 1: Tìm phần tử lớn nhất của dãy số nguyên A gồm N phần tử (N 250 và các A[i] 500). Nếu dãy có nhiều phần tử lớn nhất, chỉ cần đưa ra chỉ số của phần tử lớn nhất đầu tiên.
Input:
Output:
Số nguyên dương N và dãy A gồm N số nguyên A1, A2, ..., AN.
Chỉ số và phần tử lớn nhất trong dãy số nguyên.
Ví dụ: Tìm phần tử lớn nhất trong dãy số sau:
7, 10, 25, 17, 2, 50, 45
25
7
10
2
17
45
50
Max
THUẬT TOÁN THỰC HIỆN BẰNG PASCAL
1. Nhập N và dãy A1, A2, ..., AN;
2. Max A1; csmax 1;
3. i 2. Nếu i > N: đưa ra Max
và csmax => Kết thúc;
4. 4.1. Nếu Ai > Max thì
Max Ai; csmax i;
4.2. i i + 1 rồi quay lại bước 3;
write(‘ Nhap so phan tu cua day so: ’);
readln(N);
for i:=1 to N do
begin
write(‘ Nhap phan tu thu ’ ,i, ’ = ’);
readln(A[i]);
end;
Max:=A[1]; csmax:=1;
for i :=2 to N do
if A[i]>Max then
begin
Max:=A[i];
csmax:=i;
end;
2. Bài toán 2: Sắp xếp dãy số nguyên gồm N phần tử (N 250 và các A[i] 500) thành dãy tăng.
Input:
Output:
Số nguyên dương N và dãy A gồm N số nguyên A1, A2, ..., AN.
Dãy số A đã được sắp xếp.
Ví dụ: Sắp xếp dãy sau thành dãy tăng:
20, 12, 70, 25, 17, 9
20
12
70
25
17
9
Dãy ban đầu:
20
12
70
25
17
9
70
Duyệt lần 1:
Duyệt lần 2:
12
20
25
17
9
70
25
Duyệt lần 3:
Duyệt lần 4:
Duyệt lần 5:
12
17
9
20
25
70
12
9
17
20
25
70
9
12
17
20
25
70
THUẬT TOÁN THỰC HIỆN BẰNG PASCAL
1. Nhập số phần tử N và dãy số
A1, A2, ..., AN;
2. j N;
write(‘ Nhap so phan tu cua day so: ’);
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 so duoc sap xep la: ‘);
for i:= 1 to N do write(A[i] : 4);
3. Nếu j < 2 thì đưa ra dãy A đã
được sắp xếp rồi kết thúc.
4. j j –1; i 0;
5. i i + 1;
6. Nếu i > j thì quay lại bước 3;
7. Nếu Ai > Ai+1 thì hoán đổi vị trí
Ai và Ai+1 cho nhau;
8. Quay lại bước 5.
Trò chơi
Tổ 1 và tổ 4, mỗi tổ chọn ra 5 bạn lên bảng. Sau đó mỗi tổ cử thêm 1 đại diện lên áp dụng thuật toán sắp xếp dãy tăng để xếp 5 bạn này thành một hàng có chiều cao tăng dần từ trái sang phải.
Nhận xét tính đúng đắn khi áp dụng thuật toán sắp xếp dãy tăng của 2 tổ:
Tổ 2 nhận xét tổ 1.
Tổ 3 nhận xét tổ 4.
Tổ nào xếp nhanh hơn và đúng với thuật toán, tổ đó sẽ thắng.
Củng cố:
Xem lại thuật toán tìm max.
Xem lại thuật toán sắp xếp dãy số tăng.
Hướng dẫn bài tập:
Dựa vào thuật toán tìm max, viết thuật toán tìm min.
Dựa vào thuật toán sắp xếp dãy số tăng, viết thuật toán sắp xếp dãy số giảm.
Chúc các em làm bài tốt !
nguon VI OLET
