Kỹ thuật lập trình: Một vài điều cần biết

M t vài k thu t l p trình ậ ậ ộ ỹ

Ngày g i bài: 19/01/2006 ử So luot doc: 1318

t này là l c d ch t ng 10 ″Algorithm Design Techniques″ c a quy n sách ượ ị ủ ể Aho A.V., Hopcroft J.E. và ủ t t Bài vi ch ừ ươ ế n i ti ng ″Data Structure and Algorithms″ c a các tác gi ả ổ ế đ t. Ullman J.D. Tiêu đ do ng ườ i biên so n bài vi ạ ế ự ặ ề

Các b n tr thân m n. ẻ ế ạ

ỹ ộ ạ ẫ ẩ ề ậ ậ ố ớ ề i l ế i gi ể ứ ừ ữ ế ư ệ ẹ

ng hay. Đ c bi ẻ ứ ự ấ ng. Nhi u bài toán khó, đa ườ ậ i n ch a bên trong nh ng thu t ả ạ ẩ Aho A.V., Hopcroft J.E. và Ullman J.D đã ra đ i cách đây 20 năm nh ng ư ả i v n th y r t m i m và ch a đ ng nhi u ý t ọ ạ ẫ ặ ỹ ấ ấ ậ ề ứ ự ờ ưở ề ưở ng nghiên c u và gi ả t T t Quí Mùi, chúng tôi chân tr ng gi ậ i quy t bài toán c a ngày hôm nay. Nhân d p s ớ ạ ướ ệ ế ệ ặ ệ t ng xác đ nh cho ị ị ố t là các ượ ị ủ ế ớ ọ c d ch c a ch ợ ổ ng. Trong khi trình bày thu t toán các tác gi i thi u v i b n đ c, đ c bi ươ ớ ố ượ ả ng c a đ c gi ủ ộ ử ụ ườ ậ ố ớ ạ ầ ể ủ ệ ọ ng này. Trong quá trình biên Tin h c & ọ ả ậ đã s d ng khá nhi u k thu t ỹ ề ớ ữ ầ ệ ọ ế ớ ệ ầ ủ ế ạ t này đ ng c a bài vi ả t. Chúc các b n m t năm m i v i nhi u sáng t o m i, và mong ớ ớ ế ạ ủ ạ c các b n ti p nh n và áp d ng sáng t o ộ ượ ạ ụ ế ẻ Thu t toán, k thu t l p trình luôn là m t đi u bí n và h p d n đ i v i các b n tr , ậ các b n h c sinh và sinh viên đang ng i trên gh nhà tr ạ ọ ồ c l ng ch ng nh không th tìm đ d ng t ượ ờ ưở ạ toán đ n gi n, tuy t đ p đ n không ng . Cu n sách ″Data Structure and Algorithms″ ố ờ ả ơ c a các tác gi ủ đây đ c l gi ờ ớ ng ″M t vài k thu t thi ch t k thu t toán″ ch a đ ng nhi u ý t ộ ươ ế ế toàn b đ nh h ứ ộ ị báo đ c bi ặ b n h c sinh, sinh viên chuyên tin l ạ ọ so n, chúng tôi đã thay đ i chút ít cho phù h p v i đ i t ạ Nhà tr phân tích đánh giá đ ph c t p, đ i v i các b n l n đ u làm quen v i nh ng khái ộ ứ ạ ng gì đ n vi c đ c các ni m này có th hoàn toàn b qua chúng mà không nh h ưở ỏ ph n khác c a bài vi ề r ng nh ng ý t ậ ữ ằ trong công vi c c a mình. ưở ệ ủ

1. Thu t toán Chia đ Tr (Divide & Conquer) ể ậ ị

thu t toán đ c s d ng nhi u nh t, quan tr ng nh t là k thu t ″Chia đ Tr ″. ậ ẽ ượ ử ụ ề ấ ọ ỹ ậ ấ ỏ ơ ệ ờ ừ ậ ể ị i gi ả i ự ệ đó xây d ng thu t toán cho bài toán l n t ng h p. Ví ợ ớ ổ (2) mà các b n đã ế ừ ắ ế ạ ị Có l K thu t này s chia bài toán hi n th i thành N bài toán nh h n, th c hi n l ờ ẽ ỹ cho t ng bài toán nh này và t ự ỏ ộ (1) ho c Tìm ki m Nh phân d cho các thu t toán này là S p x p Tr n ậ ụ đã đ ậ ặ ng trình Tin h c C b n. t trong ch c bi ơ ả ượ ươ ế ọ

ể ậ ộ s có 3 c c A, B, C. Ban đ u t ụ ặ ơ ộ ộ ố ứ ự ọ ớ Đ minh h a rõ h n cho k thu t này chúng ta hãy xét m t ví d quen thu c đó là bài ộ ọ toán ″Tháp Hà N i″. Gi i A đ t m t s đĩa v i th t ầ ạ trên nh d ỹ ả ử i to nh hình v . ẽ ỏ ướ ư

ầ ủ ọ ộ ố ể ử ụ ả ả ắ Yêu c u c a bài toán là chuy n toàn b s đĩa trên sang c c B, trong quá trình chuy n ể c phép s d ng đĩa C, m i l n chuy n đúng 01 đĩa và luôn b o đ m nguyên t c đĩa đ ượ nh n m trên đĩa to trong su t quá trình chuy n. ể ể ỗ ầ ố ỏ ằ

Bài toán

ộ ả ử ỉ ộ ể ả ớ ề ọ ỏ ể

i v i thu t toán ″thông minh″ sau: Gi ậ c v i s l ạ ướ ớ ố ượ i b ồ ạ ướ ồ ế ọ ộ ễ ấ ỏ t là l ẻ c đi v i s l ớ ố ượ ấ ể ề ư ậ ằ ấ ộ s ta đ t 3 c c trên Tháp Hà N i trên có th gi ặ , ta chuy n đĩa nh nh t ấ t i các đ nh c a m t tam giác đ u. T i b ủ ạ ự sang c c bên c nh theo chi u kim đ ng h , t t là ch n, ta th c ẵ ạ hi n m t thao tác b t kỳ nh ng không đ ng đ n cái đĩa nh nh t. Các b n d dàng ệ ạ ụ ki m tra r ng đó là m t thu t toán đúng, tuy nhiên nó r t khó hi u, khó t ng quát sang ổ ể các tr ng h p khác. ườ ợ

ậ ư ộ duy c a thu t toán ″Chia đ Tr ″ đ i v i bài toán Tháp Hà N i ể ỏ ơ ớ c N-1 nh sau: (a) Chuy n N-1 đĩa đ u tiên t nguyên tr ng thái ầ ừ ạ ứ ữ ể ạ ừ ừ C sang B. A sang B và chuy n N-1 đĩa t ừ ứ ầ ệ ể ớ ị ủ C sang B ta có th dùng ể t nhiên ữ ư ậ ự ẽ ươ ư duy nh v y, vi c mô ế ề ớ ớ ả ọ ệ ụ ễ ể ậ Ta hãy th v n d ng t ủ ể ị ố ớ ử ậ ụ A sang B có th chia thành 2 bài toán nh h n v i kích này. Bài toán chuy n N đĩa t ừ ể th A sang C (gi ể ư ướ i A). (b) Chuy n đĩa th N t c a đĩa th N t ể ủ Chú ý r ng khi th c hi n bài toán (b) ph n chuy n N-1 đĩa t ự ằ i hoàn toàn thu t toán c a bài (a) nh ng v i v trí thay đ i gi a A và C và t l ổ ậ ạ ấ ư b qua s có m t c a đĩa th N trong A hay B. V i cách t ỏ ệ ư ứ ặ ủ ph ng thu t toán s t ng đ i khó do nó ph i g i đ qui đ n chính nó nh ng cách làm ố ậ ỏ trên th t là d hi u và cho phép chúng ta áp d ng cho nhi u l p bài toán khác. Chúng ta hãy xét m t vài ví d . ụ ộ

Ví d 1: Bài toán nhân các s t nhiên l n ố ự ụ ớ

nhiên n-bit X và Y. Bài toán nhân 2 s t ố ự ố ự ng ph thông v i đ ph c t p O(n nhiên n-bit (n ch 2)(3). Bây gi ớ ộ ứ ạ ườ ổ ờ ỗ ố ừ ủ ậ ơ ầ c phân tích thành 2 ph n n/2-bit nh sau: ữ Xét bài toán nhân 2 s t chúng ta s ) đã đ ượ ạ ố i bài toán này v i k thu t Chia đ Tr . Ta phân tách m i s X, Y thành 2 s xét l ể ị ạ ẽ ph n, m i ph n n/2 bit. Đ cho đ n gi n ta s luôn xét n là lũy th a c a 2. X, Y s ẽ ẽ ỗ ầ đ ượ c d y trong nhà tr ớ ỹ ể ầ ả ư

X = A | B (X = A2n/2 + B)

Y = C | D

(Y = C2n/2 + D)

Khi đó tích XY s có d ng: ẽ ạ

XY = AC2n + (AD+BC)2n/2 + BD (1)

ứ ự ư ệ ả ẽ ậ ố ể ớ ự ố ớ ộ ớ ố ữ ố c th c hi n v i th i gian ự ữ ố ề ượ ừ ủ ệ ớ ờ D a trên công th c (1) ta có th suy lu n đ n gi n nh sau cho vi c tính tích XY: ơ ệ chúng ta s tính 4 phép nhân v i các s n/2-bit là AC, AD, BC và BD, sau đó th c hi n 3 phép c ng v i các s 2n-bit, cu i cùng là 2 phép chuy n ch s (2 phép nhân v i lũy ể th a c a 2) Các phép c ng và phép chuy n ch s đ u đ O(n), do đó ta thu đ ộ c công th c tính đ ph c t p c a phép toán trên T(n) là: ể ộ ứ ạ ủ ượ ứ

T(1) = 1

T(n) = 4T(n/2) + C.n (C-const)

2) và nh v y ta ch a thu đ

ứ ư ượ ế c k t qu gì m i so ả ớ ng pháp tính t nhà tr (2) Công th c (2) cho ta T(n) = O(n v i ph ớ ườ ươ ư ậ ng ph thông. ổ ừ

Bây gi ta bi n đ i công th c (1) d i d ng: ờ ứ ế ổ ướ ạ

XY = AC2n

+ ((A-B)(D-C) + AC + BD)2n/2 + BD

(2) Công th c (2) m c dù ph c t p h n (1) nh ng chúng có th đ c tính b i: ứ ạ ể ượ ứ ư ặ ơ ở

- 3 phép nhân n/2-bit: AC, BD và (A-B)(D-C).

- 6 phép +,- các s n/2-bit. ố

- 2 phép chuy n ch s (nhân v i lũy th a c a 2). ừ ủ ữ ố ể ớ

Do v y v i cách tính trên ta có công th c sau tính đ ph c t p c a thu t toán này: ộ ứ ạ ủ ứ ậ ậ ớ

T(1) = 1

T(n) = 3T(n/2) + C.n (C-const)

(3) Công th c (3) cho ta ứ

Nh v y ta đã thu đ c m t k t qu m i cho vi c th c hi n phép nhân 2 s t nhiên ư ậ ượ ả ớ ộ ế ố ự ự ệ ệ

n-bit v i thu t toán m nh h n phép nhân bình th ng đã h c trong nhà tr ng (

4).

ậ ạ ớ ơ ườ ọ ườ

Ví d 2: Bài toán t o l ch thi đ u Tennis ạ ị ụ ấ

s c n l p m t l ch thi đ u Tennis cho n = 2 ậ ộ ộ ị ấ ậ ộ

k v n đ ng viên (VĐV). M i v n ỗ ậ ấ ấ

ỗ ầ ậ ị ả ố t n-1 v n đ ng viên khác, m i ngày thi đ u 1 tr n. ậ i thi u ph i có. Chúng ta c n l p l ch thi đ u b ng ằ i v trí (i,j) (hàng i, c t j) ch ra ỉ ị ố ạ ị ế ậ ể ộ ậ ộ Gi ấ ả ử ầ ậ đ ng viên ph i thi đ u v i l n l ớ ầ ượ ả ộ Nh v y n-1 là s ngày thi đ u t ấ ố ư ậ t l p ma tr n có n hàng, n-1 c t. Giá tr s t cách thi v n đ ng viên c n thi đ u v i v n đ ng viên i trong ngày th j. ớ ậ ộ ậ ứ ấ ầ ộ

ỹ ử ụ ố ậ ậ ị ử ấ i g i đ qui chúng ta đ a bài toán v tr ể ị ệ ử ụ ờ ọ ệ ề ườ ư S d ng k thu t Chia đ Tr , chúng ta hãy l p l ch thi đ u cho n a (n/2) s v n đ ng ộ ậ ợ ng h p viên đ u tiên. B ng vi c s d ng l ằ ầ ch có 2 VĐV. ỉ

i đ u tiên c a danh ng h p n=8. L ch thi đ u cho 4 ng ị ấ ọ ằ ế ầ ử ườ ầ ướ ị ế ủ ỗ ậ ấ ị ớ ố ệ ể t v i các VĐV s cao vào ngày 4. Các ngày còn l ầ ấ ế ố ấ ầ ượ ớ ị ớ ố ứ ự ế i thu đ ạ cao. Quá trình đi n s ườ ạ Chúng ta minh h a b ng tr ợ ườ ủ sách chi m n a trái trên c a ma tr n (4 hàng, 3 c t). Ph n n a trái d i (4 hàng, 3 c t) ộ ộ ủ ậ ử 5 đ n 8). Ph n này thu đ c a ma tr n là l ch thi đ u c a 4 VĐV còn l i (t n a c t ượ ừ ử ậ ầ ạ ừ ấ ủ ủ ng ng c a ma tr n. Đ đi n n t các trái trên b ng cách c ng 4 vào m i ph n t t ằ ể ề ầ ử ươ ứ ộ ố ậ ớ ố ph n còn l i c a ma tr n chúng ta ch c n xác đ nh l ch thi đ u gi a các VĐV v i s ữ ị ỉ ầ ạ ủ th p (≤n/2) v i các VĐV v i s cao (≥n/2). Đ làm vi c này chúng ta x p các VĐV t ừ ớ c t 1 đ n n/2 đ u l n l ượ ừ ề ố ngày 4 b ng cách hoán v vòng quanh các VĐV v i s th t ằ ợ ổ ng h p t ng c mô t đ ượ quát n=2k b t kỳ. trong hình 2. Các b n có th t ng quát quá trình này cho tr ể ổ ả ấ

2.Thu t toán Qui Ho ch Đ ng (Dynamic Programming) ộ ậ ạ

ầ ấ ứ ạ ậ cũng có th chia nh bài toán ể ầ ỏ đó tìm ra l Trong ph n trên chúng ta đã th y s c m nh c a k thu t Chia đ Tr b ng cách chia ủ ỹ nh bài toán c n làm. Tuy nhiên không ph i bao gi ả ờ i gi thành các bài toán con và t ả ủ ể ị ằ ỏ i c a bài toán l n. Trong các tr ớ ợ ng h p ườ ừ ờ

ể ề ặ ỏ nh v y, m c dù chúng ta v n có th chia nh bài toán thành nhi u bài toán con, nh ng th i gian thu đ ố ờ c s tăng theo s mũ và thu t toán tr nên vô giá tr . ị ẫ ượ ẽ ư ậ ư ậ ở

, vi c chia thành các bài toán con th ế ề ầ i quy t các bài toán con, các b n s ỏ ng ch chi m th i gian là đa th c. ứ ườ ờ ỉ c l p l i nhi u l n trong quá trình tìm ẽ ượ ặ ạ ạ ẽ ế ả ỗ ỏ i này đ tra c u v sau m i khi c n đ n. Công vi c này s đòi h i ầ ộ ấ ể ệ ế ẽ ỗ Trên th c t ệ ự ế ng h p này m t bài toán con s đ Trong tr ợ ườ i. Đ kh i m t th i gian m i khi gi ki m l i gi ờ ể ả ờ ế i gi l u tr các l ứ ề ả ờ ữ ư đ ph c t p thu t toán là đa th c. ứ ậ ộ ứ ạ

ơ ơ i c a các bài toán con l ộ ả ủ ạ ầ i ờ ề i gi ữ ấ ả ạ t cho l ượ ầ ệ t c các l t i nhi u l n v ề ầ ả ủ i c a i gi ờ Qui ho chạ lý thuy t đi u khi n. qui ho ch đ ng đ Có m t cách làm còn đ n gi n h n cách đã nêu trên. Chúng ta s l u gi ẽ ư ả c dùng l i không c n bi gi ế ằ sau hay không, không quan tâm đ n vi c các l ế ờ ế bài toán chính c a chúng ta hay không. Cách làm nh v y có tên g i là ủ đ ngộ . B n thân t ả t r ng chúng có đ i này có c n thi ả ọ ư ậ ể ế c l y t ượ ấ ừ ừ ề ạ ộ

ự ế ủ ạ ộ ư t đi n các thông s vào c a thu t toán qui ho ch đ ng không th ng nh t nh ng đi u ề ố chúng là có m t cái b ng và chúng ta c n l n l ả ấ ề Cách cài đ t th c t ậ ặ ố chung nh t ầ ầ ượ ộ ấ ở cái b ng này. Đ minh h a chúng ta hãy xét m t vài ví d . ụ ả ể ọ ộ

Ví d 3: Trò ch i Tán th ụ ơ ủ(5)

ầ ự ườ ệ ị ớ i th ng cu c. Trên th c t ấ ộ s có hai tán th A, B c n đ u tr c di n v i nhau, qui đ nh chung là ng ủ c n ván s là ng ườ ng giá tr n = 4. Gi ị ả ử ắ ẽ ạ th ự ế ườ ắ ấ ả ỗ ắ ữ ầ ắ ầ ẽ ắ ấ ắ ữ ắ ầ ộ ớ ị Gi i th ng ắ ả ử s hai tán tr ướ th A, B là m nh ngang nhau và do đó sác xu t th ng, thua trong m i ván là 50/50. Gi ủ s P(i,j) là sác xu t sao cho A c n th ng thêm i ván n a , B c n th ng thêm j ván n a ữ ử thì A s ch c ch n th ng chung cu c. Chúng ta c n tính nh ng giá tr P(i,j) này v i i, j b t kỳ. ấ

ồ ắ ế ế ứ ấ ể ậ ớ ứ ồ ộ ự ế ế ế ắ ế ế ắ ở ẽ ộ ẽ ấ ể ắ ế ứ ạ ồ ể ắ N u i=0, j>0, t c là A đã th ng r i và do đó P(0,j)=1. N u i>0, j=0, t c là B đã th ng và A đã thua r i, do đó P(i,0)=0. V i i, j > 0 ta có nh n xét sau: sác xu t đ A th ng ắ chung cu c d a vào ván ti p theo A th ng hay thua. N u ván ti p theo A th ng, khi đó ắ ván ti p theo thì sác xu t đ A sác xu t đ A th ng s là P(i-1,j), còn n u A thua ấ ể v n th ng chung cu c s là P(i,j-1). Vì ván ti p theo kh năng A th ng thua là 50/50 ắ ả ẫ nên ta có công th c P(i,j) = (P(i-1,j)+P(i,j-1))/2. Tóm l i ta có công th c truy h i sau đ ứ tính P(i,j).

ừ ễ ớ ượ ồ ủ ộ ứ ạ c công th c truy h i c a đ ph c t p ứ T công th c (4) v i i+j=n ta d dàng tính đ ứ tính toán T(n) nh sau: ư

T(1) = C(C-const)

T(n) = 2T(n-1) + D (D-const)

ư ậ ệ ố ẽ

ộ ế ể ể ủ ỉ ứ ệ ử ụ ệ i c a công vi c tính toán này. (Gi ự ự ủ i h n d i h n d

n). Nh v y vi c tính toán các h s P(i,j) s có đ ph c ộ ứ ả ỹ ậ ệ ế ơ i h n trên c a tính toán, đ hi u rõ h n ớ ạ i t ″ th c s c a vi c s d ng đ qui tính toán theo công th c(4) chúng ta s th ẽ ử ứ ớ ạ ướ ủ ộ ứ ạ i c a đ ph c t p

ệ c T(n) = O(2 (5) Ta tính đ ệ ượ t p tăng theo s mũ c a n n u tính toán b ng k thu t đ qui và đây là m t k t qu ằ ủ ố ạ r t l n. Tuy nhiên công th c trên ch cho ta gi ấ ớ s ″t ự ồ ệ tính toán gi đ ượ ớ ạ ướ ủ c ký hi u là big-omega: W). ệ

c giá tr này chúng ta s tính s l n g i hàm P khi th c hi n đ qui cách ể ượ ự ẽ ệ ọ ị ệ ỹ ẽ ợ ố ầ ớ ứ ứ c a h s t ế h p là ng t Đ tính đ tính P(i,j) theo công th c (4). Công th c (4) v i i+j=n n u xem xét k s g i ý cho chúng ta v m t đ ng th c t ề ộ ẳ ự ủ ệ ố ổ ợ ứ ươ

h p ch p i t n ph n t t ầ ử ừ ậ ầ ử ố ừ ậ (t T nh n xét trên d dàng suy ra r ng s l n g i hàm P trong l , s cách ch n ra i ph n t ọ ố ầ ổ ợ ừ ậ ầ ử t p h p ban đ u n ph n t ). ầ ợ i g i P(i,j) s ít nh t là ấ ẽ ờ ọ ễ ằ ọ

V i i=j=n/2 d th y giá tr này s b ng

. V y ta v a ch ng minh đ

ễ ấ ẽ ằ ớ ị ứ ừ ậ ượ ằ c r ng

ị ấ ớ là m t giá tr r t l n (tuy có nh h n c n d ỏ ơ ộ ậ ướ ộ ứ ạ 2n) và h u nh không th áp d ng tính toán trên th c t . ự ế i đ ph c t p tính toán P(i,j) là ể ầ ư ụ

t nh t là v a tính v a đi n s vào b ng nh mô t trong hình 3 d ố ề ố ừ ư ừ ả ấ ả ướ i Cách tính P(i,j) t đây.

c đi n tu n t nh sau: Tr i cùng B ng h s P(i,j) đ ệ ố ả ượ ầ ự ư ề ướ c tiên đ ý r ng hàng d ằ ể ướ

ấ ả ẽ ướ ầ ượ ả ướ i ượ c ả góc ph i d ng chéo ng nh sau: c a b ng là toàn 0 và hàng đ u tiên bên ph i s là toàn 1. Xu t phát t ầ ủ ả t đi n s vào b ng theo h chúng ta l n l ng Tây-B c d c theo đ ắ ọ c mô t v i i+j không thay đ i. Thu t toán đi n s P(i,j) vào b ng đ ả ề ố ớ ề ố ổ ừ ườ ả ư ượ ậ

Function Ođs(i,j: integer):real; (7)

var s,k:integer;

Begin

for s:=1 to i+j do

begin P[0,s]:=1;

P[s,0]:=0;

for k:=1 to s-1 do

P[k,s-k]:=(P[k-1,s-k]+P[k,s-k-1])/2;

end;

Ođs:=(P[i,j]);

End; {Ođs}

ậ ờ Ta hãy th phân tích thu t toán trên. Vòng l p bên trong là O(s) th i gian, hai l nh gán ặ 0 và 1 ch là O(1) th i gian, nh v y t ng s th i gian tính t ố ờ ệ ẽ vòng l p ngoài s là ư ậ ổ ử ỉ ừ ặ ờ

ắ ạ ươ ng c a thu t toán qui ho ch đ ng. b ng s so sánh v i vi c g i đ qui, và đó là t ả v i n=i+j. Ch c các b n đã th y s kỳ di u c a ph ớ ớ ng pháp đi n ề ộ ạ ệ ủ ậ ủ ấ ự t ư ưở ệ ọ ệ ố

Ví d 4: Bài toán Phân ho ch Tam giác ụ ạ

ộ ẽ ạ ọ ộ ỹ ẳ ộ ỉ ớ ể ữ ầ ỉ ố Ta s xét thêm m t ví d n a minh h a cho k thu t qui ho ch đ ng, đó là bài toán tam giác hóa đa giác. Gi ướ c. Yêu c u n i các ″cung″ n i gi a hai đ nh b t kỳ c a đa giác đ chia đa giác thành các ấ ố tam giác nh h n (phân ho ch tam giác) sao cho t ng các dây cung n i là nh nh t. ấ ỏ ỏ ơ ể . i thi u M t cách ch n dây cung nh v y đ ố ọ ậ ụ ữ s có m t đa giác trên m t ph ng v i các đ nh cho tr ặ ả ử ủ ố ổ ạ ộ Phân ho ch tam giác t c g i là m t ạ ư ậ ượ ọ ộ

ừ ữ ệ ớ ẽ Hình 4 mô t ta tính đ m t đa giác 7 c nh v i m t phân ho ch tam giác. T d li u trên hình v ạ ạ ả ộ c t ng chi u dài c a phân ho ch này là ủ ộ ạ ề ượ ổ

tuy nhiên phân ho ch này không ạ là t i u. ố ư

ỹ ờ ẽ chúng ta s dùng k thu t qui ho ch đ ng đ gi ậ ạ ạ ể ệ ể ả ệ ộ ẽ ệ ỉ ủ ủ ề ồ c tiên chúng ta có m t s nh n xét sau c g i là ề Giá trị c a phân ho ch này. Tr ồ ổ ạ ộ ộ ố ướ ủ ậ Bây gi i bài toán phân ho ch tam 0, giác này. Đ ti n cho vi c theo rõi, chúng ta s ký hi u các đ nh c a đa giác là V V1,.., Vn-1 theo chi u kim đ ng h . T ng chi u dài các dây cung c a m t phân ho ch ạ s đ ẽ ượ ọ đây:

ủ ề ấ ỉ ờ B đ 1. cũng có t ọ i thi u m t đ nh đ ổ ề Trong m i phân ho ch tam giác, hai đ nh k nhau b t kỳ c a đa giác bao gi c n i v i m t dây cung. ộ ạ ượ ố ớ ộ ỉ ể ố

s V ượ ố ớ ấ ứ ủ ạ iVi+1 s ph i ch a thêm hai c nh ứ ẽ ạ ả

i-1Vi và Vi+1Vi+2 và do đó vùng phân ho ch này không là tam giác.

ả ử i,Vi-1 là hai đ nh k mà không đ Gi ỉ ề ho ch tam giác. Khi đó vùng phân ho ch ch a c nh V ạ n a là V ữ c n i v i b t c dây dung nào c a phân ứ ạ ạ

s (V ủ ạ ộ ả ồ ạ i ả ử k sao cho (Vi,Vk) và (Vk,Vj) s là c nh c a đa giác ho c dây cung c a phân

i,Vj) là m t dây cung c a phân ho ch tam giác, khi đó ph i t n t ủ

ủ ẽ ạ ặ B đ 2. ổ ề Gi m t đ nh V ộ ỉ ho ch.ạ

ứ i,Vj) ph i là c nh c a m t tam giác c a phân ho ch. Đ nh th 3 ủ ủ ả ạ ạ ộ ỉ ậ ậ Th t v y, c nh (V chính là Vk c n tìm. ạ ầ

ế ố ư i u, chúng ta ch n 2 đ nh k b t kỳ, ọ ỉ i đ nh Vk sao cho V

0 và V1. Khi đó ph i t n t

ặ 0Vk và V1Vk là c nh ho c ề ấ ạ ư ậ ư ạ ọ ừ ề ớ ở ị ớ ả ớ ỗ ng ng v i 2 đa giác con xác đ nh b i dây cung v a tìm ươ ứ c phân chia đa giác ban đ u thành 2 ph n. V i ví d đa giác 7 c nh đã nêu trên gi ụ ầ 0V3, khi đó s đ a v 2 bài toán con ng v i hai đa giác 3 v i cung V ầ ẽ ư ề ạ ứ ớ ớ ỉ Đ b t đ u tìm ki m phân ho ch tam giác t ể ắ ầ ạ ch ng h n V ả ồ ạ ỉ ạ ẳ dây cung c a phân ho ch. V i m i cách ch n k nh v y ta đ a bài toán tìm phân ủ ho ch v 2 bài toán con, t ạ đ ượ s ta ch n đ nh V ọ ử sau đây:

i quy t bài toán phân ho ch tam giác cho hai tr ầ ế ạ ả ế ụ ớ ợ ng h p cung 3,V4,V5) và ữ ươ ứ ế ớ ẽ Ti p theo chúng ta c n gi t ớ ươ ứ V3V5 thì s chia thành 2 bài toán con n a t (V0,V3,V5,V6). Cách ti p c n nh v y s có th i gian tăng s mũ v i n. ư ậ ẽ ườ ng ng v i hình 5 trên. Ví d v i Bài toán con 2, n u chúng ta b t đ u t ắ ầ ừ ng ng v i hai đa giác con là (V ố ế ậ ờ ớ

Chú thích c a ng t. ủ i vi ườ ế

ộ ắ ế ắ t t ng ph n t đ u c a các ầ ậ i v i nhau theo hình th c xét l n l ạ ớ ế ầ ử ầ ủ ầ ượ ừ (1) S p x p tr n. Thu t toán s p x p tách dãy ban đ u thành 2 dãy và sau đó ti n hành ế ″tr n″ hai dãy này l ứ ộ dãy này.

d a trên ý ị ế ứ ự ự ế ậ ộ ng luôn chia dãy đã cho thành 2 ph n b ng nhau và đ a vi c tìm trên dãy l n v bài ắ ệ ề ư ầ ằ ớ (2) Tìm ki m nh phân. Thu t toán tìm ki m trên m t dãy đã s p th t t ưở toán tìm ki m trên các dãy con này. ế

ng pháp tính nhân trong nhà tr ươ ỏ ệ ườ ổ ữ ộ ố ỗ ớ ậ ổ ư ậ ệ ấ ờ ng ph thông. Chia nh vi c nhân 2 s n-ch (3) Ph ố s XY thành n bài toán con, m i bài toán con nhân X v i m t s có m t ch s . V i ữ ố ớ ố ộ m i bài toán con nh v y vi c nhân m t O(n) th i gian, do v y t ng s đ ph c t p là ố ộ ứ ạ ỗ O(n2).

ớ ạ ế ạ ạ ớ ng. Tuy nhiên thu t toán mô t đây hoàn toàn ừ ắ trên gh nhà tr ế ắ ằ ườ t h n cách nhân thông th ng ố ơ ậ ổ ườ ớ

(4) T i đây s có b n th c m c r ng th thì t i sao không d y cách nhân m i này cho ẽ h c sinh ngay t ọ ả ở ng ph thông v i n<5000. Ma(.t kha'c no' không t tr ở ườ la.i qua' phu+'c ta.p va` kho^ng sa'ng su?a nhu+ thua^.t toa'n ho.c sinh ddang su+? du.ng hie^.n nay.

World Series Ođs, chúng tôi s a l ừ ử ạ ớ i cho thích h p h n v i ơ ợ (5) Nguyên tác là c m t ụ t Nam. c a Vi th c t ự ế ủ ệ

(6) Cách tính nh sau: ư

V i i=j=n/2 ta c n ph i ch ng minh: ứ ả ầ ớ

ứ ứ ẵ ớ ấ ẳ s nó đã đúng v i n, ta s ch ng minh nó cũng đúng v i n+2. Ta ch ng minh b t đ ng th c này qui n p theo n (n-ch n). V i n=2, b t đ ng th c là ạ ứ hi n nhiên. Gi ẽ ứ ấ ẳ ớ ả ử ể ớ

Th t v y khi đó ta có: ậ ậ

ặ ằ theo qui n p giá tr này s l n h n ho c b ng ẽ ớ ạ ơ ị