7.1.6 Một số bài toán cơ bản về mảng
7.1.6.1. Bài toán tìm kiếm trên mảng:
Tìm kiếm là một trong những bài toán cơ sở trong xử lý thông tin. Có nhiều bài toán tìm kiếm, tuy nhiên có thể quy về tìm kiếm trên mảng như sau: Cho mảng và phần tử x có kiểu dữ liệu cùng với kiểu dữ liệu của phần tử mảng. Hãy tìm xem có phần tử mảng nào có giá trị bằng x hay không.
Để giải quyết bài toán dạng này có thể sử dụng phương pháp tìm kiếm tuần tự hay tìm kiếm nhị phân.
Thủ tục tìm kiếm tuần tự là duyệt lần lượt các phần tử mảng, so sánh giá trị của nó với x. Việc tìm kiếm dừng khi tìm thấy hoặc đã hết mảng, tức là phát hiện ra là mảng không có giá trị khóa nào bằng x.
Có thể triển khai thủ tục tìm kiếm trên mảng bằng một vòng lặp while, dùng cờ báo là biến found kiểu Boolean.
Ví dụ 7.11: Viết chương trình nhập vào một dãy số thực có n phần tử và một số thực x. Kiểm tra xem x có xuất hiện trong dãy số đó không?
Program vidu_7_11;
Var A:array[1..100] of real;
i,n:integer;
x:real;
found:boolean;
Begin
write(' Nhap so phan tu cua day so n = ');readln(n);
writeln(' Nhap tung phan tu cua day so:');
For i:=1 to n do
begin
write('A[',i,']= ');readln(A[i]);
end;
writeln('In day so vua nhap:');
For i:=1 to n do
write(A[i]:7:2);
{Tim x trong day so A}
writeln;
write(' Nhap so can tim x = ');readln(x);
found:=false;
For i:=1 to n do
if A[i]=x then
begin
found:=true;
break; {dừng vòng lặp lại}
end;
if found then
writeln(x:5:2,' co xuat hien trong day so')
else writeln(x:5:2,' khong xuat hien trong day so');
readln;
end.
7.1.6.2. Bài toán sắp xếp dãy số tăng (giảm)
Sắp xếp cũng là một trong những bài toán cơ sở trong xử lý thông tin. Từ dãy dữ liệu ban đầu chưa có thứ tự, cần tiến hành sắp xếp để nhận được dãy kết quả có thứ tự tăng hoặc giảm dần theo một khóa cho trước nào đó. Bài toán quy về sắp xếp một mảng số nguyên.
Dưới đây sẽ trình bày phương pháp sắp xếp chọn trực tiếp hay còn được gọi là phương pháp nổi bọt. Không mất tính tổng quát ta xét bài toán sắp xếp tăng, cụ thể như sau:
Mô tả
- Chọn phần tử nhỏ nhất trong dãy nguồn, xếp nó vào vị trí đầu tiên trong dãy đích. Đây là phần tử thứ nhất và cũng là phần tử cuối cùng của dãy đích.
- Chọn phần tử nhỏ nhất trong dãy nguồn còn lại, đây là phần tử nhỏ thứ hai, xếp nó vào vị tri thứ hai và cũng là vị trí cuối của dãy đích vào lúc này.
- Lặp lại việc này cho đến khi hết dãy nguồn.
Để tiết kiệm chỗ, ta cũng xếp dãy đích và dãy nguồn liền nhau trong mảng. Do đó, ở bước thứ i, thao tác "xếp vào cuối dãy đích" chính là "đổi chỗ cho a[i]".
Minh hoạ:
Giả sử cần sắp xếp dãy số sau:
44 55 12 42 94 18 06 67
Sự thay đổi của dãy số qua từng bước sắp xếp như sau:
Xuất phát: 44 55 12 42 94 18 06 67
Bước 1: 06 / 55 12 42 94 18 44 67
Bước 2: 06 12 / 55 42 94 18 44 67
Bước 3: 06 12 18 / 42 94 55 44 67
Bước 4: 06 12 18 42 94 55 44 67
Bước 5: 06 12 18 42 44 / 55 94 67
Bước 6: 06 12 18 42 44 55 / 94 67
Bước 7: 06 12 18 42 44 55 67 / 94
Bước 8: 06 12 18 42 44 55 67 94
Thủ tục chi tiết
Var i,j,k: integer;
x: real;
Begin
for i:=1 to n-1 do
for j:=i+1 to n do
if a[j]
“đổi chỗ a[i] và a[j] cho nhau”
End;
Ví dụ 7.12: Viết chương trình nhập vào một dãy số thực có n phần tử (1<=n<=100). Sắp xếp dãy số theo chiều tăng dần. In lên màn hình dãy số trước và sau khi sắp xếp.
Program vidu_7_12;
Type kieudayso = array[1..100] of real;
Var A: kieudayso;
i, j, n: integer;
tg: real;
Begin
Write(‘ Nhap so phan tu cua day so n = ’);readln(n);
writeln(' Nhap tung phan tu cua day so:');
For i:=1 to n do
begin
write('A[',i,']= ');readln(A[i]);
end;
writeln('In day so vua nhap:');
For i:=1 to n do
write(A[i]:7:2);
{ Sắp xếp dãy số}
For i:=1 to n-1 do
For j:=i+1 to n do
If A[i]< A[j] then
Begin {hoán vị A[i] và A[j] cho nhau}
tg:=A[i];
A[i]:=A[j];
A[j]:=tg;
End;
Writeln(‘ Day so sau khi sap xep la: ‘);
For i:=1 to n do
write(A[i]:7:2);
readln;
End.
7.1.7. Một số ví dụ khác
Ví dụ 7.13: Viết đoạn chương trình chèn một số vào dãy đã sắp tăng mà không thay đổi thứ tự sắp xếp của dãy:
Write('Nhap so can chen k =');
Readln(k);
i:=1;
While (k>a[i]) and (i<=n) do i:=i+1;
Writeln('Vi tri chen i=',i:2);
If i>n then
Begin
a[i]:=k; n:=n+1;
End
Else
Begin
For j:=n downto i do
a[j+1]:=a[j];
a[i]:=k;
n:=n+1;
End;
Ví dụ 7.14: Viết chương trình tính tổng các phần tử của ma trận, nhập vào hàng k và tính trung bình cộng các phần tử trên hàng k. Hiển thị ma trận nhập dạng bảng và các kết quả tính:
Program Vidu14;
Uses Crt;
Var i,j,m,n,k :integer;
a: array[1..10,1..10] of real;
S,Sk,TBC :real;
BEGIN
Clrscr;
Write('Cho so hang cua ma tran m= ');Readln(m);
Write('Cho so cot cua ma tran n= ');Readln(n);
Writeln('Nhap tri cac phan tu cua ma tran:');
For i:=1 to m do
For j:=1 to n do
Begin
Write('a[',i,',',j,']= ');
Readln(a[i,j]);
End;
Writeln('Ma tran nhap:');
For i:=1 to m do
Begin
For j:=1 to n do
Write(a[i,j]:7:2);
Writeln;
End;
S:=0;
For i:=1 to m do
For j:=1 to n do
S:=S+a[i,j];
Writeln('Tong cac pt cua ma tran S= ',S:6:2);
Write('Nhap hang k :');Readln(k);
Sk:=0;
For j:=1 to n do
Sk:=Sk+a[k,j];
TBC:=Sk/n;
Writeln('TBC cac phan tu hang',k:2,' la: ',TBC:6:2);
Readln;
END.
7.2. Kiểu chuỗi (xâu) ký tự 7.2.1 Khái niệm
Xâu ký tự là một kiểu dữ liệu nhận giá trị là dãy các ký tự trong bảng mã ASCII, dãy ký tự này được đặt trong một cặp dấu nháy đơn (‘ ’)
Ví dụ 7.15:
St1 = ‘NGON NGU PASCAL’
St2 = ‘Tin hoc nam 2002’
St3 = ‘123456’
St4 = ‘Truong Dai hoc Dien Luc’
- Độ dài của một xâu là số ký tự của xâu đó. Xét ví dụ 7.20:
độ dài của st1 là 15,
đồ dài của st2 là 16,
độ dài của st3 là 6,
độ dài của st4 là 23,
- Xâu rỗng là xâu không chứa ký tự nào, nó có độ dài là 0, được ký hiệu là ‘’. Xâu rỗng khác với xâu chứa ký tự trống ‘ ’. Xâu chỉ chứa 1 ký tự trống có độ dài là 1.
-
Xâu ký tự
Số thứ tự
Trong bộ nhớ của máy, một biến xâu sẽ chiếm một số byte bằng độ dài tối đa của nó cộng thêm 1. Byte đầu tiên, gọi là byte 0, chứa một ký tự có mã bằng độ dài thực của xâu, mỗi byte còn lại chứa một ký tự. Cấu trúc của biến St1 nói trên có dạng:
|
N
|
G
|
O
|
N
|
|
N
|
G
|
U
|
|
P
|
A
|
S
|
C
|
A
|
L
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
Độ dài N (=15) của biến St1 và ký tự trong byte 0 (ký hiệu là St[0]) liên quan với nhau như sau:
N = Ord ( St[0] )
St[0]= Chr( N )
7.2.2. Khai báo xâu ký tự
7.2.2.1. Khai báo kiểu dữ liệu xâu:
TYPE Tên_kiểu_xâu = string; {mặc định là xâu dài tối đa 256 ký tự}
Hoặc
TYPE Tên_kiểu_xâu = string[độ dài tối đa của xâu];
VAR biến_xâu : Tên_kiểu_xâu;
Trong đó độ dài tối đa của xâu là một số nguyên dương nằm trong đoạn [0..256].
Ví dụ 7.16: Khai báo kiểu họ tên là kiểu xâu ký tự có độ dài tối đa là 40 ký tự.
TYPE kieu_hoten = string[40];
VAR ht: kieu_hoten; {khai báo biến ht có kiểu là kieu_hoten}
*Chú ý: Khi một biến xâu được dùng làm đối số của hàm hay thủ tục thì nó cần phải được khai báo theo cách này ( trừ các biến xâu có kiểu String ).
7.2.2.2. Khai báo biến kiểu dữ liệu xâu:
VAR tên_biến_xâu: string;
Hoặc
VAR tên_biên_xâu: string[độ dài tối đa của xâu];
Ví dụ 7.17:
VAR st1: string; {khai báo biến xâu st mặc định có độ dài tối đa là 256}
st2: string[50]; {khai báo biến xâu st có độ dài tối đa là 50}
* Chú ý: Nếu xâu st có độ dài tối đa là N mà ta lại gán cho nó xâu có độ dài lớn hơn N thì xâu st chỉ nhận N ký tự đầu tiên.
Ví dụ 7.18:
- Var st: string[15];
Sau lệnh gán st:=’Truong Dai hoc Dien Luc’; thì st sẽ nhận giá trị là: ‘Truong Dai hoc ’
- Var st1: string[50];
st1 := ‘C5CNTD’
* Chú ý: Cần phân biệt độ dài với độ dài tối đa của biến xâu: độ dài tối đa được xác định ngay khi khai báo là khả năng có thể chứa của biến xâu, còn độ dài của xâu là số ký tự đang thực có trong xâu. Như ví dụ 7.23, xâu st1 có độ dài tối đa là 50 nhưng độ dài thực tế của xâu là 6.
Chia sẻ với bạn bè của bạn: |