Bài 11. Kiểu mảng

Chuong IV: KI?U D? LI?U Cể C?U TR�C
Bài 11: Ki?u M?ng
Giáo án điện tử tin học lớp 11
GV Võ Minh Hoàng
Ngày soạn: 03/01/2009
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ố lượng ngày có nhiệt độ TB cao hơn nhiệt d? trung bình trong tuần?
* Dữ liệu nhập vào (INPUT): t1,t2,t3,t4,t5,t6,t7.
* Dữ cần tính và in ra (OUTPUT): tb, dem.
Hãy xác định Input, Output và viết chương trình giải bài toán trên ?
Bài toán đặt vấn đề:
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.
Quan sát chương trình, hãy cho biết nếu muốn tính nhiệt độ trung bình của N ngày trong năm (VD: N=365) thì sẽ gặp khó khăn gì ?
Khai báo quá lớn (t1,t2,t3,...,t365) và chương trình quá dài (với 365 lệnh IF) !!!!!

? Để khắc phục khó khăn đó ta sử dụng kiểu dữ liệu mảng một chiều.
Mảng một chiều là một dãy hữu hạn các phần tử cùng kiểu
A
1 2 3 4 5 6 7
Trong đó :
Khi tham chiếu đến phần tử thứ i ta viết A[i].
Ví dụ: A[5] = 19.
? Tên mảng : A.
? Số phần tử của mảng: 7.
Ví dụ:
? Kiểu dữ liệu của các phần tử: Kiểu nguyên.
19
1. Khái niệm
2. Khai báo mảng một chiều trong PASCAL
* Cách 1: Khai báo gián tiếp
TYPE = array[..] of ;
Var : ;
Ví dụ: TYPE nhietdo = array[1..365] of integer;
Var A: nhietdo;
Trong đó : ? Chỉ số đầu, chỉ số cuối thường là các hằng hoặc biểu thức nguyên;
? Chỉ số đầu ? chỉ số cuối;
? Giữa 2 chỉ số là dấu ..
* Cách 2: Khai báo trực tiếp
Var : array[..] of ;
Var A,B : array[1..100] of real;
Ví dụ: Var nhietdo : array[1..365] of integer;
3. Các thao tác xử lí trong mảng một chiều
A
n
1. NhËp sè phÇn tö cña m¶ng (n).
Write(‘ Nhap vao so ngay:’);
Readln(n);
2. Nhập vào giá trị của các phần tử trong mảng (A[i]).
For i:=1 to n do
Begin
write(‘nhiet do ngay thu’ ,i, ’ : ’);
readln(A[i]);
end;
Các bước
Thể hiện bằng pascal
a. Nhập mảng một chiều
víi n = 7
19
17
19
21
18
20
17
Ví dụ: Nhập nhiệt độ n ngày.
b. In mảng một chiều
Writeln(‘ Mang vua nhap : ’);
For i:=1 to n do Write(A[i]:5);
Mang vua nhap:


- Th«ng b¸o
- In gi¸ trÞ cña c¸c phÇn tö
17 20 18 21 19 17 19
Kết quả in ra màn hình:
Ví dụ: In mảng vừa nhập.
* Đếm các phần tử trong mảng thoả mãn điều kiện cho trước
dem :=0;
For i :=1 to n do
IF A[i]>TB then dem:=dem+1;
c. Các thao tác xử lí khác
Ví dụ: Đếm số ngày có nhiệt độ cao hơn nhiệt độ TB của tuần.
TB = 18.7
Dem=0
7
6
5
4
3
2
1
i
0
1
1
2
3
3
4
20
21
19
19
+1
+1
+1
+1
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:
Thông thường, các thao tác xử lí trong mảng một chiều đều dùng câu lệnh FOR...DO.
* Tính tổng các phần tử trong mảng thoả mãn điều kiện cho trước
Ví dụ: Tính tổng các phần tử trong mảng chia hết cho 3.
S :=0;
For i :=1 to n do
IF A[i] mod 3 = 0 then S:=S+A[i];
S = 45
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ùng giá trị thì đưa ra chỉ số của phần tử lớn nhất đầu tiên.
Hãy xác định Input, Output và nêu thuật toán tìm Max?
* INPUT: Nhập số nguyên dương n và dãy n số nguyên dương a1,a2,...,an.
* OUTPUT: Chỉ số và giá trị của phần tử lớn nhất trong dãy.
Quả này lớn nhất
Quả này mới lớn nhất
ồ! Quả này lớn hơn
Tìm ra quả lớn nhất rồi!
thuật toán tìm max
1. Nhập n và dãy a1,...,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 ? 1;
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.
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 := 1 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 :
7
Phan tu thu 1 =
15
20
16
25
18
12
19
Gia tri cua phan tu Max : 25
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 =
Phan tu thu 6 =
Phan tu thu 7 =
Bài 2. Nhập vào một dãy số nguyên, sắp xếp dãy theo trình tự không giảm.
* INPUT: Nhập số nguyên dương n và dãy n số nguyên dương a1,a2,...,an.
* OUTPUT: Dãy số được sắp xếp theo trình tự không giảm.
Các em hãy cho biết để giải bài toán trên, ở lớp 10 chúng ta dùng thuật toán gì?
Là Thuật toán tráo đổi kiểu nổi bọt từ trên xuố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.
Số phần tử ở các lượt duyệt (j) sẽ giảm từ n xuống hai phần tử.
Tại mỗi lượt duyệt:
- Cho i chạy từ 1 đến số phần tử -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 (Tg).
Các em hãy cho biết trong Pascal nhận xét 1 được thể hiện bằng lệnh gì ?
1
For j := n downto 2 do
2
For i := 1 to j-1 do
IF A[i]>A[i+1] then
Tg := A[i];
A[i] := A[i+1];
A[i+1]:=Tg;
Begin
end;
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 , tg : 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
Tg := A[i];
A[i]:=A[i+1];
A[i+1]:=Tg;
end;
Writeln(‘ Day so duoc sap xep ’);
For i:=1 to n do Write(A[i]:5);
Readln;
END.
Bài 3. Nhập vào một dãy A tăng gồm N (N ? 250) số nguyên dương khác nhau và một số k. Cho biết vị trí của số hạng có giá trị bằng k trong dãy (nếu có) ?
* INPUT: Nhập số nguyên dương n, dãy n số nguyên dương a1,a2,...,an và số nguyên k
* OUTPUT: Chỉ số i mà ai = k hoặc thông báo "Không tìm thấy" nếu không có số hạng nào của dãy A có giá trị bằng k.
Các em hãy nêu các cách để giải bài toán trên ?
Lần lượt từ số hạng thứ nhất, so sánh giá trị số hạng đang xét với k cho đến khi gặp được số hạng bằng k, hoặc dãy đã được xét hết và không có số hạng nào có giá trị bằng k.
Từ ý tưởng trên hãy viết đoạn chương trình bằng PASCAL để tìm số hạng của dãy có giá trị bằng k?
Cách 1: Tìm kiếm tuần tự
Cách 2: 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 chỉ số cần tìm là i = 6.
22
21
6
6
21
Dau:=1; Cuoi:=n; tim_thay:=false;
while ( Dau<= Cuoi) or 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)
Else Writeln(`Khong tim thay`);
Vì dãy A là dãy tăng, ta thực hiện thu hẹp nhanh phạm vi tìm kiếm bằng cách so sánh k với A[giua] và xét các trường hợp:
- A[giua]=k ? tìm thấy chỉ số giữa và kết thúc;
- A[giua]>k ? Thu hẹp về phía bên trái (Cuối = Giữa -1);
- A[giua] Quá trình trên được lặp lại chừng nào còn chưa tìm thấy hoặc Dau <= Cuoi.
Hãy nhớ!
? Mảng một chiều là một dãy hữu hạn các phần tử cùng kiểu.
? Khai báo: tên mảng, chỉ số đầu, chỉ số cuối, kiểu phần tử.
Tham chiếu phần tử mảng:
Tên biến mảng[chỉ số phần tử]
? Nhiều thao tác xử lí mảng dùng cấu trúc lặp FOR ..TO.. DO.
15 20 19 25 18 12 16
Var A:ARRAY[1..100] OF integer;
A[5] = 18