Giáo trình Lập trình hàm và Lập trình Logic - Phan Huy Khánh

gọi để thực hiện tính toán L hệt công việc của bốn hàm trên nhưng được viết lại như sau (dòng tiếp theo là ví dụ áp dụng) : ; Hàm (sum h L ) (list-it (lambda (x y) (+ (h x) y)) L 0) (list-it (lambda (x y) (+ (sqrt x) y)) ’(1 2 3 4 5) 0) --> 8.38233 ; Hàm (product h L) (list-it (lambda (x y) (* (h x) y)) L 1) (list-it (lambda (x y) (* (sqrt x) y)) ’(1 2 3 4 5) 1) --> 10.9545 ; Hàm (myappend L1 L2) (list-it cons L1 L2) (list-it cons ’(a b c) ’(1 2)) --> ’(a b c 1 2) ; Hàm (mymap h L) (list-it (lambda (x y) (cons (h x ) y)) L ’()) (list-it (lambda (x y) (cons (sqrt x ) y)) ’(1 2 3 4 5) ’()) --> ’(1 . 1.41421 1.73205 2 . 2.23607) (map sqrt ’(1 2 3 4 5)) --> ’(1 . 1.41421 1.73205 2 . 2.23607) Chú ý khi áp dụng, cần cung cấp tham đối thực sự cho các tham đối là hàm h. 5. Định nghĩa các hàm fold Trong chương 1, ta đã định nghĩa hàm foldr «bao qua phải» dùng để tính toán tích luỹ kết quả trên các phần tử của một danh sách. Sau đây ta định nghĩa trong Scheme hai hàm fold là foldl (left) và foldr (right) cùng nhận vào một hàm f hai tham đối : một phần tử xuất phát a và một danh sách L, để trả về kết quả là áp dụng liên tiếp (luỹ kế) hàm f cho a và với mọi phần tử của L. Hai hàm khác nhau ở chỗ hàm foldl lấy lần lượt các phần tử của L từ trái qua phải, còn hàm foldl lấy lần lượt các phần tử của L từ phải qua trái : (define (foldl f a L) (if (null? L) a (foldl f (f a (car L)) (cdr L)))) (define (foldr f a L) (if (null? L) a (f (car L) (foldr f a (cdr L))))) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 95 (foldl cons 0 ’(1 2 3 4 5)) --> ’(((((0 . 1) . 2) . 3) . 4) . 5) (foldr cons 0 ’(1 2 3 4 5)) --> ’(1 2 3 4 5 . 0) III.11.6. Tham đối hoá từng phần Như đã trình bày ở chương 1 về nguyên lý lập trình hàm, kỹ thuật tham đối hóa từng phần (currying) cho phép dùng biến để truy cập đến các hàm có số tham biến bất kỳ f(x1, ... , xn). Chẳng hạn, hàm hai biến f(x, y) được xem là hàm một biến x trả về giá trị là hàm y : x → (y → f(x, y)) Giả sử xét hàm max tìm số lớn nhất trong thư viện Scheme, với n=2 : (max (* 2 5) 10) --> 10 Sử dụng kỹ thuật Currying, ta viết : (define (curry2 f) (lambda (x) (lambda (y) (f x y)))) (((curry2 max) (* 2 5)) 10) --> 10 Với n=3, ta cũng xây dựng tương tự : (define (curry3 f) (lambda (x) (lambda (y) (lambda (z) (f x y z))))) ((((curry3 max) (* 2 5)) 10) (+ 2 6)) --> 10 Từ đó ta có thể xây dựng cho hàm n đối bất kỳ. Ưu điểm của kỹ thuật Currying là có thể đặc tả một hàm ngay khi mới biết giá trị của tham số thứ nhất, hoặc các tham số đầu tiên cho các hàm có nhiều hơn hai tham đối. Đối với hàm một biến, ưu điểm của kỹ thuật Currying là người ta có thể tổ hợp tuỳ ý các hàm mà không quan tâm đến các tham đối của chúng. III.11.7. Định nghĩa đệ quy cục bộ Trong chương trước, ta đã làm quen với khái niệm hàm bổ trợ để định nghĩa các hàm Scheme. Hàm bổ trợ có thể nằm ngay trong hàm cần định nghĩa, được gọi là hàm cục bộ. Người ta có thể sử dụng dạng hàm letrec trong thư viện Scheme để định nghĩa đệ quy một hàm cục bộ. Chẳng hạn ta cần xây dựng một danh sách các số tự nhiên 0..n với n cho trước như sau : ; iota : number −> list(number) ; hoặc iota : n −> (0 1 2 ... n) (define (iota n) (if (zero? n ) ’(0) (append (iota (- n 1)) (list n)))) (iota 10) --> '(0 1 2 3 4 5 6 7 8 9 10) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 96 Định nghĩa trên đây đúng đắn, tuy nhiên việc sử dụng hàm ghép danh sách append làm tốn bộ nhớ, do luôn luôn phải thêm các phần tử mới vào cuối một danh sách. Vì vậy ý tưởng cải biên là làm ngược lại vấn đề : xây dựng hàm cho phép nhận một số m để trả về danh sách các số tự nhiên từ m đến n là (m m+1 ....n). Thay vì sử dụng hàm ghép danh sách, ta sử dụng cons để xây dựng hàm bổ trợ như sau : (define (m-to-n m n) (if (< n m) ’() (cons m (m-to-n (+ m 1) n)))) (m-to-n 3 10) --> ’(3 4 5 6 7 8 10) Do hàm m-to-n không dùng ở đâu khác, nên cần đặt bên trong hàm iota. Sau khi định nghĩa, cần gọi với tham đối m=0 : (define (iota n) (define (m-to-n m n) (if (< n m) ’() (cons m (m-to-n (+ m 1) n)))) (m-to-n 0 n)) (iota 10) --> '(0 1 2 3 4 5 6 7 8 9 10) Giả sử thay vì định nghĩa hàm cục bộ m-to-n, ta sử dụng dạng let để tạo ra lần lượt các số tự nhiên kể từ m. Tuy nhiên không cần dùng đến tham biến n vì n đã được cấp bởi hàm iota : (define (iota n) (let ((m-to-n (lambda (m) (if (< m n) ’() (cons m (m-to-n (+ m 1))))))) (m-to-n 0))) (iota 10) --> ’() Ta thấy kết quả sai vì lời gọi m-to-n trong hàm chỉ dẫn đến thực hiện let một lần mà không thực hiện gọi đệ quy. Để khắc phục, ta sử dụng dạng letrec, là dạng let đặc biệt để tạo ra lời gọi đệ quy. Cú pháp của letrec giống hệt let cũng gồm phần liên kết và phần thân : (letrec ((v1 e1 ) ... (vk eN)) s) Các biến vi, i=1..N, được gán giá trị ei để sau đó thực hiện phần thân s là một biểu thức nào đó. Tuy nhiên mỗi phép gán biến có thể «nhìn thấy» lẫn nhau, nghĩa là khi tính biểu thức ei thì có thể sử dụng các biến vi với i, j tuỳ ý. Nghĩa là không giống hoàn toàn let, các biến cục bộ v1, ... , vN đều được nhìn thấy trong tất cả các biểu thức e1, ... , ek. Tuy nhiên, cần chú ý rằng mỗi biểu thức ej được tính mà không cần tính giá trị của biến vj, khi ej là một biểu thức lambda. Nhờ ngữ nghĩa này, dạng letrec thường được sử dụng để định nghĩa các thủ tục đệ quy tương hỗ (mutually recursive).. Chẳng hạn, các vị từ odd? và even? là trường hợp điển hình cho các hàm thừa nhận định nghĩa đệ quy tương hỗ. Sau đây là ví dụ sử dụng letrec để định LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 97 nghĩa tương hỗ hai thủ tục cục bộ kiểm tra một số nguyên là chẵn (even) hay lẻ (odd) mà không sử dụng hai hàm thư viện của Scheme là even? và odd? : (letrec ((local-even? (lambda (n) (if (= n 0) #t (local-odd? (- n 1))))) (local-odd? (lambda (n) (if (= n 0) #f (local-even? (- n 1)))))) (list (local-even? 27) (local-odd? 27))) --> ’(#f #t) Bây giờ hàm iota được định nghĩa lại như sau : (define (iota n) (letrec ((m-to-n (lambda (m) (if (< n m) ’() (cons m (m-to-n (+ m 1 ))))))) (m-to-n 0))) (iota 10) −−> ’(0 1 2 3 4 5 6 7 8 9 10) Sử dụng phối hợp dạng letrec và lambda như sau : (lambda (x1 ... xN) (define f1 e1) ... (define fN eN) s) ⇔ (lambda (x1 ... xN) (letrec (f1 e1) ... (fN eN)) s)) III.12. Xử lý trên các hàm III.12.1. Xây dựng các phép lặp Trong mục trước, ta đã định nghĩa hàm list-it sử dụng kỹ thuật tích luỹ kết quả để tạo ra một cấu trúc lập trình giống nhau áp dụng cho nhiều hàm khác nhau. Sau đây, ta sẽ xây dựng các hàm lặp mới là append-map, map-select, every và some để mở rộng thư viện các hàm của Scheme (vốn chỉ có hai thủ tục lặp có sẵn là map và for-each). 1. Hàm append-map Khi một hàm f nhận tham đối là các phần tử của một danh sách để trả về các giá trị là danh sách, người ta cần nối ghép (concatenation) các danh sách này. Ta xây dựng hàm append- map như sau : (define (append-map f L) (apply append (map f L))) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 98 Áp dụng hàm append-map, ta có thể xây dựng hàm flatting để làm phẳng («cào bằng») một danh sách phù hợp khác rỗng theo nguyên tắc : ghép kết quả làm phẳng các phần tử của danh sách ở mức thứ nhất, kết quả làm phẳng của nguyên tử là danh sách (thu gọn về nguyên tử) : (define (flatting s) (if (list? s) (append-map flatting s) (list s))) (flatting ’(a (b c) ((d (e))) "yes" ())) −−> ’(a b c d e "yes") (flatting ’a) −−> ’(a) (flatting 10) −−> ’(10) (flatting ’()) −−> ’() 2. Hàm map-select Nhiều khi, người ta chỉ muốn áp dụng hàm map cho một số phần tử của một danh sách thoả mãn một vị từ p? nào đó mà thôi, nghĩa là sử dụng map có lựa chọn. Ta xây dựng hàm map-select với ý tưởng như sau : sử dụng append-map và gán giá trị ’() cho các phần tử không thoả mãn vị từ, và do vậy các giá trị rỗng này không đưa vào danh sách kết quả cuối cùng khi hàm trả về. (define (map-select f L p?) (append-map (lambda (x) (if (p? x) (list (f x)) ’())) L)) (map-select (lambda (x)(/ 1 x)) ’(a 3 0 5 7 9) (lambda (x) (and (number? x) (not (zero? x))))) −−> ’(1/3 1/5 1/7 1/9) (map-select sqrt '(1 2 3 4 5) odd?) −−> ’(1. 1.73205 2.23607) 3. Các hàm every và some Khi các đối số của phép hội lôgic and là các giá trị của hàm f nào đó, ta có thể định nghĩa hàm every để mở rộng and như sau : (every f ’(e1 ... eN)) = (and (f e1) ... (f eN)) Tuy nhiên ta không thể định nghĩa every một cách trực giác là áp dụng phép and cho danh sách các giá trị của f : (define (every f L) (apply and (map f L))) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 99 Bởi vì hàm apply không nhận and làm tham đối. Trong Scheme, and không phải là hàm mà là một dạng đặc biệt. Ta định nghĩa every theo cách đệ quy truyền thống như sau : (define (every f L) (if (null? L) #t (and (f (car L)) (every f (cdr L))))) (every even? '(0 2 4 6 8)) −−> #t (every number? '(1 3 a 5)) −−> #f Một cách tương tự, ta xây dựng hàm some để mở rộng phép tuyển lôgic or bằng cách thay thế and bởi or có dạng: (some f ’(e1 ... eN)) = (or (f e1) ... (f eN)) Hàm some như sau : (define (some f L) (if (null? L) #f (or (f (car L)) (some f (cdr L))))) (some number? ’(1 3 a 5)) −−> #t (some odd? ’(0 2 4 6 8)) −−> #f III.12.2. Trao đổi thông điệp giữa các hàm Sau khi định nghĩa các hàm và cài đặt các kiểu dữ liệu, người sử dụng có thể thao tác trực tiếp trên dữ liệu bằng cách sử dụng kỹ thuật lập trình truyền thông điệp (message transmission). Thay vì xem dữ liệu như là một giá trị kiểu đơn vị (một số nguyên, một bộ đôi, một danh sách, v.v ... ), ta có thể xem dữ liệu như là một hàm nhận các thông điệp và thực hiện tính toán tuỳ thuộc vào thông điệp đã nhận. Người ta gọi đây là hàm bẻ ghi (switch function). Những hàm thấy được từ bên ngoài chỉ còn là một lời gọi với một thông điệp đặc biệt. Ta xét lại ví dụ về xử lý các số hữu tỷ ở chương trước. Ta đã khai báo các hàm tạo số hữu tỷ, xác định tử số và mẫu số như sau : functions create-rat : integer × integer → rational numer : rational → integer denom : rational → integer Bây giờ ta định nghĩa lại hàm create-rat có dạng như sau : create-rat : (integer × integer) → (symbol → Integer) Hàm create-rat sẽ tạo ra một hàm nhận vào một thông điệp (kiểu ký hiệu) để trả về một số nguyên, tuỳ theo nội dung thông điệp cho biết đó là tử số hay mẫu số : (define (create-rat x y) ; precondition: y ≠ 0 (define g (gcd x y)) ; gcd là ước số chung lớn nhất của x, y LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 100 (define N (quotient x g)) (define D (quotient y g)) (lambda (message) (cond ((eq? message ’numerator) N) ((eq? message ’denominator) D) (else (error ”unknown message” message))))) ((create-rat 9 15) ’numerator) --> 3 ((create-rat 9 15) ’denominator) --> 5 ((create-rat 9 15) ’denom) --> *** Error: "unknown message" (denom) (create-rat 9 15) --> *** Error: ’#{Procedure 6700 (unnamed in create-rat)} Ta tiếp tục định nghĩa hai hàm numer và denom sẽ gọi đến hàm create-rat : ; numer : (integer × integer) → integer (define (numer R) (R ’numerator)) ; denom : (integer × integer) → integer (define (denom R) (R ’denominator)) (numer (create-rat 9 15)) --> 3 (denom (create-rat 9 15)) --> 5 Với cách xây dựng các hàm xử lý các số hữu tỷ trên đây, người sử dụng chỉ có thể gọi đến một hàm nhờ một thông điệp message : lỗi sai do một lời gọi hàm nào đó, vô tình hay cố ý, đều không thể xảy ra. Trong trường hợp một thông điệp cần các tham đối bổ sung, hàm bẻ ghi sẽ dẫn về một hàm cần phải thực hiện với những tham đối này. Nếu cần thêm một bộ kiểm tra =rat, chỉ cần thêm mệnh đề sau đây vào điều kiện kiểm tra message của hàm create-rat (trước else) trên đây : ((eq? message ’=rational) (lambda(R) (= (* N (denom R)) (* D (numer R))))) Lúc này, ta có thể viết hàm =rat trả về một hàm một tham đối là số hữu tỷ cần so sánh như sau : (define (=rat R1 R2) ((R1 ’=rational) R2)) ; áp dụng hàm trả về với R2 (=rat (create-rat 1 3) (create-rat 1 3)) --> #t (=rat (create-rat 2 3) (create-rat 3 2)) --> #f Kỹ thuật lập trình xem dữ liệu như là một hàm nhận các thông điệp để thực hiện tính toán thường khó sử dụng, đòi hỏi người lập trình phải quản lý tốt ý đồ xử lý theo nội dung thông điệp. Tất cả những gì là dữ liệu đều có thể tạo ra hàm nhờ lambda nhưng rất khó nhận biết được những thông điệp nào sẽ thoả mãn hàm. Chẳng hạn sau đây là một ví dụ sử dụng bộ đôi nhưng thay đổi hai hàm car là cdr : LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 101 (define (cons x y) (lambda (m) (cond ((eq? m ’car) x) ((eq? m ’cdr) y) (else (error "unknown message"))))) (define (car D) (D ’car)) (define (cdr D) (D ’cdr)) (cdr (cons ’tom ’jerry)) --> ’jerry (car (cons '’tom '’jerry)) --> ’tom (car ’(1 2 3)) --> ERROR: attempt to call a non-procedure III.12.3. Tổ hợp các hàm Từ khái niệm hàm bậc cao, ta có thể định nghĩa các hàm tổ hợp (function composition) như sau : ; gºf : (T1 → T2) → T3 Hoặc tổ hợp trực tiếp ngay trong tên hàm : (define (compofg x ) (g (f x)) chẳng hạn : (define (cacddddr L) (car (cddddr L))) (cacddddr ’(a b c d e f)) −−>’e Hoặc sử dụng lambda để tạo ra dạng một «lời hứa» : (define (compos g f) (lambda (x) (g (f x)))) chẳng hạn : ((compos car cddddr) ’(a b c d e f g )) −−> ’e (define fifth (compos car cddddr)) (fifth ’(a b c d e f g )) −−> ’e Nhờ khái niệm bậc của hàm, nhiều sai sót có thể được phát hiện. Giả sử ta xét các hàm map và cdr làm việc với dữ liệu kiểu danh sách : map : (T1 → T2) × List(T1) → List(T2) cdr : List(T) → List(T) Nếu áp dụng hàm map là hàm bậc 2 có cdr làm tham đối sẽ gây ra lỗi : (map cdr (list 1 2 3)) --> ERROR: cdr: Wrong type in arg1 1 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 102 Trong định nghĩa hàm cdr, danh sách có kiểu List(T), nên danh sách (1 2 3) phải có kiểu List(Integer). Như vậy, để áp dụng được hàm map, cần phải có : T1 = List(T) = Integer nhưng điều này là không thể xảy ra. Tương tự, từ định nghĩa hàm sau đây : f : (Number → T1) → T2 ta định nghĩa hàm : (define (f g) (g 2)) thì lời gọi sau đây là sai : (f f) --> ERROR: Wrong type to apply: 2 Tuy nhiên những lời gọi sau đây lại cho kết quả đúng : (f list) --> '(2) ; tạo danh sách một phần tử (f sqrt) --> 1.41421 ; tính căn bậc hai một số nguyên Ví dụ sau là một định nghĩa hàm sử dụng một hàm khác làm tham đối nhưng thực tế, tham đối này chẳng đóng vai trò gì trong việc tính toán ở thân hàm, chỉ có mặt cho «phải phép» xét về mặt cú pháp : (define (f g n) (if (= n 0) 1 (* n (g g (- n 1))))) (define (mystery n) (f f n)) (mystery 5) --> 120 (f f 5) --> 120 Người đọc có thể nhìn nhận ra ngay mystery là hàm tính giai thừa ! Xét về phép toán, định nghĩa trên tỏ ra hợp lý (tính đúng giai thừa). Tuy nhiên, mọi ngôn ngữ có định kiểu mạnh sẽ từ chối định nghĩa này, vi không thể xác định được bậc của hàm f và vai trò của nó trong thân hàm. Một cách tương tự, người đọc có nhận xét gì khi thay đổi lại định nghĩa hàm tính giai thừa như sau : (define (fac g h n) (if (= n 0) 1 (* n (h h h (- n 1))))) Có thể thay đổi dòng cuối cùng thành (g g g ... ) ? III.12.4. Các hàm có số lượng tham đối bất kỳ Khi gọi thực hiện một hàm, bộ diễn dịch Scheme đặt tương ứng các tham đối hình thức với các tham đối thực sự. Sau đây là các dạng định nghĩa hàm có nhiều tham đối tuỳ ý và dạng sử dụng phép tính lambda tương đương. Dạng định nghĩa 1 : (define (f x y z) ... ) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 103 tương đương với : (define f (lambda (x y z) ... ) Ví dụ với lời gọi : (f 1 (+ 1 2) 4) các tham đối hình thức lần lượt được nhận giá trị : x=1, y=3, z=4. Dạng định nghĩa 2 : (define (g . L) ... ) (chú ý g là tên hàm, có dấu cách trước và sau dấu chấm) tương đương với : (define g (lambda L ... )) Ví dụ với lời gọi : (g 1 2 3 4 5) tham đối hình thức là danh sách L được lấy giá trị L = ’(1 2 3 4 5). Dạng định nghĩa 3 : (define (h x y . z) ... ) tương đương với : (define h (lambda (x y . z) ... ) Ví dụ với lời gọi : (h 1 2 3 4) các tham đối hình thức được lấy giá trị như sau : ((x y . z) được so sánh với (1 2 3 4), từ đó, x=1, y=2, z=(3 4) Trong 3 dạng định nghĩa trên đây, hàm f thừa nhận đúng 3 tham đối, hàm g có số lượng tham đối tuỳ ý, hàm h phải có tối thiểu 2 tham đối. Ta có thể dễ dàng định nghĩa hàm list theo dạng 2 : (define (list . L) L) (list 1 2 3 4 5 6 7 8 9 0) --> ’(1 2 3 4 5 7 8 9 0) Ta có thể mở rộng một hàm hai tham đối để định nghĩa thành hàm có nhiều tham đối. Ví dụ, từ hàm cộng + là phép toán hai ngôi, ta định nghĩa hàm add để cộng dồn các phần tử của tham đối là một dãy số nguyên tuỳ ý : (define (add . L) ; L : List(Number) (define (add-bis L R) (if (null? L) R (add-bis (cdr L) (+ (car L) R)))) (add-bis L 0)) (add 2 3 4 5) --> 14 Áp dụng hàm apply, hàm add có thể định nghĩa theo cách khác như sau : (define (add . L) (if (null? L) 0 (+ (car L) (apply add (cdr L ))))) (add 1 2 3 4 5) --> 15 (define L ’(1 2 3 4 5)) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 104 (apply add L) --> 15 Một cách tổng quát, các dạng định nghĩa 2 và 3 có thể viết dưới dạng : (define (f v0 v1 . . vn- 1 .vN) s) tương đương với dạng lambda : (define (f) (lambda (L) s)) trong đó thân hàm s là một biểu thức, L là một danh sách các đối tuỳ ý. III.13. Một số ví dụ III.13.1. Phương pháp xấp xỉ liên tiếp Nhiều khi, ta cần giải phương trình có dạng : x = f (x) (1) trong đó f là một hàm có biến số x. Chẳng hạn để tìm giá trị x từ phương trình : x2 = 2 ta có thể viết lại dưới dạng phương trình (1) : x = (x2 + 2)/2x (2) Để giải phương trình (2), ta sử dụng phương pháp xấp xỉ liên tiếp như sau : x0 = c xn+1 = (xn2 + 2)/2xn trong đó c là một giá trị nào đó để khởi động quá trình lặp. Nếu viết lại các phương trình trên theo dạng (1) và đặt hằng c = f (xo), ta nhận được : x0 = f (xo) (3) xn+1 = f(xn) Như vậy, lời giải tìm nghiệm x từ phương trình (1) là tìm gíới hạn của dãy { xn} theo (3). Trong toán học, người ta phải chứng minh tính hội tụ của dãy để nhận được x = f(x). Áp dụng phương pháp xấp xỉ liên tiếp, ta có thể «giải» hay giải thích cách dùng phép đệ quy tính n! : fac(n) = 1, với n ≤ 0 fac(n) = n * fac(n-1) Từ cách tính lặp các giá trị { xn}, ta xây dựng hàm xấp xỉ liên tiếp như sau : (define (n-iter f x x0) (if (zero? n) x0 (f (n-iter f (- n 1) x0)))) Ví dụ 1 : tính 2 nhờ phương pháp xấp xỉ liên tiếp 1 2 xx x = + với x0 = 1 : (n-iter (lambda (x) (+ (/ x 2) (/ 1. 0 x))) 10 1) --> 1. 41421 Ví dụ 2 : Tính gần đúng x = sin (2x) : (n-inter (lambda (x) (sin (* 2 x))) 10 1) --> 0.948362 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 105 III.13.2. Tạo thủ tục định dạng Sau đây là một ví dụ tự tạo một thủ tục định dạng format các kết quả đưa ra. Thủ tục hoạt động tương tự Common Lisp có dạng như sau : (define (format format-str . L-args) trong đó, format-str là chuỗi định dạng, còn L-args là các biểu thức tham đối (số lượng tuỳ ý) được đưa ra theo cách quy ước trong chuỗi định dạng tương ứng. Chuỗi định dạng đưa ra mọi ký tự có mặt trong đó, trừ ra các ký tự có đặt trước một ký tự đặc biệt ^ được quy ước như sau : ^s hoặc ^S chỉ vị trí để write đưa ra giá trị tham đối tương ứng ^a hoặc ^A chỉ vị trí để display đưa ra giá trị tham đối tương ứng ^% nhảy qua dòng mới ^^ in ký tự ^ Ví dụ : (format "Display ^^ with the format:^% x = ^s" (+ 1 2)) --> Display ^ with the format: x = 3 (format "sin ^s = ^s^%" (/ 3.141592 2) (sin (/ 3.141592 4))) --> sin 1.5708 = 0.707107 Thủ tục format-str không trả về giá trị mà tuỳ theo nội dung chuỗi định dạng để đưa ra kết quả. Cách hoạt động đơn giản như sau : thủ tục duyệt chuỗi định dạng và đưa ra mọi ký tự không đặt trước một ký tự đặc biệt ^. Khi gặp ^, thủ tục sẽ xử lý lần lượt từng trường hợp bởi case. Tham số i trong hàm bổ trợ format-to chỉ định vị trí của ký tự hiện hành. (define (format str . L) (let ((len (string-length str))) (letrec ((format-to (lambda (i L) (if (= i len) (newline) ; 'indefinite (let ((c (string-ref str i))) (if (eq? c #\^) (case (string-ref str (+ 1 i)) ((#\a #\A) (display (car L)) (format-to (+ i 2) (cdr L))) ((#\s #\S) (write (car L)) (format-to (+ i 2) (cdr L))) ((#\%) (newline) (format-to (+ i 2) L)) ((#\^) (display #\^) (format-to (+ i 2) L)) (else (display "unknown character"))) (begin (display c) (format-to (+ i 1) L)))))))) (format-to 0 L)))) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 106 III.13.3. Xử lý đa thức 1. Định nghĩa đa thức Ta xét các đa thức (polynomial) biến x hệ số thực. Mỗi đa thức là tổng hữu hạn các đơn thức (monomial). Mỗi đơn thức có thể là 0 hoặc một biểu thức dạng : axn với a là hệ số thực và n là bậc của x, n nguyên dương và a ≠ 0. Khi n = 0, đơn thức ax0 trở thành hằng a. Đơn thức 0 không có bậc, đôi khi người ta nói bậc của nó là -∞. Ví dụ : 9x4+ 7x5 + -10+ -7x5 +27x là một đa thức của x. Lúc này dấu cộng có vai trò phân cách các đơn thức. Ta chưa định nghĩa phép cộng trên đa thức, tuy nhiên một cách trực giác, ta có thể rút gọn đa thức thành : 9x4 + -10 +27x Để xử lý các đa thức trong Scheme, trước hết ta cần đưa ra một cách biễu diễn đa thức thống nhất. Ta đã biết rằng phép cộng các đơn thức có cùng bậc theo nguyên tắc như sau : axn +bxn = o nếu a+b = 0 axn +bxn = (a+b)xn nếu không Bằng cách cộng tất cả các đơn thức cùng bậc và sắp xếp một đa thức theo bậc giảm dần, ta nhận được cách biễu diễn chính tắc (canonical) cho các đa thức như sau : apxp + ... +aixi Đối với một đa thức khác 0, đơn thức có bậc cao nhất được gọi là đơn thức trội (dominant), và bậc của nó là bậc của đa thức, hệ số của nó là hệ số định hướng (director) hay hệ số trội. Ví dụ đa thức trên đây có bậc là 4 và được viết lại là : 9x4 +27x + -10 Người ta định nghĩa phép cộng hai đa thức : (apxp + ... +aixi) + (aqxq + ... +ajxj) bằng cách cộng các đơn thức cùng bậc và đặt các đơn thức dưới dạng chính tắc, ta nhận được đa thức tổng. 2. Biễu diễn đa thức Có hai phương pháp biễu diễn các đa thức trong Scheme : 1. Biễu diễn đầy đủ (full representation) Theo phương pháp này, người ta tạo một danh sách gồm tất cả các hệ số (bằng 0 hoặc khác 0), bắt đầu từ hệ số trội. Ví dụ đa thức 9x4 +27x + -10 được biễu diễn bởi danh sách : ’(9 0 0 27 -10) 2. Biễu diễn hổng (hollow representation) Sử dụng một danh sách các đơn thức khác 0 theo bậc giảm dần, mỗi đơn thức được xác định bởi bậc và hệ số tương ứng. Nghĩa là mọi đa thức P, khác 0, đều có dạng : P = cxd + Q với cxd là đơn thức trội có bậc d và hệ số d, Q là đa thức còn lại có bậc thấp hơn. Sau đây ta chọn xét phương pháp biễu diễn hổng các đa thức. Việc sử dụng nguyên tắc phân tách một cách chính tắc một đa thức thành một đơn thức trội và một đa thức còn lại có bậc thấp hơn cho phép định nghĩa đa thức như là một cấu trúc dữ liệu. Giả thiết từ lúc này trở đi, mọi đa thức đều có cùng biến x và các hàm xử lý lấy tên với tiếp đầu ngữ poly. LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 107 Trước tiên, ta tiến hành các thao tác xử lý đa thức mà chưa nêu ra cách biểu diễn hổng trong Scheme.Ta gọi zero-poly là đa thức 0, còn cons-poly là hàm tạo đa thức khác 0, có ba tham biến. Hai tham biến thứ nhất và thứ hai định nghĩa đơn thức trội gồm hệ số và bậc của nó, tham biến thứ ba chỉ định đa thức còn lại có bậc thấp hơn (là đa thức đã cho nhưng đã bỏ đi đơn thức có bậc cao nhất) : poly = zero-poly hoặc : poly = (cons-poly coeff degree poly) với điều kiện coeff ≠ 0 Các hàm tiếp cận đến các thành phần đa thức là degree-poly, coeff-domin, remain-poly thõa mãn các quan hệ sau : (coeff-domin (cons-poly coeff degree poly)) = coeff (degree-poly (cons-poly coeff degree poly)) = degree (remain-poly (cons-poly coeff degree poly)) = poly Để phân biệt các đa thức 0, xây dựng vị từ zero-poly? thõa mãn quan hệ : (zero-poly? zero-poly) = #t (zero-poly? (cons-poly coeff degree poly)) = #f Để duy trì quan điểm trừu tượng hoá vấn đề, tạm thời ta chưa nêu cụ thể cách xây dựng các hàm tạo mới đa thức và các hàm tiếp cận đến các thành phần của đa thức vừa trình bày trên đây mà tiếp tục sử dụng chúng trong các phép xử lý dưới đây. 3. Xử lý đa thức Cho trước đa thức P = cxd + Q, các phép xử lý trên P bao gồm : • Nhân đa thức với một hằng số a*P • So sánh hai đa thức P1 ? P2 • Cộng hai đa thức P1 + P2 • Nhân hai đa thức P1 * P2 1. Nhân đa thức với một hằng số Để nhân hằng số a với đa thức P, lấy a nhân với hệ số trội rồi sau đó lấy a nhân với đa thức còn lại : (define (mult-scalar-poly a P) (cond ((zero? a) zero-poly) ; xử lý hệ số =0 ((zero-poly? P) zero-poly) ; xử lý đa thức 0 (else (let ((d (degree-poly)) (c (coeff-domin P)) (Q (remain-poly))) (cons-poly d (* c a) (mult-scalar-poly a Q)))))) 2. So sánh hai đa thức So sánh hai đa thức bằng cách so sánh hai đơn thức trội, sau đó tiếp tục so sánh hai đa thức còn lại : (define (equal-poly? P1 P2) (cond ; xử lý đa thức 0 ((zero-poly? P1) (zero-poly? P2)) ((zero-poly? P2) (zero-poly? P1)) (else; xử lý đa thức ≠ 0 LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 108 (let ((d1 (degree-poly P1)) (d2 (degree-poly P2)) (c1 (coeff-domin P1)) (c2 (coeff-domin P2)) (Q1 (remain-poly P1)) (Q2 (remain-poly P2))) ; hoặc so sánh hai đa thức còn lại trước tiên theo bậc và hệ số (and (= d1 d2) (= c1 c2) ; và so sánh hai đa thức còn lại của hai đa thức còn lại (equal-poly? Q1 Q2)))))) 3. Phép cộng đa thức Khi cộng hai đa thức P1 và P2 cần phân biệt hai trường hợp : • Nếu các đa thức P1 và P2 có cùng bậc, chỉ việc cộng các đơn thức trội và xem xét trường hợp chúng có triệt tiêu lẫn nhau không. • Nếu các đa thức P1 và P2 không có cùng bậc, tìm đa thức có đơn thức bậc cao hơn, sau đó thực hiện phép cộng các đa thức còn lại. (define (add-poly P1 P2) (cond ; xử lý các đa thức 0 ((zero-poly? P1) P2) ((zero-poly? P2) P1) ; xử lý các đa thức ≠ 0 (else (let ((d1 (degree-poly P1)) (d2 (degree-poly P2)) (c1 (coeff-domin P1)) (c2 (coeff-domin P2)) (Q1 (remain-poly P1)) (Q2 (remain-poly P2))) (cond ((= d1 d2) ; hai đa thức có cùng bậc (let ((c (+ c1 c2))) (if (zero? c) (add-poly Q1 Q2) (cons-poly d1 c (add-poly Q1 Q2))))) ((< d1 d2) ; hai đa thức không có cùng bậc (cons-poly d2 c2 (add-poly P1 Q2))) (else (cons-poly d1 c1 (add-poly Q1 P2)))))))) 4. Phép nhân hai đa thức Giả sử : P1 = (c1xd1 + Q1) và P2 = (c2xd2 + Q2) khi đó, kết quả phép nhân hai đa thức P1 và P2 là : (c1xd1 + Q1) ∗ (c2xd2 + Q2) = c1∗c2 x(d1 + d2) + (c1xd1 + Q1) ∗ Q2 + Q1 ∗ (c2xd2 + Q2) Hàm mul-poly được xây dựng như sau : LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 109 (define (mul-poly P1 P2) (cond ((zero-poly? P1) zero-poly) ((zero-poly? P2) zero-poly) (else (let ((d1 (degree-poly P1)) (d2 (degree-poly P2)) (c1 (coeff-domin P1)) (c2 (coeff-domin P2)) (Q1 (remain-poly P1)) (Q2 (remain-poly P2))) (if (zero-poly? Q1) ; Q1 = 0 (cons-poly (+ d1 d2) (* c1 c2) (mul-poly P1 Q2)) ; Q1 ≠ 0 (add-poly (add-poly (mul-poly (cons-poly d1 c1 zero-poly) P2) (mul-poly Q1 Q2)) (mul-poly Q1 P2))))))) 5. Biễu diễn trong một đa thức Bây giờ ta tìm cách biểu diễn hổng các đa thức trong Scheme : mỗi đa thức được biễu diễn bởi một danh sách các đơn thức khác 0 theo thứ tự bậc giảm dần. Ta chọn cách biễu diễn mỗi đơn thức bởi một bộ đôi như sau : (degree . coefficient) Như vậy mỗi đa thức được biễu diễn bởi một danh sách kết hợp alist. Chẳng hạn đa thức : 9x4 +27x + -10 được biễu diễn bởi alist : ((4. 3) (1. 20) (0. -10)) Sau đây ta xây dựng các hàm tạo mới đa thức và các hàm tiếp cận đến các thành phần của đa thức như sau : (define (cons-poly degree coeff Q) (cond ((zero? coeff) (display ”Error: the coefficient can’t be zero !”)) ((zero-poly? Q) (list (cons degree coeff))) (else (cons (cons degree coeff) Q)))) (define degree-poly caar) (define coeff-domin cdar) (define (remain-poly Q) (if (null? (cdr Q)) zero-poly (cdr Q))) LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 110 Hình 0.14. Biễu diễn đơn thức bởi bộ đôi. Đối với đa thức 0 ta có thể biễu diễn tùy ý, Chẳng hạn : (define zero-poly 0) (define (zero-poly? P) (and (number? P) (zero? P))) 6. Đưa ra đa thức Để nhìn thấy các đa thức trên màn hình, hay trên giấy in, ta có thể biễu diễn chúng nhờ các kí tự ASCII thông dụng. Chẳng hạn đơn thức axn sẽ được biễu diễn dạng ax^n. Sau đây ta xây dựng hàm print-poly để đưa ra một đa thức. Hàm này đưa ra liên tiếp các đơn thức nhờ gọi đến hàm print-mono. Trong trường hợp bậc một đơn thức là 1 thì không in ra dạng ax^1 mà in ra x (đảm bảo tính thẩm mỹ) : (define (print-poly P) (if (zero-poly? P) zero-poly (let ((c (coeff-domin P)) (d (degree-poly P)) (Q (remain-poly P))) (print-mono d c) (if (not (zero-poly? Q)) (begin (display ”+”) (print-poly Q)))))) (define (print-mono degree coeff) (cond ((zero? degree) (display coeff)) ((=1 degree) (display coeff) (display “x”)) (else (display coeff) (display ”x”) (display ”^”) (display degree)))) (define P1 (cons-poly 2 9 (cons-poly 1 27 (cons-poly 0 -10 0)))) P1 --> ’((2 . 9) (1 . 27) (0 . -10)) (print-poly P1) --> 9x^2+27x+-10 (add-poly P1 P1) --> ’((2 . 18) (1 . 54) (0 . -20)) (print-poly (add-poly P1 P1)) --> 18x^2+54x+-20 (print-poly (mul-poly P1 P1)) --> 81x^4+486x^3+1278x^2+-1350x+400 Những xử lý ký hiệu trên các đa thức mà ta vừa trình bày trên đây thường được ứng dụng trong các hệ thống tính toán hình thức (formal calculus). coefficientdegree car cdr LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 111 III.13.4. Thuật toán quay lui Khi giải những bài toán tổ hợp (combinatorial problems) hay bài toán trò chơi đố chữ (puzzle) người ta thường không có thuật toán trực tiếp để tìm ra lời giải, mà thường áp dụng thuật toán «thử sai» (try and error). Ý tưởng của thuật toán là người ta phải thử liên tiếp các phương án, hoặc dẫn đến thành công và kết thúc, hoặc khi thất bại thì phải quay lui (backtracking) trở lại phương án đã lựa chọn trước đó để tiếp tục quá trình. 1. Bài toán tám quân hậu Một ví dụ cổ điển là bài toán tám quân hậu (đã xét ở chương 1). Yêu cầu đặt 8 quân hậu lên bàn cờ vua 8×8 ô lúc đầu không chứa quân nào sao cho các quân hậu không ăn được lẫn nhau. Lời giải được tiến hành dần dần như sau : Giả sử gọi quân hậu là Q, đầu tiên đặt Q tại cột thứ nhất, sau đó, tìm cách đặt Q ở cột thứ hai sao cho không bị Q ở cột trước ăn và cứ thế tiếp tục cho các cột tiếp theo. Có thể tại một sự lựa chọn nào đó không cho phép đặt được Q tiếp theo (tại cột j). Khi đó, người ta phải xem lại sự lựa chọn cuối cùng trước sự thất bại đó (ở cột kế trước j-1) để bắt đầu lại. Nếu tất cả khả năng cho sự lựa chọn cuối cùng đều thất bại, người ta lại phải quay lui đến sự lựa chọn trước lựa chọn cuối cùng (ở cột j-2), v.v... Kỹ thuật quay lui thường được minh hoạ bởi một cây mà mỗi nút trong là một trạng thái tìm kiếm lời giải và một đường đi từ gốc đến một lá (nút ngoài) nào đó có thể là một lời giải của bài toán đã cho. Xuất phát từ nút gốc của cây, là trạng thái đầu, có thể tiếp cận đến các con của nó là các lựa chọn có thể để đạt đến trạng thái tiếp theo. Khi đi đến một nút cho biết thất bại, người ta phải quay lên nút cha và bắt đầu với nút con chưa được tiếp cận. Nếu như đã được tiếp cận hết các con mà mà vẫn thất bại, người ta lại quay lên nút tổ tiên (cha của nút cha)v.v... Quá trình quay lui đã được giải quyết trong phương pháp tìm kiếm theo chiều sâu trước (depth-first-search algorithm). Hình 0.15. Tìm lời giải trên cây trạng thái. Ý tưởng của thuật toán như sau : Gọi thuật toán depth-first-search với trạng thái đầu (nút gốc) đã biết : • Nếu trạng thái đầu là đích (goal state), kết thúc thành công • Ngược lại, tiếp tục các bước sau cho đến khi thành công hoặc thất bại : a. Từ trạng thái đầu chưa phải là nút thành công, tiếp cận một trạng thái kế tiếp, giả sử gọi là S. Nếu không tiếp cận được trạng thái kế tiếp nào, ghi nhận thất bại. b. Gọi lại thuật toán depth-first-search với S là trạng thái đầu. c. Nếu thành công, kết thúc. Ngược lại, tiếp tục vòng lặp. 2. Tìm kiếm các lời giải Ta định nghĩa hàm a-solution cho phép trừ một trạng thái đã cho, trả về một lời giải kế tiếp trạng thái này hoặc #f nếu thất bại. Nguyên lý hoạt động rất đơn giản như sau : thành công thành công xuất phát LẬP TRÌNH HÀM VÀ LẬP TRÌNH LÔGIC 112 • Nếu là trạng thái cuối cùng (không còn trạng thái kế tiếp), thì đó là một lời giải để trả về, nếu không phải thì trả về #f và xem như thất bại. • Nếu đang ở trạng thái trung gian, liệt kê tất cả các trạng thái kế tiếp và bắt đầu sự lựa chọn một trạng thái kế tiếp chừng nào chưa tìm ra lời giải. Giả thiết ta đã xây dựng được các hàm : hàm followingstates cho phép liệt kê tất cả các trạng thái có thể tiếp cận đến xuất phát từ một trạng thái đã cho, vị từ finalstate? kiểm tra trạng thái cuối cùng, vị từ solution? kiểm tra tính hợp thức của lời giải. Trong hàm a-solution có sử dụng some là dạng or mở rộng (xem III.12.1) : (define (a-solution state) (if (finalstate? state) (if (solution? state) state #f) (some a-solution (followingstates state)))) Trong một số trường hợp, người ta mong muốn nhận được danh sách tất cả các lời giải. Ta xây dựng hàm list-of-solutions bằng cách gộp vào danh sách lần lượt các lời giải tiếp theo có thể tìm được như sau : (define (list-of-solutions state) if (finalstate? state) (if (solution? state) (list state) ’()) (append-map list-of-solutions (followingstates state)))) Cuối cùng, người ta mong muốn nhận được một số lời giải tùy theo yêu cầu của người sử dụng. Ta xây dựng hàm some-solutions dựa theo cách xây dựng hàm a-solution nhưng khi tìm thấy một lời giải, máy yêu cầu người sử dụng trả lời có tiếp tục tìm lời giải khác không. Vị từ other-solution? dùng để duy trì quá trình tìm kiếm. Sau khi đã đưa ra hết các lời giải tìm thấy, hàm trả về #f. (define (some-solutions state) (if (finalstate? state) (if (solution? state) (other-solution? state) #f) (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))))