Bài tập mảng 1 chiều

NHIỆT LIỆT CHÀO MỪNG QUÝ THẦY CÔ ĐẾN DỰ GIỜ THĂM LỚP
KIỂM TRA BÀI CŨ
Phát biểu khái niệm mảng một chiều, cú pháp khai báo mảng, cách thức để tham chiếu đến các phần tử trong mảng?
bµi to¸n s¾p xÕp
bµi to¸n t×m max, min
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
1. TìM GIá TRị MAX.
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
Bài toán: Cho mảng A chứa các số nguyên dương như sau: 2, 7, 6, 9, 1, 4.
Hãy tìm giá trị lớn nhất và vị trí xuất hiện của chúng trong mảng trên:
2
7
6
9
1
4
A:
1
2
3
4
5
6
a. Khái niệm
b. Thuật toán
c. Chương trình
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
Thuật toán tìm max:
2
7
6
9
1
4
A:
1
2
3
4
5
6
1. TìM GIá TRị MAX.
B1: Nhập mảng A cho trước; (n phần tử)
B2: max  A1, i  1;
B3: Nếu i>n thì thông báo max rồi kết thúc;
B41: Nếu Ai > max thì max  Ai;
B42: i  i+1 rồi quay lại B3;
Đầu tiên gán giá trị của phần tử thứ nhất cho biến max, tiếp theo lần lượt so sánh giá trị của max với tất cả các phần tử còn lại, nếu giá trị của max nhỏ hơn giá trị của phần tử đang so sánh thì gán ngay giá trị đó cho max; như vậy đến lượt so sánh cuối cùng sẽ tìm được giá trị của max.
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
Minh họa thuật toán tìm max:
2
6
9
1
4
A:
1
2
3
4
5
6
T
F
7
T
F
F
2
7
9
Max
1. TìM GIá TRị MAX.
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
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 cua mang:’);
Readln(N);
For i:=1 to N do
Begin
Write(‘phan tu thu’,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 rồi quay lại B3
For i:=2 to N do
if a[i]>Max then
begin
Max:=a[i];
csMax:=i;
end;
Writeln(‘GTLN la:’,Max,’Vi tri:’,csMax);
Type arrInt=array[1..250] of integer;
Var N, i , max, csmax : integer; a: arrInt;
Program tim_max;
Begin
Write(‘nhap so luong phan tu cua mang:’);
Readln(N);
For i:=1 to N do
Begin
Write(‘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;
Write(‘Gia tri lon nhat la:’, max:4, ‘Vi tri dat max la:’, csmax:4);
End.
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
Minh họa thuật toán tìm min: (tương tự max)
2
6
9
1
4
A:
1
2
3
4
5
6
F
F
7
F
T
F
2
Min
1
1. TìM GIá TRị MIN.
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
Type arrInt=array[1..250] of integer;
Var N, i , min, csmin : integer; a: arrInt;
Program tim_min;
Begin
Write(‘nhap so luong phan tu cua mang:’);
Readln(N);
For i:=1 to N do
Begin
Write(‘phan tu thu’,i);
Readln(a[i]);
End;
min:=a[1]; csmin:=1;
For i:=2 to N do
if a[i] begin
min:=a[i];
csmin:=i;
end;
Write(‘Gia tri nho nhat la:’, min:4, ‘Vi tri dat min la:’, csmin:4);
End.
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
1. bài toán sắp xếp.
a. Khái niệm:
Sắp xếp là quá trình bố trí lại các phần tử của một tập các đối tượng nào đó theo một thứ tự nhất định.
Ví dụ: Sắp xếp điểm trung bình của các học sinh trong lớp theo thứ tự từ cao đến thấp, sắp xếp các học sinh theo đội hình từ thấp đến cao, sắp xếp tên theo thứ tự A, B, C,...
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
1. bài toán sắp xếp.
Minh họa: Cho 10 chiếc cọc có chiều cao khác nhau, cần sắp xếp các cọc theo thứ tự từ thấp đến cao.
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
1. bài toán sắp xếp.
b. Thuật toán sắp xếp trao đổi:
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
B1: Nhập n, các số hạng a1, a2,…,an;
B2: m ← n;
B3: Nếu m<2 thì đưa ra dãy a đã được sắp xếp rồi kết thúc;
B4: m ← m-1, i ← 0;
B5: i ← i+1;
B6: Nếu i>m thì quay lại B3;
B7: Nếu ai>ai+1 thì tráo đổi ai và ai+1 cho nhau;
B8: Quay lại B5.
 Sơ đồ khối.
M ? N
Nhập N và a1, a2,..., aN
M ? M - 1; i ? 0
M < 2 ?
i > M ?
Đúng
Sai
ai > ai+1 ?
i ? i + 1
Đưa ra A rồi
kết thúc
Đúng
Sai
Sai
Đúng
Tráo đổi ai và ai+1
b. Thuật toán sắp xếp trao đổi:
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 dã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ề kế cận đá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 sẽ được sắp xếp
CHO DÃY SỐ SAU: 3 2 9 7 6
Nhận xét: Ta thấy rằng, sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng ở vị trí cuối dãy.
Tương tự: Sau lượt thứ hai, giá trị lớn thứ hai được xếp đúng ở vị trí sát cuối dãy,… Có thể hình dung, sau mỗi lượt có ít nhất 1 số hạng đã được xếp đúng vị trí và không còn tham gia vào quá trình đổi chỗ nữa, giống như các bọt nước từ đáy hồ (đầu dãy) nổi dần và khi đã lên mặt nước (cuối dãy) rồi thì tan biến. Có thể vì thế mà sắp xếp bằng tráo đổi còn có tên gọi là sắp xếp nổi bọt (Bubble Sort).
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
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 lệnh nào?
for j:=N downto 2 do
Đ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 biến 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;
Type
arrInt=array[1..250] of integer;
Var
N, i , j , tg : integer; A: arrInt;
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
tg:=A[i];
A[i]:=A[i+1];
A[i+1]:=tg;
end;

writeln(‘Day duoc sap xep la:’);
for i:=1 to N do write(A[i]:4);
readln;
End.
Program sap_xep_mang;
SỞ GIÁO DỤC VÀ ĐÀO TẠO
THỪA THIÊN HUẾ
2. Sắp xếp.
a. Bài toán
b. Thuật toán
1. Tìm giá trị max, min.
c. Chương trình
a. Khái niệm
b. Thuật toán
c. Chương trình
CỦNG CỐ
DẶN DÒ
 Kiểu mảng là một kiểu dữ liệu có cấu trúc được dùng nhiều trong lập trình. Những bài toán sắp xếp, tìm kiếm là các bài toán thường gặp và có ý nghĩa quan trọng, cần nắm kỹ thuật toán, cấu trúc dữ liệu để giải quyết các bài toán trên.
 Kiểu mảng một chiều thường được dùng trong những chương trình cần tổ chức dữ liệu như một dãy các phần tử cùng kiểu để giải quyết các bài toán đặt ra.
 Khi cần tổ chức dữ liệu có cấu trúc bảng, ta nghĩ đến việc dùng mảng hai chiều. (về nhà xem nội dung bài mảng hai chiều)