Giáo trình Lập trình hàm và lập trình Lôgic (Phần 1)

ĐẠI HỌC ĐÀ NẴNG 
TRƯỜNG ĐẠI HỌC BÁCH KHOA 
KHOA CÔNG NGHỆ THÔNG TIN 
GIÁO TRÌNH 
LẬP TRÌNH HÀM 
VÀ LẬP TRÌNH LÔGIC 
PGS.TS. PHAN HUY KHÁNH biên soạn 
ĐÀ NẴNG 3/2009 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 2 
Mục lục 
CHƯƠNG 1 CÁC NGÔN NGỮ LẬP TRÌNH..................................................................5 
I. MỞ ĐẦU VỀ NGÔN NGỮ LẬP TRÌNH ............................................................ 5 
I.1. Vài nét về lịch sử.......................................................................................................5 
I.2. Định nghĩa một ngôn ngữ lập trình......................................................................6 
I.3. Khái niệm về chương trình dịch ...........................................................................8 
II. PHÂN LOẠI CÁC NGÔN NGỮ LẬP TRÌNH.................................................... 9 
III. NGÔN NGỮ LẬP TRÌNH MỆNH LỆNH......................................................... 11 
IV. CƠ SỞ CỦA CÁC NGÔN NGỮ HÀM.............................................................. 12 
CHƯƠNG 2 NGÔN NGỮ SCHEME..............................................................................17 
I. GIỚI THIỆU SCHEME ..................................................................................... 17 
II. CÁC KIỂU DỮ LIỆU CỦA SCHEME.............................................................. 18 
II.1. Các kiểu dữ liệu đơn giản.....................................................................................18 
II.1.1. Kiểu số ................................................................................. 18 
II.1.2. Kiểu lôgích và vị từ.............................................................. 20 
II.1.3. Ký hiệu................................................................................. 21 
II.2. Khái niệm về các biểu thức tiền tố.....................................................................23 
II.3. S-biểu thức ................................................................................................................24 
III. CÁC ĐỊNH NGHĨA TRONG SCHEME ........................................................... 25 
III.1. Định nghĩa biến .......................................................................................................25 
III.2. Định nghĩa hàm .......................................................................................................26 
III.2.1. Khái niệm hàm trong Scheme.............................................. 26 
III.2.2. Gọi hàm sau khi định nghĩa ................................................. 26 
III.2.3. Sử dụng các hàm bổ trợ ....................................................... 27 
III.2.4. Tính không định kiểu của Scheme....................................... 28 
III.3. Cấu trúc điều khiển.................................................................................................29 
III.3.1. Dạng điều kiện if.................................................................. 29 
III.3.2. Biến cục bộ .......................................................................... 30 
III.3.3. Định nghĩa các vị từ ............................................................. 32 
III.4. Sơ đồ đệ quy và sơ đồ lặp.....................................................................................33 
III.4.1. Sơ đồ đệ quy ........................................................................ 33 
III.4.2. Ví dụ..................................................................................... 34 
III.4.3. Tính dừng của lời gọi đệ quy ............................................... 36 
III.4.4. Chứng minh tính dừng ......................................................... 37 
III.4.5. Sơ đồ lặp .............................................................................. 37 
III.5. Vào/ra dữ liệu...........................................................................................................39 
III.6. Kiểu dữ liệu phức hợp ...........................................................................................40 
III.6.1. Kiểu chuỗi ............................................................................ 40 
III.6.2. Kiểu dữ liệu vectơ................................................................ 43 
III.6.3. Khái niệm trừu tượng hoá dữ liệu........................................ 43 
III.6.4. Định nghĩa bộ đôi................................................................. 45 
III.6.5. Đột biến trên các bộ đôi ....................................................... 47 
III.6.6. Ứng dụng bộ đôi .................................................................. 47 
III.7. Kiểu dữ liệu danh sách ..........................................................................................52 
III.7.2. Dạng case xử lý danh sách................................................... 62 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 3 
III.7.3. Kỹ thuật đệ quy xử lý danh sách phẳng............................... 64 
III.7.4. Kỹ thuật đệ quy xử lý danh sách bất kỳ............................... 67 
III.8. Biểu diễn danh sách................................................................................................70 
III.8.1. Biểu diễn danh sách bởi kiểu bộ đôi .................................... 70 
III.8.2. Danh sách kết hợp................................................................ 73 
III.8.3. Dạng quasiquote................................................................... 76 
III.9. Một số ví dụ ứng dụng danh sách.......................................................................77 
III.10. Sử dụng hàm.............................................................................................................80 
III.10.1. Dùng tên hàm làm tham đối................................................. 81 
III.10.2. Áp dụng hàm cho các phần tử của danh sách ...................... 83 
III.10.3. Kết quả trả về là hàm ........................................................... 85 
III.11. Phép tính lambda.....................................................................................................86 
III.11.1. Giới thiệu phép tính lambda................................................. 86 
III.11.2. Biễu diễn biểu thức lambda trong Scheme .......................... 87 
III.11.3. Định nghĩa hàm nhờ lambda................................................ 88 
III.11.4. Kỹ thuật sử dụng phối hợp lambda...................................... 90 
III.11.5. Định nghĩa hàm nhờ tích luỹ kết quả ................................... 93 
III.11.6. Tham đối hoá từng phần ...................................................... 95 
III.11.7. Định nghĩa đệ quy cục bộ .................................................... 95 
III.12. Xử lý trên các hàm..................................................................................................97 
III.12.1. Xây dựng các phép lặp......................................................... 97 
III.12.2. Trao đổi thông điệp giữa các hàm........................................ 99 
III.12.3. Tổ hợp các hàm.................................................................. 101 
III.12.4. Các hàm có số lượng tham đối bất kỳ................................ 102 
III.13. Một số ví dụ ......................................................................................... 104 
III.13.1. Phương pháp xấp xỉ liên tiếp ............................................. 104 
III.13.2. Tạo thủ tục định dạng ........................................................ 105 
III.13.3. Xử lý đa thức...................................................................... 106 
III.13.4. Thuật toán quay lui ............................................................ 111 
CHƯƠNG 3 NGÔN NGỮ PROLOG............................................................................122 
I. GIỚI THIỆU NGÔN NGỮ PROLOG ............................................................. 122 
I.1. Prolog là ngôn ngữ lập trình lôgich ..................................................... 122 
I.1.1. Cú pháp Prolog .................................................................. 123 
I.1.2. Các thuật ngữ ..................................................................... 123 
I.1.3. Các kiểu dữ liệu Prolog...................................................... 123 
I.1.4. Chú thích............................................................................ 124 
I.2. Các kiểu dữ liệu sơ cấp của Prolog...................................................... 124 
I.2.1. Kiểu hằng số ...................................................................... 124 
I.2.2. Kiểu hằng lôgich ................................................................ 125 
I.2.3. Kiểu hằng chuỗi ký tự........................................................ 125 
I.2.4. Kiểu hằng nguyên tử .......................................................... 125 
I.2.5. Biến.................................................................................... 125 
II. SỰ KIỆN VÀ LUẬT TRONG PROLOG ........................................................ 125 
II.1. Xây dựng sự kiện ................................................................................. 125 
II.2. Xây dựng luật....................................................................................... 128 
II.2.1. Định nghĩa luật................................................................... 128 
II.2.2. Định nghĩa luật đệ quy....................................................... 132 
II.2.3. Sử dụng biến trong Prolog ................................................. 135 
III. KIỂU DỮ LIỆU CẤU TRÚC CỦA PROLOG................................................. 136 
III.1. Định nghĩa kiểu cấu trúc của Prolog.................................................... 136 
III.2. So sánh và hợp nhất các hạng .............................................................. 138 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 4 
IV. QUAN HỆ GIỮA PROLOG VÀ LÔGICH TOÁN HỌC ................................ 141 
IV.1. Các mức nghĩa của chương trình Prolog.............................................. 142 
IV.2. Nghĩa khai báo của chương trình Prolog ............................................. 142 
IV.3. Khái niệm về gói mệnh đề ................................................................... 143 
IV.4. Nghĩa lôgich của các mệnh đề ............................................................. 144 
IV.5. Nghĩa thủ tục của Prolog...................................................................... 145 
IV.6. Tổ hợp các yếu tố khai báo và thủ tục ................................................. 152 
V. VÍ DỤ : CON KHỈ VÀ QUẢ CHUỐI .............................................................. 153 
V.1. Phát biểu bài toán................................................................................. 153 
V.2. Giải bài toán với Prolog....................................................................... 154 
V.3. Sắp đặt thứ tự các mệnh đề và các đích ............................................... 157 
V.3.1. Nguy cơ gặp các vòng lặp vô hạn...................................... 157 
V.3.2. Thay đổi thứ tự mệnh đề và đích trong chương trình ........ 159 
VI. SỐ HỌC ........................................................................................................... 162 
VI.1. Các phép toán số học ........................................................................... 162 
VI.2. Biểu thức số học................................................................................... 162 
VI.3. Định nghĩa các phép toán trong Prolog................................................ 164 
VI.4. Các phép so sánh số học ...................................................................... 168 
VI.5. Các phép so sánh hạng......................................................................... 169 
VI.6. Vị từ xác định kiểu............................................................................... 170 
VI.7. Một số vị từ xử lý hạng........................................................................ 171 
VII. ĐỊNH NGHĨA HÀM........................................................................................ 172 
VII.1. Định nghĩa hàm sử dụng đệ quy .......................................................... 172 
VII.2. Tối ưu phép đệ quy .............................................................................. 179 
VII.3. Một số ví dụ khác về đệ quy ................................................................ 180 
VII.3.1. Tìm đường đi trong một đồ thị có định hướng .................. 180 
VII.3.2. Tính độ dài đường đi trong một đồ thị............................... 181 
VII.3.3. Tính gần đúng các chuỗi .................................................... 181 
VIII. BIỂU DIỄN CẤU TRÚC DANH SÁCH ......................................................... 182 
IX. MỘT SỐ VỊ TỪ XỬ LÝ DANH SÁCH CỦA PROLOG................................. 184 
X. CÁC THAO TÁC CƠ BẢN TRÊN DANH SÁCH.......................................... 185 
X.1. Xây dựng lại một số vị từ có sẵn ........................................................ 185 
X.1.1. Kiểm tra một phần tử có mặt trong danh sách ................... 185 
X.1.2. Ghép hai danh sách ............................................................ 186 
X.1.3. Bổ sung một phần tử vào danh sách .................................. 189 
X.1.4. Loại bỏ một phần tử khỏi danh sách.................................. 189 
X.1.5. Nghịch đảo danh sách ........................................................ 190 
X.1.6. Danh sách con .................................................................... 190 
X.1.7. Hoán vị............................................................................... 191 
X.2. Một số ví dụ về danh sách.................................................................... 192 
X.2.1. Sắp xếp các phần tử của danh sách.................................... 192 
X.2.2. Tính độ dài của một danh sách .......................................... 193 
X.2.3. Tạo sinh các số tự nhiên..................................................... 194 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 5 
CHƯƠNG 1 
CÁC NGÔN NGỮ LẬP TRÌNH 
I. Mở đầu về ngôn ngữ lập trình 
I.1. Vài nét về lịch sử 
Buổi ban đầu 
hững ngôn ngữ lập trình (programming language) đầu tiên trên máy tính điện tử là ngôn 
ngữ máy (machine language), tổ hợp của các con số hệ hai, hay hệ nhị phân, hay các bit 
(viết tắt của binary digit) 0 và 1. Ngôn ngữ máy phụ thuộc hoàn toàn vào kiến trúc phần 
cứng của máy tính và những quy ước khắt khe của nhà chế tạo. Để giải các bài toán, người lập 
trình phải sử dụng một tập hợp các lệnh điều khiển rất sơ cấp mà mỗi lệnh là một tổ hợp các số 
hệ hai nên gặp rất nhiều khó khăn, mệt nhọc, rất dễ mắc phải sai sót, nhưng lại rất khó sửa lỗi. 
Từ những năm 1950, để giảm nhẹ việc lập trình, người ta đưa vào kỹ thuật chương trình 
con (sub-program hay sub-routine) và xây dựng các thư viện chương trình (library) để khi cần 
thì gọi đến hoặc dùng lại những đoạn chương trình đã viết. 
Ngôn ngữ máy tiến gần đến ngôn ngữ tự nhiên 
Cũng từ những năm 1950, ngôn ngữ hợp dịch, hay hợp ngữ (assembly) hay cũng còn được 
gọi là ngôn ngữ biểu tượng (symbolic) ra đời. Trong hợp ngữ, các mã lệnh và địa chỉ các toán 
hạng được thay thế  ... (some-solutions (followingstates state)))) 
(define (other-solution? state) 
(display state) 
(newline) 
(display ”Other solution (Y/N)?:”) 
(eq? (read) ’n)) 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 113 
Cột j 
8 Q 
7 Q 
6 Q 
5 Q 
4 Q Hàng i 
3 Q 
2 Q 
1 Q 
 1 2 3 4 5 6 7 8 
Hình 0.16. Một lời giải của bài toán 8 quân hậu. 
Sau khi đã định nghĩa các hàm chính, ta cần định nghĩa các hàm bổ trợ finalstate?, 
solution?, followingstates tương ứng với một cách tổ chức dữ liệu cho bài toán 8 
quân hậu. Trước tiên ta cần tìm cách biểu diễn các trạng thái tìm kiếm lời giải. 
Bàn cờ vua có 8×8 ô được đánh số theo hàng 1..8 và theo cột 1..8. Do mỗi cột chỉ đăt được 
một con Q, ta cần biết vị trí là toạ độ hàng tương ứng với mỗi cột đang xét. Như vậy, một trạng 
thái sẽ là một danh sách các số nguyên (x1,..., xk) với xi là số thứ tự hàng của con Q thứ i đặt ở 
cột thứ i, i=1..k, k=1..8. 
Ví dụ trạng thái của một lời giải được cho trong Error! Reference source not found. là 
danh sách đầy đủ : 
(1 5 8 6 3 7 2 4) 
Nghĩa là lời giải được tìm thấy khi trạng thái đã có đủ 8 con Q và mỗi con Q không thể bị 
ăn bởi một con Q nào khác trên bàn cờ. Từ đó, ta định nghĩa vị từ solution? cũng là 
finalstate?. 
(define (finalstate? state) 
(= (length state) 8)) 
(define solution? finalstate?) 
Để liệt kê các trạng thái tiếp theo từ một trạng thái đã cho, ta cần xét 8 vị trí là 8 hàng có 
thể trên cột tiếp theo để đặt con Q vào. Vị trí cho Q mới này (newqueen) phải được chọn sao 
cho không bị ăn bởi các Q khác trong trạng thái đang xét. Ta cần xác dịnh hàm 
admissible? để kiểm tra nếu một vị trí cho một con Q mới là tương thích với những con Q 
đã dặt trước đó. 
... Q 
... × 
... × Q 
... Q × 
... × con Q mới tại một vị trí chấp nhận được 
... × × × × Q 
... × 
... Q × 
Hình 0.17. Vị trí chấp nhận được của một quân hậu. 
Nói cách khác, không có con Q nào nằm trên hàng, trên cột, trên đường chéo thuận và trên 
đường chéo nghịch đi qua vị trí này. Để xây dựng hàm admissible?, ta cần xây dựng một 
hàm bổ trợ kiểm tra khả năng chấp nhận của con Q mới với một con Q đã đặt trước đó tại một 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 114 
khoảng cách (distance) đã cho. Tham biến distance là khoảng cách giữa con Q mới và con 
Q trước đó. Còn existing-queens là danh sách trạng thái đang xét. 
Từ ý tưởng trên, vị từ admissible? được xây dựng như sau : 
(define (admissible? newqueen existing-queens) 
(letrec ((admisible-to? 
(lambda (existing-queens distance) 
(if (null? existing-queens) 
#t 
(let ((aqueen (car existing-queens))) 
; kiểm tra lần lượt từng con hậu đã có mặt trong danh sách 
(and ; kiểm tra không cùng đường chéo thuận 
(not (= aqueen (+ newqueen distance))) 
; kiểm tra không cùng hàng 
(not (= aqueen newqueen)) 
; kiểm tra không cùng đường chéo nghịch 
(not (= aqueen (- newqueen distance))) 
; tiếp tục kiểm tra các quân hậu tiếp theo 
(admisible-to? (cdr existing-queens) 
(+ 1 distance)))))))) 
(admisible-to? existing-queens 1))) 
Vị từ admissible? không kiểm tra hai quân hậu nằm trên cùng cột. Vị trí chấp nhận 
được của một con Q được minh hoạ trên hình 0.17. 
Để xây dựng danh sách các trạng thái tiếp theo một trạng thái đã đạt được ở bước trước, 
hàm followingstates dưới đây tìm kiếm vị trí chấp nhận được cho một con Q mới. Nếu 
tìm được vị trí thoả mãn, thêm toạ độ hàng vào cuối danh sách trạng thái để trả về : 
(define (followingstates state) 
(append-map 
(lambda (position) 
(if (admissible? position state) 
(list (cons position state)) 
’())) 
 (list-1-to-n 8))) 
Hàm list-1-to-n có mặt trong hàm followingstates dùng để liệt kê danh sách 
các số nguyên từ 1.. n được xây dựng như sau : 
(define (list-1-to-n n) 
(letrec ((loop 
(lambda (k L) 
(if (zero? k) 
L 
(loop (- k 1) (cons k L)))))) 
(loop n ’()))) 
(list-1-to-n 8) 
--> ’(1 2 3 4 5 6 7 8) 
3. Tổ chức các lời giải 
Như vậy, ta đã xây dựng xong các hàm chính và các hàm bổ trợ để tìm lời giải cho bài toán 
8 quân hậu. Các hàm chính là : 
(a-solution state) 
--> Tìm một lời giải. 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 115 
(list-of-solutions state) 
--> Tìm tất cả các lời giải. 
(some-solutions state) 
--> Tìm lần lượt các lời giải theo yêu cầu. 
Lúc đầu, trạng thái state là một danh sách rỗng, sau khi tìm ra lời giải, danh sách được 
làm đầy. Các hàm bổ trợ được sử dụng trong các hàm trên đây là : 
(finalstate? state) 
--> Vị từ kiểm tra nếu một trạng thái tương ứng với một vị trí không thể tiếp tục. 
(solution? state) 
--> Vị từ kiểm tra một trạng thái là một lời giải (tương tự hàm finalstate?). 
(followingstate state) 
--> Danh sách tất cả các trạng thái tiếp theo chấp nhận được và khả năng xuất phát từ một 
trạng thái đã cho. 
(admissible? newqueen existing-queens) 
--> Vị từ kiểm tra nếu vị trí của con Q mới không bị ăn bởi các con Q khác đặt tại các cột 
trước đó trong danh sách trạng thái. 
Bây giờ ta chạy demo bài toán 8 quân hậu và nhận được kết quả như sau : 
(a-solution ’()) 
--> ’(4 2 7 3 6 8 5 1) 
(some-solutions '()) 
--> (4 2 7 3 6 8 5 1) 
Other solution (Y/N)?: y 
(5 2 4 7 3 8 6 1) 
Other solution (Y/N)?: y 
(3 5 2 8 6 4 7 1) 
Other solution (Y/N)?: y 
(3 6 4 2 8 5 7 1) 
Other solution (Y/N)?: y 
(5 7 1 3 8 6 4 2) 
Other solution (Y/N)?: y 
(4 6 8 3 1 7 5 2) 
Other solution (Y/N)?: n 
#t 
Số lượng tất cả các lời giải cho bài toán tám quân hậu được tính như sau : 
(length (list-of-solutions '())) 
--> 92 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 116 
Bài tập chương 2 − NGÔN NGỮ SCHEME 
1. Giải thích các biểu thức số học sau đây, sau đó tính giá trị và so sánh kết quả : 
(+ 23 (- 55 44 33) (* 2 (/ 8 4))) 
(define a 3) 
a 
(/ 6 a) 
(define b (+ a 1)) 
(+ a b (* a b)) 
2. Giải thích các biểu thức lôgic sau đây, sau đo tính giá trị và so sánh kết quả (có thể sử 
dụng hai biến a và b trong bài tập 1) : 
(= 2 3) 
(= a b) 
(not (or (= 3 4) (= 5 6))) 
(+ 2 (if (> a b) a b)) 
3. Giải thích các biểu thức điều kiện sau đây, sau đo tính giá trị và so sánh kết quả : 
(if (= 1 1) ”waaw” ”brrr”) 
(if (= 4 4) 5 6) 
(if (> a b) a b) 
(if (and (> b a) (< b (* a b))) b a) 
(+ 2 (if (> a b) a b)) 
((if (< a b) + -) a b) 
(cond ((= 1 1) ”waaw 1”) 
((= 2 2) ”waaw 2”) 
((= 3 3) ”waaw once more”) 
(else ”waaw final”)) 
(* (cond ((> a b) a) 
((< a b) b) 
(else -1)) 
(+ a 1)) 
4. Viết dạng ngoặc tiền tố của các biểu thức : 
a) (p−a) (p−b) (p−c) 
b) 1 + 2x2 + 3x3 
c) )cos(1
)cos()sin(
yx
yxyx
++
−+
5. Các biểu thức sau đây có đúng về mặt cú pháp hay không? 
f (x y z) (f) (x y z) (f) ((f f)) 
() ff ((a) (b) (c)) 
6. Giải thích các s-biểu thức sau đây, sau đo tính giá trị và so sánh kết quả : 
(and #f (/ 1 0)) 
(if #t 2 (/1 0)) 
(if #f 2 (/ 1 0)) 
(and #t #t #f (/ 1 0)) 
(and #t #t #t (/ 1 0)) 
7. Viết hàm yêu cầu người sử dụng gõ vào một số nằm giữa 0 và 1000 để trả về giá trị 
bình phương của số đó. Đặt hàm này vào trong một vòng lặp với menu. 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 117 
8. Viết hàm sử dụng menu để giải hệ phương trình đại số tuyến tính : 
ax + by = 0 
cx + dy = 0 
9. Viết hàm tính giá trị tiền phải trả từ giá trị không thuế (duty-free). Biết rằng hệ số thuế 
VAT là 18,6%. 
10. Viết hàm tính chiều cao h của tam giác theo các cạnh a, b, c cho biết diện tích tam giác 
được tính : 
S = p(p-a) (p-b) (p-c) 
với p là nửa chu vi (sử dụng hàm bổ trợ tính để tính p). 
11. Viết biểu thức tính nghiệm phương trình bậc hai ax2 + bx + c = 0. 
12. Cho biết giá trị của a=10, hãy tính : 
(let ((a (* a a)) (b (* 4 5)) (c (* a 5))) 
(+ a b c)) 
13. Tính giá trị hai biểu thức sau : 
(let ((x 5)) 
(let* ((y (+ x 10)) (z (* x y))) 
(+ x y z))) 
(let ((x 4)) 
(if (= x 0) 1 (let ((x 10)) (* x x)))) 
14. Viết biểu thức Scheme để tính giá trị : 
2 2 2 2
2 2 2 2
x + y - x - y
1 + x + y + x - y 
 khi biết giá trị của x, y 
15. Viết hàm (sum n) = 1 + 1/2 +...+ 1/n vói n nguyên, n > 0 
16. Viết hàm (power n x) = xn với x bất kỳ và n nguyên. Cho xn = x * xn−1. 
Mở rộng cho trường hợp n < 0. 
17. Tương tự bài tập 16 nhưng sử dụng phương pháp chia đôi : 
x0 = 1, xn = x* xn−1 nếu n lẻ và xn = (xn/2)
2
 nếu n chẵn. 
18. Viết vị từ kiểm tra một năm đã cho có phải là năm nhuần không ? 
19. Viết hàm(nbsec h m s) tính ra số giây từ giờ, phút, giây đã cho. Ví dụ : 
(nbsec 10 3 45) 
--> 36225 
20. Viết hàm (Hanoi n A B C) giải bài toán «Tháp Hà Nội». Ví dụ : 
(Hanoi 2 ’A ’B ’C) 
--> Move A to B 
Move A to C 
Move B to C 
1. Giải thích các biểu thức sau đây, sau đó tính giá trị và so sánh kết quả : 
(cons 1 2) 
(car (cons (cons 1 2) (cons 3 4))) 
(cons (cons (cons (cons 1 2) 3) 4) 5) 
(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 ()))))) 
(list 1 2 3 4 5) 
(car (list 1 2 3 4 5)) 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 118 
(cdr (list 1 2 3 4 5)) 
(cadr (list 1 2 3 4 5)) 
(caddr (list 1 2 3 4 5)) 
2. Viết hàm tạo các danh sách sau : 
(a b c d) 
(a ((b c) d (e f))) 
(a (b (c d) . e) (f g) . h) 
3. Cho biết những biểu thức nào có cùng kết quả trong số các biểu thức sau đây : 
(list 1 ’(2 3 4)) 
(append ’(1) ’(2 3 4)) 
(list 1 2 3 4) 
(cons ’1 ’(2 3 4)) 
(cons ’(1) ’(2 3 4)) 
(cons ’1 ’((2 3 4))) 
(append ’(1) ’((2 3 4))) 
4. Cho biết giá trị của các biểu thức sau : 
’(+ 4 7) ’(a b) 
’5 (cons ’a ’((b c))) 
(cdr ’(a)) (cdr week-list) 
(car ’((+ 4 1))) (cdr ’((+ 4 1))) 
(cdr ’((a) b)) (cdr ’((a) (b))) 
(cdr ’’(a b)) 
5. Cho biết các danh sách tương ứng với các sơ đồ sau : 
1) 2) 
6. Từ hàm member, hãy định nghĩa vị từ member?. 
7. Định nghĩa một hàm để phá hết các ngoặc trong một danh sách. 
Chẳng hạn, đối với danh sách ((a b c) (d (e f) g) h (i j)) 
thì hàm trả về : (a b c d e f g h i j) 
8. Hàm concat sau đây dùng để ghép hai danh sách tương tự append : 
(define (concat list1 list2) 
 (define (iter response remaining) 
 (if (null? remaining) 
 (reverse response) 
 (iter (cons (car remaining) response) 
 (cdr remaining)))) 
 (iter list2 list1)) 
Tuy nhiên hàm không trả về kết quả đúng, hãy viết lại cho phù hợp, sao cho : 
(concat ’(1 2 3 4 5) ’(6 7 8 9)) 
--> ’(1 2 3 4 5 6 7 8 9) 
a b 
d e 
c
a b c d e f
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 119 
9. Viết biểu thức trích danh sách để trả về kết quả là danh sách con ’(sat, sun) : 
’(mon tue wed thu fri sat sun). 
10. Viết các hàm trả về phần tử thứ hai, thứ ba và thứ tư của một danh sách. 
11. Viết dạng tổ hợp của car và cdr để nhận được giá trị là ký hiệu a từ các danh sách : ((b 
a) (c d)), (() (a d)), (((a))) 
12. Cho biết giá trị của (car ’’a) và (cdr ’’a) (chú ý hai dấu quote). 
13. Viết định nghĩa tương tự định nghĩa của kiểu list cho kiểu plate-list. 
14. Viết hàm (count s L) đếm số lượng ký hiệu s là chữ cái xuất hiện trong danh sách chữ 
cái L. Ví dụ : 
(count ’R ’(T O M A N D J E R R Y)) 
--> 2 
15. Viết hàm (double L) nhận vào một danh sách các ký hiệu L để trả về danh sách mà các 
ký hiệu đã được viết lặp lại. Ví dụ : 
(double ’(TOM AND JERRY)) 
--> ’(TOM TOM AND AND JERRY JERRY) 
16. Viết hàm (undouble L) nhận vào một danh sách các ký hiệu L trong đó các ký hiệu 
đều bị viết lặp lại để trả về danh sách chỉ chứa mỗi ký hiệu một lần. Ví dụ : 
(undouble (double ’(TOM AND JERRY))) 
--> ’(TOM AND JERRY) 
17. Từ ví dụ xử lý hình chữ nhật trình bày trong lý thuyết, viết vị từ disjoint? trả về #t 
nếu hai hình chữ nhật rời nhau, nghĩa là không có điểm nào chung. 
18. Xây dựng các hàm xử lý hình chữ nhật sử dụng biểu diễn các thành phần bởi danh sách. 
19. Cho biết giá trị các biểu thức dạng quasiquode sau đây : 
`(1 + 2 = ,(+ 1 2)) 
`(the car of the list (a b) is ,(car ’(a b))) 
`(cons ,(+ 2 5) ,(list ’a ’b)) 
(let ((L ’(1 2 3))) 
`((+ ,@L) = ,(+ 1 2 3))) 
20. Dùng kiểu bộ đôi (pair-doublet) để biểu diễn số phức (a + bi). Hãy tính cộng, nhân và luỹ 
thừa bậc n nguyên dương của một số phức. Cho biết : 
Cộng: (a + bi) ± (c + di) = (a ± c) + (b ± d)i 
Trừ : (a + bi) − (c + di) = (a − c) + (b − d)i 
Nhân : (a + bi) × (c + di) = (ac − bd) + (ad ± bc)i 
Chia : −2 2 2 2
(a + bi) (ac + bd) (bc ad) = + i
(c + di) (c + d ) (c + d )
, với điều kiện c2 + d2 ≠ 0. 
Luỹ thừa : (a + bi)n = rn(cosnϕ + isinnϕ), trong đó : 
r = 2 2a + b , ϕ = barctg
a
Căn bậc hai : a + bi = x + yi , trong đó : 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 120 
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞+ = − +⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
2 2 2 2a a b a a bx = + , y + 
2 2 2 2 2 2
Nếu a > 0, tính x và lúc đó, y = b x
2
, nếu a < 0, tính y và lúc đó, x = b y
2
. 
21. Cho biết giá trị của : 
((lambda (x y z) (+ x y z)) 1 (+ 2 5) 3) 
((lambda (L) ((lambda (x) (append L (list x))) 0)) '(a)) 
22. Cho các định nghĩa sau : 
(define (f xl x2 x3 x4) 
 (lambda (m) (m xl x2 x3 x4))) 
(define (g i z) 
 (z (lambda (u v w x) 
 (cond ((= i 1) u) 
 ((= i 2) v) 
 ((= i v) w) 
 (else '()))))) 
(define x (f -2 3 4 20)) 
(define y (list 3 5)) 
(define z (cons y (list 3 5))) 
Cho biết kết quả trả về của các lời gọi sau đây : 
(g 0 x) 
(g 4 1) 
(g 3 x) 
(eq? (cadr z) (car y)) 
(eq? (car z) (cdr z)) 
23. Cho : 
U0 =V0 =1 
Un = Un-1 + Vn-1 
Vn = Un-1 * Vn-1 
Dùng letrec tính giá trị của U3 *V4 ? 
24. Các hàm sau đây làm gì ? Tìm độ phức tạp của chúng ? 
(define (mystery1 L) 
(if (null? L) 
() 
(append (mystery1 (cdr L)) 
(list (car L))))) 
(define (mystery2 L) 
(if (null? (cdr L)) 
(car L) 
(if (> (car L) (mystery2 (cdr Ll))) 
(car L) 
(mystery2 (cdr L))))) 
25. Cho đa thức bậc n hệ số thực (hoặc nguyên) một biến như sau : 
P(x) = a0 + a1x + a2x
2 + . . . + anx
n 
Để biểu diễn P(x) trong Scheme, người ta thường sử dụng một danh sách các hệ số theo 
một chiều : 
(a0, a1, a2, . . . an) hoặc (an, an−1,. . . a1, a0) 
Hãy viết trong Scheme hàm (eval-pol p x) để tính giá trị của đa thức P(x) với một 
LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 121 
giá trị x sử dụng cả hai phương pháp đệ quy và phương pháp lặp, mỗi phương pháp xử lý theo 
hai cách biểu diễn hệ số trên đây. 
26. Viết hàm tính độ sâu của danh sách : 
(profondeur ’(a (b ( c d)) e)) 
--> 3 
27. Viết hàm đếm số lượng các phần tử có giá trị bằng phần tử đã cho : 
(nb-occurrence* ’a ’(e a c a (b c a) (a a)) 
--> 5 
28. Viết hàm tạo danh sách nối vòng cho một danh sách đã cho. 
29. Viết hàm kiểm tra một danh sách có là tiền tố của một danh sách đã cho. 
30. Viết hàm đếm các phần tử của một danh sách nối vòng đã cho. 
31. Viết đầy đủ thủ tục xác định danh sách con L[B..A], nghĩa là tìm hai cận B (below), A 
(above), 1 ≤ A, B ≤ N sao cho tổng các phần tử của nó là tổng con lớn nhất của L (xem 
ví dụ ở mục III.8.1, 3). 
32. Cho một xâu ký tự có độ dài N, N được xem rất lớn. Hãy phân loại mỗi ký tự theo 4 
kiểu như sau : kiểu chữ thường, kiểu chữ hoa, kiểu chữ số và kiểu khác (ký tự không 
thuộc ba kiểu trên) ? 
33. Cho một danh sách có N từ (word) 32 bit, N được xem rất lớn. Hãy đếm số bit bằng 1 
trong mỗi từ của danh sách đã cho ? 
34. Cho một danh sách có N số nguyên. Hãy viết các thủ tục sắp xếp mô phỏng các thuật 
toán sắp xếp chèn và chọn. 
35. Khi sắp xếp một dãy, người ta thường sử dụng hàm bổ trợ swap(a, b) để hoán đối 
giá trị của hai biến. Hãy cho biết vì sao hàm sau đây không sử dụng được ? 
(define (swap a b) 
(let ((temp a)) 
(begin (set! a b) 
(set! b temp))))