Bài 11. Kiểu mảng

TRẦN HỮU TRANG
TRƯỜNG TRUNG HỌC PHỔ THÔNG

TIN HỌC 11
Đặng Hữu Hoàng
BÀI 11
KIỂU MẢNG MỘT CHIỀU
Thời gian 3 tiết
BÀI TOÁN ĐẶT VẤN ĐỀ
Xác định Input, Output
Viết chương trình bài toán trên?
Input: t1, t2, t3, t4, t5, t6, t7.
Output: tb, dem.
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.
Số lượng ngày trong tuần có nhiệt độ cao hơn nhiệt độ trung bình của tuần.
Khi N lớn thì chương trình có những hạn chế nào?
Những hạn chế:
Phải khai báo quá nhiều biến.
Chương trình tính toán phải viết khá dài
Khắc phục những hạn chế:
Ghép chung 7 biến trên thành một dãy.
Đặt chung 1 tên và đặt cho một phần tử một chỉ số.
Sử dụng: KIỂU DỮ LIỆU MẢNG MỘT CHIỀU
1. KHÁI NIỆM KIỂU MẢNG MỘT CHIỀU
Nghiên cứu sách giáo khoa, em hiểu như thế nào là 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ó cùng kiểu dữ liệu.
Mảng được đặt tên và mỗi phần tử mang một chỉ số.
Những yếu tố nào để xác định mảng một chiều?
Kiểu dữ liệu của các phần tử.
Cách đánh chỉ số của các phần tử.
A
1 2 3 4 5 6 7
Trong đó
Khi tham chiếu đến phần tử thứ i - ta viết A[i].
A[6] = 22.
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
22
2. KHAI BÁO KIỂU MẢNG MỘT CHIỀU TRONG PASCAL
Cấu trúc khai báo gián tiếp kiểu mảng một chiều trong Pascal?
TYPE = array[..] of ;
Var : ;
Chỉ số đầu, chỉ số cuối: là các hằng hoặc biểu thức nguyên.
Chỉ số đầu ≤ chỉ số cuối
Giữa hai chỉ số là dấu ..
Ví dụ: TYPE nhietdo = array[1..366] of integer;
Var A:nhietdo;
Kiểu phần tử: kiểu của các phần tử mảng
2. KHAI BÁO KIỂU MẢNG MỘT CHIỀU TRONG PASCAL
Cấu trúc khai báo trực tiếp kiểu mảng một chiều trong Pascal?
Var : array[..] of ;
Chỉ số đầu, chỉ số cuối: là các hằng hoặc biểu thức nguyên.
Chỉ số đầu ≤ chỉ số cuối
Giữa hai chỉ số là dấu ..
Ví dụ: Var nhietdo : array[1..366] of integer;
Kiểu phần tử: kiểu của các phần tử mảng
Quan sát một số khai báo kiểu mảng một chiều như sau:
Arrayr=array[1..200] of real;
Arrayr=array[byte] of real;
Arrayb=array[-100..0] of boolean;
Khai báo nào đúng?

Các khai báo đúng:
Arrayr=array[1..200] of real;
Arrayb=array[-100..0] of boolean;
Cấu trúc khi tham chiếu tới phần tử của mảng một chiều?
[chỉ số]
A
1 2 3 4 5 6 7
Khi tham chiếu đến phần tử thứ i - ta viết A[i].
A[6] = 22.
Ví dụ:
22
3. THAM CHIẾU TỚI PHẦN TỬ CỦA MẢNG
Quan sát sách giáo khoa trang 54, chương trình giải toán tổng quát với N ngày trong Pascal
Khai báo mảng một chiều
Nhập mảng một chiều
Tính tổng
Đếm số phần tử thỏa mãn điều kiện
Khai báo mảng một chiều dạng gián tiếp
Khai báo mảng một chiều dạng trực tiếp
Nhập mảng một chiều tính tổng:
Đếm số phần tử thỏa mãn điều kiện
Quan sát chương trình chạy và các kết quả như sau
SỰ KHÁC NHAU TRONG PHẦN KHAI BÁO MẢNG
Phần khai báo mảng một chiều không có từ khóa Const
Phần khai báo mảng một chiều có từ khóa Const
BÀI TOÁN 1
Xác định Input, Output
Viết chương trình bài toán trên?
Input:
Số nguyên dương N (N≤250)
Dãy N số nguyên dương A1, A2,…, AN, mỗi số đều không vượt quá 500.
Tìm phần tử lớn nhất của dãy số nguyên.
Output:
Chỉ số và giá trị của phần tử lớn nhất trong dãy số đã cho.
Quan sát sách giáo khoa trang 56, chương trình giải toán tìm phần tử lớn nhất của dãy nguyên
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.
* Khai báo trực tiếp biến mảng một chiều
* Khai báo gián tiếp biến mảng một chiều
BÀI TOÁN 2
Xác định Input, Output
Viết chương trình bài toán trên?
Input:
Số nguyên dương N (N≤250)
Dãy N số nguyên dương A1, A2,…, AN, mỗi số đều không vượt quá 500.
Sắp xếp dãy số nguyên bằng thuật toán tráo đổi
Output:
Dãy số A đã được xếp thành dãy không giảm.
Quan sát sách giáo khoa trang 57_58, chương trình giải toán sắp xếp dãy số nguyên bằng thuật toán tráo đổi
* Khai báo gián tiếp biến mảng một chiều
NHẬN XÉT 1
Số phần tử ở các lượt duyệt (j) sẽ giảm từ n xuống hai phần tử.
For j := n downto 2 do
Hãy cho biết trong Pascal nhận xét 1 được thể hiện bằng lệnh gì ?

NHẬN XÉT 2
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).
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;
Hãy cho biết trong Pascal nhận xét 2 được thể hiện bằng lệnh gì ?

BÀI TOÁN 3
Xác định Input, Output
Viết chương trình bài toán trên?
Input:
Dãy A là dãy tăng gồm N (N≤250) số nguyên dương A1, A2,…, AN, và số nguyên k.
Tìm kiếm nhị phân
Output:
Chỉ số i và Ai= k hoặc thông báo”Khong tim thay” nếu không có số hạng nào của dãy A có giá trị bằng k.
Quan sát sách giáo khoa trang 58_59, chương trình giải toán tìm kiếm nhị phân
* Khai báo trực tiếp biến mảng một chiều
* Khai báo gián tiếp biến mảng một chiều
Hãy nêu các cách để giải chương trình tìm kiếm
Tìm kiếm tuần tự
Tìm kiếm nhị phân
CÁCH 1: TÌM KIẾM TUẦN TỰ
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?
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.
CÁCH 2: TÌM KIẾM NHỊ PHÂN
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.
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?
DẶN DÒ
1. Học tiếp §11_ “Kiểu mảng hai chiều” _Trang 59 _ Sách giáo khoa.
2. Thực hiện phần câu hỏi 1, 2, 3, 4 và bài tập 5, 6, 7, 8 _ trang 79 _Sách Giáo khoa
Thực hiện tháng 01 năm 2008
E_mail: [email protected]