Nguyên Lý Và Phương Pháp Lập Trình
MỘT SỐ BÀI TẬP TRONG CÁC CHƯƠNG
Bài 1. Cho biết các phẩm chất của chương trình và giải thích các phẩm chất
đó?
Có 10 phẩm chát của chương trình:
- Tính đúng đắn, tính chính xác (correctness): chương trình phải thực hiện
được và đáp ứng đúng chức năng theo yêu cầu lập trình ban đầu.
- Tính chắc chắn (robustness): phân tích chương trình thành các chương
trình con, tính độc lập giữa các chương trình con của chương trình càng
cao càng tốt.
- Tính thân thiện (user friendliness): chương trình phải dễ nhìn, trực quan
và dễ sử dụng.
- Khả năng thích nghi (adapability): chương trình có khả năng phát triển,
tiến hóa theo yêu cầu.
- Tính tái sử dụng (reuseabitilty): chương trình có thể dùng làm một phần
trong chương trình khác.
- Tính tương liên (interoperability): khả năng tương tác với người dùng
và với phần mềm khác.
- Tính hiệu quả (efficiency): chương trình phải thực hiện được chức năng
của nó trong giới hạn tài nguyên sao cho là thấp nhất.
- Tính khả chuyển (porability): khả năng chuyển đổi dễ dàng giữa các
môi trường.
- Tính an toàn (security): chương trình phải đảm bảo an toàn thông tin
cho hệ thống máy tính vận hành, không phát sinh hay lây lan virus làm
tổn hại đến hệ thống.
- Tính dừng (halt): chương trình không được chạy vô hạn mà phải được
dừng sau một khoảng thời gian xác định.
Bài 2. Giải thích tính dừng của chương trình?
Chương trình không được chạy vô hạn mà phải được dừng sau một khoảng
thời gian xác định. Có nghĩa là:
- Chương trình phải tồn tại một điều kiện dừng (điều kiện kết thúc) để có

thuật toán sẽ thay đổi ( ở các vòng lặp, việc rẻ nhánh, cấu trúc điều khiển,…)

Tối ưu hoá thời gian:
- Kỹ thuật tối ưu hoá việc rẽ nhánh.
+ Không thế để các điều kiện A
i
theo thứ tự ngẫu nhiên.
+ Phải sắp các A
i
theo xác suất sai của A
i
giảm dần.
- Kỹ thuật tối ưu các vòng lặp.
+ Tách các lệnh không phụ thuộc vào chỉ số lặp ra khỏi
vòng lặp.
+ Giảm số toán tử phức tạp trong vòng lặp nhờ các biến phụ.
VD:
Đoạn chương trình gốc Đoạn chương trình tối ưu

…
vòng lặp
…
sin(x) + …
…
sx=sin(x)
…
vòng lặp
…
sx + …
…

- Nguyên lý phân cấp bộ nhớ.
VD: Từ điển có 1 000 000 từ.
 3 000 từ thông dụng sẽ được đặt ở bộ nhớ trong.
 997 000 từ còn lại sẽ được đặt ở bộ nhớ ngoài.
- Nguyên lý dùng công thức thay bộ nhớ.

Bài 6. Tìm giải pháp tối ưu cho chương trình đếm số ký tự theo loại: loại ký số,
loại ký tự hoa, loại ký tự thường và các ký tự loại khác.
- Dùng mảng mọt chiều.
- Xem mọt ký tự nhu là mọt chỉ số trong mảng mà giá trị của thành
phần sẽ xác định kiểu của ký tự.
- Mỗi ký tự là mọt số nguyên có trị trong khoảng từ [0 đến 255]
- Tạo mảng mọt chiều TypeTable[0 255] nhu sau:
TypeTable[‘a’]=. . . TypeTable[‘z’]=’thuong’

TypeTable[‘A’]=. . . TypeTable[‘Z’]=’hoa’

TypeTable[‘0’]=. . . TypeTable[‘9’]=’so’

Các truờng hợp khác của chỉ số sẽ có trị là “khác”

Phân tích lợi điểm:

• Xử lý chuỗi qua chỉ số mảng, tang tốc đọ.
• Tốn bọ nhớ.

Bài 7. Tìm giải pháp tối ưu cho chương trình đếm số bit 1 của mỗi từ (kiểu số
word – 32 bit) trong danh sách các từ cho trước (số lượng từ rất lớn).
Dùng mảng một chiều
• Tách một từ (word - W) thành 4 bytes.
• Trong mỗi byte thay vì đếm số bit 1 ( mất thời gian) ta truy cập
mảng một chiều
Ctable[0]:=0; { không có bit nào mang trị 1)// số bit 1 của 256 kí tự trong
mã ASSCI
. . . . .

}
for (int y = i; y < j - 1; y++)
{
if (a[y] > a[y + 1])
{
DoiCho(y, y + 1);
}
}
i++;
j ;
}
}
Phạm My:
 Ý tưởng Bubble sort:
 Xuất phát từ cuối dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ hơn
trong cặp phần tử đó về vị trí đúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở
bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí đầu dãy là i.
 Lặp lại xử lý trên cho đến khi không còn cặp phần tử nào để xét.
 Cải tiến:
 Thay vì ta duyệt từ cuối mảng ta duyệt 2 lược từ 2 phía :
 Lượt đi: đẩy phần tử nhỏ về đầu mảng.
 Lượt về: đẩy phần tử lớn về cuối mảng.
 Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa.
 Thuật giải:
 Bước 1: l=0; r=n-1; //Đoạn l->r là đoạn cần được sắp xếp
k=n; //ghi nhận vị trí k xảy ra hoán vị sau cùng
// để làm cơ sơ thu hẹp đoạn l->r
 Bước 2:
Bước 2a:
j=r; //đẩy phần tử nhỏ về đầu mảng

Y = an
.x
n
+ a
n-1
. x
n-1
+ … + a
1
.x + a
0
Bài 11. Sắp xếp một dãy số nguyên 20000 số phân biệt khác nhau (các số nguyên
đó có trị từ 1 30000) mà bộ nhớ trong chỉ có 1200 từ (4 bytes/từ).
Bộ nhớ có 1200 từ, 1 từ có 4 bytes. Vậy ta có tất cả: 1200*4=4800 (byte).
Mà, 1 byte có 8 bit => có tất cả: 4800*8=38400 (bit).
Để lưu được 20000 số phân biệt. Xét mảng gồm 38400 bit, để lưu 20000 số
phân biệt khác nhau có giá trị từ 1 đến 30000 ta sẽ đánh số tương ứng với
giá trị của nó trên mảng.
VD: để lưu số 100 ta sẽ đánh số 1 vào vị trí thứ 99 của mảng (vì mảng bắt
đầu từ vị trí số 0). Khi duyệt mảng, cứ đến vị trí thứ i có giá trị 1 thì tương
ứng với số có giá trị i-1. Và random cho tới vị trí số 29999 và đủ 20000 số.
Những số j không được lưu trữ thì vị trí tại j-1 đó có giá trị là 0.
Bài 12. Hãy đặc tả ngôn ngữ được biểu thị bởi biểu thức chính qui:
a) a. 0(0|1)*0
b) b. (0|1)*0(0|1)(0|1)
c) c. 0*10*10*10*
Biểu thức chính quy Giá trị
0(0|1)*0
L(0(0|1)*0)
= L(0(0|1)*)

∩
({0}
∪
{1})
∩
({0}
∪
{1})
= {0;1}*
∩
{0}
∩
{0;1}
∩
{0;1}
= {0}
0*10*10*10*
L(0*10*10*10*)
= L(0*)
∩
L(10*)
∩
L(10*)
∩
L(10*)
= {0}* ∩ {10}* ∩ {10}* ∩ {10}*
=
∅


Ví dụ: Câu lẹnh, biểu thức,
3. Mọt tạp hợp các luạt sinh (productions) trong đó mỗi luạt sinh bao
gồm mọt ký hiẹu chua kết thúc - gọi là vế trái, mọt mũi tên và mọt
chuỗi các token và / hoạc các ký hiẹu chua kết thúc gọi là vế phải.
4. Mọt trong các ký hiẹu chua kết thúc đuợc dùng làm ký hiẹu bắt đầu
của van phạm.
VD:
list →list+digit|list-digit|digit
digit → 0 | 1 | 2 | 9




Nhu vạy van phạm phi ngữ cảnh ở đây là:



- Tạp hợp các ký hiẹu kết thúc: 0, 1, 2, , 9, +, -
- Tạp hợp các ký hiẹu chua kết thúc: list, digit.



- Các luạt sinh đã nêu trên.



- Ký hiẹu chua kết thúc bắt đầu: list. ”
S → ( L ) | a
L → L,S | S
- Ký hiệu kết thúc: “(”, “)”, “,”,a
- Ký hiệu không kết thúc: S,L

::= 'switch' '(' <dynamic-expression> ')' '{'
<declaration> * <statement> * <case> * '}'
case
::= <case-label> * <statement> *
case-label
::= 'case' <static-expression> ':'
::= 'default' ':'
dynamic-expression
::= <expression>
static-expression
::= <expression>
Cao Nguyen Ho:
switch = 'switch', '(', variable , ')',
'{', 'case', white space, value , ':'
{ assignment| 'break;'},
'default:'
{ assignment| 'break;'},
'}'
variable = alphabetic character, { alphabetic character | degit };
value = alphabetic character, { alphabetic character | degit };
alphabetic character = "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" ;
digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ;
assignment = { funtion | command }, ';'
funtion =
command = …

c) Định nghĩa union trong C

<Var> → A|B|C
Bài 18. Dùng BNF đặc tả cho phép toán ++ và trong C
<stmt>::= <incr_stmt>|<decr_stmt>
<incr_stmt> ::= <variable_name>'++'|'++'<variable_name>;
<decr_stmt> ::= <variable_name>' '|' '<variable_name>;
Bài 19. Chứng minh văn phạm sau nhập nhằng:
<S>  <A>
<A>  <A> + <A> | <id>
<id>  a | b | c
Bài 20. Chỉnh sửa văn phạm trong bài 9 để thêm vào phép toán sao cho phép
toán này có độ ưu tiên cao nhất

Note: có 2 bài 21, do đó bài ở trên là bài 21A, bài dưới là 21B.
Bài 21. (Bài 21A). Hãy đặc tả ngôn ngữ định nghĩa bởi văn phạm sau:
<S>  <A> <B> <C>
<A>  a <A> | a
<B>  b <B> | b
<C>  c <C> | c Luật sinh gồm có
<S> -> <A> <B> <C>
<A> -> a <A>
<A> -> a .
<B> ->b <B>
<B> ->b .
<C> ->c <C>

{ a[i] = x  ( ∃j: j ≥ 1  a[j] = x  i  j ) }
Bài 25. Thực hiện kiểm tra văn phạm hồi qui không trái (pairwise disjoint test):
a) a. A → aB | b | cBB
A -> aB | b | CBB
first (aB) = a
first (b) = b
first (cBB) = c
b) b. B → aB | bA | aBb
B -> aB | ba | aBb
first (aB) = a
first (ba) = b
first (aBb) = a
c) c. C → aaA | b | caB
C -> aaA | b | caB
first (aaA) = a
first (b) = b
first (caB) = c
Bài 26. Xác định trị từ vựng có thể hình thành các token trong các chương trình
sau:
a. Pascal:
Function max(I, j : integer) : integer;
begin
if i>j then max :=i
else max := j;
end;
b. C:
int i, j;
int max(i, j)
{
return i>j ? i:j;