Chương 1 - Tổng quan về giải thuật

Tính chất của giải thuật. Tính chính xác: để đảm bảo kết quả tính toán hay cácthao tác mà máy tính thực hiện được là chính xác.*Tính rõ ràng: giải thuật phải được thể hiện bằng các câulệnh minh bạch; các câu lệnh được sắp xếp theo thứ tựnhất định.*Tính khách quan: Một giải thuật dù được viết bởi nhiềungười trên nhiều máy tính vẫn phải cho kết quả như nhau.*Tính phổ dụng: giải thuật không chỉ áp dụng cho một bàitoán nhất định mà có thể áp dụng cho một lớp các bài toáncó đầu vào tương tự nhau.*Tính...
Nội dung trích xuất từ tài liệu:
Chương 1 - Tổng quan về giải thuật(6tiết) 1 Ngôn ngữ Lập trìnhGiải thuật 2*Đúngđắn,chínhxác(correctness).*Chắcchắn(robustness).*Thânthiện(userfriendliness).*Khảnăngthíchnghi(adapability):Chươngtrìnhcó khảnăngđểpháttriểntiếnhóatheoyêucầu.*Tínhtáisửdụng(reuseability):Chươngtrìnhcóthể dùng để làm một phần trong một chương trình lớn khác. 3*Tínhhiệuquả(efficiency).*Tính khả chuyển (porability): Khảnăng chuyển đổi giữa các môitrường.*Tínhantoàn(security).*Tínhdừng(halt). 4* Fortran * C++* Pascal * C#* Java * F#*C * VB.Net * …. 5* BorlandC++* MicrosoftVisualBasic* MicrosoftVisualC++* Jbuider* EclipseSDK* Visual.Net*… 6 Input>Process>Output*Giảiquyếtvấnđềgì?*Giảthiết,thôngtinđượccungcấp*Đạtđượcnhữngyêucầunào? 7*Phảibiểudiễnđầyđủđượcthôngtinnhậpvàxuất củabàitoán*Phùhợpvớigiảithuậtđượcchọn*Càiđặtđượctrênngônngữlậptrìnhcụthể 8*Giải thuật là một tậphợphữuhạncủa các chỉ thị hay phương cáchđược định nghĩa rõ ràng cho việchoàntấtmộtsốsựviệctừmộttrạngthái ban đầu cho trước; khi các chỉthịnày được ápdụngtriệt đểthìsẽdẫn đến kết quả sau cùng như đãdựđoán. 9*Tính chính xác: để đảm bảo kết quả tính toán hay các thaotácmàmáytínhthựchiệnđượclàchínhxác.*Tính rõ ràng: giải thuật phải được thể hiện bằng các câu lệnh minh bạch; các câu lệnh được sắp xếp theo thứ tự nhấtđịnh.*Tính khách quan: Một giải thuật dù được viết bởi nhiều ngườitrênnhiềumáytínhvẫnphảichokếtquảnhưnhau.*Tínhphổdụng: giảithuậtkhôngchỉ ápdụngchomộtbài toánnhất địnhmàcóthể ápdụngchomộtlớpcácbàitoán cóđầuvàotươngtựnhau.*Tính kết thúc: giải thuật phải gồm một số hữu hạn các bướctínhtoán. 10 *Xữlýfile.*Tìmkiếm *Đồhọa.*Sắpxếp. *Đồthị.*Đệquy. *V.v…*Xữlýchuỗikýtự. 11• Mãtựnhiên• Pseudocode(mãgiả)• Flowchart(lưuđồ)Khithiếtkếgiảithuậtphảimôtảrõ:• InputĐầuvào• OutputĐầura(kếtquả)• ProcessMôtảgiảithuật 12Vídụ:Tìmướcsốchunglớnnhấtcủa2sốnguyêndươngavàb*Đầuvào:2sốnguyêndươngavàb*Đầura:ướcsốchunglớnnhấtcủaavàb*Giảithuật:Cách1:DùngmãtựnhiênBước1:Nếua=bthìkếtluậnalàướcsốchunglớnnhất,kếtthúcBước2:Nếua>bthìa=a–b; Ngượclạithìb=b–a;Bước3:QuaytrởlạiBước1 13Cách2:Dùngmãgiả(Pseudocode)WHILEa≠bDO IFa>bTHEN a=ab ELSE b=ba ENDIFENDWHILE 14Cách3:Dùnglưuđồ(flowchart) 15*Dễhiểu,khôngchitiếtđếncáckỹthuậtlậptrình*Ởcấpđộhếtsứctổngquát:gầnngônngữtựnhiên*Hoặcrấtchitiết:nhưdùngngônngữtựaPascal,C++,…*Cáctừkhóa *IFTHEN…ENDIF *IFTHEN...ELSE...ENDIF *WHILEDO…ENDWHILE *DO…UNTIL *WRITE… 16 *RETURN…*Lưu đô thuật toan la công cu dung để biêu ̀ ́ ̀ ̣ ̀ ̉ diênthuậttoan,viêcmôta nhâp (input),dư ̃ ́ ̣ ̉ ̣ ̃ liêu xuât (output) va luồng xữ ly thông qua ̣ ́ ̀ ́ cackyhiệuhinhhoc ́ ́ ̀ ̣*Phươngphápduyệtlưuđồ *Duyêttừtrênxuống ̣ *Duyêttừtraisangphaỉ ̣ ́ 17 Bắtđầu/kếtthúcĐiề Rẽnhánh u Giá trị trả vềkiện Luồngxửlý Điểm nối Khốixửlý Nhập/Xuất 181. Chosônguyênn.Tinhtrituyệtđốicuan ́ ́ ̣ ̉2. GiảivàbiệnluậnphươngtrìnhbậcI:ax+b=03. Nhậpvàsốnguyênk(k>0),Xuấtramàn hìnhkdòngchữ“Xinchào”4. Tinhtổng:S = 1 + 2 + 3 +  + n ,vơin>0 ́ ́5. Tinhtổng: S (n) = 1 − 2 + 3 − 4 +  + (−1) n +1 n ,vơin>0 ́ ́6. Nhâpvaobacanha,b,ccuatamgiac.Xuất ̣ ̀ ̣ ̉ ́ ramanhinhtamgiacđothuộcloaitamgiac ̀ ̀ ...