Kỹ thuật lập trì nh
1
CHƯƠNG i ĐạI CƯƠNG Về LậP TRìNH

I. Khái niệm thuật toán:
I.1. Khái niệ m
:
Thuậ t toá n là tậ p hợp cá c quy tắ c có logic nhằ m giả i một lớp bà i toán nà o
đó để được một kế t quả xá c định.
I.2. Các tí nh chất đặc trưng của thuật toán
:
I.2.1. Tí nh tổng quát :
Thuậ t toá n được lậ p không phả i chỉ để giả i một bà i toá n cụ thể mà thôi mà
còn phả i giả i đ ược một lớp cá c bà i toá n có dạ ng tương tự.
I.2.2. Tí nh giới hạn :
Thuậ t toá n giả i một bà i toá n phả i đ ược thực hiệ n qua một số giới hạ n các
thao tá c để đạ t đế n kế t quả .
I.2.3. Tí nh duy nhất :
Toà n bộ quá trì nh biến đổi, cũng như trậ t tự thực hiệ n phả i đ ược xác định
và là duy nhấ t. Như vậ y khi dùng thuậ t toá n cùng một dữ liệ u ban đầ u phả i cho
cùng một kế t quả .
I.3. Phân loại:

Theo cấ u trúc, ta có thể phâ n thà nh ba loạ i thuậ t toá n cơ bả n sau :
- Thuậ t toá n không phâ n nhá nh.
- Thuậ t toá n có phâ n nhá nh.
- Thuậ t toá n theo chu trì nh có bước lặ p xá c định và có bước lặ p không
xá c định.
II. Mô tả thuật toán bằng lưu đồ
:
II.1. Lưu đồ
Dùng để gọi chương trì nh
con
Mũi tê n

Chỉ hướng truyề n thông
tin, liê n hệ cá c khối
II.3. Một số ví dụ biể u diễ n thuật toán bằng lưu đồ
II.3.1. Thuật toán không phân nhánh:
Ví dụ 1
: Tí nh A = x
2
+ y
2

Begin
Nhaọp (x,y)
A = x
2
+ y
2
Xuaỏt (A)
End

Ví dụ 2
: Tí nh
y
x
CByAx

ẹ

Ví dụ 2
: Giả i phương trì nh bậ c nhấ t Ax+B =0 với cá c nghiệ m thực.
Begin
Nhaọp (a, b)
Xuaỏt (PTVẹ)
End
a = 0
S
S
Xuaỏt (-b/a)
b = 0 Xuaỏt (PTVN)
ẹ
ẹ

Kü tht lËp tr× nh
4
VÝ dơ 3 : Gi¶ i ph­¬ng tr× nh bË c hai Ax
2
+Bx+C =0 víi c¸ c nghiƯ m thùc.
Begin
Nhập (a, b, c)
Xuất (‘X
1
= ’,(-b + SQRT(Delta)) / (2*a))
Xuất (‘X
2
= ’,(-b - SQRT(Delta)) / (2*a))
End

n
x
=

1
, với cá c x
i
do ta nhậ p và o.
Begin
Nhaọp (n)
i = 1
S = 0
Nhaọp (x
i
)
End
i = i+1
S = S+x
i
i <= n
Xuaỏt (S)
S
ẹ

III. CáC NGôN NGữ LậP TRìNH & CHươNG TRìNH DịCH
:
III.1. Ngôn ngữ lập trì nh:

III.1.1. Giới thiệ u: Con người muốn giao tiế p với má y tí nh phải thông qua
ngôn ngữ. Con người muốn má y tí nh thực hiệ n công việ c, phả i viế t cá c yê u cầu

nguồn
Trình biên
dòch
Chương trình
đích
Máy tính
thực hiện
Kết quả
Dữ liệu

H× nh I.1. Ch­¬ng tr× nh thùc thi theo c¬ chÕ dÞch cđa tr× nh biª n dÞch
III.2.2. Tr× nh th«ng dÞch: qu¸ tr× nh dÞch vµ thùc thi x¶ y ra cïng 1 thêi
gian, dÞch ®Õ n ®© u thi hµ nh lƯ nh ®Õ n ®ã.
Chương trình
nguồn
Chương trình
thông dòch
Kết quả
Dữ liệu

H× nh I.2. Ch­¬ng tr× nh thùc thi theo c¬ chÕ dÞch cđa tr× nh th«ng dÞch
Kỹ thuật lập trì nh
7
CHươNG 2 LàM QUEN VớI NGôN NGữ C

* Giới thiệu ngôn ngữ C
Ngôn ngữ C do Dennis Ritchie là người đầu tiên đề xuất, đ thiế t kế và cà i
đặ t C trong môi trường UNIX. Nó có nguồn gốc từ ngôn ngữ BCPL do Martin
Richards đ ưa ra và o nă m 1967 và ngôn ngữ B do Ken Thompson phá t triể n từ
ngôn ngữ BCPL nă m 1970 khi viế t hệ điề u hà nh Unix.


I.1. Cấu trúc cơ bản của một chương trì nh C

[tiề n xử lý]
[Cá c hà m]
main()
Kỹ thuật lập trì nh
8
{ [khai bá o biế n;]
[nhậ p dữ liệ u ;]
[xử lý ;]
[xuấ t ;]
}
Ví dụ
: Chương trì nh hiệ n trê n mà n hì nh câ u Chao cac ban
void main()
{ printf(Chao cac ban\n);
}
Một và i nhậ n xét quan trọng
:
- Chương trì nh C bao giờ cũng có một hay nhiề u hà m, trong đó có một
hà m chí nh bắ t buộc phả i có là hà m main(). Đâ y chí nh là hà m đ ược thực hiệ n
đầ u tiê n trong chương trì nh.
- Cặ p dấ u { } để xá c định một khối lệ nh.
- Hà m printf( Chao cac ban \n) là hà m chuẩ n của C dùng để xuấ t câ u
thông bá o Chao cac ban ra mà n hì nh. Ký tự \n là ký tự đặ c biệ t dùng để
xuống dòng.
- Dấ u ; để chấ m dứt một lệ nh.
- Chương trì nh C có phâ n biệ t chữ thường với chữ hoa. Đa số cá c từ khoá
của C đ ược viế t bằ ng chữ thường, còn một số í t đ ược viế t bằ ng chữ hoa mà ta

: Chương trì nh in lũy thừa 2, 3, 4, 5; có dùng hà m để tí nh lũy thừa :
#include <stdio.h>
#define max 50 /*Tiề n xử lý, định nghĩ a max =50*/
float luythua(int n, int m) /*Hà m luythua với 2 thông số*/
{ float s=1; /*Khai bá o và khởi tạ o biế n s*/
for ( ;m>0;m--) /*Lặ p giả m dầ n từ m tới 1*/
s=s*n;
return s; /*Trả kế t quả về */
}
void main()
{ int n,n2,n3,n4,n5; /*Khai bá o biế n kiể u nguyê n*/
for (n=10;n<=50;n++) /*Lặ p từ 10 đế n 50 bằ ng for*/
{ n2= luythua(n,2); /*Gọi hà m luythua*/
n3= luythua(n,3);
n4= luythua(n,4);
n5= luythua(n,5);
printf(%3d \t %5.2f \t %5.2f\t %5.2f\t %5.2f\t %5.2f\n,
n,n2,n3,n4,n5); /*in n và n
m
dạ ng 5 chữ số với 2 số lẻ */
}
} /*Hế t main*/
* Hàm xuất chuẩn printf()

Cú pháp
:
printf(chuỗi-địnhdạ ng,thamso1,thamso2,...)
ý nghĩ a
:
Hà m printf() sẽ xem xét chuỗi-địnhdạ ng, lấ y giá trị cá c tham số (nế u cầ n)

Type : định kiể u của tham số theo sau chuỗi-địnhdạ ng để lấ y giá trị ra
Type
ý nghĩ a
d,i Số nguyê n cơ số 10
u Số nguyê n cơ số 10 không dấ u
o Số nguyê n cơ số 8
x Số nguyê n cơ số 16, chữ thường(a,b,...,f)
X Số nguyê n cơ số 16, chữ in (A,B,...,F)
f Số thực dạ ng [-]dddd.ddd...
e Số thực dạ ng [-]d.ddd e[+/-]ddd
E Số thực dạ ng [-]d.ddd E[+/-]ddd
g,G Số thực dạ ng e(E) hay f tùy theo độ chí nh xá c
c Ký tự
s Chuỗi ký tự tậ n cùng bằ ng \0
% Dấ u % cầ n in

Kỹ thuật lập trì nh
11
Flag : Dạ ng điề u chỉ nh
Flag
ý nghĩ a
nế u không có in dữ liệ u ra với canh phả i
- in dữ liệ u ra với canh trá i
+ Luôn bắ t đầ u số bằ ng + hay -
# in ra tùy theo type, nế u:
0 : Chè n thê m 0 đứng trước giá trị >0
x,X : Chè n thê m 0x hay 0X đứng trước số nà y
e,E,f : Luôn luôn có dấ u chấ m thậ p phâ n
G,g : Như trê n nhưng không có số 0 đi sau
Width : định kí ch thước in ra

%s s Blue moon! độ rộng 10
%3s s Blue moon! Nhiề u ký tự hơn cầ n thiế t
%.6s s Blue m Chí nh xá c 6 ký tự
%-11.8s s Blue moo Chí nh xá c 8, canh trá i
Ví dụ 2: int i = 123;
float x = 0.123456789;
Dạng Thông số
tương ứng
Xuất Nhận xét
%d i 123 độ rộng 3
%05d i 00123 Thê m 2 số 0
%7o i 123 Hệ 8, canh phả i
%-9x i 7b Hệ 16, canh trá i
%c i { Ký tự có m ASCII 123
%-#9x i 0x7b Hệ 16, canh trá i
%10.5f x 0.12346 độ rộng 10, có 5 chữ số thậ p
phâ n
%-12.5e x 1.23457e-01 Canh trá i, in ra dưới dạ ng
khoa học
Ví dụ 3: Viế t chương trì nh in hì nh chữ nhậ t kép bằ ng cá c ký tự ASCII
C9 CD BB C8 CD BC
void main()
{ printf(\n\xC9\xCD\xBB);
printf(\n\xC8\xCD\xBC\n);
}
Kỹ thuật lập trì nh
13

int Số nguyê n có dấ u 2 bytes
-32768

32767
unsigned int Số nguyê n không dấ u 2 bytes
0

65535
long Số nguyê n dà i có dấ u 4 bytes
-2147483648
2147483647
unsigned long Số nguyê n dà i không dấ u 4 bytes
0

4294967295
float Số thực độ chí nh xá c đơn 4 bytes
3.4 E-38

3.4 E+38
double Số thực độ chí nh xá c kép 8 bytes
1.7 E-308

1.7
E+308
long double Số thực độ chí nh xá c hơn
double
10 bytes
3.4 E-4932

1.1

bien_ten_dai_hon_32_ky_tu_dau_tien_2
I.3.2. Khai báo biế n
Các biến phải được khai bá o trước khi sử dụng nhằ m giúp cho chương
trì nh dịch có thể xử lý chúng.
Khai bá o biế n có dạ ng :
Kiể udữliệ u tê nbiế n1 [,tenbiế n2 ...] ;
Ví dụ: int a,b,c;
float x,y,delta;
char c;
* Khai bá o và khởi tạ o biế n
:
Kiể u dữ liệ u tê nbiế n = giá trị ;
I.3.3. Hàm nhập dữ liệ u chuẩn
a) Hàm scanf()
Cú pháp
: scanf(chuỗi-địnhdạ ng,điạ chỉ thamsố 1, điạ chỉ thamsố2,...)
- Chuỗi-địnhdạ ng của scanf() gồm có ba loạ i ký tự :
+ Chuỗi điề u khiể n
+ Ký tự trắ ng
+ Ký tự khá c trắ ng
! Chuỗi điề u khiể n có dạ ng :
%[width][h/l] type
Kỹ thuật lập trì nh
15
Với type: xá c định kiể u của biế n địa chỉ tham số sẽ nhậ n giá trị nhậ p và o
Type
ý nghĩ a
d,i Số nguyê n cơ số 10 (int)
o Số nguyê n cơ số 8 (int)
u Số nguyê n cơ số 10 không dấ u (unsigned)

! Ký tự trắ ng: nế u có trong chuỗi-dạ ng sẽ yê u cầ u scanf() bỏ qua một hay
nhiề u ký tự trắ ng trong chuỗi nhậ p và o. Ký tự trắ ng là ký tự khoả ng trắ ng ( ),
tab (\t), xuố ng hà ng (\n). Một ký tự trắ ng trong chuỗi-địnhdạ ng sẽ đ ược hiể u
là chờ nhậ p đế n ký tự khá c trắ ng tiế p theo.
Kỹ thuật lập trì nh
16
Ví dụ 4: scanf(%d ,&num);
Hà m scanf() cho ta nhậ p một ký tự khá c trắ ng nữa thì mới thoát ra. Ký tự
đó sẽ nằ m trong vùng đệ m và sẽ đ ược lấ y bởi hà m scanf() hoặ c gets() tiế p theo.
! Ký tự khá c trắ ng: nế u có trong chuỗi-địnhdạ ng sẽ khiế n cho scanf() nhậ n
và o đúng ký tự như thế .
Ví dụ 5
: scanf(%d/%d/%d,&d,&m,&y);
Hà m scanf() chờ nhậ n một số nguyê n, cấ t và o d, kế đế n là dấ u /, bỏ dấu
nà y đi và chờ nhậ n số nguyê n kế tiế p để cấ t và o m. Nế u không gặ p dấ u / kế
tiế p số nguyê n thì scanf() chấ m dứt.
Chú ý
: Hà m scanf() đòi hỏi cá c tham số phả i là cá c địa chỉ của các biế n
hoặ c là một con trỏ.
* Toá n tử địa chỉ &
: Lấ y địa chỉ của một biế n
Ví dụ 6
: int n;

biế n n
&n;

địa chỉ của n
printf(trị = %d, địa chỉ = %d,n,&n);
b) Hàm getch():

: Hà m getch() còn cho phép ta nhậ p và o 1 ký tự mở rộng như cá c
phí m F1, F2,.., cá c phí m di chuyể n cursor. Cá c phí m nà y luôn có 2 bytes: byte
thứ nhấ t bằ ng 0, còn byte 2 là m scancode của phí m đó. Để nhậ n biế t ta đ gõ
phí m ký tự hay phí m mở rộng, ta có chương trì nh sau:
void main()
{
int c;
int extended = 0;
c = getch();
if (!c)
extended = getch();
if (extended)
printf("The character is extended\n");
else
printf("The character isn't extended\n");
}
Phí m Mã scancode
F1 59
F2 60
F3 61
F4 62
F5 63
F6 64
F7 65
F8 66
F9 67
F10 68
Home 71
"
72

trì nh chương trì nh thực hiệ n.
I.4.1. Phân loại :
a.
Hằng số
: là cá c giá trị số đ xá c định và không đổi.
int unsigned long hệ 8 hệ 16 float/double
Dạ ng nnnn
-nnnn
nnnnU/u

nnnnL/l
-nnnnl/L
0nnnn 0xnnnn nnnn.nnnn
nnnn.nnnE/e

nnn
Ví dụ 4567
-12
123U
12uL
456789L
-1234L
0345 0x1AB 123.654
123.234E-4
Chú ý
:
- Cá c hằ ng số viế t không dấ u hoặ c không số mũ đ ược hiể u là số nguyê n,
ngược lạ i là double.
- Cá c hằ ng số nguyê n lớn hơn int sẽ đ ược lưu trữ theo kiể u long, còn lớn
hơn long thì đ ược lưu trữ theo kiể u double.

& Hằ ng ký tự có thể tham gia và o cá c phép toá n như mọi số nguyê n khá c.
Ví dụ
:9-0=57-48=9
& Hằ ng ký tự có thể là cá c ký tự đặ c biệ t dạ ng \c
1
mà ta đ xét ở hà m
printf() như \n,\a,\t ...
c.
Hằng chuỗi
: Là một chuỗi ký tự nằ m trong hai dấ u nhá y kép .
Ví dụ
: Day la mot chuoi
Hang chuoi co ky tu đạ c biệ t như \ \n \248


chuỗi rỗng.
Chú ý
:
- Phân biệt A

A
Hằ ng: Chuỗi Ký tự
Dạ ng lưu trữ :
A \0 A
- Nhậ n xét: ở dạ ng lưu trữ, ta thấ y tậ n cùng của chuỗi có ký tự NULL \0
mà không có ở dạ ng ký tự. Chí nh vì vậ y mà không có ký tự rỗng .
- Một chuỗi có thể đ ược viế t trê n nhiề u hà ng với điề u kiệ n hà ng trê n phả i
có dấ u \.
Ví dụ
:Day la mot chuoi duoc viet tren \

I.5.1. Phép gán:
Cú pháp
: biế n = biể u thức;
Chú ý

: Phép gá n trong ngôn ngữ C trả về một kế t quả là trị của biể u thức
Ví dụ 1
: c = 10;
a = b = c;
printf(a=%d , b=%d,a,b);

a=10,b=10
Ví dụ 2
: x = b + 2*c;
y= a + (x= b + 2*c)

y = a + x;
Ví dụ 3
: (n+3) = 4+z; (không hợp lệ vì bê n trá i là biể u thức)
= c +o; (không hợp lệ vì bê n trá i là hằ ng)
I.5.2. Các phép toán số học :
a.
Phép toán hai toán hạng
: +, -, *, /, %
Phép toán Kiể u toán hạng Kiể u kế t quả
+, -, * char, int, long, float,
double
Kiể u của toá n hạ ng có kiể u cao nhấ t
/ nguyê n/nguyê n Kiể u nguyê n và là phép chia nguyê n
thực(nguyê n)/thực

a = a+1
a-- hoặ c --a

a = a-1
Chú ý
: Tuy nhiê n a++ sẽ khá c ++a khi chúng đứng trong biể u thức (có
phép gá n).
a++ : Tă ng a sau khi giá trị của nó đ ược sử dụng.
++a : Tă ng a trước khi giá trị của nó đ ược sử dụng.
Ví dụ
:
main()
a b n
{ int a=4 , b=6, n;
n = a + b;
n = a++ + b;
n = ++a + b;
n = --a + b;
n = a-- + b;
n = a+ b;
}
4
4
5
6
5
4
4
6
6

I += 3
<< : là phép dịch chuyể n bit qua trá i .
>> : là phép dịch chuyể n bit qua phả i .
I.5.4. Phép toán quan hệ :
< : nhỏ hơn
> : lớn hơn
>= : lớn hơn hoặ c bằ ng
<= : nhỏ hơn hoặ c bằ ng
!= : khá c
== : bằ ng
Chú ý
:
- Phâ n biệ t toá n tử so sá nh == với phép gá n =
- C không có kiể u dữ liệ u boolean mà qui ước : Giá trị 0 là sai
Giá trị !=0 là đúng
Ví dụ
:
a=10;
b= (a>6)*(a-6)

b = 4
c= (a< 5)*(a-5)

c = 0
Ví dụ
: Tì m số lớn nhấ t trong 3 số nguyê n a, b, c
#include <stdio.h>
#include <conio.h>
void main ()
{ int a, b, c, max;

false false false
Ví dụ 1: Xét ký tự c có phả i là ký số hay không?
char c;
if (c >= 0 && c <= 9)
printf (% c là kí tự số , c);
Ví dụ 2
: Xét ký tự ch là chữ cá i hay không?
if ((ch> =a) and (ch< =z)) or ((ch> =A) and (ch< =Z))
printf(%c là chu cai \n,ch);
Ví dụ 3
:
int a=10, b=5, c=0;
a && b

1
a && c

0
a | | c

1

Ví dụ 4
:
int a=10, b=5;
Kỹ thuật lập trì nh
24
int i=2, j=0;
(a>b) && (i<j)


I.5.8. Toán tử trê n bit (bit wise) :
Dạng Ký hiệ u
ý nghĩ a
NOT bit ~ lấ y bù 1
AND bit & giao
OR bit | hội
XOR bit ^ hội loạ i trừ
dịch trá i << nhâ n 2
dịch phả i >> chia 2

Kỹ thuật lập trì nh
25
Bả ng châ n trị:
Bit Bit Bit kế t quả
A B ~ A A & B A | B A ^ B
0 0 1 0 0 0
0 1 1 0 1 1
1 0 0 0 1 1
1 1 0 1 1 0
Ví dụ:
a= 4564 0001 0001 1101 0100
b= 13667 0011 0101 0110 0011
a & b 0001 0001 0100 0000
a | b 0011 0101 1111 0111
a ^ b 0010 0100 1011 0111
ý nghĩ a
:
1. Phép AND bit thường đ ược dùng để kiể m tra một bit cụ thể nà o đó trong
thà nh phầ n dữ liệ u x có trị 0 hay 1. Việ c nà y thực hiệ n bằ ng cá ch sử dụng một
mặ t nạ (mask) với bit cầ n quan tâ m bằ ng 1 còn cá c bit khá c bằ ng 0. Ta lấ y mask