Lờicảmơn
Phần1.Giớithiệuchung
Phần2.Cơsởlýthuyết
Phần3.Phântíchnhiệmvụ
Phần4.Thiếtkếvàphươngánthựchiện
Phần5.Kếtluậnvàđịnhhướngpháttriểntiếp
Phần6.Phụ lục
Lờicảm ơn
Ngàynày,vớisựpháttriểnnhảyvọtcủakhoahọccôngnghệnóichungcủa
ngànhtinhọcnóiriêng,vớinhữngtínhnăngưuviệt,sựtiệndụngvàđượcứngdụng
rộngrãi,tinhọcngàynaylàmộtphầnkhôngthểthiếuđượccủanhiềungànhtrong
côngcuộcxâydựngvàpháttriểnxãhội.Hơnthế nữanócòn đisâuđờisốngcủacon
người.
TinhọcđãthâmnhậpkhámạnhmẽvàoViệtNam.Nhiềulĩnhvựchoạtđộngtừ
lĩnhvựcquảnlýhànhchính,quảnlýkinhtế,tự độnghóacôngnghiệp...đếncáclĩnhvực
giáodụcvàđàotạođềucóthayđổiđángkể nhờ ứngdụngtinhọc.Máy tínhlàcôngcụ
cầnthiếtđốivớiconngườitrongthờiđạingàynay.Hoạtđộngcủamộtmáytínhlàxử lý
cácthôngtinđưavàotheomộtchươngtrìnhđã đượclậpsẵnnhằmđưarakếtquả phục
vụ yêucầunàođócủangườisửdụng.Việcxâydựngcácchươngtrìnhchomáytínhlà
hết sức cần thiết bởi vì các chương trình là linh hồn của máy tính. Trong xây dựng
chươngtrìnhđểcómộtchươngtrìnhcóhiệuquảcầnphảicóchuyêngiaphântíchbài
toánđưarasơđồthuậttoánvàtừđócáclậptrìnhviêntiếnhànhsinhmãnguồncho
chươngtrình.Vấnđềđặtraliệucóthểxâydựngmộtphầnmềmhỗtrợngườilậptrình
xâydựngsơđồthuậttoánhaykhông?Vớimongmuốnđó...emlựachọnđềtài:“Xây
dựngcôngcụ tạosơđồ khối”
Phần1.Giớithiệuchung
Ngàynày,vớisựpháttriểnnhảyvọtcủakhoahọccôngnghệnóichungcủa
ngànhtinhọcnóiriêng,vớinhữngtínhnăngưuviệt,sựtiệndụngvàđượcứngdụng
rộngrãi,tinhọcngàynaylàmộtphầnkhôngthểthiếuđượccủanhiềungànhtrong
côngcuộcxâydựngvàpháttriểnxãhội.Hơnthế nữanócòn đisâuđờisốngcủacon
người.
TinhọcđãthâmnhậpkhámạnhmẽvàoViệtNam.Nhiềulĩnhvựchoạtđộngtừ
lĩnhvựcquảnlýhànhchính,quảnlýkinhtế,tự độnghóacôngnghiệp...đếncáclĩnhvực
giáodụcvàđàotạo đềucóthayđổiđángkể nhờ ứngdụngtinhọc.Máytínhlàcôngcụ
cầnthiếtđốivớiconngườitrongthờiđạingàynay.Hoạtđộngcủamộtmáytínhlàxử lý
cácthôngtinđưavàotheomộtchươngtrìnhđã đượclậpsẵnnhằmđưarakếtquả phục
vụ yêucầunàođócủangườisửdụng.Việcxâydựngcácchươngtrìnhchomáytínhlà
hết sức cần thiết bởi vì các chương trình là linh hồn của máy tính. Trong xây dựng
chươngtrìnhđểcómộtchươngtrìnhcóhiệuquảcầnphảicóchuyêngiaphântíchbài
toánđưarasơđồthuậttoánvàtừđócáclậptrìnhviêntiếnhànhsinhmãnguồncho
chươngtrình.Vấnđềđặtraliệucóthểxâydựngmộtphầnmềmhỗtrợngườilậptrình
xâydựngsơđồthuậttoánhaykhông?Vớimongmuốnđó...emlựachọnđềtài:“Xây
dựngcôngcụ tạosơđồ khối”
Phần2.Cơsởlýthuyết
2.1Giảithuật
1.Kháiniệmgiảithuật
Giảithuậtlàmộthệthốngchặtchẽvàrõràngcácquytắcnhằmxácđịnh
mộtdãycácthaotáctrênnhữngdữliệuvàosaochosaumộtsốhữuhạnbướcthực
hiệncácthaotácđótathuđượckếtquảcủabàitoán.
Ví dụ 1: Giả sửcó hai bình A và B đựng hai loại chất lỏng khác nhau,
chẳng hạn bình A đựng rượu, bình B đựng nước mắm. Giải thuật để hoán đổi
(swap)chấtlỏngđựngtronghaibìnhđólà:
À YêucầuphảicóthêmmộtbìnhthứbagọilàbìnhC.
À Bước1:ĐổrượutừbìnhAsangbìnhC.
À Bước2:ĐổnướcmắmtừbìnhBsangbìnhA.
À Bước3:ĐổrượutừbìnhCsangbìnhB.
Vídụ2:Mộttrongnhữnggiảithuậttìmướcchunglớnnhấtcủahaisốavà
blà:
À Bước1:Nhậpvàohaisốavàb.
À Bước2:Sosánh2sốa,bchọnsốnhỏnhấtgánchoUCLN.
À Bước 3: Nếu một trong hai số a hoặc b không chia hết cho
UCLNthìthựchiệnbước4,ngượclại(cảavàbđềuchiahếtchoUCLN)
thìthựchiệnbước5.
À Bước4:Giảm UCLNmộtđơnvịvàquaylạibước3
À Bước5:InUCLNKếtthúc
2Cácđặctrưngcủagiảithuật
o Tínhkếtthúc:Giảithuậtphảidừngsaumộtsốhữuhạnbước.
o Tínhxácđịnh:Cácthaotácmáytínhphảithựchiệnđượcvàcácmáy
tính khác nhau thựchiện cùngmột bướccủacùng một giảithuật phảicho cùng
mộtkếtquả.
o Tínhphổdụng:Giảithuậtphải"vét'hếtcáctrườnghợpvàápdụngcho
mộtloạtbàitoáncùngloại.
o Tínhhiệuquả:Mộtgiải thuật được đánhgiálàtốtnếunóđạthaitiêu
chuẩnsau:
Thựchiệnnhanh,tốnítthờigian.
Tiêuphííttàinguyêncủamáy,chẳnghạntốnítbộnhớ.
GiảithuậttìmUCLNnêutrênđạttínhkếtthúcbởivìquamỗilầnthựchiện
bước4thìUCLNsẽgiảmđimộtđơnvịcho nêntrongtrườnghợpxấunhất thì
UCLN=1,giảithuậtphảidừng.Cácthaotáctrìnhbàytrongcácbước,máytính
đềucóthểthựchiệnđượcnênnócótínhxácđịnh.Giảithuậtnàycũngđạttính
phổdụngvìnóđượcdùngđểtìmUCLNchohaisốnguyeêndươngavàbbấtkỳ.
Tuynhiêntínhhiệuquảcủagiảithuậtcóthểchưacao;cụthểlàthờigianchạy
máycóthểcòntốnnhiềuhơnmộtsốgiảithuậtkhácmàchúngtasẽcódịptrởlại
trongphầnlậptrìnhC.
3Cácphươngphápbiểudiễngiảithuật
Đểbiểudiễngiảithuật,cầnphảicómộttậphợpcáckýhiệudùngđểbiểu
diễn,mỗikýhiệubiểudiễnchomộthànhđộngnàođó.Tậphợpcáckýhiệuđólại
tạothànhngônngữbiểudiễngiảithuật.
3.1Ngônngữtựnhiên
Ngônngữtựnhiênlàngônngữcủachúngtađangsửdụng,chúngtacóthể
sửdụngngônngữtựnhiênđểmôtảgiảithuậtgiốngnhưcácvídụởtrên.
Vídụ:Tacógiảithuậtgiảiphươngtrìnhbậcnhấtdạng0=+baxnhưsau:
À Bước1:Nhậngiátrịcủacácthamsốa,b
À Bước2:Xétgiátrịcủaaxemcóbằng0haykhông?Nếua=0thì
làmbước3,nếuakháckhôngthìlàmbước4.
À Bước3:(abằng0)Nếubbằng0thìtakếtluậnphươngtrìnhvô
sốnghiệm,nếubkhác0thìtakếtluậnphươngtrìnhvônghiệm.
À Bước4:(akhác0)Takếtluậnphươngtrìnhcónghiệmx=b/a
Ưunhượcđiểm.
1. Dễhiểu,dễlàm
2. Phụthuộcvào“cáchhànhvăn”củangườidiễnđạt
3. Vớinhữnggiảithuậtphứctạp,cáchdiễnđạtnàytrởnênrườmrà
4. …
3.2Diễnđạtthuậtgiảibằnggiảngônngữ
3.2.1. Giảngônngữ:
1. Dựatrênngônngữlậptrìnhbậccao
2. Gầnvớingônngữtựnhiêncủaconngười
Vídụ:
NgônngữgiảPascal(tựaPascal)cócáckýphápkhágiốngvớingônngữlập
trìnhPascal,đượcrútgọnsaochodễdiễnđạt
3.2.2. Diễnđạtthuậtgiảibằnggiảngônngữ
Giảngônngữđượcđưaravớimụcđíchdiễnđạtcácgiảithuậtsaochogần
vớingônngữlậptrìnhvàngônngữtựnhiên.
Sửdụnggiảngônngữkhiếnviệcchuyểntừgiảithuậtsangchươngtrìnhdễ
dànghơn.
Vídụ:Giảithuậttínhtổngnsốtựnhiênđầutiên
NhậpN
i:=0
S:=0
REPEAT
S:=S+i
i:=i+1
UNTIL(i>N)
InS
3.3.NgônngữLưuđồ(sơđồ)
3.3.1. NgônngữLưuđồ
Ngônngữsơđồ(lưuđồ)làmộtngônngữđặcbiệtdùngđểmôtảgiảithuật
bằngcácsơđồhìnhkhối.Mỗikhốiquiđịnhmộthànhđộng.
ChẳnghạntadùnglưuđồđểbiểudiễngiảithuậttìmUCLNnêutrênnhưsau: