Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
MỤC LỤC
MỤC LỤC ............................................................................................................................... 1
.................................................................................................................................................. 2
Lời nói đầu .............................................................................................................................. 3
Chương 1 ................................................................................................................................. 4
Một số kỹ thuật – phong cách lập trình tốt ............................................................................. 4
0.1 Cách đặt tên cho biến hàm .......................................................................................... 4
0.2 Phong cách viết mã nguồn .......................................................................................... 6
0.3 Tối ưu sự thực thi mã nguồn ....................................................................................... 8
Kỹ thuật đệ quy ..................................................................................................................... 16
1.1 Kỹ thuật đệ quy ......................................................................................................... 16
1.2 Xây dựng một chương trình đệ quy .......................................................................... 20
1.3 Các ví dụ đệ quy ........................................................................................................ 21
1.4 Khử đệ quy ................................................................................................................ 27
1.4.1 Tìm hiểu cơ chế thực hiện hàm đệ quy ............................................................. 27
1.4.2 Các trường hợp khử đệ quy đơn giản ................................................................ 29
1.4.3 Khử đệ quy dùng stack ...................................................................................... 31
Bài toán liên quan tổ hợp ...................................................................................................... 37
2.1 Phương pháp sinh ...................................................................................................... 37
2.1.1 Bài toán sinh dãy nhị phân độ dài n .................................................................. 37
2.1.2 Bài toán liệt kê tập con k phần tử ...................................................................... 39
2.1.3 Bài toán liệt kê các hoán vị ................................................................................ 42
2.2 Thuật toán quay lui (Back Tracking) ........................................................................ 45
2.2.1 Thuật toán quay lui liệt kê dãy nhị phân n ........................................................ 47
2.2.2 Thuật toán quay lui liệt kê tập con k phần tử .................................................... 48
2.2.3 Thuật toán quay lui liệt kê hoán vị n phần tử .................................................... 50
2.2.4 Bài toán sắp xếp quân Hậu ................................................................................ 51
2.2.5 Bài toán mã đi tuần ............................................................................................ 57
Tìm kiếm và Sắp xếp ............................................................................................................. 63
Học phần kỹ thuật lập trình 2 được thiết kế dành cho sinh viên khoa công
nghệ thông tin ĐH Kỹ Thuật Công Nghệ, là phần tiếp nối với môn kỹ thuật lập trình
1. Mục đích của môn học là bổ sung những kỹ thuật lập trình đệ quy, khử đệ quy,
các bài toán trên tập hợp, phương pháp sinh, kỹ thuật quay lui, tìm kiếm và sắp xếp
trên mảng, ngăn xếp và hàng đợi…Song song với phần lý thuyết là các ví dụ minh
họa cụ thể, cho phép sinh viên hiểu rõ vấn đề hơn.
Ngoài những kỹ thuật lập trình, giáo trình còn đề cập tới phương diện phong
cách lập trình trong chương 1. Việc sớm làm quen với phong cách lập trình sẽ hỗ
trợ sinh viên hoàn thiện kỹ năng viết chương trình.
Bài giảng được viết lần đầu tiên nên sẽ không tránh khỏi những sai sót. Kính
mong sự đóng góp của các giảng viên và sinh viên nhằm hoàn thiện phần bài giảng
này trong lần tái bản sau.
Tất cả những ý kiến đóng góp điều được trân trọng.
Xin chân thành cảm ơn!
Tác giả
3
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
Chương 1
Một số kỹ thuật – phong cách lập trình tốt
Một chương trình nguồn được xem là tốt không chỉ được đánh giá thông qua thuật
giải đúng và cấu trúc dữ liệu thích hợp. Mà còn phụ thuộc vào phong cách và kỹ thuật mã
hoá (coding) của người viết chương trình.
Nếu một người lập trình viết một chương trình tuy thực hiện đúng yêu cầu đặt ra
nhưng mã nguồn quá lộn xộn và phong cách lập trình cẩu thả, thì mã nguồn này sẽ gây khó
khăn cho chính người lập trình!
Đôi khi người mới lập trình không quan tâm đến vấn đề này do ban đầu chỉ làm
việc với chương trình nhỏ. Tuy nhiên, vấn đề phát sinh khi họ phải làm việc với dự án lớn
và chương trình lúc này không còn đơn giản vài chục dòng lệnh nữa. Nếu không rèn luyện
một phong cách và trang bị một số kỹ thuật lập trình tốt thì người lập trình đối mặt với
str/s C++ string string strFirstName
si short integer short siTables
i/n integer int iCars
int nCars
li long integer long liStars
f floating point float fPercent
d Double precision floating point double dMiles
ld long double precision floating
point
long double ldPI
sz Null terminated string char szName[NAME_LEN]
if Input file stream ifstream ifNameFile
is Input stream istream isInput
of Output file stream ofstream ofNameFile
os Output stream ostream osOut
S Struct struct sPoint {…}
C Class class CStudent {…}
w Word word wChar
u Unsigned..
m_ biến thành viên của hàm class CStudent
{
private:
string m_strName;
}
g_ biến toàn cục string g_strBuff
lp long pointer LPCTSTR lpszClassName
5
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
h handle trong windows HINSTANCE hInstance
Bảng 1.1: Minh họa tiền tố của cú pháp Hungary.
}
else
Action3();
ActionMain();
}
• Sử dụng khoảng trắng : chương trình sẽ dễ nhìn hơn.
int count;
for(count=0;count<10;count++)
{
printf(“%d”,count*count+count);
}
int count;
for (count = 0; count < 10; count++)
{
printf(“%d”, count * count + count);
}
• Tránh viết nhiều lệnh trên cùng một dòng :
if(a>5){b=a;a++;} if (a > 5)
{
6
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
b=a;
a++;
}
• Định nghĩa các hằng số : một thói quen là người lập trình không định nghĩa những hằng
số thường xuyên sử dụng. Dẫn đến những con số khó hiểu xuất hiện trong chương
trình, một số tài liệu lập trình gọi những con số này là “magic mumber”.
…
for(int i=0; i < 100; i ++)
A[i] = Rand(100);
Tham số ra: giá trị trả về
0: không phải số nguyên tố
1: là số nguyên tố
*/
….// phần thực hiện của hàm
}
Ví dụ chú thích cho biến
byte Image; // buffer ảnh
int Rows, Cols; // số dòng, số cột
7
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
int r, c; // dòng cột hiện hành
int PixelCount; // tổng số pixel
Tuy nhiên không phải bất cứ lệnh nào cũng chú thích, việc chú thích tràn lan ngay
cả với câu lệnh đơn giản cũng không có ý nghĩa gì. Đôi khi còn làm cho chương trình
khó nhìn hơn!
• Nên viết biểu thức điều kiện mang tính tự nhiên : biểu thức nên viết dưới dạng khẳng
định, việc viết biểu thức dạng phủ định sẽ làm khó hiểu!
if ( !(iBlock < Block1 ) || !(iBlock >= Block2))
…
Mỗi biểu thức trong điều kiện được viết dưới dạng phủ định, ta nên viết lại dưới dạng
khẳng định cho dễ hiểu hơn:
if ( (iBlock >= Block1 ) || (iBlock < Block2))
…
• Dùng chính ngôn ngữ đó để tính kích thước của đối tượng : không nên dùng giá trị
tường minh cho kích thước của dữ liệu. Khi cần lấy kích thước của biến int, ta có thể
dùng sizeof(int) thay cho các giá trị 2 hay 4. Tương tự như vậy khi lấy kích thước của
phần tử trong một mảng int ta dùng sizeof(array[0]) thay cho sizeof(int). Sau này khi
mảng array có thay đổi kiểu dữ liệu thì cách viết sizeof(array[0]) cũng không ảnh
hưởng.
int n = strlen(str)
for(i =0; i < n; i++)
….
• Thay thế một biểu thức bằng một biểu thức tương đương nhưng lợi về thực thi : một số
chương trình xử lý ảnh đòi hỏi tốc độ cao, thì người lập trình có thể thay thế các phép
nhân chia bằng phép dịch chuyển bit. Thay thế sử dụng chỉ mục trong mảng C/C++
bằng con trỏ…
Ví dụ: khi so sánh khoảng cách của hai điểm ta thường làm như sau
if (sqrt(dx1*dx1+dy1*dy1) < sqrt(dx2*dx2+dy2*dy2))
…
Thay bằng
if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2))
...
• Dùng số nguyên thay cho số thực : do việc xử lý số thực chậm hơn xử lý số nguyên nên
ta có thể dùng số nguyên thay cho số thực có phần lẻ nhỏ.
9
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
Ví dụ: điểm trung bình của sinh viên là số thực ta có thể thay bằng số nguyên: DTB là
8.72 thì lưu theo số nguyên 872, khi xuất ra thì chia cho 100.
• Loại bỏ vòng lặp : nếu thân vòng lặp đơn giản và số lần lặp cũng không nhiều, ta có thể
làm cho đoạn chương trình hiệu quả hơn bằng cách bỏ vòng lặp.
Ví dụ:
for(i =0; i < 3; i++)
A[i] = B[i] + C[i];
Thay bằng
A[1] = B[1] + C[1];
A[2] = B[2] + C[2];
A[3] = B[3] + C[3];
Đoạn chương trình thay thế loại bỏ vòng lặp, tức là lệnh rẽ nhánh, lệnh rẽ nhánh làm
chậm chương trình do ngắt luồng thực thi.
chương trình B thì ta kiểm tra giá trị của w trước khi vào vòng lặp. Do đó B có hai vòng
lặp nhưng chỉ thực hiện một trong hai và chỉ kiểm tra giá trị w duy nhất 1 lần!
• Thoát khỏi vòng lặp sớm nhất : một số trường hợp không cần phải lặp hết toàn bộ vòng
lặp mà đã đạt được mục đích thì có thể thoát ra khỏi vòng lặp.
Ví dụ: chỉ cần xác định giá trị -99 có xuất hiện trong danh sách hay không ta có hai
chương trình A và B minh họa như sau:
Chương trình A Chương trình B
found = FALSE;
for(i=0;i<10000;i++)
{
if( list[i] == -99 )
{
found = TRUE;
}
}
if( found ) printf("Yes, there is a -99.");
found = FALSE;
for(i=0; i<10000; i++)
{
if( list[i] == -99 )
{
found = TRUE;
break;
}
}
if( found ) printf("Yes, there is a -99.");
Chương trình A khi tìm thấy thì vẫn cứ lặp cho đến hết, trong khi B thì sẽ thoát
ngay. Rõ ràng khi đã tìm thấy thì không cần phải lặp tiếp, khi đó B sẽ tối ưu hơn!
• Gom các vòng lặp : các vòng lặp cùng số lần lặp thì nên gom lại
Ví dụ:
Cải tiến thành:
flag = x>y;
• Lưu tạm giá trị thường sử dụng : trong chương trình đôi khi một giá trị được tính toán
một lần nhưng lại thường được sử dụng mà ít có thay đổi giá trị. Khi đó ta có thể dùng
biến lưu trữ giá trị của biểu thức này, khi nào cần thì có thể sử dụng biến đó thay vì
phải tính toán lại.
Ví dụ: đoạn chương trình giải phương trình bậc hai.
…
12
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
if ((b*b)-4*a*c < 0)
printf(“Phuong trinh vo nghiem!”);
else if ((b*b)-4*a*c == 0)
printf(“Phuong trinh co nghiem kep”);
…
else
{
x1= (-b + sqrt((b*b)-4*a*c))/(2*a);
x2= (-b - sqrt((b*b)-4*a*c))/(2*a);
…
}
Trong đoạn chương trình trên delta được tính lại 4 lần, ta có thể cải tiến chỉ tính duy
nhất một lần!
delta = (b*b)-4*a*c;
if ( delta < 0)
printf(“Phuong trinh vo nghiem!”);
else if (delta == 0)
printf(“Phuong trinh co nghiem kep”);
…
else
t = a;
a = b;
b = t;
}
Chuyển thành macro swap
#define swap(a, b) {int t = a; a = b; b = t;}
14
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
• Giảm số lượng tham số truyền vào hàm : việc sử dụng hàm có quá nhiều tham số được
truyền vào có thể làm ảnh hưởng đến ngăn xếp dành cho việc gọi hàm. Nhất là trường
hợp tham số là kiểu dữ liệu cấu trúc. Sử dụng con trỏ hay tham chiếu trong trường hợp
này để đơn giản hoá.
Ví dụ :
void Print(struct Student s)
{
printf(“%d”, s.StudentCode);
…
}
Thay bằng:
void Print(const struct Student *s)
{
printf(“%d”, s->StudentCode);
…
}
15
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
Chương 1
Kỹ thuật đệ quy
định nghĩa của giai thừa n như sau: n! = 1.2.3...(n-1).n
hoặc định nghĩa:
n! =
≥−
=
1)!.1(
01
nnn
n
Phương pháp thứ nhất là dùng vòng lặp:
long GT(int n)
{
long result = 1;
for(int i=1; i <= n; i++)
result *= i;
return result;
}
Phương pháp thứ hai là dùng hàm đệ quy:
long Giaithua(int n)
{
if (n == 0) return 1;
else return (n*Giaithua(n-1));
}
Phân tích chương trình thực hiện đệ quy:
Giả sử chương trình có lời gọi hàm như sau
long l = Giaithua(5);
17
Giaithua(0)
1
18
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
- Đệ quy tuyến tính : thân hàm gọi một lần đến chính nó:
U
n
a, n =1
r + U
n-1
, n>1
double U(int n, double a, double r)
{
if (n == 1)
return a ;
return r + U(n-1, a, r) ;
}
- Đệ quy nhị phân : thân hàm có hai lần gọi chính nó
U
n
1, n =1, 2
U
n-2
+ U
n-1
, n>2
long Fibo(int n)
{
if (n<2 ) return 1 ;
return Fibo(n-1) + Fibo(n-1) ;
+ G
n-2
, n>=5
G
n
n-3, n <8
U
n-1
+ G
n-2
, n>=8
long G(int n);
19
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
long U( int n)
{
if (n<5)
return n;
return U(n-1) + G(n-2);
}
long G(int n)
{
if (n<8)
return n-3;
return U(n-1) + G(n-2);
}
Đệ quy gián tiếp : trong một hàm có lời gọi hàm đến một hàm khác và bên trong
hàm này lại có lời gọi hàm đến hàm ban đầu. Ví dụ như hàm F
1
gọi hàm F
Ví dụ 1: Tính tổng các số nguyên từ 1 đến N.
∑∑∑
−
−
−
=
+−+=+=
2
1
1
1
)1(
N
i
N
i
N
i
iNNiNi
Ta phân tích như sau:
+ Trường hợp đặc biệt N=1 thì kết quả là 1
+ Trường hợp khác ta thực hiện đệ quy: N + Tong(N-1).
Ví dụ 2: tìm USCLN của hai số nguyên dương a, b.
+ Trường hợp đặc biệt khi a = b khi đó USCLN(a, b) = a
+ Trường hợp chung a và b khác nhau ta có thể thực hiện đệ quy như sau:
- USCLN(a, b) = USCLN(a-b, b) nếu a>b
- USCLN(a, b) = USCLN(a, b-a) nếu a<b.
Hàm tìm USCLN đệ quy được viết như sau:
int USCLN(int a, int b)
{
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
Với N = 2: ta có cách làm như sau: chuyển đĩa bé nhất sang C
3
, chuyển đĩa lớn sang C
2
,
chuyển đĩa nhỏ từ C
3
sang C
2
.
Hình 2.2: Minh họa tháp Hanoi với n =2.
Với N = 3: ta thực hiện với giả thiết đã biết cách làm với N-1 đĩa (2 đĩa trong ví dụ
N=3): chuyển đĩa 1 và 2 sang cọc 3, chuyển đĩa 3 sang cọc 2, chuyển hai đĩa 1, 2 từ cọc
3 sang cọc 2.
1 1 1 12 2 2 23 3
3 3
22
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
Hình 2.3: Minh họa trường hợp N = 3.
Trong trường hợp N = 3 như hình 2.3, thực hiện ba bước để đưa 3 đĩa về cọc 2: gồm B1,
B2 và B3. Với B2 thì đơn giản do chuyển 1 đĩa, còn bước B1 và B3 phải di chuyển nhiều
hơn 1 đĩa nên chúng sẽ bao gồm nhiều bước nhỏ trong đó. B1 gồm {B1.1, B1.2, B1.3} và
C
1
C
2
C
3
1, 2 qua cọc 3 1, 2 qua cọc 2
C
3
C
1
C
2
C
3
C
1
C
2
C
3
C
1
C
2
C
3
B1.1
B1.2
B1.3 B3.1
B3.2
B3.3
23
C
1
C
2
C
1
C
2
C
3
24
Giáo trình Kỹ thuật lập trình 2 Khoa CNTT – ĐH KTCN
DichChuyen(N, 1, 2, 3);
return 0;
}
void DichChuyen(int N, int C1, int C2, int C3)
{
if (N == 1) printf(“%d - > %d”, C1, C2);
else
{
DichChuyen(N-1, C1, C3, C2);
DichChuyen(1, C1, C2, C3);
DichChuyen(N-1, C3, C2, C1);
}
}
Tìm phần tử lớn nhất trong mảng dùng đệ quy : cho mảng a[n], n > 1, hãy tìm phần tử
lớn nhất trong mảng a[n]. Ta thử phân tích như sau: ý tưởng là đi từ phần đuôi và so
sánh với phần tử cuối cùng của mảng với biến tạm m, chọn ra phần tử lớn nhất ⇒ lưu
lại vào m. Bước tiếp theo thực hiện tương tự nhưng lúc này mảng rút ngắn lại còn n-1
phần tử.
Hình 2.5 : Tìm phần tử lớn trong mảng dùng đệ quy
Hàm đệ quy tìm phần tử lớn nhất mô tả như sau: giả sử chỉ số mảng tính từ 1.
DeQuyMax(int a[N], int n, int &max)// Gỉa sử n > 0
n =1
25
Copyright: Tài liệu đại học ©