DỮ
LIỆU KIỂU MẢNG (ARRAY)
I. KHAI BÁO MẢNG
Cú pháp:
TYPE <Kiểu
mảng> = ARRAY [chỉ số] OF <Kiểu dữ liệu>;
VAR <Biến
mảng>:<Kiểu mảng>;
hoặc khai báo trực tiếp:
VAR <Biến
mảng> : ARRAY [chỉ số] OF <Kiểu dữ liệu>;
Ví dụ:
TYPE Mangnguyen = Array[1..100] of Integer;
Matrix
= Array[1..10,1..10] of Integer;
MangKytu
= Array[Byte] of Char;
VAR A: Mangnguyen;
M:
Matrix;
C:
MangKytu;
hoặc:
VAR A: Array[1..100] of Integer;
C:
Array[Byte] of Char;
II. XUẤT NHẬP TRÊN DỮ
LIỆU KIỂU MẢNG
-
Để truy cập đến phần tử thứ k trong mảng một chiều A, ta sử dụng cú pháp: A[k].
-
Để truy cập đến phần tử (i,j) trong mảng hai chiều M, ta sử dụng cú pháp:
M[i,j].
-
Có thể sử dụng các thủ tục READ(LN)/WRITE(LN) đối với các phần tử của biến kiểu
mảng.
BÀI TẬP MẪU
Bài tập 5.1: Viết
chương trình tìm giá trị lớn nhất của một mảng chứa các số nguyên gồm N phần
tử.
Ý tưởng:
-
Cho số lớn nhất là số đầu tiên: Max:=a[1].
-
Duyệt qua các phần tử a[i], với i chạy từ 2 tới N: Nếu a[i]>Max thì thay Max:=a[i];
Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var A:Mang;
N,i,Max:Integer;
Begin
{Nhập
mảng}
Write(‘Nhap
N=’); Readln(N);
For
i:=1 To N Do
Begin
Write(‘A[‘,i,’]=’);
Readln(A[i]);
End;
{Tìm
phần tử lớn nhất}
Max:=A[1];
For
i:=2 To N Do
If
Max<A[i] Then Max:=A[i];
{In
kết quả ra màn hình}
Writeln(‘Phan
tu lon nhat cua mang: ’, Max);
Readln;
End.
Bài tập 5.2: Viết
chương trình tính tổng bình phương của các số âm trong một mảng gồm N phần tử.
Ý tưởng:
Duyệt
qua tất cả các phần tử A[i] trong mảng: Nếu A[i]<0 thì cộng dồn (A[i])2
vào biến S.
Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var A:Mang;
N,i,S:Integer;
Begin
{Nhập
mảng}
Write(‘Nhap
N=’); Readln(N);
For
i:=1 To N Do
Begin
Write(‘A[‘,i,’]=’);
Readln(A[i]);
End;
{Tính
tổng}
S:=0;
For
i:=1 To N Do
If
A[i]<0 Then S:=S+A[i]*A[i];
{In
kết quả ra màn hình}
Writeln(‘S=
’, S);
Readln;
End.
Bài tập 5.3: Viết chương trình nhập vào một
mảng gồm N số nguyên. Sắp xếp lại mảng theo thứ tự tăng dần và in kết quả ra
màn hình.
Ý tưởng:
Cho
biến i chạy từ 1 đến N-1, đồng thời cho biến j chạy từ i+1 đến N: Nếu
A[i]>A[j] thì đổi chổ A[i], A[j].
Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var A:Mang;
N,i,j,Tam:Integer;
Begin
{Nhập
mảng}
Write(‘Nhap
N=’); Readln(N);
For
i:=1 To N Do
Begin
Write(‘A[‘,i,’]=’);
Readln(A[i]);
End;
{Sắp
xếp}
For
i:=1 To N-1 Do
For
j:=i+1 To N Do
If
A[i]>A[j] Then
Begin
Tam:=A[i];
A[i]:=A[j]; A[j]:=Tam;
End;
{In
kết quả ra màn hình}
Writeln(‘Ket
qua sau khi sap xep:’);
For
i:=1 To N Do Write(A[i]:5);
Readln;
End.
Bài tập 5.4: Viết chương trình nhập vào một
mảng A gồm N số nguyên và nhập thêm vào một số nguyên X. Hãy kiểm tra xem phần
tử X có trong mảng A hay không?
Ý tưởng:
Dùng
thuật toán tìm kiếm tuần tự. So sánh x với từng phần tử của mảng A. Thuật toán
dừng lại khi x=A[i] hoặc i>N.
Nếu
x=A[i] thì vị trí cần tìm là i, ngược lại thì kết quả tìm là 0 (không tìm
thấy).
Uses Crt;
Type Mang = ARRAY[1..50] Of Integer;
Var A:Mang;
N,i,x:Integer;
Function
TimKiem(x, N: Integer; A:Mang):Integer;
Var
i:Integer;
Begin
I:=1;
While (I <= N) and
(X<>A[I]) do I:=I+1;
If I <= N Then
Timkiem:=I Else Timkiem:=0;
End;
Begin
{Nhập
mảng}
Write(‘Nhap
N=’); Readln(N);
For
i:=1 To N Do
Begin
Write(‘A[‘,i,’]=’);
Readln(A[i]);
End;
Write(‘Nhap
X=’); Readln(x);
{Kết
quả tìm kiếm}
If
TimKiem(X,N,A)<>0 Then
Writeln(‘Vi
tri cua X trong mang la:’, TimKiem(X,N,A))
Else
Writeln(‘X khong co trong mang.’);
Readln;
End.
Bài tập 5.5: Giả sử mảng A đã được sắp xếp
theo thứ tự tăng dần. Viết hàm để kiểm tra xem phần tử X có trong mảng A hay
không?
Ý tưởng:
So sánh x với phần tử ở giữa mảng
A[giua]. Nếu x=A[giua] thì dừng (vị trí cần tìm là chỉ số của phần tử giữa của
mảng). Ngược lại, nếu x>A[giua] thì
tìm ở đoạn sau của mảng [giua+1,cuoi], ngược lại thì tìm ở đoạn đầu của mảng
[dau,giua-1].
Sau
đây là hàm cài đặt cho thuật toán này:
Function
TimKiemNhiPhan(X, N: Integer; A: Mang):Integer;
Var dau,cuoi,giua:Integer;
Found:Boolean;
Begin
dau:=1; {điểm mút trái của khoảng tìm
kiếm}
cuoi:=N; {điểm mút phải của khoảng tìm
kiếm}
Found:=False; {chưa tìm thấy}
While (dau <=cuoi) and (Not Found)
Do
Begin
giua:=(dau + cuoi)
Div 2;
If X = A[giua] Then Found:=True {đã tìm thấy}
Else
If X >
A[giua] Then dau:=giua+1
Else
cuoi:=giua-1;
End;
If Found Then TimKiemNhiPhan:= giua
Else TimKiemNhiPhan:=0;
End;
Bài tập 5.6: Viết chương trình tìm ma trận
chuyển vị của ma trận A.
Ý tưởng:
Dùng
mảng 2 chiều để lưu trữ ma trận. Gọi B là ma trận chuyển vị của
ma trận A, ta có: Bij = Aji.
Uses Crt;
Type Mang = ARRAY[1..10,1..10] Of Integer;
Var A,B:Mang;
m,n,i,j:Integer;
Begin
{Nhập
ma trận}
Write(‘Nhap
số dòng m=’); Readln(m);
Write(‘Nhap
số cột n=’); Readln(n);
For
i:=1 To m Do
For
j:=1 To n Do
Begin
Write(‘A[‘,i,j,’]=’);
Readln(A[i,j]);
End;
{Tìm
ma trận chuyển vị}
For
i:=1 To m Do
For
j:=1 To n Do B[i,j]:=A[j,i];
{In
ma trận chuyển vị ra màn hình}
For
i:=1 To m Do
Begin
For
j:=1 To n Do Write(B[i,j]:5);
Writeln;
End;
Readln;
End.
Bài tập 5.7: Cho một mảng 2 chiều A cấp mxn
gồm các số nguyên và một số nguyên x. Viết chương trình thực hiện các công việc
sau:
a/
Đếm số lần xuất hiện của x trong A và vị trí của chúng.
b/
Tính tổng các phần tử lớn nhất của mỗi dòng.
Uses Crt;
Type Mang = ARRAY[1..10,1..10] Of Integer;
Var A:Mang;
m,n,i,j,x,dem,S,max:Integer;
Begin
{Nhập
ma trận}
Write(‘Nhap
số dòng m=’); Readln(m);
Write(‘Nhap
số cột n=’); Readln(n);
For
i:=1 To m Do
For
j:=1 To n Do
Begin
Write(‘A[‘,i,j,’]=’);
Readln(A[i,j]);
End;
{Nhập
x}
Write(‘Nhap
x=’); Readln(x);
{Đếm
số lãn xuất hiện của x và vị trí của x}
dem:=0;
Writeln(‘Vi
tri cua x trong mang A: ‘);
For
i:=1 To m Do
For
j:=1 To n Do
If
x=A[i,j] Then
Begin
Write(i,j,’
; ‘);
dem:=dem+1;
End;
Writeln(‘So
lan xuat hien cua x trong mang A la: ‘,dem);
{Tính
tổng các phần tử lớn nhất của mỗi dòng}
S:=0;
For
i:=1 To m Do {duyệt qua từng dòng}
Begin
{Tìm
phần tử lớn nhất của dòng thứ i}
Max:=A[i,1];
For
j:=2 To n Do {duyệt từng phần tử của
dòng thứ i}
If
max<A[i,j] Then max:=A[i,j];
{Cộng
max vào biến S}
S:=S+max;
End;
Writeln(‘Tong
cac phan tu lon nhat cua moi dong la: ‘,S);
Readln;
End.
Bài tập 5.8: Giải phương trình bằng phương
pháp chia nhị phân.
Ý tưởng:
Giả
sử cần tìm nghiệm của phương trình f(x)=0 trên đoạn [a,b] với y=f(x) đồng biến
và đơn trị trên đoạn [a,b]. Ta giải như sau:
Gọi
m là trung điểm của đoạn [a,b]. Nếu f(m)*f(a)<0 thì giới hạn đoạn tìm nghiệm
thành [a,m]. Tương tự đối với đoạn [m,b]. Quá trình này lặp lại cho đến khi
f(m)<e, lức này ta có 1 nghiệm gần đúng
là m.
Giả
sử f(x) là một đa thức: f(x) = a0 + a1x + a2x2
+ ... + anxn. Lúc này, ta có thể dùng mảng một
chiều để lưu trữ các hệ số ai của đa thức.
Uses Crt;
Type HESO=Array[0..20]
Of Real;
Var a:HESO;
n:Byte;
Min,Max,epsilon:Real;
Procedure
NhapDaThuc;
Var
i:Byte;
Begin
Write('Bac cua da thuc: n= '); Readln(n);
Writeln('Nhap cac he so cua da thuc:');
For i:=0 To n Do
Begin
Write('a[',i,']='); Readln(a[i]);
End;
Writeln('Nhap doan tim nghiem:[a,b]');
Write('a= '); Readln(Min);
Write('b= '); Readln(Max);
Write('Nhap sai so cua phuong trinh: ');
Readln(epsilon);
End;
{Tính giá
trị của đa thức}
Function
f(x:Real):Real;
Var S,tam:Real;
i:Byte;
Begin
S:=a[0]; tam:=1;
For i:=1 To n Do
Begin
tam:=tam*x;
S:=S+a[i]*tam;
End;
f:=S;
End;
Procedure
TimNghiem(Min,Max:real);
Var
m:Real;
Begin
If f(Min)*f(Max)>0 Then Writeln('Phuong
trinh vo nghiem.')
Else If abs(f(Min))<epsilon Then
Writeln('Nghiem la x=',min:0:2)
Else If abs(f(Max))<epsilon Then
Writeln('Nghiem la x=',max:0:2)
Else
Begin
m:=(Min+Max)/2;
If abs(f(m))<=epsilon Then Writeln('Nghiem
la x=',m:0:2)
Else If f(Min)*f(m)<0 Then
TimNghiem(Min,m)
Else TimNghiem(m,Max);
End;
End;
Begin
NhapDaThuc;
TimNghiem(Min,Max);
Readln;
End.
Bài tập
5.9: Viết chương trình nhập vào số tự nhiên N (N lẻ), sau đó điền các số từ
1 đến n2 vào trong một bảng vuông sao cho tổng các hàng ngang, hàng
dọc và 2 đường chéo đều bằng nhau (bảng này được gọi là Ma phương).
Ví
dụ: Với N=3 và N=5 ta có
Bắc
|
||||||||||
2
|
7
|
6
|
3
|
16
|
9
|
22
|
15
|
|||
9
|
5
|
1
|
20
|
8
|
21
|
 14 |
2
|
|||
4
|
3
|
8
|
Tây
|
7
|
25
|
13
|
1
|
19
|
Đông
|
|
24
|
12
|
5
|
18
|
6
|
||||||
11
|
4
|
17
|
10
|
23
|
||||||
Nam
|
||||||||||
Phuơng pháp:
Xuất
phát từ ô bên phải của ô nằm giữa. Đi theo hướng
đông bắc để điền các số 1, 2, ...
Khi
điền số, cần chú ý một số nguyên tắc sau:
-
Nếu vượt ra phía ngoài bên phải của bảng thì quay trở lại cột đầu tiên.
-
Nếu vượt ra phía ngoài bên trên của bảng thì quay trở lại dòng cuối cùng.
-
Nếu số đã điền k chia hết cho N thì số tiếp theo sẽ được viết trên cùng một
hàng với k nhưng cách 1 ô về phía bên phải.
Uses Crt;
Var
A:Array[1..20,1..20] Of Word;
n,i,j,k:Word;
Begin
Write('Nhap N= '); Readln(n);
Clrscr;
{Định vị ô xuất phát}
i:=n DIV 2 + 1;
j:=n DIV 2 + 2;
{Điền các số k từ 1 đến n*n}
For k:=1 To n*n Do
Begin
A[i,j]:=k;
If k MOD n=0 Then j:=j+2
Else Begin
{Đi theo
hướng đông bắc}
j:=j+1; i:=i-1;
End;
If j>n Then j:=j MOD n;
If i=0 Then i:=n;
End;
{In kết quả ra màn hình}
For i:=1 To n Do
Begin
For j:=1 To n Do write(a[i,j]:4);
Writeln;
End;
Readln;
End.
Bài tập 5.10: Viết chương trình nhập vào 2
mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau
trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập
vào đã có trong mảng thì không bổ sung vào mảng. In ra màn hình các phần tử là
giao của 2 tập hợp A, B.
Ý tưởng:
Duyệt
qua tất cả các phần tử aiÎA. Nếu
aiÎB thì viết ai ra màn
hình.
Uses Crt;
Type
Mang=ARRAY[1..50] Of Integer;
Var
A,B:Mang;
n,m:Byte;
Function
KiemTra(x:Integer; n:Byte; A:Mang):Boolean;
Var
i:Byte; Found:Boolean;
Begin
Found:=False;
i:=1;
While (i<=n) AND (not Found) Do
If x=A[i] Then Found:=True Else i:=i+1;
KiemTra:=Found;
End;
Procedure
NhapMang(Var n:Byte; Var A:Mang);
Var
ch:Char;
x:Integer;
Begin
n:=0;
Repeat
Write('x='); Readln(x);
If not KiemTra(x,n,A) Then
Begin
n:=n+1; A[n]:=x;
End;
Writeln('An ESC de ket thuc nhap!');
ch:=Readkey;
Until ch=#27;
End;
Procedure
GiaoAB(n:Byte; A:Mang;m:Byte; B:Mang);
Var
i:Byte;
Begin
For i:=1 To n Do
If KiemTra(A[i],m,B) Then Write(A[i]:4);
End;
Begin
Clrscr;
Writeln('Nhap mang A: ');
NhapMang(n,A);
Writeln('Nhap mang B: ');
NhapMang(m,B);
Writeln('Giao cua 2 mang A&B la: ');
GiaoAB(n,A,m,B);
Readln;
End.
Bài tập 5.11: Cho một mảng số nguyên gồm n
phần tử. Tìm dãy con gồm m phần tử (m£n) sao cho dãy con này có tổng lớn nhất. (Dãy con là
dãy các phần tử liên tiếp nhau trong mảng).
Uses Crt;
Type
Mang=ARRAY[1..50] Of Integer;
Var
A:Mang;
n,m,i,j,k:Byte;
S,Max:Integer;
Begin
Write('So phan tu cua mang: n= '); Readln(n);
For i:=1 To n Do
Begin
Write('a[',i,']='); Readln(a[i]);
End;
Write('Nhap so phan tu cua day con: m= ');
Readln(m);
k:=1; {Vị trí phần tử đầu tiên của dãy con}
{Giả sử m phần tử đầu tiên của mảng A là dãy
con có tổng lớn nhất}
Max:=0;
For i:=1 To m Do Max:=Max+A[i];
{Tìm các dãy con khác}
For i:=2 To n-m+1 Do
Begin
{Tính
tổng của dãy con thứ i}
S:=0;
For j:=i To i+m-1 Do S:=S+A[j];
If S>Max Then {Nếu dãy con tìm được có
tổng lớn hơn dãy con trước}
Begin
Max:=S; {Thay tổng mới}
k:=i; {Thay vị trí đầu tiên của dãy con mới}
End;
End;
Writeln('Day con co tong lon nhat la:');
For i:=k To k+m-1 Do Write(A[i]:5);
Readln;
End.
Bài tập 5.12: Viết chương trình in ra màn
hình tam giác Pascal. Ví dụ, với n=4 sẽ in ra hình sau:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Ý tưởng:
Tam giác Pascal được tạo ra theo qui luật sau:
+
Mỗi dòng đều bắt đầu và kết thúc bởi số 1.
+
Phần tử thứ j ở dòng k nhận được bằng cách cộng 2 phần tử thứ j-1 và j ở dòng
thứ k-1.
Uses Crt;
Var
Dong:Array[0..20] Of Byte;
n,i,j:Byte;
Begin
Write('n= '); Readln(n);
Clrscr;
Dong[0]:=1;
Writeln(Dong[0]:4);
{Khoi tao gia tri cua dong}
For i:=1 To n Do Dong[i]:=0;
{Voi moi dong i}
For i:=1 To n Do
Begin
For j:=i DownTo 1 Do
Begin
Dong[j]:=Dong[j-1]+Dong[j];
Write(Dong[j]:4);
End;
Writeln(Dong[i]:4);
End;
Readln;
End.
BÀI TẬP TỰ GIẢI
Bài tập 5.13: Viết chương trình nhập vào một
dãy số thực và số thực x. Thông báo lên màn hình số lượng các phần tử trong dãy
bằng x và vị trí của chúng.
Bài tập 5.14: Nhập vào một mảng các số
nguyên.
a/
Xếp lại mảng đó theo thứ tự giảm dần.
b/
Nhập vào một số nguyên từ bàn phím. Chèn số đó vào mảng sao cho mảng vẫn có thứ
tự giảm dần. (không được xếp lại mảng)
Gợi ý:
-
Tìm vị trí cần chèn: i.
-
Đẩy các phần tử từ vị trí i tới n sang phải 1 vị trí.
-
Gán: A[i]=x;
Bài tập 5.15: Cho 2 mảng số nguyên: Mảng A có
m phần tử, mảng B có n phần tử.
a/
Sắp xếp lại các mảng đó theo thứ tự giảm dần.
b/
Trộn 2 mảng đó lại thành mảng C sao cho mảng C vẫn có thứ tự giảm dần (Không
được xếp lại mảng C).
Gợi ý:
-
Dùng 2 chỉ số i,j để duyệt qua các phần tử của 2 mảng A, B và k là chỉ số cho
mảng C.
-
Trong khi (i<=m) và (j<=n) thì:
{Tức là khi đồng thời cả 2 dãy A, B đều chưa
duyệt hết}
+
Nếu A[i]>B[j] thì: C[k]:=A[i]; i:=i+1;
+
Ngược lại: C[k]:=B[j]; j:=j+1;
-
Nếu dãy nào hết trước thì đem phần còn lại của dãy kia bổ sung vào cuối dãy C.
Bài tập 5.16: Viết chương trình tính tổng và
tích 2 ma trận vuông A, B cấp n.
Gợi ý:
Công
thức tính tổng 2 ma trận: Cij =
Aij + Bij
Công
thức tính tích 2 ma trận: Cij =
Bài tập 5.17: Viết chương trình nhập vào 2
dãy số nguyên (a)n và (b)m, m£n. Kiểm tra xem dãy {b} có phải là dãy con của dãy
{a} không?
Bài tập 5.18: Viết chương trình nhập vào một
dãy số nguyên a1, a2, ..., an. Tìm trong dãy
{a} một dãy con tăng dần dài nhất (có số phần tử lớn nhất) và in ra màn hình
dãy con đó.
Bài tập 5.19: Cho mảng 2 chiều A cấp mxn.
Viết chương trình sắp xếp lại mảng A theo yêu cầu sau:
a/
Các phần tử trên mỗi dòng được sắp xếp theo thứ tự giảm dần.
b/
Các dòng được sắp xếp lại theo thứ tự tăng dần của tổng các phần tử trên mỗi
dòng.
Bài tập 5.20: Viết chương trình để kiểm tra
một dãy các số nguyên được nhập vào từ bàn phím đã được sắp theo thứ tự tăng
dần hay chưa theo 2 cách: Đệ qui và không đệ qui.
Gợi ý:
-
Nếu dãy có 1 phần tử thì dãy tăng dần.
-
Ngược lại:
+
Nếu A[n-1]>A[n] thì dãy không tăng dần.
+
Ngược lại: Gọi đệ qui với dãy có n-1 phần tử (bỏ bớt đi phần tử cuối cùng).
Bài tập 5.21: Viết chương trình nhập vào 2
mảng số nguyên A, B đại diện cho 2 tập hợp (không thể có 2 phần tử trùng nhau
trong một tập hợp). Trong quá trình nhập, phải kiểm tra: nếu phần tử vừa nhập
vào đã có trong mảng thì không bổ sung vào mảng.
a/
In ra màn hình hợp của 2 tập hợp A, B.
b/
In ra màn hình hiệu của 2 tập hợp A, B.
Gợi ý:
a/ - In ra màn hình tất cả các phần tử
của tập hợp A.
-
Duyệt qua tất cả các phần tử biÎB. Nếu
biÏA thì in bi ra màn
hình.
b/
Duyệt qua tất cả các phần tử aiÎA. Nếu
aiÏB thì in ai ra màn
hình.
Bài tập 5.22: Viết chương trình tính tổng của
2 đa thức h(x) = f(x) + g(x). Trong đó, mỗi đa thức có dạng: a0 + a1x
+ a2x2 + ... + anxn.
Gợi ý:
Dùng
các mảng A, B, C để lưu trữ các hệ số ai của các đa thức f(x), g(x)
và h(x).
Bài tập 5.23: Viết chương trình để tìm các
phương án đặt 8 quân hậu trên bàn cờ vua (ma trận 8x8) sao cho các quân hậu
không ăn được nhau.
Gợi ý:
Dùng
giải thuật quay lui.
Bài tập 5.24: Viết chương trình tính định
thức của ma trận vuông cấp n.
Gợi ý:
Dùng
cách tính định thức theo phương pháp GAUSE.
Không có nhận xét nào:
Đăng nhận xét