Kỹ thuật đệ quy: Tổng quan và ứng dụng

KYÕ THUAÄT ÑEÄ QUI

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 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 ñ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ä 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ä 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å hôïp.

I. KHAÙI NIEÄM VEÀ CHÖÔNG TRÌNH ÑEÄ QUI

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

(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.

Ví duï 1. Vôùi n laø soá nguyeân khoâng aâm, ta ñònh nghóa n! nhö sau:

0!=1, n!=n.(n-1)! neáu n≥1. Haõy caøi ñaët chöông trình tính n!.

Ñ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 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 baèng phöông phaùp ñeä qui nhö sau.

/* gia tri traû veà cuûa haøm */ /* ñieàu kieän kieän döøng */

ret = 1;

ret = n*GiaiThua(n-1); /* goïi laïi chính noù */

long ret; if(n==0) else return ret;

long GiaiThua(int n) /* n >= 0 */ { }

ln (

) /

Ñ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 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 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õ 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 laø ñieàu kieän döøng cuûa haøm GiaiThua.

>

=

0

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 exp vaø log (haøm logarithm ln(x)) nhôø vaøo nhaän xeùt sau ñaây: e

x

:

=

0 x

:

x

<

= −

0 x

:

x

x− .

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

/* ñieàu kieän döøng */

/* goïi ñeä qui */

ret = sqrt3(-x);

/* moät ñieàu kieän döøng khaùc */

ret = exp(log(x)/3);

#include #include double sqrt3(double x) { double ret; if(x==0) ret = 0; else if(x<0) else return ret;

}

Ví duï 3. Caøi ñaët caùc haøm in, thoâng baùo loãi trong cheá ñoä vaên baûn. Caùch caøi ñaët sau ñaây laø moät daïng goïi ñeä qui tieàm aån, chính xaùc hôn ñaây laø caùch goïi xoay voøng, haøm InChuoi goïi haøm BaoLoi ñeå thoâng baùo loãi khi toïa ñoä in khoâng hôïp leä, ngöôïc laïi haøm BaoLoi goïi haøm InChuoi ñeå in caâu thoâng baùo loãi taïi doøng cuoái cuøng cuûa maøn hình

gotoxy(x, y); cprintf(ch);

BaoLoi(); if( x>=1 && x+strlen(ch)-1<=MAXCOL && y>=1 && y<=MAXROW) { } else

#include #include void BaoLoi(); void InChuoi(int x, int y, char *ch); #define MAXROW 25 #define MAXCOL 80 /* in chuoãi ch taïi vò trí (x, y) treân maøn hình */ void InChuoi(int x, int y, char *ch) { } void BaoLoi() { InChuoi(1, 25, "Toa do in sai !"); printf("%c%c%c", 7, 7, 7);

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

}

II. CAÙC DAÏNG CHÖÔNG TRÌNH ÑEÄ QUI

Caùc chöông trình ñeä qui thöôøng gaëp coù theå thuoäc moät trong boán loaïi chöông

trình ñeä qui sau ñaây:

- Ñeä qui tuyeán tính; - Ñeä qui nhò phaân; - Ñeä qui phi tuyeán; - Ñeä qui hoã töông.

Sau ñaây, chuùng ta seõ ñònh nghóa vaø cho ví duï cuï theå veà caùc loaïi chöông trình

ñeä qui.

II.1 Ñeä qui tuyeán tính

Caùc ví duï 1 vaø 2 trong phaàn treân minh hoïa caùc haøm ñeä qui coù daïng tuyeán tính.

Caùc haøm ñeä qui tuyeán tính coù daïng sau ñaây.

/* Traû veà giaù trò hay keát thuùc coâng vieäc ...*/

/* Laøm moät soá coâng vieäc ... */ /* Goïi ñeä qui */

< Teân vaø danh saùch tham soá > { if(< ñieàu kieän döøng >) { } else { } }

II.2 Ñeä qui nhò phaân

Caùc haøm ñeä qui nhò phaân coù daïng sau ñaây.

{

/* Traû veà giaù trò hay keát thuùc coâng vieäc ... */

/* Laøm moät soá coâng vieäc ...*/ /* Goïi ñeä qui (1) ñeå giaûi quyeát vaán ñeà nhoû hôn */ /* Goïi ñeä qui (2) ñeå giaûi quyeát noát vaán ñeà coøn laïi */

< Teân vaø danh saùch tham soá > { if(< ñieàu kieän döøng >) } else { }

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

}

Ñeä qui nhò phaân ñoùng vai troø raát quan troïng, chuùng ta thöôøng duøng phöông

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...

Ví duï: Daõy Fibonaci {Fn} ñöôïc ñònh nghóa truy hoài nhö sau:

Fo=F1=1, Fn=Fn-1 + Fn-2 neáu n ≥ 2.

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 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 nhöng cuõng laø caùch caøi ñaët chaïy chaäm nhaát.

long ret, Fn_1, Fn_2;

ret = 1;

Fn_1 = Fibo(n-1); Fn_2 = Fibo(n-2); ret = Fn_1 + Fn_2;

if(n <= 1) else { } return ret;

long Fibo(int n) { }

Chöông trình treân laø moät ví duï veà ñeä qui nhò phaân coù theå deã daøng ñöa veà ñeä qui tuyeán tính, trong tröôøng hôïp nhö vaäy thì caøi ñaët theo ñeä qui tuyeán tính seõ toát hôn. Moät soá thuaät toaùn khaùc mang tính "chia ñeå trò" theo kieåu nhò phaân thì caøi ñaët ñeä qui nhò phaân seõ theå hieän roõ tính töï nhieân cuûa thuaät vaø coù thôøi gian chaïy khaù toát.

Döôùi ñaây laø moät phieân baûn ñeä qui tuyeán tính ñeå tính phaàn töû thöù n cuûa daõy

Fibonaci.

F_n_2: Fn-2 */ F_n: Fn;

void FiboLinear(int n, long* F_n_1, long* F_n) /* F_n_1: Fn-1; { long F_n_2; if(n<=1) { *F_n_1 = 1; *F_n = 1;

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

FiboLinear(n-1, &F_n_2, &(*F_n_1) ); *F_n = *F_n_1 + F_n_2;

} else { }

}

II.3 Ñeä qui phi tuyeán

Trong caùc chöông trình ñeä qui phi tuyeán, vieäc goïi ñeä qui seõ ñöôïc thöïc hieän beân

trong voøng laëp, sau ñaây laø maãu chung cuûa moät haøm hay thuû tuïc ñeä qui phi tuyeán.

for(i=1; i<=n; i++) { /* Laøm moät soá coâng vieäc ...*/ if(< ñieàu kieän döøng >) { /* Laøm moät soá coâng vieäc ...*/

< Teân vaø danh saùch tham soá >; { } else /* Goïi ñeä qui */ }

}

Ví du: Cho daõy {Xn} xaùc ñònh theo coâng thöùc truy hoài sau ñaây:

Xo=1, Xn=n2Xo + (n-1)2X1 + ... + 12Xn-1 , neáu n ≥ 1.

Nhö caùc ví duï tröôùc, chuùng ta coù theå tính daõy naày baèng phöông phaùp ñeä qui, bôûi vì baûn chaát ñöôïc ñònh nghóa ñeä qui cuûa daõy. Tröôøng hôïp naày vieäc goïi ñeä qui ñöôïc thöïc hieän trong voøng laëp.

/* gia tri tra ve */ int i; long ret;

ret=1;

long Xn(int n) { if(n==0) else { ret = 0;

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

for(i=0; i

} return ret;

}

II.4 Ñeä qui hoã töông

Moät chöông trình ñeä qui hoã töông goïi laïi chính noù moät caùch giaùn tieáp thoâng qua chöông trình khaùc. Ví duï 3 beân treân laø moät ví duï veà ñeä qui hoã töông. Moät daïng ñeä qui hoã töông ñôn giaûn laø tröôøng hôïp hai haøm goïi qua laïi laãn nhau, daïng naày coù caáu truùc nhö sau:

/* laøm moät soá vieäc */ Proc2(...) /* laøm moät soá vieäc */ /* laøm moät soá vieäc */ Proc1(...) /* laøm moät soá vieäc */

void Proc1(...) { } void Proc2(...) { }

Ví duï: Xeùt hai daõy {Xn}, {Yn} ñöôïc ñònh nghóa nhö sau:

Xo=Yo=0 Xn = Xn-1 + Yn-1 Yn = n2Xn-1+ Yn-1

Hai daõy naày ñöôïc tính nhôø vaøo hai haøm TinhX vaø TinhY goïi hoã töông laãn nhau

ñöôïc minh hoïa qua caøi ñaët döôùi ñaây.

long ret; /* giaù trò traû veà */

ret = 1;

if(n<=0) else ret = TinhX(n-1)+TinhY(n-1);

return ret;

long TinhX(int n); long TinhY(int n); long TinhX(int n) { }

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

/* giaù trò traû veà */ long ret;

ret = 1;

ret = n*(long)n*TinhX(n-1)+TinhY(n-1); if(n<=0) else

return ret;

long TinhY(int n) { }

III. THEO DOÕI HOAÏT ÑOÄNG CUÛA CHÖÔNG TRÌNH ÑEÄ QUI

Do coù caáu truùc ñaëc bieät, caùc chöông trình ñeä qui khaùc haún vôùi caùc chöông trình thoâng thöôøng. (Caùc chöông trình thoâng thöôøng chæ duøng caùc leänh tuaàn töï, caáu truùc reû nhaùnh, leänh nhaûy, hay caáu truùc laëp). Vì vaäy ngöôøi laëp trình raát khoù khaên trong vieäc theo doõi vaø kieåm tra caùc chöông trình ñeä qui, nhaát laø khi chöông trình coù loãi. Vôùi caùc coâng cuï baét loãi chöông trình hieän nay, ngöôøi laäp trình chæ theo doõi ñöôïc traïng thaùi hieän haønh trong moät laàn goïi ñeä qui chöù chöa hình dung ñöôïc toaøn boä traïng thaùi cuûa chöông trình (chaúng haïn nhö ñang goïi ñeä qui ôû taàng thöù maáy vaø ñang ôû laàn goïi naøo trong taàng naày, giaù trò cuûa caùc bieán cuïc boä ôû moãi laàn goïi laø bao nhieâu, giaù trò cuûa caùc tham soá ...).

Trong phaàn naày chuùng ta seõ nghieân cöùu moät phöông phaùp theo doõi caùc chöông trình ñeä qui, phöông phaùp naày coù theå duøng keát hôïp chaët cheõ vôùi caùc coâng cuï baét loãi chöông trình.

Moãi chöông trình ñeä qui seõ ñöôïc bieåu dieãn baèng moät caây, goác cuûa caây ñaïi dieän cho laàn goïi ñaàu tieân, caùc nuùt cuûa caây ñaïi dieän cho caùc laàn goïi ñeä qui, moãi nuùt löu giaù trò hieän taïi cuûa caùc bieán cuïc boä hay caùc tham soá trong moät laàn goïi ñeä qui, caùc nuùt laù öùng vôùi laàn goïi ñeä qui gaëp ñieàu kieän döøng. Tuøy theo loaïi ñeä qui maø caây coù caáu truùc ñaëc tröng, ví duï ñeä qui nhò phaân seõ ñöôïc bieåu dieãn baèng caây nhò phaân, ñeä qui tuyeán tính bieåu dieãn baèng moät caây suy thoaùi (thaønh moät xaâu ñôn).

F5=F3+F4

F3=F1+F2

F4=F2+F3

F2=F0+F1

F3=F1+F2

F1=1

F2=F0+F1

F1=1

F2=F0+F1

F1=1

F0=1

Ví du: Bieåu dieãn cuûa haøm ñeä qui Fibo trong phaàn treân vôùi n=5, ta kyù hieäu Fibo(n) laø Fn. Hình döôùi ñaây laø caây nhò phaân bieåu dieãn cuûa haøm Fibo. Chuùng ta cuõng nhaän thaáy coù nhieàu nuùt laëp laïi trong caây. Ñieàu naày chöùng toû cuøng moät giaù trò ñöôïc tính ñi, tính laïi nhieàu laàn. Ñieàu naày laøm cho chöông trình chaïy raát chaäm.

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

IV. MOÄT SOÁ BAØI TOAÙN ÑEÄ QUI THOÂNG DUÏNG

IV.1 Baøi toaùn Thaùp Haø noäi

Choàng soá 1

Choàng soá 2

Choàng soá 3

Coù ba choàng ñóa ñöôïc ñaùnh soá laø 1, 2, 3. Khôûi ñaàu choàng ñóa soá 1 coù n ñóa, ñöôïc xeáp sao cho ñóa lôùn hôn luoân naèm beân döôùi, vaø hai choàng ñóa kia chöa coù ñóa naøo. Haõy chuyeån heát caùc ñóa töø choàng soá 1 sang choàng soá 3, moãi laàn chæ chuyeån 1 ñóa, ñöôïc pheùp duøng choàng soá 2 laøm trung gian, trong quaù trình chuyeån phaûi baûo ñaûm ñóa lôùn hôn luoân naèm beân döôùi. Hình veõ beân döôùi minh hoïa tröôøng hôïp n=3 ñóa.

Baøi toaùn Thaùp Haø noäi coù theå giaûi raát ñôn giaûn baèng phöông phaùp ñeä qui theo

thuaät toaùn sau.

Thuaät toaùn Thaùp haø noäi

Neáu soá ñóa n=1 thì hieån nhieân coù theå chuyeån theo yeâu caàu cuûa baøi toaùn. Neáu ngöôïc laïi: - Böôùc 1: Goïi ñeä qui ñeå chuyeån n-1 ñóa töø choàng thöù 1 sang choàng thöù 2

(choàng thöù 3 laøm trung gian).

- Böôùc 2: Chuyeån ñóa thöù n töø choàng 1 sang choàng 3. - Böôùc 3: Goïi ñeä qui ñeå chuyeån n-1 ñóa töø choàng thöù 2 sang choàng thöù 3

(choàng thöù 1 laøm trung gian).

Thuaät toaùn treân ñöôïc caøi ñaët ñeä qui baèng haøm Tower döôùi ñaây. Haøm naày goïi haøm MoveDisk ñeå chuyeån ñóa cuoái cuøng. Trong caøi ñaët naày haøm MoveDisk chæ nhaèm höôùng daãn trình töï chuyeån ñóa. Baèng caùch söûa haøm MoveDisk thích hôïp, chuùng ta coù theå giaû laäp quaù trình di chuyeån ñóa treân maøn hình cuûa maùy tính.

#include void MoveDisk(int src, int des) { printf("Töø %d Ñeán %d\n", src, des);

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

if(n>0) { /* chuyeån n-1 ñóa töø col1 sang col2; col3 trung gian */ Tower(n-1, col1, col3, col2); MoveDisk(col1, col3); /* chuyeån ñóa cuoái */

/* chuyeån n-1 ñóa töø col2 sang col3; col1 trung gian */ Tower(n-1, col2, col1, col3);

} void Tower(int n, int col1, int col2, int col3) /*col1: xuaát phaùt; col2: trung gian; col3: ñeán*/ { }

}

Tower(3,1,2,3) Töø 1 Ñeán 3

Tower(2,1,3,2) Töø 1 Ñeán 2

Tower(2,2,1,3) Töø 2 Ñeán 3

Tower(1,1,2,3) Töø 1 Ñeán 3

Tower(1,3,1,2) Töø 3 Ñeán 2

Tower(1,2,3,1) Töø 2 Ñeán 1

Tower(1,1,2,3) Töø 1 Ñeán 3

Chuùng ta seõ minh hoïa hoaït ñoäng cuûa thuaät toaùn baèng caùch veõ caây bieåu dieãn cho thuaät toaùn vôùi n=3, thuaät toaùn treân thuoäc loaïi ñeä qui nhò phaân neân caây bieåu dieãn seõ laø moät caây nhò phaân. Caùc nuùt laù öùng vôùi caùc leänh goïi Tower(0,?,?,?) ñöôïc boû qua bôûi vì caùc leänh naày khoâng laøm gì caû.

Döïa vaøo hình veõ treân chuùng ta laäp ñöôïc baûng moâ taû traïng thaùi hoaït ñoäng cuûa thuaät toaùn vôùi n=3, caùc ñóa ñöôïc kyù hieäu laø a, b, c vôùi giaû söû a > b > c, caùc ñóa treân hình veõ töø döôùi leân treân seõ ñöôïc kyù hieäu töø traùi qua phaûi.

Söï hoaït ñoäng cuûa thuaät toaùn

Khôûi ñaàu Töø 1 Ñeán 3 Töø 1 Ñeán 2 Töø 3 Ñeán 2 Coät 1 a b c a b a a Coät 2 Coät 3 b b c c c

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

Töø 1 Ñeán 3 Töø 2 Ñeán 1 Töø 2 Ñeán 3 Töø 1 Ñeán 3 c c b c b a a a b a b c

IV.2 Thuaät toaùn phaùt sinh chænh hôïp vaø hoaùn vò

IV.2.1 Hoaùn vò vaø chænh hôïp

Cho moät taäp hôïp n phaàn töû Ω={1, 2, ..., n}. Moät hoaùn vò cuûa Ω laø moät daõy a1 a2 ... an, trong ñoù ai ∈ Ω vaø chuùng ñoâi moät khaùc nhau. Moät taäp hôïp n phaàn töû seõ coù taát caû n! hoaùn vò.

Ví duï: - Neáu Ω={a,b,c} thì a b c vaø b a c laø hai hoaùn vò cuûa Ω. - Neáu Ω={1, 2, 3} thì coù taát caû 3!=1x2x3=6 hoaùn vò cuûa Ω laø 123, 132, 231, 213,

312, 321.

Cho moät taäp hôïp n phaàn töû Ω={1, 2, ..., n} vaø moät soá nguyeân k (1 ≤ k ≤ n). Moät chænh hôïp chaäp k cuûa Ω laø moät daõy μ coù k phaàn töû ñöôïc laáy ra töø Ω vaø caùc phaàn töû cuûa μ ñoâi moät khaùc nhau.

k n

Ví duï: Vôùi Ω={1, 2, 3} thì 1 2, 2 1, 1 3, 3 1, 2 3, 3 2 laø caùc chænh hôïp chaäp 2 cuûa Ω.

n = ! n n

k n

Ta thaáy ngay moät chænh hôïp chaäp n cuûa moät taäp hôïp Ω (coù n phaàn töû) chính laø moät hoaùn vò cuûa Ω. Soá caùc chænh hôïp chaäp k cuûa n phaàn töû ñöôïc kyù hieäu laø: A , ta coù A , hôn nöõa A coù theå tính theo coâng thöùc sau ñaây.

k = n

(

! n n k −

Soá löôïng caùc chænh hôïp chaäp k cuûa n phaàn töû ñöôïc xaùc ñònh theo coâng thöùc:

Ví duï: Coù 4 ñôït söûa xe vaø 3 khaùch haøng teân Lan, Huøng, Chaâu. Caùc thoâng tin lieân quan ñöôïc cho trong hai baûng nhö sau:

Ñôït söûa Khaùch haøng Thôøi ñieåm giao xe

Lan Huøng Chaâu 19:00 15:00 10:30

1 2 3 4 Nghæ Thôøi ñieåm baét ñaàu 7:00 9:30 12:00 15:00 18:00 Thôøi gian söûa 2,0 giôø 1,5 giôø 2,0 giôø

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

Coù theå nhaän söûa ñeå ñaùp öùng yeâu caàu cho caû 3 khaùch haøng treân hay khoâng? Chuùng ta coù theå laäp baûng cho moãi tröôøng hôïp cuûa chænh hôïp chaäp 3 cuûa 4

phaàn töû ñeå xeùt xem moãi tröôøng hôïp coù bao nhieâu khaùch haøng ñöôïc thoûa maõn.

...

Khaùch haøng Lan Huøng Chaâu 3 Phöông aùn 2 ñôït 1 ñôït 3 ñôït 2 (treå) Phöông aùn 3 ñôït 3 ñôït 2 ñôït 1

Phöông aùn 1 ñôït 1 ñôït 2 ñôït (treå)

IV.2.2 Thuaät toaùn phaùt sinh chænh hôïp

Do hoaùn vò laø moät tröôøng hôïp ñaëc bieät cuûa chænh hôïp (khi k=n) neân chuùng ta chæ baøn ñeán thuaät toaùn phaùt sinh taát caû caùc chænh hôïp chaäp k cuûa n phaàn töû. Ñaây cuõng laø thuaät toaùn duyeät qua taát caû caùc chænh hôïp trong caùc baøi toaùn toå hôïp nhö ví duï treân. Thuaät toaùn coù moät tham soá i, khi goïi ñeä qui thì giaù trò tham soá naày thay ñoåi, khôûi ñaàu i nhaän giaù trò 1.

- Goïi haøm: Phatsinh(a, n, k, 1) - Haøm ñeä qui Phatsinh(a, n, k, i)

Laëp j=i ñeán n laøm

goïi ñeä qui Phatsinh(a, n, k, i+1)

xöû lyù a1 a2 ... ak

Ñoåi choã aj vaø ai Neáu j

Cuoái laëp

IV.3 Thuaät toaùn phaùt sinh toå hôïp

IV.3.1 Toå hôïp

Cho moät taäp hôïp n phaàn töû Ω={1, 2, ..., n} vaø moät soá nguyeân k (1 ≤ k ≤ n). Moät

toå hôïp chaäp k cuûa Ω laø moät taäp con cuûa Ω coù k phaàn töû.

Ví duïï: Vôùi Ω={1, 2, 3}, caùc toå hôïp chaäp 2 cuûa Ω laø {1,2}, {1,3}, {2,3}.

k n

Soá löôïng toå hôïp chaäp k cuûa n phaàn töû ñöôïc kyù hieäu laø C ñöôïc tính theo coâng

thöùc sau ñaây.

k = n

! n k n k −

Soá löôïng caùc toå hôïp chaäp k cuûa n phaàn töû ñöôïc xaùc ñònh theo coâng thöùc:

IV.3.2 Thuaät toaùn

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

Thuaät toaùn sau phaùt sinh taát caû caùc toå hôïp chaäp k cuûa taäp {1, 2, ..., n}. Töông töï thuaät toaùn phaùt sinh chænh hôïp, thuaät toaùn naày goïi ñeä qui vôùi tham soá i, khôûi ñaàu i=1 vaø ao=0.

- Khôûi taïo ao=0 - Goïi haøm Phatsinh(a, n, k, 1) - Haøm ñeä qui Phatsinh(a, n, k, i)

ai=ai-1 Trong khi ai < n-k+i laøm

goïi ñeä qui Phatsinh(a, n, k, i+1)

ai=ai+1 Neáu i

Cuoái laëp

V. MOÄT SOÁ ÖÙNG DUÏNG KHAÙC

Trong phaàn naày chuùng ta tìm lôøi giaûi ñeä qui cho moät soá baøi toaùn ñaõ ñöôïc giaûi trong caùc chöông khaùc maø khoâng caàn duøng kyõ thuaät ñeä qui. Moät soá lôøi giaûi ñöôïc trình baøy ôû ñaây maëc duø khoâng hieäu quaû veà maët thôøi gian chaïy nhöng raát ñôn giaûn vaø ñeïp. Khi kích thöôùc baøi toaùn khaù nhoû thì coù leû ñaây laø nhöõng thuaät toaùn khaù hay. Maët khaùc, caùc baøi giaûi naày cuõng laø minh hoïa cho caùch suy nghó vaø giaûi baøi toaùn moät caùch töï nhieân.

V.1 Tính toång

Vieäc tính toång n soá trong moät maûng moät chieàu (chaúng haïn nhö maûng goàm caùc

soá nguyeân) coù theå giaûi quyeát deã daøng baèng thuaät toaùn ñeä qui nhö sau:

- Neáu n<1 thì toång soá=0 - Ngöôïc laïi thì laøm

Tính toång a[0] + … + a[n-2] baèng ñeä qui Coäng giaù trò tính ñöôïc vôùi a[n-1]. Cuoái ngöôïc laïi

Thuaät toaùn coù theå caøi baèng moät haøm ñeä qui nhö sau.

return 0;

if(n<1) else return TongSo(a, n-1) + a[n-1]; long TongSo(int a[], int n) { }

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

V.2 Tìm phaàn töû lôùn nhaát, phaàn töû nhoû nhaát

Thuaät toaùn ñeä qui sau ñaây tìm chæ soá cuûa phaàn töû lôùn nhaát trong caùc soá a[0], a[1], …, a[n-1]. (Bieán csmax löu chæ soá caàn tìm.) Tröôøng hôïp tìm phaàn töû nhoû nhaát coù theå laøm hoaøn toaøn töông töï.

- Neáu n<1 thì csmax=-1 (maûng khoâng coù phaàn töû); - Ngöôïc laïi neáu n=1 thì csmax=0; - Ngöôïc laïi neáu n>1 thì laøm

tính csmax baèng ñeä qui cho a[0], a[1], …, a[n-2]

neáu a[csmax]

Sau ñaây laø caøi ñaët cho tröôøng hôïp tìm soá lôùn nhaát trong moät maûng caùc soá

nguyeân. Haøm ChiSoMax traû veà moät chæ soá cuûa phaàn töû lôùn nhaát cuûa maûng.

int csmax;

csmax = 0;

csmax = ChiSoMax(a, n-1); if(a[csmax] < a[n-1]) csmax = n-1;

if(n<1) csmax=-1; else if(n==1) else { } return csmax; int ChiSoMax(int a[], int n) { }

V.3 Saép xeáp theo thöù töï taêng hay giaûm

Chuùng ta trôû laïi baøi toaùn saép xeáp caùc soá trong moät maûng sao cho coù ñöôïc thöù töï taêng a[0]≤a[1] ≤ … ≤ a[n-1]. Tröôøng hôïp caàn saép xeáp theo thöù töï giaûm thì coù theå giaûi quyeát hoaøn toaøn töông töï.

V.3.1 Thuaät toaùn 1

Vieäc saép xeáp n phaàn töû theo thöù töï taêng coù theå thöïc hieän ñeäqui nhö sau:

Neáu n>1 thì Saép xeáp a[0], a[1], …, a[n-2] nhôø goïi ñeä qui Neáu a[n-2]>a[n-1] thì { neáu a[n-2]≤a[n-1] thì ñaõ saép xong } Ñoåi choã a[n-2] vaø a[n-1] Saép xeáp a[0], a[1], …, a[n-2] nhôø goïi ñeä qui Cuoái neáu { a[n-2]>a[n-1] } Cuoái neáu { n>1}

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui SapXep nhö sau.

int x;

x = a[n-2]; a[n-2] = a[n-1]; a[n-1] = x; SapXep(a, n-1); SapXep(a, n-1); if(a[n-2]>a[n-1]) { } if(n>1) { } void SapXep(int a[], int n) { }

V.3.2 Thuaät toaùn 2

Thuaät toaùn ñeä qui sau ñaây saép xeáp taêng döïa vaøo haøm ChiSoMax. Haøm naày traû veà chæ soá trong maûng cuûa phaàn töû lôùn nhaát cuûa maûng; haøm naày cuõng coù theå caøi ñaët ñeä qui nhö trình baøy beân treân.

Neáu n>1 thì Tìm csmax=ChiSoMax(a, n-1) { chæ soá cuûa phaàn töû lôùn nhaát trong caùc ptöû a[0], …, a[n-2] } Neáu a[csmax]>a[n-1] thì Ñoåi choã a[csmax] vaø a[n-1] Cuoái neáu Saép xeáp a[0], …, a[n-2] nhôø goïi ñeä qui Cuoái neáu { n>1 }

Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui SapXep_1 nhö sau.

int x, csmax;

void SapXep_1(int a[], int n) { if(n>1) { csmax = ChiSoMax(a, n-1); if(a[csmax]>a[n-1]) {

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

x = a[csmax]; a[csmax] = a[n-1]; a[n-1] = x;

} SapXep_1(a, n-1); } }

V.4 Ñeám caùc phaàn töû phaân bieät

Phaàn naày trình baøy caùch giaûi ñeä qui ñeå ñeám caùc phaàn töû phaân bieät trong maûng, caùc phaàn töû truøng nhau chæ ñeám moät laàn. Ví duï neáu maûng goàm 11 phaàn töû 19, 7, 7, 21, 23, -23, -21, -19, 1, 1, 7 thì keát quaû ñeám laø 8.

V.4.1 Thuaät toaùn 1

Thuaät toaùn ñeä qui sau ñaây duøng moät haøm xaùc ñònh xem phaàn töû x coù naèm

trong maûng a hay khoâng:

int XuatHienTrong(int a[], int n, int x).

Thuaät toaùn goàm caùc böôùc sau:

Neáu n<0 thì keát quaû ñeám = 0 Neáu n=1 thì keát quaû ñeám = 1 Neáu n>1 thì Goïi ñeä qui: kq1=Soá phaàn töû phaân bieät trong a[0], …, a[n-2] Neáu a[n-1] xuaát hieän trong a[0], …, a[n-2] thì keát quaû ñeám = kq1 Ngöôïc laïi keát quaû ñeám = kq1+1 Cuoái neáu

Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui DemPhanBiet nhö sau.

int i=0;

i++;

while(i

int XuatHienTrong(int a[], int n, int x) { } int DemPhanBiet(int a[], int n) { int ketqua, kq1; if(n<1) ketqua = 0;

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

ketqua = 1;

ketqua = kq1;

kq1 = DemPhanBiet(a, n-1); if(XuatHienTrong(a, n-1, a[n-1])) else ketqua = kq1+1;

else if(n==1) else { } return ketqua;

}

V.4.2 Thuaät toaùn 2

Thuaät toaùn treân ñaõ duøng theâm moät haøm tìm kieám ñeå bieát a[n] coù xuaát hieän trong a[1], a[2], …, a[n-1] hay khoâng. Sau ñaây laø moät caùch giaûi “thuaàn tuùy ñeä qui”. Tuy nhieân vieäc goïi ñeä qui coù theå bò thöïc hieän nhieàu laàn hôn.

Neáu n<0 thì keát quaû ñeám = 0 Neáu n=1 thì keát quaû ñeám = 1 Neáu n>1 thì Goïi ñeä qui: kq1=Soá phaàn töû phaân bieät trong a[0], …, a[n-2] Neáu a[n-1]=a[n-2] thì keát quaû ñeám = kq1 Ngöôïc laïi { a[n-1]≠ a[n-2] } Goïi ñeä qui: kq2=Soá phaàn töû phaân bieät trong a[0], …, a[n-3] Goïi ñeä qui: kq3=Soá phaàn töû phaân bieät trong a[0], …, a[n-3], a[n-1] Neáu kq2=kq3 thì keát quaû ñeám = kq1 ngöôïc laïi keát quaû ñeám = kq1+1 Cuoái ngöôïc laïi { a[n-1]≠ a[n-2] } Cuoái neáu

Thuaät toaùn coù theå ñöôïc caøi ñaët baèng haøm ñeä qui DemPhanBiet_1 nhö sau. Haøm traû veà keát quaû ñeám. Vieäc ñeám soá phaàn töû phaân bieät trong n-1 phaàn töû a[0], …, a[n- 3], a[n-1] vaãn duøng maûng a: giaù trò a[n-2] ñöôïc ghi nhôù vaøo bieán x (gaùn x=a[n-2]), thay taïm a[n-2] bôûi a[n-1] (gaùn a[n-2]=a[n-1]), goïi ñeä qui haøm ñeám kq3 := DemPhanBiet_1(a, n-1), sau ñoù traû laïi giaù trò cuõ cho a[n-2] (gaùn a[n-2]=x).

int ketqua, kq1, kq2, kq3; int x;

int DemPhanBiet_1(int a[], int n) { if(n<1) ketqua = 0;

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

ketqua = 1;

if(a[n-1]==a[n-2]) ketqua = kq1;

{ kq1 = DemPhanBiet_1(a, n-1); else { kq2 = DemPhanBiet_1(a, n-2);

/* Ñeám a[1], ..., a[n-3], a[n-1]; taïm thay a[n-2]=a[n-1] */

if(kq2==kq3) ketqua = kq1;

ketqua = kq1+1;

x = a[n-2]; a[n-2] = a[n-1]; kq3 = DemPhanBiet_1(a, n-1); a[n-2] = x; /* traû laïi giaù trò cuõ cho a[n-2] */ else }

} return ketqua;

else if(n==1) else /* n >= 2; a[n-2], a[n-1] hop le */ }

V.5 Tính luõy thöøa nhanh

Vieäc tính luõy thöøa baäc n (n nguyeân) coù theå tính nhanh baèng caùch traùnh vieäc tính laïi caùc pheùp toaùn. Ví duï ñeå tính x14, vì x14=(x7)*(x7) neân chæ caàn tính x7 moät laàn; cuõng töông töï vì x7=(x3)*(x3)*x neân chæ caàn tính x3 moät laàn, … Haøm LuyThua ñeä qui sau ñaây caøi ñaët thuaät toaùn naày.

float ret, xlast;

ret = 1/LuyThua(x, -n); if(n<0)

float LuyThua(float x, int n) { else if(n==0) ret = 1; else if(n==1) ret = x; else /* n > 1 */ if(n%2==0) {

Kyõ thuaät ñeä qui - Trần Đan Thư, Khoa CNTT, Trường ĐHKHTN, ĐHQGTP HCM

xlast = LuyThua(x, n/2); ret = xlast*xlast;

{ } else { xlast = LuyThua(x, (n-1)/2);

}

} return ret;

ret = xlast*xlast*x; }