Bài giảng Kỹ thuật lập trình Chương 1: Võ Quang Hoàng Khang (Chi Tiết)

Võ Quang Hoàng Khang

1  Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)?

2

3  Một hàm được gọi có tính đệ quy nếu trong thân của hàm đó có lệnh gọi lại chính nó.

 Ví dụ S(n) được tính thông qua S(n-1)

 2 điều kiện quan trọng Tồn tại bước đệ quy. Điều kiện dừng.

4  B1. Tham số hoá bài toán.  B2. Phân tích trường hợp chung: đưa bài toán về dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghĩa dần tiến đến trường hợp suy biến.

 B3. Tìm trường hợp suy biến.

5 Hàm đệ quy gồm 2 phần:

 Phần cơ sở: Điều kiện để thoát khỏi đệ quy

(điểm dừng)

 Phần đệ quy: gọi đến chính nó với giá trị mới

 Ví dụ:

của tham số nhỏ hơn giá trị ban đầu.

6 • Công thức truy hồi tính

• Hàm đệ quy: long GiaiThua( int n ) {

if(n==0)

return 1;

else

return GiaiThua(n-1)*n;

7

}

• Hàm đệ quy nhập mảng 1 chiều:

void NhapMang(int a[],int n) {

if(n>0) {

NhapMang(a,n-1); cin>>a[n-1];

}

8

}

9 Trong thân hàm có duy nhất 1 lời gọi hàm gọi lại chính nó một cách tường minh.

TenHam () {

if (điều kiện dừng) {

//Trả về giá trị hay kết thúc công việc

} //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có)

}

10 Ví dụ 1: Tính  Điều kiện dừng: S(0) = 0.  Công thức truy hồi: S(n) = S(n-1) + n.

if(n==0) //điểm dừng

int TongS (int n) {

return 0;

return ( TongS(n-1) + n );

}

11 Ví dụ 2: Tính n!

long GiaiThua(int n)

if (n==0)

//điểm dừng

{

return 1;

return n*GiaiThua(n-1);

else

}

với n=5

12

TenHam () {

if (điều kiện dừng) {

//Trả về giá trị hay kết thúc công việc

} //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có) . . . TenHam (); //Thực hiện các công việc (nếu có)

}

Trong thân hàm có 2 lời gọi hàm gọi lại chính nó một cách tường minh.

13

Ví dụ: Tính số hạng thứ n của dãy Fibonaci được định nghĩa f0=f1=1 ; bởi công thức truy hồi: fn = fn-1 + fn-2 ; (n>1)

Điều kiện dừng: f(0) = f(1) = 1.

long Fibonaci(int n) {

if(n==0 || n==1)

return Fibonaci(n-1)+ Fibonaci(n-2);

return 1;

}

14 Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp.

TenHam () {

for (int i = 1; i<=n; i++) {

//Thực hiện một số công việc (nếu có) if (điều kiện dừng) { . . .

//Trả về giá trị hay kết thúc công việc

} else {

//Thực hiện một số công việc (nếu có) TenHam ();

}

15

}

Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như

sau: X0 =1 ;

Xn = n2X0 + (n-1)2X1 + … + 12Xn-1 ; (n≥1)

Điều kiện dừng: X(0) = 1.

if(n==0)

long TinhXn(int n) {

return 1; long s = 0; for (int i=1; i<=n; i++)

s = s + i * i * TinhXn(n-i);

return s;

16

}

Trong thân của hàm này có lời gọi hàm đến hàm kia và ngược lại.

17

TenHam2 (); TenHam1 () {

//Thực hiện một số công việc (nếu có) …TenHam2 (); //Thực hiện một số công việc (nếu có)

} TenHam2 () {

//Thực hiện một số công việc (nếu có) …TenHam1 (); //Thực hiện một số công việc (nếu có)

}

18

(n>0)

Ví dụ: Tính số hạng thứ n của hai dãy {Xn}, {Yn} được định nghĩa như sau: X0 =Y0 =1 ; Xn = Xn-1 + Yn-1; Yn = n2Xn-1 + Yn-1; (n>0)

- Điều kiện dừng: X(0) = Y(0) = 1.

long TinhYn(int n); long TinhXn (int n) {

if(n==0)

return 1;

return TinhXn(n-1) + TinhYn(n-1);

} //---------------------------------------------------------------------- long TinhYn (int n) {

if(n==0)

return 1;

19 return nnTinhXn(n-1) + TinhYn(n-1);

}

 Thay vì sử dụng lời giải đệ quy cho một bài toán, ta có thể thay thế bằng lời giải không đệ quy (khử đệ quy) bằng phương pháp lặp.

 Ưu và khuyết điểm của đệ quy:

Ưu điểm

Khuyết điểm

Thuận lợi cho việc biểu diễn bài toán Gọn (đối với chương trình)

Có khi không được tối ưu về thời gian Có thể gây tốn bộ nhớ

 Trong lập trình HẠN CHẾ viết hàm đệ quy nếu thấy không

cần thiết.

20

Ví dụ 1: Vi trùng cứ 1 giờ lại nhân đôi. Vậy sau 5 giờ sẽ có mấy con vi trùng nếu ban đầu có 2 con? *Giải pháp: Gọi Vh là số vi trùng tại thời điểm h. *Ta có:

•Vh= 2Vh-1 •V0= 2

Đệ quy tuyến tính với V(h)=2V(h-1) và điều kiện dừng V(0) = 2

21

Ví dụ 2: Gửi ngân hàng 1000 USD, lãi suất 12%/năm.

Số tiền có được sau 30 năm là bao nhiêu? Giải pháp:

•Gọi Tn là số tiền có được sau n năm. •Ta có:

Tn= Tn-1+ 0.12Tn-1= 1.12Tn-1 V(0) = 1000

Đệ quy tuyến tính với T(n)=1.12*T(n-1) và điều kiện dừng V(0) = 1000

22 Ví dụ 3: Bài toán tháp Hà Nội

Chuyển một chồng n đĩa với kích thước khác nhau từ cột A sang cột C theo nguyên tắc:

 Mỗi lần chỉ chuyển 1 đĩa.  Không được đặt đĩa lớn trên

đĩa nhỏ.

 Có thể dùng cột B làm cột

trung gian B

23

* Tham số hoá bài toán: HaNoi (n, A, B, C) n: Số đĩa.

Trong đó:

A: Cọc nguồn

B: Cọc trung gian

C: Cọc đích

(A, B, C có kiểu ký tự)

24

Giải thuật đệ quy bài toán Tháp Hà Nội: * Trường hợp suy biến:

Nếu n = 1 thì chuyển đĩa từ A qua C

* Trường hợp chung (n  2):

Thử với n=2:

+ Chuyển đĩa thứ nhất từ A sang B

+ Chuyển đĩa thứ hai từ A sang C

+ Chuyển đĩa thứ nhất từ B sang C

 Tổng quát:

+ Chuyển (n -1) đĩa từ A sang B (C làm trung gian)

+ Chuyển 1 đĩa từ A sang C (B làm trung gian)

+ Chuyển (n -1) đĩa từ B sang C (A làm trung gian)

25 1 đĩa

B

C

A

1 đĩa

B

C

A

2 đĩa

B

C

A

2 đĩa

B

C

A

2 đĩa

B

C

A

2 đĩa

B

C

A

N đĩa

B

C

A

N đĩa

B

C

A

N đĩa

B

C

A

Giải thuật đệ quy bài toán Tháp Hà Nội:

void HaNoi (int n, char A, char B, char C) {

if (n==1)

cout<

else {

HaNoi(n-1, A, C, B); HaNoi(1, A, B, C); HaNoi(n-1, B, A, C);

}

35 Bài tập 1: Viết hàm đệ quy biểu diễn nhị phân của 1 số nguyên n. Ví dụ: n=13  1101

Xuất dạng nhị phân của n:

- Nếu (n/2 > 0) thì xuất dạng nhị phân của n/2;

- Xuất (n%2);

void XuatNhiPhan(int n) {

if (n/2>0)

XuatNhiPhan(n/2);

}

cout<

36 Bài tập 2: Chuyển số giây thành giờ, phút, giây.

void DoiGio(int n, int &h, int &m, int &s) {

if (n<60)

s=n;

else if (n/3600>0) {

Ví dụ: nhập 3665 -> 1: 1: 5 giây

h=n/3600; DoiGio(n%3600, h, m, s);

} else {

m=n/60; DoiGio(n%60, h, m, s);

}

37

}

Bài tập 3: Tính tổng các chữ số của một số nguyên n.

+ Nếu (n<10) thì Tổng = n

+ Nếu (n>=10) thì Tổng = n%10 + Tổng các chữ số của n/10

Ví dụ: n=1980 =>Tổng=1+9+8+0=18

int Tong(int n) {

if (n<10)

else

return n;

return n%10 + Tong(n/10);

}

38 Bài tập 4: Xuất ngược các chữ số của số nguyên n.

+ Nếu n<10 thì Xuất n + Nếu n>=10 thì Xuất n%10 và Xuất ngược n/10

void XuatSoNguoc(int n) {

if (n<10)

cout<

else {

Ví dụ n=1980  xuất 0891

cout<
}

} 39

- Trường hợp chung:

+ In ký tự cuối cùng của chuỗi X.

+ Lấy phần chuỗi còn lại.

- Trường hợp suy biến: Nếu chuỗi rỗng thì không làm gì cả.

void InNguoc(char X) {

static int len=strlen(X); if (len>0) {

Bài tập 5: Viết hàm đệ quy in đảo ngược chuỗi X

cout<
}

40

}

Bài tập 6: Viết hàm đệ quy kiểm tra xem một số có phải số nguyên tố không

bool isPrime(int N) {

if (N==1)

return true; int static M=N-1; if (M==1)

return true;

else if (N%M==0) return false;

else {

M--; isPrime(N);

}

41

}

Bài tập 7: In hình tam giác sau bằng cách đệ quy

if (n>1)

void InSao(int n) {

InSao(n-1);

cout<<"";

for (int i=0; i
cout<
}

42

Bài tập 8: Cho mảng a có n phần tử, tính tổng các phần tử trong mảng bằng đệ quy

Điều kiện dừng: nếu n=0 thì sum(a,n)=0 Giải thuật chung: sum (a,n) = a[n-1] + sum(a, n-1), n>0

43

Bài tập 9: Cho mảng a có n phần tử, tìm giá trị lớn nhất trong mảng bằng đệ quy

Điều kiện dừng: Mảng 1 phần tử thì trị lớn nhất là a[0]

Giải thuật chung:

Max (a,n) = a[0] , n=1

a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1), n>1

44

1. Viết hàm đệ quy tính: xn 2. Viết hàm đệ quy đếm số lần xuất hiện của kí tự ch trong

3. Viết hàm đệ quy tính giá trị phần tử thứ k của dãy số sau: 1 2 3 6 11 20 37 68 125 …. Sau đó viết chương trình in ra màn hình n số của dãy số trên.

chuỗi S.

45

1. Viết hàm đệ quy tính tổng S=1+2+3+4+…+n (với n>0) 2. Viết hàm đệ quy tính n! (với n>=0) 3. Viết hàm đệ quy tìm số hạng thứ k của dãy Fibonaci. Sau đó

viết chương trình in ra màn hình n số hạng của dãy.

4. Viết hàm đệ quy tìm ước số chung lớn nhất của 2 số nguyên

dương.

5. Viết hàm đệ quy giải quyết bài toán tháp HÀ NỘI. 6. Viết hàm đệ quy biểu diễn nhị phân của 1 số nguyên n. 7. Viết hàm đệ quy chuyển số giây thành giờ, phút, giây. Ví dụ:

nhập 3665 -> 1: 1: 5 giây

8. Viết hàm đệ quy tính tổng các chữ số của một số nguyên n.

46

9. Viết hàm đệ quy xuất ngược các chữ số của số nguyên n. 10.Viết hàm đệ quy in đảo ngược chuỗi X. 11.Viết hàm đệ quy kiểm tra xem một số n có phải số nguyên

tố không?

12.Cho mảng a có n phần tử, tính tổng các phần tử trong mảng

bằng đệ quy.

13.Cho mảng a có n phần tử, tìm giá trị lớn nhất trong mảng

bằng đệ quy.

14.Làm các bài tập trên mảng 1 chiều, sử dụng kỹ thuật đệ quy. 15.Viết hàm đệ quy in các ước số của số nguyên dương n.

47

Bài giảng Kỹ thuật lập trình: Chương 1 - Võ Quang Hoàng Khang

Chủ đề:

1

 Cho S(n) = 1 + 2 + 3 + … + n =>S(10)? S(11)?

2

3

 Một hàm được gọi có tính đệ quy nếu trong thân của hàm đó có lệnh gọi lại chính nó.

4

 B1. Tham số hoá bài toán.  B2. Phân tích trường hợp chung: đưa bài toán về dạng bài toán cùng loại nhưng có phạm vi giải quyết nhỏ hơn theo nghĩa dần tiến đến trường hợp suy biến.

5

Hàm đệ quy gồm 2 phần:

 Phần đệ quy: gọi đến chính nó với giá trị mới

6

• Công thức truy hồi tính

7

• Hàm đệ quy nhập mảng 1 chiều:

NhapMang(a,n-1); cin>>a[n-1];

8

9

Trong thân hàm có duy nhất 1 lời gọi hàm gọi lại chính nó một cách tường minh.

10

Ví dụ 1: Tính  Điều kiện dừng: S(0) = 0.  Công thức truy hồi: S(n) = S(n-1) + n.

}

11

Ví dụ 2: Tính n!

12

13

14

Trong thân của hàm có lời gọi hàm gọi lại chính nó được đặt bên trong vòng lặp.

//Thực hiện một số công việc (nếu có) TenHam ();

15

Ví dụ: Tính số hạng thứ n của dãy {Xn} được định nghĩa như

16

17

//Thực hiện một số công việc (nếu có) …TenHam2 (); //Thực hiện một số công việc (nếu có)

18

long TinhYn(int n); long TinhXn (int n) {

} //---------------------------------------------------------------------- long TinhYn (int n) {

19 return n*n*TinhXn(n-1) + TinhYn(n-1);

}

Ưu điểm

Khuyết điểm

20

•Vh= 2Vh-1 •V0= 2

*Đệ quy tuyến tính với V(h)=2*V(h-1) và điều kiện dừng V(0) = 2

21

•Gọi Tn là số tiền có được sau n năm. •Ta có:

22

Ví dụ 3: Bài toán tháp Hà Nội

23

24

25

1 đĩa

B

C

A

1 đĩa

B

C

A

2 đĩa

B

C

A

2 đĩa

B

C

A

2 đĩa

B

C

A

2 đĩa

B

C

A

N đĩa

B

C

A

19 return nnTinhXn(n-1) + TinhYn(n-1);

Đệ quy tuyến tính với V(h)=2V(h-1) và điều kiện dừng V(0) = 2