Báo cáo khoa học: "Đệ quy và các ph-ơng pháp khử đệ quy"

Chia sẻ: Nguyễn Phương Hà Linh Nguyễn Phương Hà Linh | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

162
lượt xem 32
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đệ quy là công cụ mạnh trong tin học để lập trình các bài toán khó. Tuy nhiên các hàm đệ quy th-ờng đòi hỏi bộ nhớ lớn, vì vậy vấn đề khử đệ quy là rất cần thiết. Trong báo cáo này trình bầy cấu trúc, nguyên lý hoạt động của hàm đệ quy và cách xây dựng một hàm không đệ quy t-ơng ứng. So với các ph-ơng pháp khử đệ quy đã biết, thì mô hình trình bầy ở đây đơn giản và dễ dàng áp dụng hơn....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo khoa học: "Đệ quy và các ph-ơng pháp khử đệ quy"

§Ö quy vμ c¸c ph−¬ng ph¸p khö ®Ö quy PGS. TS. Ph¹m v¨n Êt Khoa C«ng nghÖ th«ng tin - Tr−êng §H GTVT Tãm t¾t: §Ö quy lμ c«ng cô m¹nh trong tin häc ®Ó lËp tr×nh c¸c bμi to¸n khã. Tuy nhiªn c¸c hμm ®Ö quy th−êng ®ßi hái bé nhí lín, v× vËy vÊn ®Ò khö ®Ö quy lμ rÊt cÇn thiÕt. Trong b¸o c¸o nμy tr×nh bÇy cÊu tróc, nguyªn lý ho¹t ®éng cña hμm ®Ö quy vμ c¸ch x©y dùng mét hμm kh«ng ®Ö quy t−¬ng øng. So víi c¸c ph−¬ng ph¸p khö ®Ö quy ®· biÕt, th× m« h×nh tr×nh bÇy ë ®©y ®¬n gi¶n vμ dÔ dμng ¸p dông h¬n. Summary: The recursive is a powerfull tool for programming difficult problems. However the recursion functions offen demand a larger memory, so the recursive removal is very neccessary. In this paper, we will present the structure and the activity of recursion functions and a method of creating a corresponding non recursion function. This method is simpler and easier to apply compared with known methods. { i. CÊu tróc cña hμm ®Ö quy in x2 // phÐp to¸n c¬ b¶n Hµm ®Ö quy gåm 2 phÇn: P(x-1) // Lêi gäi §Q thø 1 + PhÇn suy biÕn gåm mét dÉy c¸c c©u in x // phÐp to¸n c¬ b¶n lÖnh vµ kh«ng chøa c¸c lêi gäi ®Ö quy. P(x-1) // Lêi gäi §Q cuèi + PhÇn tæng qu¸t còng bao gåm nhiÒu in 1 // phÐp to¸n c¬ b¶n c©u lÖnh, nh−ng bao gåm mét hoÆc nhiÒu lêi gäi ®Ö quy (gäi tíi chÝnh hµm ®ang xÐt). } D−íi ®©y, sÏ gäi c¸c c©u lÖnh kh«ng } chøa lêi gäi ®Ö quy lµ c¸c phÐp to¸n c¬ b¶n. VÝ dô xÐt hµm sau: ii. Nguyªn lý ho¹t ®éng void P(x) // x nguyªn d−¬ng 2.1. Tr−íc khi b¾t ®Çu ch−¬ng trinh { §Æt mét dÊu hiÖu ®Æc biÖt vµo ng¨n xÕp if(x==1) // Suy biÕn - kh«ng cã lêi gäi ®Ö (vÝ dô k = 0) lµm dÊu hiÖu kÕt thóc hµm quy 2.2. C¸ch xö lý lêi gäi ®Ö quy // chØ gåm c¸c phÐp to¸n c¬ b¶n 2.2.1. §Æt gi¸ trÞ hiÖn t¹i cña ®èi vµo { ng¨n xÕp (®Ó sau nµy lÊy ra dïng). in 8 // phÐp to¸n c¬ b¶n 2.2.2. §Æt mét dÊu hiÖu vµo ng¨n xÕp (®Ó } sau nµy biÕt lèi trë vÒ - trë vÒ sau lêi gäi ®Ö quy nµo). else // Tæng qu¸t, sÏ cã c¸c lêi gäi ®Ö quy
2.2.3. C¨n cø vµo tham sè lêi gäi ®Ö quy .... ®Ó thay ®æi gi¸ trÞ cña ®èi. else if(k==m) // trá vÒ tõ lêi gäi cuèi 2.2.4. NhÈy (trë vÒ) ®Çu hµm. { 2.3. PhÇn suy biÕn - trë vÒ 1. C¸c c©u lÖnh sau lêi gäi §Q m 2.3.1. Xö lý c¸c phÐp to¸n c¬ b¶n. 2. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu (k) tõ ®Ønh ng¨n xÐp 2.3.2. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu (k) tõ ®Ønh ng¨n xÐp. 3. NhÈy tíi ®o¹n ch−¬ng tr×nh xö lý trë vÒ (Goto 2.4.2) 2.3.3. NhÈy tíi ®o¹n ch−¬ng tr×nh xö lý trë vÒ (xem 2.4). } 2.4. PhÇn tæng qu¸t - sÏ gÆp c¸c lêi gäi ®Ö quy iii. tæ chøc hμm kh«ng ®Ö quy 2.4.1. Xö lý c¸c phÐp to¸n c¬ b¶n. 3.1. Hç trî 2.4.2. Xö lý lêi gäi ®Ö quy ®Çu tiªn gÆp CÇn t¹o mét ng¨n xÕp vµ x©y dùng c¸c ph¶i. phÐp to¸n: 2.5. §o¹n ch−¬ng tr×nh xö lý trë vÒ a. push(x,k) ®Ó ®−a ®èi x vµ dÊu hiÖu k lªn ng¨n xÕp. 2.5.1. Dùa vµo gi¸ trÞ cña k ®Ó ph©n biÖt 3 tr−êng hîp. b. pop(x,k) ®Ó lÊy ®èi x vµ dÊu hiÖu k tõ ®Ønh ng¨n xÕp. a. KÕt thóc hµm (k=0) b. Trë vÒ tõ lêi gäi ®Ö quy i (k=i < m) 3.2. CÊu tróc cña hµm kh«ng ®Ö quy (dïng goto) gåm 4 phÇn c. Trë vÒ tõ lêi gäi cuèi (k=m) PhÇn 1. Khëi ®Çu. 2.5.2. CÊu tróc cña ®o¹n ch−¬ng tr×nh Push(0,0) // §−a dÊu hiÖu ®Æc biÖt lªn nh− sau: ng¨n xÕp lµm dÊu hiÖu kÕt thóc hµm if(k==0) PhÇn 2. PhÇn tæng qu¸t (®Æt nh·n lµ KÕt thóc hµm §ÇuHµm). else if(k==1) a. Xö lý c¸c phÐp to¸n c¬ b¶n { b. Khi gÆp lêi gäi §Q ®Çu tiªn th×: 1. C¸c c©u lÖnh sau lêi gäi §Q 1 + Push(x,1) 2. Xö lý lêi gäi §Q 2 + Thay ®æi x } + ChuyÓn ®Õn PhÇn 2 (goto §ÇuHµm) else if(k==2) PhÇn 3. PhÇn suy biÕn. { a. Xö lý c¸c phÐp to¸n c¬ b¶n. 1. C¸c c©u lÖnh sau lêi gäi §Q 2 b. LÊy gi¸ trÞ cña ®èi (x) vµ dÊu hiÖu (k) tõ 2. Xö lý lêi gäi §Q 3 ®Ønh ng¨n xÐp. } c. ChuyÓn ®Õn PhÇn 4 (goto TrëVÒ) //
Cã thÓ bá lÖnh nµy. push(0,0); DauHam: PhÇn 4. Xö lý trë vÒ (®Æt nh·n lµ TrëVÒ) if(x>1) a. NÕu k=0 - kÕt thóc hµm. { b. NÕu 0 < k < m (trë vÒ tõ lêi gäi §Q // Tæng qu¸t thø k). cout
{ 5.1. Hµm ®Ö quy tæng qu¸t cã thÓ diÔn ®¹t nh− sau Am(x); P(x) : if (S(x)) // suy biÕn push(x,m);x=fm(x); goto DauHam; C(x) } else // tæng qu¸t else if(k==m) // trë vÒ tõ lêi gäi §Q { cuèi A1(x); P(f1(x)); // Gäi §Q 1 { A2(x); P(f2(x)); // Gäi §Q 2 Am+1(x); ... pop(x,k); goto TroVe; Am(x); P(fm(x)); // Gäi §Q m } Am+1(x); vi. M« h×nh khö ®Ö quy tæng qu¸t } dïng while 5.2. Hµm kh«ng ®Ö quy t−¬ng øng Cã thÓ thay c¸c c©u lÖnh goto vµ c¸c P(x): nh·n trong m« h×nh ë môc 5, b»ng c¸ch dïng int k; //khai b¸o biÕn k while vµ break (theo phong c¸ch C/C++) nh− sau: push(0,0) ; // dÊu hiÖu kÕt thóc DauHam: P(x): if (!S(x) // kh«ng suy biÕn - tæng qu¸t int k; //khai b¸o biÕn k { push(0,0) ; // dÊu hiÖu kÕt thóc A1(x); while(1) push(x,1);x=f1(x); goto DauHam; { } while(!S(x)) // S(x) sai - tæng qu¸t //suy biÕn { C(x); A1(x); pop(x,k); push(x,1);x=f1(x); TroVe: } if(k==0) return ; // S(x) ®óng - suy biÕn else if(k==1) // trë vÒ tõ lêi gäi §Q 1 C(x); { pop(x,k); A2(x); while(1) push(x,2);x=f2(x); goto DauHam; { } if(k==0) return ; ... else if(k==1) // trë vÒ tõ lêi gäi §Q 1 else if(k==m-1) // trë vÒ tõ lêi gäi §Q m -1 {
A2(x); // Suy biÕn push(x,2);x=f2(x); break; cout