1
LẬP TRÌNH CĂN BẢN
GIỚI THIỆU VỀCẤU TRÚC DỮ
LIỆU VÀGIẢI THUẬT
2
Nộidung
1. Từbài toán đến chương trình
2. Giải thuật
lKiểudữliệu
lKhái niệm vềngôn ngữlập trình
lChương trình dịch
3
1.TừBàiToán ĐếnChươngTrình
lCácbướcgiảibàitoánbằngmáytính
lMôtảcácbướcgiảibàitoán
lVẽsơđồ xửlý
lViếtchươngtrìnhxửlýbằngngônngữgiả
lChọnngônngữlậptrìnhvàchuyểnchương
trìnhtừngônngữgiảsang ngônngữlập
trình
lThựchiệnchươngtrình: nhậpvàocáctham
số, nhậnkếtquả
4
2. GiảiThuật
lKháiniệmgiảithuật
lCác đặctrưngcủagiảithuật
lNgônngữbiểudiễngiảithuật
lMộtsốgiảithuậtcơbản
lCáccấutrúcsuyluậncơbảncủagiải
thuật
lTừgiảithuậtđếnchươngtrình
5
KháiNiệmGiảiThuật
lVídụ:Hoán đổichấtlỏngtrong2 bìnhA (nước
mắm) vàB (rượu):
lYêucầuphảicóthêmmộtbìnhthứbagọilàbìnhC.
lBước1: Đổ rượutừbìnhBsang bìnhC.
lBước2: Đổ nướcmắmtừbìnhAsang bìnhB.
lBước3: Đổ rượutừbìnhC sang bìnhA.
l“Giải thuật làmột dãy các thao tác trên những dữ
liệu vào sao cho sau một hữu hạn bước ta thu
được kết quảcủa bài toán”.
6
Các ĐặcTrưngCủaGiảiThuật
lTínhkếtthúc
lSốbướclàhữuhạn
lTínhxác định
lMáyphảithựchiệnđược
lChocùngkếtquảtrêncácmáykhácnhau
lTínhphổdụng
lTínhhiệuquả
lThờigian
lTàinguyênmáy
7
NgônNgữBiểuDiễnGiảiThuật
lNgônngữtựnhiên
lNgônngữsơđồ
lNgônngữgiả
8
NgônNgữTựNhiên
lLàngônngữcủachúngta
lVídụ:Giảithuậtgiảiphươngtrìnhbậcnhất
ax+b=0.
Bước1: Nhậngiátrịcủa các tham sốa, b.
Bước2: Xétgiátrịcủaaxem cóbằng0haykhông?
Nếua=0thìlàm bước3,nếuakhác không thì
làm bước4.
Bước3: (abằng0)Nếubbằng0 =>pt vô sốnghiệm.
Nếubkhác0=> pt vô nghiệm.
Bước4:( akhác0) Takết luận phương trình có
nghiệmx=-b/a.
9
NgônNgữ Sơ Đồ (1)
lMôtảgiảithuậtbằngcácsơđồ hìnhkhốiđã
đượcquy ướctrước
10
NgônNgữ Sơ Đồ (2)
lVídụ:Dùnglưuđồđể biểudiễngiảithuậttìm
USCLNnhưsau:
11
NgônNgữGiả
lLàmộtsựkếthợpgiữangônngữtựnhiên với
cáccấutrúc câulệnhcủamộtngônngữlập
trình.
lVídụ: Giảithuậtgiảiphươngtrìnhbậcnhất
ax+b=0.
lNhậpvàoa, b
lIf a==0 then
If b==0 then
Kếtluậnphươngtrìnhvôsốnghiệm
else
Kếtluậnphươngtrìnhvônghiệm
else
Kếtluậnphươngtrìnhcónghiệmx=-b/a
12
MộtSốGiảiThuật Cơ Bản(1)
lVídụ1: Yêucầu:
lNhậpvào1 dãyn
sốhạnga
1
, a2, .., an
lTínhtổngS:
S= a1 + a2 + a3 + ...
+ an
lIn S ramànhình
13
MộtSốGiảiThuật Cơ Bản(2)
lVídụ2: Yêu
cầu:
lNhậpvào2
sốa vàb là
2 hệsốcủa
pt: ax+b=0
lChobiết
nghiệmcủa
phương
trình.
14
C
á
c
C
ấ
u
Tr
ú
c
Suy
Lu
ậ
n
B
ả
n
CủaGiảiThuật(1)
lGiảithuậtđượcthiếtkếtheo 3 cấutrúcsuyluận
cơbản:
lTuầntự(Sequential):
lCáccôngviệcđượcthựchiệntuầntự, côngviệcnàynốitiếp
côngviệckia.
lCấutrúclựachọn(Selection)
lLựachọnmộtcôngviệcđể thựchiệncăncứvàomộtđiềukiện
nào đó
lCấutrúc1:Nếu< điềukiện> (đúng) thìthựchiện<côngviệc>
lCấutrúc2:Nếu< điềukiện> (đúng) thìthựchiện<côngviệc
1>, ngượclại(điềukiệnsai) thìthựchiện<côngviệc2>
lCấutrúc3: Trườnghợp< i> thựchiện<côngviệci>
15
C
á
c
C
ấ
u
Tr
ú
c
Suy
Lu
ậ
n
B
ả
n
CủaGiảiThuật(2)
lCấutrúclặp(Repeating)
lLặplạithực hiện mộtcôngviệckhông hoặc
nhiềulầncăncứvàomộtđiềukiệnnào đó.
lCó2 dạng nhưsau:
lLặpvới sốlần xác định
lLặpvới sốlần khôngxác định
16
TừGiảiThuậtĐếnChươngTrình
lCả2 đềulà tậpcácchỉthị(instruction) –làm
thếnào để giảiquyết1 côngviệc(task).
lGiảithuật
lNóichuyệnvớicon người, dễhiểu.
lDùngngônngữđơngiản(English) –khôngviết
bằngmã.
lChươngtrình
lNóichuyệnvớimáytính.
lCóthểđượcxemnhư1 diễntảhìnhthức(formal
expression) của1 giảithuật.
17
3. KiểuDữLiệu
lVídụ:
int x,y;
float r=3.25;
l“Kiểudữliệulàmộttậphợpcácgiátrịcócùng
mộttínhchấtvà tậphợpcácphéptoán thao
táctrêncácgiátrịđó”.
lCó2 loại
lKiểudữliệusơcấp
lKiểudữliệucócấutrúc
18
KiểuDữLiệu Sơ Cấp
l“Kiểudữliệusơcấplàkiểudữliệumà
giátrịcủanólà đơnnhất”.
lVídụ:Kiểuint trong C
llàkiểusơcấp
lgồmcác sốnguyêntừ-32768..32767
lvàcácphéptoán: +, -, *, /, %…
19
KiểuDữLiệuCóCấuTrúc
l“Kiểudữliệucócấutrúclàkiểudữliệu
màcácgiátrịcủanólàsựkếthợpcủa
cácgiátrịkhác”.
lVídụ:KiểuchuỗikýtựtrongC.
llàkiểucócấutrúc.
lVídụ: char *chuoi= “Chao cacban!”;
20
4. NgônNgữLậpTrình
lKháiniệmvềngônngữlậptrình
lChươngtrìnhdịch