Chơng III. Kỹ thuật lập trình đơn thể
I. Định nghĩa và sử dụng đơn thể
1. Khái niệm phân loại
Khái niệm: Đơn thể (hay Module) là một đoạn chơng trình đợc viết theo
một cấu trúc nào đó, giải quyết một vấn đề tơng đối độc lập của bài toán.
Khi viết một chơng trình, chúng ta có thể triển khai theo hai cách:
Cách 1: Toàn bộ các lệnh của chơng trình đợc viết trong hàm main().
Các lệnh đợc viết theo trình tự để giải quyết bài toán đặt ra.
Cách 2: Chơng trình đợc tạo thành từ nhiều đơn thể khác nhau. Các đơn
thể thực hiện những nhiệm vụ tơng đối độc lập và đợc lắp ghép lại thành ch-
ơng trình thông qua những lời gọi đơn thể trong hàm main().
u nhợc điểm:
- Với cách 1: sẽ thích hợp khi viết những chơng trình có kích thớc nhỏ.
Toàn bộ thuật toán đợc thể hiện trong một đoạn mã từ trên xuống dới. Tuy
nhiên, cách này không phù hợp với các chơng trình lớn do:
+ Kích thớc chơng trình cồng kềnh, khó kiểm soát, chỉnh sửa.
+ Các đoạn mã có thể lặp đi lặp lại, chơng trình dài không cần thiết.
- Với cách 2: Chơng trình đợc chia nhỏ thành các đơn thể khắc phục đợc
hai nhợc điểm cơ bản trên. Đặc biệt phù hợp với các chơng trình có kích thớc
lớn.
Trong C++, ta có hai loại đơn thể sau:
[1]. Các lớp đối tợng: Chơng trình bao gồm một số đoạn mã mô tả các
lớp các đối tợng nào đó sẽ sử dụng trong chơng trình chính. Loại đơn thể này đ-
ợc nghiên cứu trong nội dung môn học Lập trình hớng đối tợng.
[2]. Các hàm: Chơng trình đợc cấu tạo từ các hàm. Mỗi hàm thực thi một
nhiệm vụ tơng đối độc lập, trong đó có một hàm main đóng vai trò nh chơng
trình chính để sử dụng các hàm khác.
Trong phạm vi môn học, ta chỉ xem xét các đơn thể dới dạng các hàm.
2. Các đặc trng của hàm
Một hàm trong C++ có các đặc trng sau:
[1]. Tên hàm: do ngời lập trình tự đặt và có những đặc điểm sau:

Nhận xét:
- Trong pascal, ta có hai loại chơng trình con: thủ tục (procedure) và hàm
(function). Trong C++, chúng ta có duy nhất một loại chơng trình con (mà ta
gọi là đơn thể), đó là hàm.
- Một chơng trình trong C++ đợc cấu tạo từ các hàm, trong đó hàm main là
hàm bắt buộc phải có, đóng vai trò nh chơng trình chính.
4. Định nghĩa và sử dụng hàm
a. Cấu trúc một hàm:
Một hàm thờng có cấu trúc nh sau:
- Hàm không có giá trị trả về (hàm void):
- Hàm có giá trị trả về:
Biên soạn: Nguyễn Mạnh Cờng Trang
2
<Kiểu hàm> <Tên hàm> <([<kiểu đối> <tên đối>])>
{
//Các lệnh trong thân hàm;
}
Đề cơng chi tiết Kỹ thuật lập trình
Trong đó:
- <Kiểu hàm>: là kiểu giá trị trả về của hàm. Nếu hàm không có giá trị
trả về, ta dùng kiểu void. Ngợc lại, ta thờng sử dụng các kiểu chuẩn nh int,
float, double, char
- <Tên hàm>: do ngời dùng tự định nghĩa.
- [<kiểu đối> <tên đối>]: liệt kê danh sách các đối của hàm và kiểu dữ
liệu của đối (nếu hàm có đối).
VD1: hàm tính n! đợc viết theo 2 dạng: có và không có giá trị trả về:
Nhận xét:
- Hai điểm khác nhau cơ bản giữa hai loại hàm này là: Kiểu trả về (long và
void) và câu lệnh cuối hàm (return kq; và cout<<kq;)
- Nếu hàm có giá trị trả về thì trong thân hàm thờng dùng lệnh:




+
+++++
lẻ n nếu
chẵn n nếu
1
2
1

2
1
2
1
2
1
1
2
32
n
n
Một vấn đề đặt ra là: khi nào thì viết hàm dới dạng có giá trị trả về, khi
nào thì viết hàm không có giá trị trả về?
Nói chung, tuỳ thuộc vào bài toán cụ thể ta có thể quyết định điều này,
tuy nhiên:
- Nếu ta chỉ dùng hàm để thực thi một công việc nào đó mà kết quả của nó
chỉ cần đợc kết xuất ra màn hình là đủ thì hàm thờng đợc viết dới dạng không
có giá trị trả về.
- Nếu kết quả trả về của hàm có thể đợc dùng trong những công việc tiếp

{
kq=1; int Mau = 1;
for(int i=1; i<=n; i++)
{
Mau *=2;
kq+=1/Mau;
}
cout<<kq;
}
#include
.
//Các hàm đặt ở đây

void main()
{
Thân hàm main;
}
#include
.
//Nguyên mẫu của hàm đặt ở đây

void main()
{
Thân hàm main;
}
//Các hàm đặt ở đây
Đề cơng chi tiết Kỹ thuật lập trình
Cách 2: Các hàm đặt trong th viên:
B1: Viết các hàm (trừ hàm main()) trong một file sau đó lu dới định
dạng .h. File này thờng đợc gọi là file th viện. (để thuận tiện cho việc soát lỗi,

#include <conio.h>
#include <stdio.h>
#include <iostream.h>
#include <C:\TC\BIN\ TV.h
void main()
{
int a;
cout<< Nhập a ;
cin>>a;
if (NT(a) == 0)
cout<< Số <<a<< Không phải nguyên tố ;
else
{
cout<< Số <<a<< là số nguyên tố ;
cout<< Giai thừa của <<a<< là <<GT(a);
}
getch();
}
Chú ý:
Biên soạn: Nguyễn Mạnh Cờng Trang
5
Đề cơng chi tiết Kỹ thuật lập trình
- Các file th viện .h không nhất thiết phải có các chỉ thị tiền xử lý #include

- Không thể soát lỗi bằng cách bấm F9 trong file th viện .h.
c. Sử dụng hàm
Để nắm cách sử dụng hai loại hàm trên, ta xét cách sử dụng các biến và
các lệnh trong chơng trình.
Giả sử ta xét a, b là một biến và gets() là một lệnh có trong chơng trình.
khi đó:

Biên soạn: Nguyễn Mạnh Cờng Trang
6
Đề cơng chi tiết Kỹ thuật lập trình
+ Muốn biến này tồn tại trong suốt thời gian chơng trình làm việc, ta cần
thêm từ khóa static trớc khai báo biến để khai báo biến dới dạng biến tĩnh.
VD1: Xét ví dụ sau:
int x;
void Ham(int a)
{
cout<< Biến x trong hàm <<x; //bien toan cuc
if (a%2==0)
{ int x=5; x+= a;
cout<< Biến x trong hàm << x; // bien cuc bo
}
}
void main()
{
x=1; int a = 2;
Ham(a);
cout<< Biến x trong hàm main <<x; //bien toan cuc
int x = 3;
cout<< Biến x trong hàm main <<x; //bien cuc bo
getch();
}
Nhận xét:
- Biến x dới dạng toàn cục có phạm vi hoạt động trong toàn bộ chơng trình,
kể từ khi khai báo.
- Nếu trong một khối có khai báo biến cục bộ trùng tên với viến toàn cục
thì kể từ khi khai báo, khối đó sẽ sử dụng biến cục bộ mà không sử dụng biến
toàn cục.

a) truyền tham chiếu b) Truyền tham trị
2. Truyền tham số
Nếu chơng trình viết trong các file có phần mở rộng .h, ta có duy nhất
một cách truyền tham số: Truyền theo tham trị. Từ C++3.0 trở lên, cho phép sử
dụng cả hai cách truyền tham số trong các chơng trình viết dới dạng các file
.CPP.
Xét trờng hợp ta có các biến thông thờng (không phải là biến con trỏ)
- Nếu biến đợc truyền dới dạng thông thờng thì cách truyền đó là truyền
theo tham trị.
- Nếu ta không truyền biến vào hàm mà thay vào đó, ta truyền địa chỉ của
biến vào thì đó là cách truyền tham chiếu.
VD: int a=3, b=5;
Ham (&a, b);
Khi đó biến a đợc truyền vào hàm dới dạng tham chiếu; biến b đợc truyền
vào hàm dới dạng tham trị.
Xét trờng hợp ta có các biến con trỏ.
Vì bản thân con trỏ thờng chứa địa chỉ của biến nào đó (mà nó trỏ tới)
nên khi truyền con trỏ vào hàm thì mặc nhiên đã là truyền theo dạng tham
chiếu.
VD: int a, *p;
a = 5; p = & a;
Ham(p);
Khi đó biến p đợc truyền vào hàm nhng thực chất là ta đã chuyền địa chỉ
của a vào hàm. Vậy có thể coi đây là trờng hợp truyền biến a vào hàm dới dạng
tham chiếu (tức sau khi ra khỏi hàm, biến a có thể bị thay đổi giá trị).
VD1: Xét hàm sau:
int tang(int a)
{
a++;
}

cout<< Giá trị b sau khi gọi hàm <<b;
getch();
}
III. Kỹ thuật đệ quy
1. Khái niệm về đệ quy
Trong C++, một hàm có thể gọi đến chính nó. Tính chất này của hàm gọi
là tính đệ quy. Khi một hàm gọi đến chính nó, hàm đợc viết theo kiểu đệ quy.
VD: Xét hàm tính n!. Ta có định nghĩa sau: n! = n * (n-1)! .
Hàm lặp:
long GT(int n)
{
long kq=1;
if (n==0 || n==1)
kq=1;
else
for (int i=1; i<=n; i++)
kq *=i;
return kq;
}
Hàm đệ quy:
long GT(int n)
{
if (n==1)
return 1;
else
return GT(n-1) * n;
}
Thực hiện: Giả sử n =3. Khi đó, quy trình thực hiện nh sau:
Biên soạn: Nguyễn Mạnh Cờng Trang
9

Bản sao 1 Bản sao n
Bỏ qua lệnh
gọi đệ quy

Bắt đầu :
tính 3!
Gọi đệ quy Gọi đệ quy Gọi đệ quy
Kết thúc
Return 1*2*3
Hàm GT(2) Hàm GT(1)
Bỏ qua lệnh
gọi đệ quy
Return 1Return 1*2
Đề cơng chi tiết Kỹ thuật lập trình
u nhợc điểm của phơng pháp đệ quy:
- Chơng trình ngắn gọi, dễ hiểu.
- Quá trình dịch phức tạp.
- Nói chung, tốn nhiều không gian nhớ hơn lặp.
Phơng pháp đệ quy đặc biệt thích hợp với một số bài toán nh duyệt cây,
đồ thị Tuy nhiên, nói chung ta nên ít sử dụng đệ quy khi viết chơng trình do
các nhợc điểm trên.
2. Thiết kế chơng trình theo kiểu đệ quy.
Các bài toán áp dụng giải thuật đệ quy thờng có đặc điểm sau:
- Bài toán dễ dàng giải quyết trong một số trờng hợp riêng ứng với các giá
trị đặc biệt của tham số. Trong trờng hợp này, ta có thể giải quyết bài toán mà
không cần gọi đệ quy. Ta gọi trờng hợp này là trờng hợp suy biến.
- Trong trờng hợp tổng quát, bài toán có thể quy về bài toán cùng dạng nh-
ng giá trị của tham số thay đổi. Và sau một số hữu hạn bớc biến đổi đệ quy, sẽ
dẫn tới trờng hợp suy biến.
Giả sử bài toán tính n!, dễ dàng thấy:

return n * GT(n-1);
Sau khi thiết kế, việc lập hàm đệ quy trở lên rất đơn giản.
VD2. Dãy số Catalan đợc phát biểu đệ quy nh sau:
C
1
= 1;
C
n
=


=

1
1
n
i
ini
CC
Hãy xây dựng hàm đệ quy tìm số CataLan thứ n.
Hàm đệ quy đợc thiết kế nh sau:
Bớc 1:
- Suy biến: n = 1; Công thức suy biến: C
n
= 1;
- Không suy biến: n khác 1; công thức tổng quát: C
n
=



C+=CataLan(i)*CataLan(n-i);
return C;
}
}

3. Đệ quy và các dãy truy hồi
Khái niệm: Một dãy truy hồi là dãy mà các số hạng đứng sau đợc định
nghĩa dựa trên số hạng đứng trớc của dãy.
VD: Cho dãy sau:
a[1] = 1;
a[n] = a[n-1] * n;
Dễ dàng thấy đây chính là dãy các giai thừa của các số tự nhiên: 1!, 2!,
3!, 4!
Hoặc dãy các số Fibonacci:
A[1] = 1;
A[2] = 1;
A[n] = A[n-1] + A[n-2] (với n>2).
Với các dãy truy hồi, ta hoàn toàn có thể dùng các thuật toán lặp để tính.
Tuy nhiên các giải thuật đệ quy thờng đợc áp dụng rất hiệu quả trên các dãy
truy hồi .
4. Một số ví dụ về đệ quy
VD1: USCLN của hai số nguyên a, b đợc định nghĩa nh sau:
USCLN(a, b) = a nếu b =0
= USCLN(b, a%b) nếu b khác 0.
Viết hàm lặp và đệ quy để tính USCLN của hai số nguyên a, b.
Hàm lặp:
int USCLN_Lap(int a, int b)
{
int Sodu;
while (y !=0)

F[0] = F[1] = 1;
F[i] = F[i-1] + F[i-2];
VD: 1, 1, 2, 3, 5, 8, 13
Viết hàm đệ quy tìm số Fibonacci thứ n.
Bớc 1:
- Suy biến: n <=1; công thức suy biến: Fibo(n) = 1;
- Không suy biến: n >1; công thức tổng quát: Fibo(n) = Fibo(n-1) +
Fibo(n-2).
Bớc 2:
if(n<=1)
return 1;
else
return Fibo(n-1) + Fibo(n-2);
Lập trình:
int Fibo(int n)
{
if(n<=1)
return 1;
else
return Fibo(n-1) + Fibo(n-2);
Biên soạn: Nguyễn Mạnh Cờng Trang
1
4
§Ò c¬ng chi tiÕt Kü thuËt lËp tr×nh
}
Biªn so¹n: NguyÔn M¹nh Cêng Trang
1
5