Lý thuyết:
1. Kiểu mảng một chiều
Mảng một 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ó một chỉ số.
Để mô tả màng một chiều cần xác định kiểu của các phần tử và cách đánh số các phần tử của nó [mỗi phần tử của nó có một chỉ số].
Để người lập trình có thể xây dựng và sử dụng kiều mảng một 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 một chiều;
- Số lượng phần tử của mảng;
- Kiểu dữ liệu của phần tử;
- Cách khai báo biến;
- Cách tham chiếu đến phần tử.
Có thể truy cập [hay thao tác] trên mỗi phần tử của mảng, trong việc làm đó mỗi phần tử của mảng được xác định bởi tên của mảng và chỉ số tương ứng của phần tử này.
Kiểu mảng là một kiểu dữ liệu có cấu trúc, rất cần thiết và hữu ích trong nhiều chương trình.
❖ Khai báo
Khai báo mảng một chiều có dạng tổng quát như sau:
Cách 1: Khai báo trực tiếp biến mảng một chiều:
var :array [kiểu chỉ số] of ;
Cách 2: Khai báo gián tiếp biến mảng qua kiểu mảng một chiều:
type = array [kiêu chỉ số] of ;
var :;
Trong đó:
Kiểu chỉ số thường là một đoạn số nguyên liên tục có dạng n1...n2 với n1, n2 là các hàng hoặc biểu thức nguyên xác định chỉ số đầu và chỉ số cuối [n1 Max then
begin
Max:= A[i]; csmax:= i;
end;
writeln['Gia tri cua phan tu Max: ', Max];
write In[’Chi so cua phan tu Max: ' , csmax]; readln
End
Kh chạy chương trình, giả sử ta nhập giá trị các phân tử:
Phần tử thứ nhất là 15;
Phần tử thứ hai là 5;
Phần tử thứ ba là 9;
Phần tử thứ tư là 6;
Phần tử thứ năm là 8;
thì trên màn hình thông báo kết quả: 'Gia tri cua phan tu Max: 15", 'Chi so cua phan tu lon nhat la 1*.
Khi đó màn hình có dạng như hình 26 dưới đây:
Từ chương trình này, chúng ta rút ra được một số điều cơ bản cần phải quan tâm, đó là:
- Dùng mảng có kiểu phần tử là nguyên để biểu diễn một dãy hữu hạn số nguyên và cách khai báo mảng này.
- Câu lệnh for-do thứ nhất trong chương trình thể hiện một nhiệm vụ trong bước 1 của thuật toán, dùng để nhập các phần tử của mảng, số phần tử thực sự của mảng do người chạy chương trình nhập vào bởi câu lệnh ngay trước câu lệnh for-do này.
- Câu lệnh for-do thứ hai trong chương trình thể hiện vòng lặp [gồm bước 3 và 4 trong thuật toán], dùng để duyệt tuần tự từng phần tử trong mảng lọc lấy.
Đối với ví dụ 2, về bài toán: “Sắp xếp dãy số nguyên bằng thuật toán đổi chỗ". Chương trình của bài toán như sau:
program sapxep;
uses crt;
const Nmax = 250;
type
ArrInt = array[1..Nmax] of integer;
var
N,I,j,t: integer;
A: Arrlnt;
Begin
clrscr
write [ ' Nhap so luong phan tu cua day so, N-'];
readln[N]; for i:= 1 to N do begin
write[' Phan tu thu',i,' = '];
readln[A[i]];
end,
for j:= N downto 1 do begin
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;
end;
writeln['Day so duoc sap xep la:’]; for i:= 1 to N do write[A[i]:4];
readln
End.
Khi chạy chương trình, giả sử ta nhập số phần tử của dãy là 5 với giá trị các phần tử như sau:
Phần tử thứ nhất= 5;
Phần tử thứ hai= 7;
Phần tử thứ ba= 9;
Phần tử thứ tư= 3;
Phần tử thứ năm= 6;
thì trên màn hình sẽ có thông báo:
Day so duoc sap xep la:
3 5 6 7 9
Màn hình kết quả có dạng như hình 27 dưới đây:
Từ chương trình này, chúng ta rút ra được một số điều cơ bản cần phải quan tâm, đó là:
- Khái niệm lượt: sau lượt [lần] duyệt thứ nhất giá trị lớn nhất xếp đúng vị trí là ờ cuối dãy. Tương tự, sau lượt thứ hai, giá trị lớn thứ hai được xếp ở vị trí sát cuối,.. Sau mỗi lượt có ít nhất một số hạng đã xếp đúng vị trí. Trong thuật toán phải thực hiện bao nhiêu lượt như vậy, mỗi lượt thực hiện trên đoạn nào [từ đâu đến đâu] của dãy số? Giá trị của j chính là chỉ số phần tử cuối trong đoạn được duyệt của lượt. Đây chính là câu lệnh for j : N downto 2 do với biến đếm j chạy từ N về 2.
- Mỗi lượt bao gồm việc thực hiện một số thao tác: so sánh một phần tử với phần tử đứng ngay sau nó để xử lí, bắt đầu từ phần tử đầu tiên trong dãy đến phần tử thứ j. Thao tác so sánh để quyết định xử lí [tráo đổi hai phần tử] được lặp một số lần. Đây chính là câu lệnh lặp mà chương trình dùng để thể hiện mỗi lượt.: 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;
Giá trị biến đếm chính là chỉ số phần tử được lấy so sánh với phần tử kề sau nó
trong dãy số. Trong cấu trúc lặp này, chỉ lấy đến j-1 chứ không phải là đến j.
Đối với ví dụ 3 về bài toán: "Tìm kiếm nhị phân"
Thuật toán
Bước 1: Nhập N, các số hạng a1, a2... aN và khóa k
Bước 2: Dau