0
K
K
Ỹ
Ỹ
THU
THU
Ậ
Ậ
T L
T L
Ậ
Ậ
P TRÌNH
P TRÌNH
KỸ THUẬT PHÁT TRIỂN CHƯƠNG TRÌNH
NỘI DUNG

Hàm và Thủ tục

Phát triển chương trình bằng phương pháp tinh
chỉnh dần từng bước.

Định nghĩa và sử dụng hàm trong ngôn ngữ C

Hàm đệ quy
1
KH
KH
Á
Á

– 5! = 5 * 4!
– 4! = 4 * 3! ...
• Có thể thực hiện gọi đệ qui
• Điều kiện kết thúc gọi đệ qui: 1! = 0! = 1
– 2! = 2 * 1! = 2 * 1 = 2;
– 3! = 3 * 2! = 3 * 2 = 6;
3

? Bài toán nào có thể dùng đệ quy?

Hàm đệ quy thường được viết theo thuật toán sau:
if (trường hợp suy biến) {
Lời giải bài toán trong trường hợp suy biến;
}
else {
Gọi đệ quy tới hàm với giá trị khác của tham số;
}
4

Ví dụ 1. Hàm giai thừa
V
V
Í
Í
D
D
Ụ
Ụ
V
V

Final va lue = 120
5! = 5 * 24 = 120 is re turned
4! = 4 * 6 = 24 is re turne d
2! = 2 * 1 = 2 is returne d
3! = 3 * 2 = 6 is re tu rn ed
1 returne d
5 * 4!
1
4 * 3!
3 * 2!
2 * 1!
5!
5 * 4!
1
4 * 3!
3 * 2!
2 * 1!
fig05_14.c (Part 1 of 2)
fig05_14.c (Part 1 of 2)
1
/* Fig. 5.14: fig05_14.c
2
Recursive factorial function */
3
#include <stdio.h>
4

5
long factorial( long number ); /* function prototype */
6
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
22
/* recursive definition of function factorial */
23
long factorial( long number )
24
{
25
/* base case */
26
if ( number <= 1 ) {
27
return 1;
28
} /* end if */
29
else { /* recursive step */
30
return ( number * factorial( number - 1 ) );

• Các con thỏ không bao giờ chết.
• Hai tháng sau khi ra đời một cặp thỏ mới sẽ sinh ra một cặp
thỏ con (1 đực, 1 cái).
• Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh
được một cặp mới.
• Giả sử bắt đầu từ một cặp mới ra đời thì đến tháng thứ n sẽ có
bao nhiêu cặp?
9
V
V
Í
Í
D
D
Ụ
Ụ
V
V
Ề
Ề
CHƯƠNG TRÌNH Đ
CHƯƠNG TRÌNH Đ
Ệ
Ệ
QUY
QUY

function Fib(n: integer):integer;
begin
if n = 0 then Fib := 0 else

+
return
1 /* Fig. 5.15: fig05_15.c
2 Recursive fibonacci function */
3 #include <stdio.h>
4

5 long fibonacci( long n ); /* function prototype */
6

7 /* function main begins program execution */
8 int main()
9 {
10 long result; /* fibonacci value */
11 long number; /* number input by user */
12

13 /* obtain integer from user */
14 printf( "Enter an integer: " );
15 scanf( "%ld", &number );
16

17 /* calculate fibonacci value for number input by user */
18 result = fibonacci( number );
19

20 /* display result */
21 printf( "Fibonacci( %ld ) = %ld\n", number, result );
22
23 return 0; /* indicates successful termination */

37
38 } /* end function fibonacci */

13
V
V
Í
Í
D
D
Ụ
Ụ
V
V
Ề
Ề
CHƯƠNG TRÌNH Đ
CHƯƠNG TRÌNH Đ
Ệ
Ệ
QUY
QUY

Ví dụ 3. Đường Hilbert
• Đường Hilbert cấp 0 là hình rỗng.
• Đường Hilbert cấp i + 1 được thành lập từ 4 đường cấp i được
quay theo 1 góc thích hợp và nối với nhau bởi 3 đoạn thẳng.
14
V
V

CHƯƠNG TRÌNH Đ
Ệ
Ệ
QUY
QUY

x, y - biến toạ độ; h - độ dài của đoạn nối; plot - vẽ từ vị trí hiện tại
xác định bởi x, y

procedure A(i:integer);
begin
if i > 0 then
begin
B(i−1); x := x − h; plot;
A(i−1); y := y − h; plot;
A(i−1); x := x + h; plot;
D(i−1);
end;
16
V
V
Í
Í
D
D
Ụ
Ụ
V
V
Ề

Ề
Ề
CHƯƠNG TRÌNH Đ
CHƯƠNG TRÌNH Đ
Ệ
Ệ
QUY
QUY
18
B
B
À
À
I TO
I TO
Á
Á
N TH
N TH
Á
Á
P H
P H
À
À
N
N
Ộ
Ộ
I

Ộ
Ộ
I
I

Trường hợp 1 đĩa: Chuyển đĩa từ cột A sang cột C

Trường hợp 2 đĩa:
• Chuyển đĩa thứ nhất (tính từ đĩa trên cùng, hay đĩa nhỏ nhất)
từ cột A sang cột B
• Chuyển đĩa thứ 2 từ cột A sang cột C
• Chuyển đĩa thứ nhất từ cột B sang cột C.

Trường hợp n đĩa (n >2)
• Chuyển (n−1) đĩa từ cột A sang cột B
• Chuyển đĩa thứ n từ cột A sang cột C
• Chuyển (n − 1) đĩa từ cột B sang cột C