Bài 11. Kiểu mảng

Giáo Viên: Nguyễn Quang Ánh
Trường THPT EaH’leo
Tiết 18
Kiểm Tra bài cũ
1> Hãy cho biết đoạn chương trình sau dùng để đếm số lẽ trong phạm vi N có những lỗi gì?
Write(‘Nhap vao N = ‘);Readln(N);
dem :=0;
i := 1;
While i<=N do
Begin
dem := dem + i;
i := i + 2;
End;
Writeln(‘So le = ‘,dem);
2> Với đoạn chương trình trên khi nhập N = 8 thì dem sẽ được kết quả là bao nhiêu?
Program Tinh_So_Le;
Uses Crt;
Var I, dem, N : Integer;
Begin
Clrscr;
Write(‘Nhap vao N = ‘);Readln(N);
dem :=0;
i := 1;
While i<=N do
Begin
dem := dem + 1;
i := i + 2;
End;
Writeln(‘So le = ‘,dem);
Readln;
End.
Bài 11
KIỂU MẢNG
1> Kiểu mảng một chiều:
* Mảng một chiều là dãy hữu hạn các phần tử cùng kiểu, mỗi phần tử mang một chỉ số. Mảng phải được đặt tên và để mô tả mảng một chiều ta cần xác định kiểu của các phần tử và cách đánh chỉ số các phần tử.
*Ví dụ: Xét bài toán nhập vào nhiệt độ(trung bình) của mỗi ngày trong tuần, tính và đưa ra màn hình nhiệt độ trung bình của tuần và số ngày trong tuần có nhiệt độ cao hơn nhiệt độ trung bình của tuần.
* Ý Tưởng
Ta có thể dùng 7 biến để lưu trữ nhiệt độ của các ngày trong tuần.
Program Nhiet_do_tuan;
Uses Crt;
Var t1, t2, t3, t4, t5, t6, t7, tb: real; dem:integer;
Begin
Clrscr;
Writeln('Nhap vao nhiet do cua 7 ngay :'); Readln(t1, t2, t3, t4, t5, t6, t7);
tb:=(t1+t2+t3+t4+t5+t6+t7)/7; dem:=0;
if t1>tb then dem:=dem + 1;
if t2>tb then dem:=dem + 1;
if t3>tb then dem:=dem + 1;
if t4>tb then dem:=dem + 1;
if t5>tb then dem:=dem + 1;
if t6>tb then dem:=dem + 1;
if t7>tb then dem:=dem + 1;
Writeln('Nhiet do trung binh trong tuan la tb = ',tb:6:2);
Writeln('So ngay co nhiet do cao hon nhiet do tb la = ',dem);
Readln;
End.
Chương giải bài toán có thể được viết bằng Pascal như sau:
Câu hỏi đặt ra
Khi giải bài toán trên với N ngày(N khá lớn) thì sẽ có nhược điểm gi?
- Để giải quyết những nhược điểm trên ta cần kiểu dữ liệu mảng một chiều để mô tả dữ liệu.
a> Cách khai báo mảng một chiều:
* Cách khai báo trực tiếp:
Var : Array[kiểu chỉ số] of ;
* Cách khai báo gián tiếp:
Type =Array[kiểu chỉ số] of ;
Var : ;
*Ví dụ:
Ví dụ với bài toán nhiệt độ ở trên ta có thể khai báo như sau:
Var nhietdo : array[1..100] of real;
Const max=100;
Type mang = ARRAY[1..max] Of Real;
Var nhietdo : mang;
Khai báo trực tiếp
Khai báo gián tiếp
Chỉ số phần tử ->1 2 20 99 100
Mảng nhietdo -> 22 25 27 33 25
Minh họa
Nhietdo[20]
Chương trình mẫu
Program Tinh_Nhiet_Do_Ngay;
Uses Crt;
Const max=100;
Type mang = ARRAY[1..max] Of Real;
Var nhietdo : mang;
dem, i, N : integer;
trung_binh, tong : real;
Begin
Clrscr;
Write('Nhap so ngay : '); Readln(N);
tong:=0;
For i:=1 to N do
begin
write('Nhap nhiet do ngay ',i,' : ');
Readln(nhietdo[i]);
tong:=tong+nhietdo[i];
end;
trung_binh:=tong/N;
dem:=0;
For i:=1 To N Do
If nhietdo[i]>trung_binh then dem:=dem+1;
Writeln('Nhiet do trung binh ',N,' ngay : ',trung_binh:0:1);
Writeln('So ngay co nhiet do cao hon nhiet do trung binh : ',dem);
Readln;
End.
Program Tinh_Nhiet_Do_Ngay;
Uses Crt;
Const max=100;
Type mang = ARRAY[1..max] Of Real;
Var nhietdo : mang;
dem, i, N : integer;
trung_binh, tong : real;
Begin
Clrscr;
Write('Nhap so ngay : '); Readln(N);
tong:=0;
For i:=1 to N do
begin
write('Nhap nhiet do ngay ',i,' : ');
Readln(nhietdo[i]);
tong:=tong+nhietdo[i];
end;
trung_binh:=tong/N;
dem:=0;
For i:=1 To N Do
If nhietdo[i]>trung_binh then dem:=dem+1;
Writeln('Nhiet do trung binh ',N,' ngay : ',trung_binh:0:1);
Writeln('So ngay co nhiet do cao hon nhiet do trung binh : ',dem);
Readln;
End.
BÀI TẬP
Hãy viết chương trình nhập vào dãy số An gồm N số nguyên, tính tổng của của dãy số đó và xuất ra màn hình?
Ví dụ:
Input: N = 3 và dãy {2, 5, 8}
Output: tong = 15
Cách khai báo
Const Max = 100;
Type Dayso = array[1..Max] Of integer;
Var a : Dayso;
Giáo Viên: Nguyễn Quang Ánh
Trường THPT EaH’leo
Tiết 19
Kiểm tra bài cũ
1> Hãy cho biết cấu trúc khai báo mảng một chiều?
2> Hãy khai báo một mảng số nguyên để tính tổng S = a[1]+a[2]+…+ a[N]?
* Cách khai báo trực tiếp:
Var : Array[kiểu chỉ số] of ;
* Cách khai báo gián tiếp:
Type =Array[kiểu chỉ số] of ;
Var : ;
Var a:Array[1..N] of integer;
b> Một số ví dụ:
Bài toán tìm Min(giá trị nhỏ nhất trong dãy số nguyên gồm N số nguyên.
* Xác định bài toán:
- Input: Số nguyên N và dãy số a1 -> aN
- Input: Số nguyên nhỏ nhất.
* Ý tưởng:
Khởi tạo Min = a1.
Sau đó cho i chạy từ 2 đến N và so sánh giá trị của ai với Min nếu ai < Min thì Min nhận giá trị mới là ai.
Minh họa ý tưởng
N = 5, có năm quả bóng có kích thước khác nhau chúng cùng tìm Min với Kity.
a1
a1
a2
a3
a4
a5
Min
Quả này nhỏ nhất
Quả này nhỏ hơn
Quả này mới nhỏ nhất
Tìm ra quả nhỏ nhất rồi
Sơ đồ khối và liệt kê các bước
B1: Bắt đầu.
B2: Nhập N và dãy a1, a2, …, aN.
B3:Min <- a1, i <- 2.
B4: Nếu i > N thì đưa ra Min rồi KT.
B5:
B 5.1: Nếu ai < Min thì Min <- ai.
B 5.2: i <- i + 1 rồi quay lại b4.
Bắt Đầu
Nhập N
Dãy a1 -> aN
i > N
Đưa ra Min
Kết Thúc
ai < Min
Min <- a1; i <- 1;
Min <- ai;
i <- i + 1;
Đ
S
Đ
S
Chương trình minh họa
Program Tim_Min;
Uses Crt;
Const Max = 100;
Type mang = ARRAY[1..Max] Of Integer;
var a : mang;
i, N, min : integer;
Begin
Clrscr;
Write('Nhap vao N = '); Readln(N);
For i:=1 To N Do
Begin
Write('Nhap phan tu a[',i,'] = ');
Readln(a[i]);
End;
i := 2;
min := a[1];
while i <= N do
begin
if (a[i] < min) then
begin
min:=a[i]; i:=i+1;
end
else i:=i+1;
end;
Writeln(‘So nho nhat trong day so A gom ',N,' so nguyen la :',min);
readln;
End.
Program Tim_Min;
Uses Crt;
Const Max = 100;
Type mang = ARRAY[1..Max] Of Integer;
var a : mang;
i, N, min : integer;
Begin
Clrscr;
Write('Nhap vao N = '); Readln(N);
For i:=1 To N Do
Begin
Write('Nhap phan tu a[',i,'] = '); Readln(a[i]);
End;
i := 2;
min := a[1];
while i <= N do
begin
if (a[i] < min) then
begin
min:=a[i]; i:=i+1;
end
else i:=i+1;
end;
Writeln(‘So nho nhat trong day so A gom ',N,' so nguyen la :',min);
readln;
End.
Ví dụ 2
Thuật toán sắp xếp bằng tráo đỗi vị trí.
- Hãy cho biết Input và Output của bài toán?
Xác định bài toán:INPUT: Dãy A gồm N số nguyên a1, a2,…, aN.OUTPUT: Dãy A được sắp xếp thành dãy không giảm.
Ý tưởng:
Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đỗi vị trí chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đỗi chổ nào xãy ra nữa.
 Với N = 6 và dãy A gồm 6 số hạng như sau :
 Lượt thứ nhất:
 Lượt thứ hai:
 Lượt thứ ba:
 Lượt thứ tư:
Mô phổng thuật toán sắp xếp bằng tráo đỗi
8
9
1
9
7
9
8
1
8
7
5
1
3
1
Cách 1: Liệt kê các bước
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 đã 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.
Vẽ đồ khối
Giáo Viên: Nguyễn Quang Ánh
Trường THPT EaH’leo
Tiết 20
Kiểm tra bài cũ
1> Hãy cho ý tưởng của thuật toán sắp xếp bằng tráo đỗi vị trí?
2> Hãy khai báo theo cách khai báo gián tiếp một mảng số nguyên, dãy số A trong bài toán sắp xếp bằng tráo đỗi.
Ý tưởng:
- Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đỗi vị trí chúng cho nhau. Việc đó được lặp lại cho đến khi không có sự đỗi chổ nào xãy ra nữa.
Type mang =Array[1..100] of integer;
Var a : mang
Bài 11 : KIỂU MẢNG
b> Một số ví dụ:
Program Sap_Xep_Trao_Doi;
Uses Crt;
const Max = 250;
Type mang = Array[1..Max] of integer;
Var a:mang;
i, j, N, tam : integer;
Begin
Clrscr;
Write('Nhap vao so luong phan tu cua day N='); Readln(N);
for i:=1 to N do
Begin
Write('Nhap vao phan tu a[',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
tam:=a[i];
a[i]:=a[i+1];
a[i+1]:=tam;
End;
Writeln('Day sau khi da duoc sap xep bang trao doi');
for i:=1 to N do Write(a[i],' ');
Readln;
End.
Từ ý tưởng và sô đồ khối từ tiết trước của bài toán sắp xếp bằng tráo đỗi ta có thể viết chương trình minh họa như sau.
Bài 11 : KIỂU MẢNG
b> Một số ví dụ:
Ví dụ 3: Thuật toán tìm kiếm nhị phân.
Xác định bài toán: INPUT: Dãy A gồm N số nguyên a1, a2,…, aN được sắp tăng và số nguyên k. OUTPUT: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của A bằng k.
Ý tưởng:
Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm bằng cách so sánh k với số hạng ở giữa dãy (agiữa), khi đó chỉ xãy ra một trong ba trường hợp: - Nếu agiữa= k => tìm được chỉ số, kết thúc;- Nếu agiữa > k => do dãy A đã được sắp xếp tăng nên việc tìm kiếm thu hẹp chỉ xét từ a1  agiữa - 1; - Nếu agiữa < k => do dãy A đã được sắp xếp tăng nên việc tìm kiếm thu hẹp chỉ xét từ agiữa + 1  aN.
Mô phỏng thuật toán tìm kiếm nhị phân
10
9
8
7
6
5
4
3
2
1
i
33
31
30
22
21
9
6
5
4
2
A
? Với k = 21 và dãy A gồm 10 số hạng như sau:
Lượt thứ nhất: agiữa là a5 = 9; 9 < 21 ? vùng tìm kiếm thu hẹp trong phạm vi từ a6? a10;
33
31
30
22
21
Lượt thứ hai: agiữa là a8 = 30; 30 > 21? vùng tìm kiếm thu hẹp trong phạm vi từ a6? a7;
Lượt thứ ba: agiữa là a6 = 21; 21= 21  ? Vậy số cần tìm là i = 6.
22
21
6
6
21
Sơ đồ khối
Với ý tưởng như trên ta có thể vẽ sơ đồ khối như hình bên
Chương trình minh họa
Program Tim_Kiem_Nhi_Phan;
Uses Crt;
Const Max = 100;
Type DaySo=Array[1..Max] of integer;
Var a:Dayso;
i, N, k, dau, cuoi, giua:integer;
tim_thay:Boolean;
Begin
Clrscr;
Write('Nhap vao so phan tu cua day so N = '); Readln(N);
Writeln('Nhap cac phan tu cua day so sap tang:');
for i:=1 to N do
Begin
Write('Nhap phan tu thu ',i,'='); readln(a[i]);
end;
Write('Nhap so can tim k = ');Readln(k);
dau:=1; cuoi:=n; Tim_thay:=False;
While(dau<=cuoi)and not(Tim_thay) do
Begin
Giua:=(dau+cuoi) div 2;
if a[giua]=k then
Tim_thay:=True
Else if(a[giua]>k) then Cuoi:= Giua -1
else Dau:=Giua + 1;
end;
If Tim_thay then Writeln('Chi so tim duoc la :',Giua,' Co phan tu a[',giua,']=',k,'=k')
Else Writeln('Khong tim thay phan tu nao bang ',k);
Readln;
End.
Giáo Viên: Nguyễn Quang Ánh
Trường THPT EaH’leo
Tiết 21
2> Kiểu mảng hai chiều:
* Xét bài toán: Giải bài toán phương trình bậc nhất bằng phưong pháp Crame được tính như sau :
- Nếu D ≠ 0 thì hệ pt có nghiệm x=Dx/D, y=Dy/D
- Nếu D = 0:
+ Dx ≠ 0 hoặc Dy ≠ 0 thì hệ vô nghiệm.
+ Dx = Dy = 0 thì hệ pt có vô số nghiệm.
* Để giải quyết bài toán lưu trữ các hệ số trong D, Dx, Dy thì chúng ta có thể mô tả như sau : Định thức D là kiểu mảng một chiều gồm hai phần tử, mỗi phần tử lại là mảng một chiều có hai phần tử. Mỗi phần tử là một số thực. Ta cần mảng hai chiều 3 phần tử chiều ngang(dòng) và 2 phần tử chiều dọc(cột).
Mô phỏng bài toán
a[1][1] x + a[1][2] y = a[1][3]
a[2][1] x + a[2][2] y = a[2][3]
a x + b y = c
a’+ b’ y = c’
Hệ phương trình có dạng:
Mô phỏng
Mô phỏng
a[1][1] a[1][2]
a[2][1] a[2][2]
a[1][1]*a[2][2] - a[1][2]*a[2][1]
a[1][1] a[1][3]
a[2][1] a[2][3]
Mô phỏng
a[1][1]* a[2][3] - a[1][3]*a[2][1]
a[1][3] a[1][2]
a[2][3] a[2][2]
Mô phỏng
Cách khai báo mảng hai chiều
* Gián tiếp:
TYPE =ARRAY [Kiểu chỉ số dòng, Kiểu chỉ số cột] OF ;
Var : ;
* Trực tiếp:
Var : ARRAY [Kiểu chỉ số dòng, Kiểu chỉ số cột] OF ;
* Ví dụ:
Const dong = 100;
Const cot = 100;
Type Mang = ARRAY [1..dong, 1..cot] OF Integer;
Var a : Mang;
Chương trình minh họa
Program Giai_He_PT_B1;
Uses Crt;
Var a : ARRAY [1..2,1..3] Of real;
i, j : integer;
d, dx, dy, x, y : real;
Begin
Clrscr;
Writeln('Nhap vao cac he so');
For i := 1 To 2 Do
begin
For j := 1 To 3 Do
Begin
write('a[',i,'][',j,'] = '); Read(a[i][j]);
end;
readln;
end;
Writeln('He phuong trinh co dang:');
Writeln(a[1][1]:6:1,'x +',a[1][2]:6:1,'y=',a[1][3]:6:1);
Writeln(a[2][1]:6:1,'x +',a[2][2]:6:1,'y=',a[2][3]:6:1);
d:=a[1][1]*a[2][2]-a[2][1]*a[1][2]; {d=(ab'-a'b)}
dx:=a[1][3]*a[2][2]-a[2][3]*a[1][2]; {dx=cb'-c'b}
dy:=a[1][1]*a[2][3]-a[2][1]*a[1][3]; {dy=ac'-a'c}
if(d<>0) then
begin
x:=dx/d;
y:=dy/d;
writeln('He co hai nghiem x =',x:0:1,' y = ',y:0:1);
end
else if ((dx=0)and(dy=0)) then Writeln('He pt co vo so nghiem')
else Writeln('He phuong trinh vo nghiem');
Readln;
End.
Chương trình có thể được viết bằng Pascal như sau:
Bài tập:
* Hãy dùng mảng hai chiều để viết chương trình xuất ra màn hình bảng cửu chương gồm 9 cột và 9 hàng.
Khai báo:
Type Mang = Array[1..9,1..9] Of Integer;
Var a : Mang;
For i:= 1 to 9 do
Begin
For j:= 1 to 9 do
Begin
a[i][j] := i*j;
End;
End;
Cách tính:
For i:= 1 to 9 do
Begin
For j:= 1 to 9 do
Begin
Write(a[i][j]:4);
End;
Writeln;
End;
Sau khi tính xong các phần tử,
ta xuất ra bản chương