Bài đọc thêm 2: Ngôn ngữ Pascal

Lê Minh Hoàng
Nội dung bài học
Kiểu liệt kê và kiểu đoạn con
Kiểu dữ liệu có cấu trúc: Mảng
Mảng 1 chiều
Mảng 2 chiều
Mảng nhiều chiều
Mảng động
Một số bài toán
Khai báo kiểu
Cú pháp khai báo kiểu do người lập trình định nghĩa
type
TypeIndentifier = TypeDeclaration;
TypeIdentifier là tên kiểu do người lập trình tự đặt
TypeDeclaration là mô tả kiểu dữ liệu theo cú pháp của từng kiểu.
Về thứ tự, FPC không ràng buộc về thứ tự khai báo hằng, biến, kiểu.
Tuy nhiên nếu không gặp khó khăn gì, khai báo kiểu (type) nên đặt sau khai báo hằng (const) và trước khai báo biến (var)
Ví dụ: Khai báo kiểu đoạn con và kiểu liệt kê
type
TMyIntType = 1..200;
TDayOfWeek = (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
Kiểu liệt kê (Enumerated Type)
type
TypeIdentifier = (Id1, Id2, ..., IdN);
Trong đó TypeIdentifier là tên kiểu, Id1..N là các tên liệt kê các hằng trong kiểu đó.
Công dụng: Dùng tên gợi nhớ thay vì mã hóa các hằng đó thành hằng số
Ví dụ
type
TDOW = (Mon, Tue, Wed, Thu, Fri, Sat, Sun);
var
DOW: TDOW;
Khi đó ta có thể viết những lệnh sau trong phần thân chương trình
DOW := Tue;
WriteLn(Ord(DOW)); //In ra số 1
DOW := TDOW(2); //DOW := Wed
Hàm Ord(hằng kiểu liệt kê) cho ta số thứ tự của hằng đó trong kiểu (hằng đầu tiên có số thứ tự 0)
Ép kiểu: Tên kiểu liệt kê(Số thứ tự): Cho ta biết hằng mang số thứ tự tương ứng
Không được nhập/in ra trực tiếp hằng/biến kiểu liệt kê.
Tự học: Đọc thêm ở đây
Kiểu đoạn con (Sub-range type)
type
TypeIdentifier = LowestValue..HighestValue;
TypeIdentifier là tên kiểu đoạn con, LowestValue và HighestValue là hai hằng thuộc cùng một kiểu đơn giản có thứ tự đã được định nghĩa trước
Ví dụ:
type
TDOW = (Sun, Mon, Tue, Wed, Thu, Fri, Sat);
TWorkingDay = Mon..Fri;
TCapitalAlphabet = `A`..`Z`;
var
WD: TWorkingDay;
Letter: TCaptitalAlphabet;
Khi đó ta có thể gán các giá trị Mon, Tue, Wed, Thu, Fri cho biến WD, gán các ký tự là chữ cái in hoa cho biến Letter.
Hàm Ord(Giá trị kiểu đoạn con) sẽ trả về số thứ tự trong kiểu cơ sở.
WD := Mon;
WriteLn(Ord(WD)); //Vẫn in ra số 1
Tự học: Đọc thêm ở đây.
Định nghĩa mảng
Mảng (array) là một tập hợp các phần tử:
Cùng kiểu
Có thứ tự
Lưu trữ liên tục trong bộ nhớ
Việc truy cập phần tử mảng được thực hiện thông qua tên mảng và chỉ số.
Khai báo mảng trong Pascal. Có 2 cách:
Khai báo kiểu mảng và biến mảng
Khai báo trực tiếp biến mảng.

Mảng 1 chiều
Mảng 1 chiều thường để lưu giá trị của các dãy.
Trong toán học ta viết, a1, a2, …, an
Trong Pascal ta viết a[1], a[2], …, a[n].
Khai báo kiểu mảng một chiều
type
ArrayType = array[IndexType] of ElementType;
ArrayType là tên kiểu mảng do người lập trình đặt, IndexType là tên kiểu chỉ số, ElementType là tên kiểu phần tử.
Kiểu chỉ số phải là kiểu đơn giản, có thứ tự,
Ví dụ
type
T = array[1..10000] of Integer;
var
a: T;
b: array[`A`..`Z`] of Boolean;
a là một mảng có 10000 phần tử số nguyên: a[1], a[2], ..., a[10000]
b là một mảng có 26 phần tử kiểu logic: b[`A`], b[`B`], ..., b[`Z`]. Ở đây dùng cách khai báo trực tiếp, không qua định nghĩa kiểu
Nhập/xuất mảng một chiều
Không thể nhập trực tiếp một mảng, phải nhập giá trị từng phần tử
Mảng luôn phải khai báo số phần tử đủ lớn để chương trình có thể thực hiện được trong mọi trường hợp, trên thực tế số phần tử có thể ít hơn số lượng khai báo
Ví dụ: Nhập vào một số nguyên dương n và các số nguyên a1, a2, ..., an. In ra dãy a1..n theo thứ tự ngược lại
Để nhập các phần tử a1..n, ta phải nhập lần lượt a1, a2, ...,an, như vậy với mọi chỉ số i chạy từ 1 tới n, ta phải nhập ai.  Cách thông dụng nhất là sử dụng vòng lặp for.
Để xuất các phần tử an..1, với mọi chỉ số i từ n về 1, ta phải xuất ai  Cách đơn giản nhất là sử dụng vòng lặp for.
Ví dụ: Nhập xuất mảng
program ArrayExample;
const
max = 10000;
var
a: array[1..max] of Integer;
n, i: Integer;
begin
Write(`n = `);
ReadLn(n);
for i := 1 to n do
begin
Write(`a[`, i, `]=`);
ReadLn(a[i]);
end;
for i := n downto 1 do
Write(a[i], `, `);
end.
Giao diện nhập/xuất
n = 5
a[1] = 1
a[2] = 4
a[3] = 2
a[4] = 3
a[5] = 5
5, 3, 2, 4, 1,

Bài tập 1
Nhập vào số nguyên dương n  10000 và các số nguyên a1, a2, ..., an.
Cho biết mảng a1..n có bao nhiêu số nguyên tố và chúng xuất hiện ở những vị trí nào trong mảng
Ví dụ
n = 10
a = (1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
Có 7 số nguyên tố: a[2], a[3], a[4], a[6], a[7], a[9], a[10].
Cách làm
Khởi tạo count := 0
Với mỗi i chạy từ 1 tới n, kiểm tra a[i] có phải số nguyên tố hay không, nếu có thì thông báo dãy a có số nguyên tố tại ví trí i và tăng biến count lên 1
Cuối cùng là in ra thông báo có count số nguyên tố
Bài tập 1 (tiếp)
//HS tự hoàn thiện nốt chương trình
...
Count := 0;
for i := 1 to n do
begin
b := a[i] > 1;
if b then
for j := 2 to Trunc(Sqrt(a[i])) do
if a[i] mod j = 0 then
begin
b := False;
Break;
end;
if b then
begin
WriteLn(`a[`, i, `]=`, a[i], ` is a prime number`);
Inc(Count);
end;
end;
WriteLn(`There are `, count, ` prime numbers`);
...

Bài tập 2
Nhập vào một số nguyên dương n  10000 và các số nguyên a1, a2, ..., an
Hãy tìm giá trị lớn nhất trong các số a1..n và chỉ ra những phần tử nào trong mảng a1..n đạt giá trị lớn nhất đó.
Ví dụ
n = 10, a[1..10] = (1, 9, 0, 2, 9, 3, 7, 8, 2, 5)
Giá trị lớn nhất: 9
Các phần tử đạt giá trị lớn nhất: a[2], a[5]
Bài tập 2 (tiếp)
Thuật toán
Khởi tạo một biến max có giá trị bằng a[1]
max := a[1];
Lần lượt so sánh max với các giá trị a[2..n], nếu gặp một giá trị lớn hơn max thì đặt lại max bằng giá trị đó.
for i := 2 to n do
if max < a[i] then max := a[i];
Kết thúc vòng lặp, max chỉ ra giá trị lớn nhất trong mảng
WriteLn(`Maximum Value = `, max);
Cuối cùng là duyệt các phần tử mảng, phần tử nào có giá trị bằng max thì in ra phần tử đó
for i := 1 to n do
if a[i] = max then
WriteLn(`a[`, i, `]=`, max);
Hãy tự viết chương trình...
Bài tập 3: SelectionSort
Nhập vào số nguyên dương n  100000 và các số nguyên a1, a2, ..., an. Hãy sắp xếp lại các phần tử trong mảng a1..n theo thứ tự không giảm: a1  a2  …  an
Thuật toán sắp xếp kiểu chọn (SelectionSort):
Bước 1: Chọn phần tử nhỏ nhất trong các phần tử {a[1..n]}, đảo giá trị cho a[1]
Bước 2: Chọn phần tử nhỏ nhất trong các phần tử {a[2..n]}, đảo giá trị cho a[2]
...
Bước i: Chọn phần tử nhỏ nhất trong các phần tử {a[i..n]}, đảo giá trị cho a[i]
...
Bước n – 1: Chọn phần tử nhỏ nhất trong 2 phần tử {a[n-1], a[n]}, đảo giá trị cho a[n-1]
Bài tập 3: SelectionSort (tiếp)
Mô hình thuật toán SelectionSort
for i := 1 to n – 1 do //Làm n – 1 bước
begin
//Tìm jmin là chỉ số pt nhỏ nhất trong tập {a[i..n]}
jmin := i;
for j := i + 1 to n do
if a[j] < a[jmin] then //Nếu gặp pt a[j]< a[jmin]
jmin := j; //Đặt lại jmin bằng chỉ số mới

//Nếu a[i] không phải pt nhỏ nhất trong tập {a[i..n]}
//Thì đảo giá trị pt nhỏ nhất trong a[i..n] cho a[i]
if jmin i then
begin //Đảo giá trị a[i] cho a[jmin]
temp := a[i];
a[i] := a[jmin];
a[jmin] := temp;
end;
end;
Bài tập 4: InsertionSort
Nhập vào số nguyên dương n  100000 và các số nguyên a1, a2, ..., an. Hãy sắp xếp lại các phần tử trong mảng a1..n theo thứ tự không giảm: a1  a2  …  an
Thuật toán sắp xếp kiểu chèn (InsertionSort):
Bước 1: Dãy chỉ gồm 1 phần tử a[1] coi như đã được sắp.
Bước 2: Xét a[2], tìm cách chèn a[2] vào dãy a[1..1] để được dãy a[1..2] đã sắp
Bước 3: Xét a[3], tìm cách chèn a[3] vào dãy a[1..2] để được dãy a[1..3] đã sắp
...
Bước i: Xét a[i], tìm cách chèn a[i] vào dãy a[1..i-1] để được dãy a[1..i] đã sắp
...
Bước n: Xét a[n], tìm cách chèn a[n] vào dãy a[1..n-1] để được dãy a[1..n] đã được sắp.
Bài tập 4: InsertionSort (tiếp)
Bài toán chèn: a[1..i-1] đã sắp: a[1]  a[2]  …  a[i-1]. Cần chèn giá trị temp=a[i] vào dãy a[1..i-1] để được dãy a[1..i] đã sắp.
Thuật toán chèn: xét chỉ số j chạy từ i - 1 ngược về đầu dãy,
Nếu gặp phần tử a[j] > temp thì kéo lùi phần tử đó về sau 1 vị trí, tạo “khoảng trống” tại vị trí j
Nếu gặp phần tử a[j]  temp hoặc j đã chạy về 0 thì đưa giá trị temp vào “khoảng trống” tại vị trí j + 1 tạo ra ở bước trước.
j := i - 1;
while (j > 0) and (a[j] > temp) do
begin
a[j + 1] := a[j];
j := j - 1
end;
a[j + 1] := temp;
1
2
3
4
5
6
j
j
j
j
j
Bài tập 4: InsertionSort (tiếp)
Mô hình thuật toán InsertionSort
for i := 2 to n do
begin
temp := a[i]; j := i - 1;
while (j > 0) and (a[j] > temp) do
begin
a[j + 1] := a[j];
j := j – 1;
end;
a[j + 1] := temp;
end;
Hãy tự viết chương trình…
Thử chương trình với 100000 giá trị ngẫu nhiên cho mảng A
Thử chương trình với A = 1, 2, …, 100000
Thử chương trình với A = 100000, 99999, …, 1
Đánh giá trường hợp tốt nhất và xấu nhất của InsertionSort
Bài tập 5 (*). ShellSort
ShellSort: là thuật toán đề xuất bởi D.L.Shell (1959), có tốc độ rất nhanh. Được coi là thuật toán sắp xếp nhanh nhất cho tới khi C.A.R Hoare phát kiến ra QuickSort (1961). Trung bình ShellSort vẫn nhanh hơn QuickSort với dãy < 1000 phần tử.
Tư tưởng của ShellSort
Với h = n div 2, dùng thuật toán InsertionSort sắp xếp các dãy con sau đây theo thứ tự:
a[1] < a[1 + h] < a[1 + 2h] <…
a[2] < a[2 + h] < a[2 + 2h] <…
…
a[h] < a[2h] < a[3h] < …
Nếu h = 1 thì ta có dãy ban đầu đã được sắp, nếu không thì đặt h := h div 2 và lặp lại.
Hãy tự viết chương trình và thử kiểm tra tốc độ ShellSort với một dãy số ngẫu nhiên…
Bài tập 6 (**): Chia kẹo
Cho n gói kẹo đánh số từ 1 đến n, gói kẹo thứ i có a[i] viên kẹo. Giả thiết 2  n  200 và 1  a[i]  200 với i: 1  i  n.
Hãy lập trình nhập vào số n và các số a[1..n], tìm cách chia các gói kẹo làm 2 nhóm sao cho độ chênh lệch về số kẹo giữa hai nhóm là nhỏ nhất có thể.
Ví dụ
n = 6, a[1..6] = (100, 4, 9, 5, 6, 98)
Cách chia
Nhóm 1 gồm các gói (1, 4, 5)
Nhóm 2 gồm các gói (2, 3, 6)
Gợi ý:
Gọi F[x] là chỉ số i nhỏ nhất thỏa mãn: Có thể chọn ra trong các gói kẹo từ 1 tới i ra một số gói mà tổng số kẹo được chọn đúng bằng x…