Bài 11. Kiểu mảng

Chương IV: KIỂU DỮ LIỆU CÓ CẤU TRÚC
Bài 14: KIỂU MẢNG
Ví dụ: Xét bài toán nhập và 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ố lượng ngày trong tuần có nhiệt độ cao hơn nhiệt độ trung bình của tuần.
Hãy xác định Input, Output c?a bài toán trên ?
Input: t1, t2, …, t7.
Output: Nhiệt độ trung bình (tb) và số lượng ngày có nhiệt độ cao hơn nhiệt độ trung bình (dem).
Program vd1;
Uses crt;
Var
t1,t2,t3,t4,t5,t6,t7,tb : real;
dem : integer;
BEGIN
Clrscr;
write(` Nhap vao nhiet do 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 = `,tb : 6 : 2);
Writeln(` so ngay co nhiet do cao hon nhiet do tb `, dem);
Readln;
END.

Nếu bài toán trên áp dụng cho 1 tháng hoặc 1 năm thì có gặp khó khăn gì không?
Sử dụng rất nhiều biến, chương trình phải viết rất dài và rất phức tạp.
Để khắc phục khó khăn đó, ta sử dụng kiểu dữ liệu mảng 1 chiều
Kiểu mảng 1 chiều
Khái niệm
Mảng 1 chiều là dãy hữu hạn các phần tử cùng kiểu. mảng được đặt tên và mỗi phần tử của nó có 1 chỉ số.
* Để mô tả mảng 1 chiều cần xác định:
+ Kiểu của các phẩn tử.
+ Cách đánh số các phần tử.
Để người lập trình xây dựng và sử dựng kiểu mảng 1 chiều, các ngôn ngữ lập trình có quy tắc, cách thức cho phép xác định:
Tên kiểu mảng 1 chiều;
Số lượng phần tử;
Kiểu dữ liệu của phần tử;
Cách khai báo biến mảng;
Cách tham chiếu tới 1 phần tử;
Ví dụ: cho mảng 1 chiều sau
1 2 3 4 5 6 7
Tên mảng: A
Số phần tử của mảng: 7
Kiểu của các phần tử: kiểu nguyên
Khi tham chiếu tới phần tử thứ i ta viết: A[i]
Ví dụ: A[6] = 17
A
- Xđ tên mảng.
- Số phần tử của mảng.
- Kiểu của các phần tử của mảng.
Khai báo

Cách 1: Khai báo trực tiếp biến mảng 1 chiều

var : array [chỉ số đầu..chỉ số cuối] of ;
Ví dụ: type nhietdo = array[1..365] of integer;
var A: nhietdo;
Trong đó:
Chỉ số đầu, chỉ số cuối thường là hằng hoặc biểu thức nguyên.
Chỉ số đầu ≤ chỉ số cuối.
Giữa 2 chỉ số là: ..
Kiểu phần tử là kiểu của các phần tử mảng.
Cách 2: Khai báo gián tiếp biến mảng qua kiểu mảng1 chiều

type = array [chỉ số đầu..chỉ số cuối] of ;
var : ;
Ví dụ: Var nhietdo : array[1..365] of integer;
Ví dụ: Các khai báo biến mảng 1 chiều sau đây là hợp lệ
type
ArrayReal = array[-100..200] of real;
ArrayBoolean = array[-n+1..n+1] of boolean;
ArrayInt = array[-100..0] of integer;
*Tham chiếu tới phần tử của mảng 1 chiều
Được xác định bởi tên mảng cùng với chỉ số được viết trong cặp ngoặc [ và ].
1 2 20 99 100
Nhietdo[20]
Chỉ số phần tử
Mảng Nhietdo
b. Nhập mảng 1 chiều:
Ví dụ: Nhập mảng nhiệt độ n ngày.
Các bước
Thể hiện bằng pascal
1. NhËp sè phÇn tö cña m¶ng (n).
2. Nhập vào giá trị của các phần tử trong mảng (A[i]).
Write(‘ Nhap vao so ngay:’);
Readln(n);
For i:=1 to n do
Begin
write(‘nhiet do ngay thu’ ,i, ’ : ’);
readln(A[i]);
end;
A
1 2 3 4 5 6 7
c. In mảng 1 chiều:
Ví dụ: in mảng vừa nhập.
Thông báo
In giá trị các phần tử
Writeln(‘ Mang vua nhap : ’);
For i:=1 to n do Write(A[i]:5);
Kết quả in ra màn hình
Mang vua nhap:
19 32 20 16 25 17 21
Thao tác xử lý khác:
Đếm số ngày có nhiệt độ cao hơn nhiệt độ của tuần
dem :=0;
For i :=1 to n do
IF A[i]>TB then dem:=dem+1;
Viết khai báo biến mảng của bài toán?
Số lượng phần tử: 366
Tên kiểu mảng: Kmang1
Tên biến mảng: Nhietdo
type Kmang1 = array [1..366] of integer;
var Nhietdo: Kmang1;
Program vd1;
Uses crt;
Var
A: Array[1..366] of integer;
i,n,dem: integer;
S,TB : real ;
BEGIN
Clrscr;
write(` Nhap vao so ngay : `) ;
readln(n) ;
S := 0 ;
For i := 1 to n do
Begin
write(` Nhap nhiet do ngay thu `,i,` : `) ;
readln(A[i]) ;
S:=S+A[i] ;
End;
TB := S/n ; dem := 0 ;
For i := 1 to n do
If A[i]>TB Then dem := dem+1;
Writeln(` Nhiet do trung binh ` ,n,` ngay = `,TB : 6 : 2) ;
Writeln(` So ngay co nhiet do cao hon nhiet do TB la: `, dem) ;
Readln ;
END.
Khai b¸o m¶ng 1 chiÒu
Nhập mảng 1 chiều
Tính tổng
Đếm số phần tử thoả mãn điều kiện










Nhap vao so ngay :
7
Nhap nhiet do ngay thu 1 :
17
Nhap nhiet do ngay thu 2 :
20
Nhap nhiet do ngay thu 3 :
18
Nhap nhiet do ngay thu 4 :
21
Nhap nhiet do ngay thu 5 :
19
Nhap nhiet do ngay thu 6 :
17
Nhap nhiet do ngay thu 7 :
19
Nhiet do trung binh 7 ngay = 18.70
So ngay co nhiet do cao hon nhiet do TB la: 4
Chương trình chạy và cho kết quả như sau:
Chương IV: KIỂU DỮ LIỆU CÓ CẤU TRÚC
Bài 14: KIỂU MẢNG (tiếp theo)
d. Một số ví dụ
Ví dụ 1:
Tìm phần tử lớn nhất của dãy số nguyên gồm N phần tử ( N  250, A[i]  500). Nếu dãy có nhiều phần tử lớn nhất thì đưa ra chỉ số lớn nhất của phần tử đầu tiên.
Xác định input và output của bài toán
Input: Nhập vào số nguyên dương N (N  250) và dãy N số nguyên dương A1, A2, …, An.
Output: Chỉ số và và giá trị của phần tử lớn nhất trong dãy số đã cho.
Nêu ý tưởng của thuật toán tìm Max?
Tìm Max dãy số: 3 2 7 9 6
Gán Max = A[1].
Cho biến i chạy từ 2 đến N. Nếu A[i] > Max thì Max  A[i] sau đó lưu lại vị trí i.
S? lớn nhất
S? này mới lớn nhất
ồ! S? này lớn hơn
Tìm ra s? l?n nhất rồi!
2
7
9
6
3
Thuật toán tìm max của dãy số nguyên
Thuật toán
Bước 1: Nhập N và dãy A1, A2, …, An;
Bước 2: Max  A1, i  2;
Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc;
Bước 4:
Nếu Ai > Max thì Max  Ai;
i  i+1 rồi quay lại bước 3;
1. Nhập n và dãy a1,a2,...,an;
write(‘ Nhap vao so luong phan tu:’);
readln(n);
for i:=1 to n do
begin
write(‘ Phan tu thu ’ ,i, ’ = ’);
readln(a[i]);
end;
2. Max ? a1 ; i ? 2;
Max:=a[1]; csmax:=1;
for i :=2 to n do
if a[i]>max then
begin
max:=a[i];
csmax:=i;
end;

3. Nếu i>N đưa ra MAX và chỉ số i => Kết thúc;
4. Nếu a[i]>max thì max?a[i],
i ? i+1 => quay lại bước 3.
thuật toán
thể hiện bằng pascal

Viết khai báo biến mảng của bài toán?
type dayso = array [1..250] of integer;
var A: dayso;
Số lượng phần tử: 250
Tên kiểu mảng: dayso
Tên biến mảng: A
Program Tim_Max;
Uses crt;
Type dayso = Array[1..250] of integer;
Var
A : dayso ;
i,n,max,csmax : integer;
BEGIN
Clrscr;
write(` Nhap vao so phan tu cua day so : `) ;
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;
Writeln(` Gia tri cua phan tu Max : `,Max) ;
Writeln(` Chi so cua phan tu Max : `, csmax) ;
Readln ;
END.










Nhap vao so phan tu cua day so :
5
Phan tu thu 1 =
3
2
7
9
6
Gia tri cua phan tu Max : 9
Chi so cua phan tu Max : 4
Chương trình chạy và cho kết quả như sau:
Phan tu thu 2 =
Phan tu thu 3 =
Phan tu thu 4 =
Phan tu thu 5 =
Ví dụ 2:
Sắp xếp dãy số nguyên dương gồm N phần tử (N< 250, A[i] < 500) thành dãy số không giảm.
Xác định input và output của bài toán
Input: Nhập vào số ngyuên dương N, và dãy A1, A2, …, An.
Output: Dãy số A được sắp xếp thành dãy số không giảm.
Để giải bài toán trên ở lớp 10 ta đã sử dụng thuật toán gì?
Sử dụng thuật toán tráo đổi kiểu nổi bọt, số lớn chìm xuống và số bé nổi lên trên.
Nêu ý tưởng của thuật toán ?
+ Với mỗi cập số hạng đứng liền trong dãy, nếu số trước lớn hơn số sau ta đổi chổ chúng cho nhau.
+ Việc đổi chổ đó được lập lại cho đến khi không còn sự đổi chổ nào xảy ra nữa, để đưa số lớn nhất về vị trí cuối cùng.
3
2
9
7
6
Cho dãy số sau: 3 2 9 7 6
Giả sử:
? Mỗi phần tử được xem như một bọt nước;
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 là 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 thứ nhất, bọt nước có trọng lượng lớn nhất sẽ chìm xuống đáy.
? Trọng lượng của bọt nước thứ i là giá trị của A[i].
Lượt 2:
i chạy từ đầu dãy đến vị trí [cuối dãy - 2] (bỏ qua phần tử cuối).
Sau lượt thứ hai bọt nước có trọng lượng lớn thứ hai nằm sát trên bọt nước lớn nhất.
Quá trình duyệt, tráo đổi được lặp đi lặp lại cho đến khi chỉ còn duyệt hai phần tử và thu được dãy không giảm.
1
Trong pascal nhận xét 1 được thực hiện bằng lệnh gì?
For j:= N dowto 2 do
Tại mỗi lượt duyệt:
Cho i chạy từ 1 đến j – 1,
Nếu A[i] > A[i+1] thì
tráo đổi vị trí A[i] và A[i+1] thông qua biến trung gian là t
For i:= 1 to j – 1
if A[i] > A[i+1] then
begin
t:= A[i];
A[i]:= A[i+1];
A[i+1]:= t;
end ;
Số phần tử ở lượt duyệt j sẽ giảm từ phần tử N đến phần tử thứ 2
2
Nhận Xét
Viết khai báo biến mảng của bài toán?
Số lượng phần tử: 250
Tên kiểu mảng: sapxep
Tên biến mảng: A
type sapxep = array [1..250] of integer;
var A: sapxep;
Khai báo mảng 1 chiều
Nhập mảng 1 chiều
Xử lí mảng bằng thuật toán nổi bọt
In kết quả
PROGRAM Sapxep;
Uses crt;
Type dayso = Array[1..250] of integer;
Var
i, j , n , t: integer;
A : dayso;
BEGIN
Clrscr;
write(‘ Nhap vao so phan tu cua day so : ’);
readln(n);
for i := 1 to n do
begin
write(‘ 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 ’);
for i:=1 to n do write(A[i]:5);
readln;
END.
Chương trình pascal