Chương 3: Duyệt và Đệ qui

Định nghĩa bằng đệ qui Trong thực tế, chúng ta gặp rất nhiều đối tợng mà khó có thể định nghĩa nó một cách tờng minh, nhng lại dễ dàng định nghĩa đối tợng qua chính nó.
Nội dung trích xuất từ tài liệu:
Chương 3: Duyệt và Đệ qui Ch¬ng 3 DuyÖt vµ §Ö qui3.1- §Þnh nghÜa b»ng ®Ö qui Trong thùc tÕ, chóng ta gÆp rÊt nhiÒu ®èi t îng mµ khã cã thÓ ®ÞnhnghÜa nã mét c¸ch têng minh, nhng l¹i dÔ dµng ®Þnh nghÜa ®èi tîng qua chÝnhnã. Kü thuËt ®Þnh nghÜa ®èi tîng qua chÝnh nã ®îc gäi lµ kü thuËt ®Ö qui(recursion). §Ö qui ®îc sö dông réng r·i trong khoa häc m¸y tÝnh vµ lý thuyÕt tÝnhto¸n. C¸c gi¶i thuËt ®Ö qui ®Òu ®îc x©y dùng th«ng qua hai bíc: bíc ph©n tÝch vµbíc thay thÕ ngîc l¹i.VÝ dô 3.1. §Ó tÝnh tæng S(n) = 1 + 2 + . . .+ n, chóng ta cã thÓ thùc hiÖn th«ngqua hai bíc nh sau:Bíc ph©n tÝch: • §Ó tÝnh to¸n ®îc S(n) tríc tiªn ta ph¶i tÝnh to¸n tríc S(n-1) sau ®ã tÝnh S(n) = S(n-1) +n. • §Ó tÝnh to¸n ®îc S(n-1), ta ph¶i tÝnh to¸n tríc S(n-2) sau ®ã tÝnh S(n-1) = S(n- 2) + n-1. •...................................................... • §Ó tÝnh to¸n ®îc S(2), ta ph¶i tÝnh to¸n tríc S(1) sau ®ã tÝnh S(2) = S(1) + 2. • Vµ cuèi cïng S(1) chóng ta cã ngay kÕt qu¶ lµ 1Bíc thay thÕ ngîc l¹i: XuÊt ph¸t tõ S(1) thay thÕ ngîc l¹i chóng ta x¸c ®Þnh S(n): • S(1) = 1 • S(2) = S(1) + 2 • S(3) = S(2) + 3 •. . . . . . . . . . . . • S(n) = S(n - 1) + nVÝ dô 3.2. §Þnh nghÜa hµm b»ng ®Ö quiHµm f(n) = n! DÔ thÊy f(0) = 1. V× (n+1) ! = 1 . 2.3 . . . n(n+1) = n! (n+1), nªn ta cã: f(n+1) = ( n+1) . f(n) víi mäi n nguyªn d¬ng.Hµm f(n) = an 86 V× a0 = 1; f(n+1) = an+1 = a.an = a. f(n) nªn f (n) = a. f(n) víi mäi sè thùc a vµsè tù nhiªn n.VÝ dô 3.3. TËp hîp ®Þnh nghÜa b»ng ®Ö qui§Þnh nghÜa ®Ö qui tËp c¸c x©u : Gi¶ sö Σ* lµ tËp c¸c x©u trªn bé ch÷ c¸i Σ. Khi®ã Σ* ®îc ®Þnh nghÜa b»ng ®Ö qui nh sau: • λ ∈ Σ*, trong ®ã λ lµ x©u rçng • wx ∈ Σ* nÕu w ∈ Σ* vµ x ∈ Σ*VÝ dô 3.4. CÊu tróc tù trá ®îc ®Þnh nghÜa b»ng ®Ö qui struct node { int infor; struct node *left; struct node *right; };3.2- Gi¶i thuËt ®Ö qui Mét thuËt to¸n ®îc gäi lµ ®Ö qui nÕu nã gi¶i bµi to¸n b»ng c¸ch rót gän bµito¸n ban ®Çu thµnh bµi to¸n t ¬ng tù nh vËy sau mét sè h÷u h¹n lÇn thùc hiÖn.Trong mçi lÇn thùc hiÖn, d÷ liÖu ®Çu vµo tiÖm cËn tíi tËp d÷ liÖu dõng. VÝ dô: ®Ó gi¶i quyÕt bµi to¸n t×m íc sè chung lín nhÊt cña hai sè nguyªn d-¬ng a vµ b víi b > a, ta cã thÓ rót gän vÒ bµi to¸n t×m íc sè chung lín nhÊt cña (bmod a) vµ a v× USCLN(b mod a, a) = USCLN(a,b). D·y c¸c rót gän liªn tiÕp cã thÓ®¹t ®îc cho tíi khi ®¹t ®iÒu kiÖn dõng USCLN(0, a) = USCLN(a, b) = a. Sau ®©ylµ vÝ dô vÒ mét sè thuËt to¸n ®Ö qui th«ng dông. ThuËt to¸n 1: TÝnh an b»ng gi¶i thuËt ®Ö qui, víi mäi sè thùc a vµ sè tùnhiªn n. double power( float a, int n ){ if ( n ==0) return(1); return(a *power(a,n-1)); } ThuËt to¸n 2: ThuËt to¸n ®Ö qui tÝnh íc sè chung lín nhÊt cña hai sènguyªn d¬ng a vµ b. int USCLN( int a, int b){ 87 if (a == 0) return(b); return(USCLN( b % a, a)); }ThuËt to¸n 3: ThuËt to¸n ®Ö qui tÝnh n! long factorial( int n){ if (n ==1) return(1); return(n * factorial(n-1)); }ThuËt to¸n 4: ThuËt to¸n ®Ö qui t×m kiÕm nhÞ ph©n: int binary_search( float *A, int x, int i, int j){ int mid = ( i + j)/2; if ( x > A[mid] && i • Cã thÓ x¸c ®Þnh ®îc mét thø tù trªn tËp c¸c cÊu h×nh tæ hîp cÇn liÖt kª, tõ ®ã x¸c ®Þnh ®îc cÊu h×nh ®Çu tiªn vµ cÊu h×nh cuèi cïng. • Tõ mét cÊu h×nh bÊt kú cha ph¶i lµ cuèi cïng, ®Òu cã thÓ x©y dùng ®îc mét thuËt to¸n ®Ó suy ra cÊu h×nh kÕ tiÕp. Tæng qu¸t, thuËt to¸n sinh kÕ tiÕp cã thÓ ®îc m« t¶ b»ng thñ tôc genarate,trong ®ã Sinh_KÕ_TiÕp lµ thñ tôc sinh cÊu h×nh kÕ tiÕp theo thuËt to¸n sinh ®·®îc x©y dùng. NÕu cÊu h×nh hiÖn t¹i lµ cÊu h×nh cuèi cïng th× thñ tôcSinh_KÕ_TiÕp sÏ g¸n cho stop gi¸ trÞ true, ngîc l¹i cÊu h×nh kÕ tiÕp sÏ ®îc sinh ra.Procedure generate; begin stop :=false; while not stop do begin ; Sinh_KÕ_TiÕp; end; end; Sau ®©y chóng ta xÐt mét sè vÝ dô minh häa cho thuËt to¸n sinh.3.3.1- Bµi to¸n liÖt kª c¸c tËp con cña tËp n phÇn tö Mét tËp hîp h÷u h¹n gåm n phÇn tö ®Òu cã thÓ biÓu diÔn t¬ng ®¬ng víitËp c¸c sè tù nhiªn 1, 2, . . . n. Bµi to¸n ®îc ®Æt ra lµ: Cho mét tËp hîp gåm n phÇntö X = { X1, X2, . ., Xn }, h·y liÖt kª tÊt c¶ c¸c tËp con cña tËp hîp X. §Ó liÖt kª ®îc tÊt c¶ c¸c tËp con cña X, ta lµm t¬ng øng mçi tËp Y⊆ X víimét x©u nhÞ ph©n cã ®é dµi n lµ B = { B 1, B2, . . , Bn } sao cho Bi = 0 nÕu Xi ∉ Yvµ Bi = 1 nÕu Xi ∈ Y; nh vËy, phÐp liÖt kª tÊt c¶ c¸c tËp con cña mét tËp hîp nphÇn tö ...