Kỹ thuật đệ qui

KYÕ THUAÄT ÑEÄ QUI<br /> Kyõ thuaät laäp trình ñeä qui coù yù nghóa raát lôùn trong khoa hoïc maùy tính, coù raát<br /> nhieàu thuaät toaùn ñoøi hoûi caøi ñaët raát phöùc taïp vaø caàu kyø neáu khoâng duøng kyõ thuaät<br /> ñeä qui. Ñoái vôùi moät soá thuaät toaùn do baûn chaát töï nhieân cuûa chuùng ñaõ mang tính ñeä<br /> qui, vieäc caøi ñaët ñeä qui laø goïn vaø ñeïp nhaát. Khuyeát ñieåm lôùn nhaát cuûa kyõ thuaät ñeä<br /> qui laø: lôøi giaûi ñeä qui cho moät soá baøi toaùn coù theå bò chaïy raát chaäm do söï buøng noã toå<br /> hôïp.<br /> I.<br /> <br /> KHAÙI NIEÄM VEÀ CHÖÔNG TRÌNH ÑEÄ QUI<br /> Moät thuû tuïc (hay haøm) ñöôïc goïi laø coù tính ñeä qui neáu trong thaân cuûa thuû tuïc<br /> (hay haøm) ñoù coù leänh goïi laïi chính noù moät caùch töôøng minh hay tieàm aån.<br /> Ví duï 1. Vôùi n laø soá nguyeân khoâng aâm, ta ñònh nghóa n! nhö sau:<br /> 0!=1,<br /> n!=n.(n-1)! neáu n≥1.<br /> Haõy caøi ñaët chöông trình tính n!.<br /> Ñaây laø moät ví duï coù theå caøi ñaët deã daøng baèng phöông phaùp thoâng thöôøng, tuy<br /> nhieân neáu döïa vaøo ñònh nghóa cuûa n! chuùng ta coù theå caøi ñaët moät caùch töï nhieân<br /> baèng phöông phaùp ñeä qui nhö sau.<br /> long GiaiThua(int n) /* n >= 0 */<br /> {<br /> long ret;<br /> /* gia tri traû veà cuûa haøm */<br /> if(n==0)<br /> /* ñieàu kieän kieän döøng */<br /> ret = 1;<br /> else<br /> ret = n*GiaiThua(n-1); /* goïi laïi chính noù */<br /> return ret;<br /> }<br /> Ñoái vôùi ví duï naày, caùch caøi ñaët baèng ñeä qui raát töï nhieân vaø ñôn giaûn nhöng<br /> khoâng phaûi laø caùch caøi ñaët hay nhaát. Chuù yù raèng baát kyø haøm ñeä qui naøo cuõng phaûi<br /> coù ñieàu kieän döøng, ñieàu kieän naày seõ keát thuùc quaù trình ñeä qui baèng moät ñoaïn maõ<br /> chöông trình ñöôïc vieát theo loái thoâng thöôøng. Caâu leänh if(n==0)... trong ví duï treân<br /> laø ñieàu kieän döøng cuûa haøm GiaiThua.<br /> Ví duï 2. Haøm tính caên baäc 3 cuûa moät soá thöïc coù theå caøi ñaët ñeä qui theo hai haøm<br /> exp vaø log (haøm logarithm ln(x)) nhôø vaøo nhaän xeùt sau ñaây:<br /> <br /> x > 0 : 3 x = e ln ( x ) / 3<br /> x = 0: 3 x = 0<br /> x < 0: 3 x = − 3 − x .<br /> <br /> Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM<br /> <br /> 14<br /> <br /> #include <br /> #include <br /> double sqrt3(double x)<br /> {<br /> double ret;<br /> if(x==0)<br /> /* ñieàu kieän döøng */<br /> ret = 0;<br /> else<br /> if(x=1 && x+strlen(ch)-1=1 && y<br /> {<br /> if(< ñieàu kieän döøng >)<br /> {<br /> /* Traû veà giaù trò hay keát thuùc coâng vieäc ...*/<br /> }<br /> else<br /> {<br /> /* Laøm moät soá coâng vieäc ... */<br /> /* Goïi ñeä qui */<br /> }<br /> }<br /> II.2 Ñeä qui nhò phaân<br /> Caùc haøm ñeä qui nhò phaân coù daïng sau ñaây.<br /> < Teân vaø danh saùch tham soá ><br /> {<br /> if(< ñieàu kieän döøng >)<br /> {<br /> /* Traû veà giaù trò hay keát thuùc coâng vieäc ... */<br /> }<br /> else<br /> {<br /> /* Laøm moät soá coâng vieäc ...*/<br /> /* Goïi ñeä qui (1) ñeå giaûi quyeát vaán ñeà nhoû hôn */<br /> /* Goïi ñeä qui (2) ñeå giaûi quyeát noát vaán ñeà coøn laïi */<br /> }<br /> <br /> Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM<br /> <br /> 16<br /> <br /> }<br /> Ñeä qui nhò phaân ñoùng vai troø raát quan troïng, chuùng ta thöôøng duøng phöông<br /> phaùp naày ñeå caøi ñaët caùc thuaät toaùn "chia ñeå trò", thuaät toaùn duyeät caây nhò phaân...<br /> Ví duï: Daõy Fibonaci {Fn} ñöôïc ñònh nghóa truy hoài nhö sau:<br /> Fo=F1=1,<br /> Fn=Fn-1 + Fn-2 neáu n ≥ 2.<br /> <br /> Haøm ñeä qui nhò phaân sau ñaây seõ tính giaù trò cuûa Fn, giaù trò phaàn töû thöù n trong<br /> daõy Fibonaci, baèng caøi ñaët ñeä qui, ñaây laø moät caøi ñaët töï nhieân vaø ñôn giaûn nhaát<br /> nhöng cuõng laø caùch caøi ñaët chaïy chaäm nhaát.<br /> long Fibo(int n)<br /> {<br /> long ret, Fn_1, Fn_2;<br /> if(n