Giáo trình Tin học đại cương part 6

Chia sẻ: Akjshdj Aksjdh | Ngày: | Loại File: PDF | Số trang:19

0
189
lượt xem
82
download

Giáo trình Tin học đại cương part 6

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'giáo trình tin học đại cương part 6', tài liệu phổ thông, tin học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:
Lưu

Nội dung Text: Giáo trình Tin học đại cương part 6

  1. ñây “thư” là m t t p d ng text, hành ñ ng chuy n thư ñư c th c hi n theo phương th c truy n g i các t p này trên các ñư ng truy n d n c a m ng. Trong nhi u trư ng h p thư còn có t ñ ng nghĩa là thông ñi p (message), ñúng ra thông ñi p c n ñư c hi u là m t thư ng n không vư t quá m t câu. E- mail là d ch v cơ b n nh t và ph thông nh t trên m ng, là n n t ng ñ xây d ng m t văn phòng không gi y (paperless office). 3.2 - Các mô hình ho t ñ ng c a d ch v E-mail: - Mô hình thông ñi p tr c ti p: Theo mô hình này, các thông ñi p ñư c g i tr c ti p, ngay l p t c t i các máy ñang ho t ñ ng trên m ng LAN. - Mô hình h p thư lưu: Là mô hình khách – ch c a d ch v thư ñi n t , theo ñó chương trình th c hi n d ch v này ñư c vi t thành hai ph n chương trình ch y ñ c l p tương ñ i: + Chương trình phía Client (khách) ch y trên các máy tr m làm vi c c a m ng và ph n phía Server (ch ) ch y trên máy ch c a m ng. Ngư i dùng so n th o thư, n ñ nh ñ a ch nh n và “ra l nh” g i thông qua chương trình client v máy ch c a m ng. + Chương trình Server ñón nh n các thư g i t Client, lưu tr vào các h p thư lưu. + M i ngư i dùng cũng nh n và ñ c thư c a mình b ng cách dùng chương trình phía client duy t danh sách các thư g i cho mình và ñ c thư quan tâm. + Chương trình Server cũng có th phát tín hi u báo có thư cho nh ng ngư i ñang làm vi c trên m ng. - Mô hình Internet Mail: Là mô hình liên k t các h p thư lưu trên Internet, m i h p thư lưu cho m t vùng. N u t t c các liên k t ñang ñư c th c hi n, thư s ñư c chuy n ñ n h p thư lưu ñích trong vài giây, trư ng h p ngư c l i nó s ñư c chuy n bư c qua t ng h p thư lưu và các ñư ng liên k t ñang th c hi n ñ ñ n ñích cu i cùng. 3.3 - T o hòm thư mi n phí v i Yahoo Có r t nhi u ñ a ch trang web ta có th t o ñư c m t ñ a ch thư mi n phí như Yahoo.com, hotmail.com, vietfun.com, … * Cách t o hòm thư mi n phí v i Yahoo: - Gõ ñ a ch www.yahoo.com (ho c gõ ñ a ch mail.yahoo.com) - Ch n Email ho c Chekmail - Ch n Sign Up Now K t qu xu t hiên c a s ta ph i khai báo các m c sau: +YahooID: Gõ tên hòm thư c n t o (Không d u, không cách) + Password: Gõ m t kh u (ít nh t 6 ký t , ph i t t ch ñ gõ ti ng vi t) - Retype password: Gõ l i m t kh u - Sercurity Question: Ch n câu h i tuỳ ch n (ch n b t kỳ) - Your answer: Gõ vào câu tr l i (ít nh t có 4 ký t ) - Birthday: Gõ ngày tháng năm sinh - Gender: Ch n gi i tính - Fist/Last name: Gõ h và tên ñ m - Langgue: Ch n ngôn ng - Zip Code: Gõ mã nư c - Industry: Ch n ngh nghi p (ch n b t kỳ) - Title: Ch n ch c v (ch n b t kỳ) - Enter the word: Gõ t hi n th h p dư i Ch n Submit this form ð trình Form 3.4 - G i và nh n thư v i Yahoo 96 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 96
  2. - Gõ ñ a ch www.yahoo.com ( ho c gõ ñ a ch mail.yahoo.com) - Ch n Email ho c Mail - Gõ ñ a ch thư vào h p Yahoo ID - Gõ m t kh u vào Password - Ch n Sign In K t qu xu t hi n c a s : Hình 3.6 * Ch n Chek mail: ð nh n thư. K t q a có c a s sau: Hình 4.6 - Sender : Ngư i g i - Subject : Tiêu ñ thư - Date : Ngày g i - Size : Kích c file - Mu n ñ c thư nào thì nháy chu t vào thư ñó. - Mu n xoá thư thì ch n vào ô vuông bên trái thư, ch n nút Delete * Ch n Compose: ð g i thư. K t q a có c a s sau: 97 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 97
  3. Hình 5.6 - To : ð a ch ngư i nh n - Cc : ð a ch ñ ng g i t i - Bcc : ð a ch ñ ng g i t i - Subject : Tiêu ñ thư - Attachmets [Attech Files ] : G i kèm file - Ph n c a s tr ng phía ch a n i dung thư ta gõ vào. - Ch n nút Send ñ g i thư ñi 3.5 - G i nh n thư b ng Outlook Express * Kh i ñ ng Outlook Express - Kích chu t vào Start - Ch n Program - Ch n Outlook Express K t q a có c a s sau: Hình 6.6 - Inbox : Nơi lưu các thư ñư c t i xu ng và nó s ñó ñ n khi b n chuy n nó ñi nơi khác. - Outbox : Nơi lưu t m th i các thư chưa ñư c chuy n - Delete Items : Lưu các thư ñư c xoá Inbox (Tương t như Recycle Bin, n u mu n xoá h n các thư n m trong thư m c này thì b n ph i: Nháy chu t ph i trên bi u tư ng c a thư m c và ch n Empty Forder) - Sent Items : Lưu các b n sao c a các thư ñã g i ñi - Drafts : N u b n so n m t thư và c n ph i th c hi n m t s vi c khác trư c khi hoàn t t b c thư thì ch c n ñóng b c thư và lưu tr nó l i. Outlook Express s lưu b c thư này trong thư m c Drafts (b n nháp). * Khai báo Accounts - Vào menu Tool/ Ch n Accounts/ Ch n Mail/ Ch n Add/ Ch n Mail - Gõ tên vào h p Display name - Ch n Next - Khai báo máy ch nh n thư vào h p Incoming mail : + Thuê bao VNN: mail.hn.vnn.vn 98 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 98
  4. + Thuê bao FPT : imail.fpt.vn + Th VNN : fmail.hn.vnn + Th FPT : pop3.cardvn.net - Khai báo máy ch g i thư vào h p Outgoing mail : + Thuê bao VNN: mail.hn.vnn.vn + Thuê bao FPT : omail.fpt.vn + Th VNN : fmail.hn.vnn + Th FPT : smtp.cardvn.net - Ch n Next - Gõ tên c a Account vào h p Account name - Gõ m t kh u vào Password - Ch n Next - Ch n Finish - Ch n Close * G i thư: B n có th g i thư theo ba cách: - So n thư m i - H i ñáp thư cũ - Chuy n m t b c thư ñã nh n * So n m t thư m i: - Ch n New Mail ( ho c ch n menu Message/ New Message ). C a s New Message xu t hi n. Các thao tác tương t như g i thư t i yahoo. * Tr l i m t b c thư (H i ñáp thư cũ): - Ch n Inbox - Ch n thư ñ c - Có hai cách tr l i như sau: + Reply : N u b n ch n l a ch n này thì thư h i ñáp c a b n ch t i có m t ñ a ch e – mail trong dòng From c a ph n tiêu ñ . Không có b n sao nào ñư c g i t i m t ngư i nào trong ph n danh sách ñư c xác ñ nh m c Cc: C a b c thư ban ñ u + Reply All : N u b n ch n l a ch n này thì b c thư c a b n t i không ch tác gi mà còn t i t t c các m i ngư i trong danh sách Cc. * G i chuy n ti p thư ñã nh n: - Ch n thư c n chuy n - Ch n Forward Message {Ho c ch n menu Message (ho c Compose), ch n Forward hay n Ctrl + F} - Gõ vào ñ a ch c n g i ñi - Ch n Send Ho c có th chuy n thư dư i hình ñính kèm * Nh n thư ñ n: Ch n Inbox/ Ch n Send and Receive/ Nh p m t kh u (Password) vào , r i n OK * ð c thư ñ n: Ch n Inbox: N u có thư ñ n, s th y hi n th tên ngư i g i. B n ch vi c nh n chu t vào tên thư mu n ñ c n i dung c a nó phía dư i. * T i thư v (Download) máy tính: - Ch n thư mu n t i v - Ch n File/ Save As - Ch n ki u file: Mail (.eml), Text (.txt), web (.html). 99 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 99
  5. - Ch n v trí mu n lưu file ñó - ð t tên file r i b m OK 3.6. Download và m t s ñ a ch Internet * Download : - Là th c hi n t i m t ph n m m ho c m t chương trình trên m ng máy tính v máy tính c a mình. - Có th Download t các trang c th (n u có m c Download) ho c t các ñ a ch sau: + Microsoft Free Product Downloads (): ð i v i nh ng ngư i s d ng Win dows thì ñây là nơi b n có th tìm th y các fonts, trò chơi, các chương trình h tr cho Internet Explore và Microsoft Office…. + Download.com và Shareware.com (www.shareware.com): ðây là nh ng nơi cho phép b n tìm ki m trên m t cơ s d li u c a hơn 190.000 chương trình mi n phí và chia x . * M t s ñ a ch Internet: www.hau1.edu.vn Trang ch c a Trư ng ðH Nông nghi p I www.express.net Trang web c a Vi t nam Thông t n xã www.ptcenter.net Trang web c a trung tâm tin h c PT www.home.vnn.vn Trang web c a VDC www.msn.com Trang web c a hãng Microsoft www.fpt.vn Trang c a FPT www.vnn.vn Trang c a VASC www.quochoi.gov.vn Trang c a Qu c h i www.vtv.org.vn Trang c a Truy n hình Vi t Nam www.nxbgd.com.vn Trang c a Nhà xu t b n giáo d c www.ykhoa.com.vn Trang Y khoa b ng Ti ng Vi t www.laodong.com.vn Trang báo Lao ñ ng www.nhandan.org.vn Trang báo Nhân dân www.vietnamtourism.com.vn Trang c a Du l ch Vi t www.hut.edu.vn Trang ch c a Trư ng ðH Bách Khoa HN www.dec.edu.vn Trang web c a Trư ng ðH C n Thơ www.fao.org Trang web c a t ch c FAO www.manguon.com Trang web c a công ty M t bão v CNTT www.real-english.com Trang web h c ti ng Anh tr c tuy n www.caycanhvietnam.com Trang web gi i thi u v cây c nh Vi t nam www.bkav.com.vn Trang web c a Trung tâm Ph n m m và Gi i pháp An ninh m ng ðH Bách khoa HN www.hoahoctro.com Trang báo Hoa h c trò www.loveclub.saigonnet.vn Câu l c b tình yêu, hôn nhân và gia ñình www.yahoo.com Trang ch c a Yahoo www.google.com Trang ñ tìm ki m www.download.com Trang ch ñ t i các ph n m m www.cnn.com Trang ch c a hãng CNN www.cocacola.com Trang ch c a hãng Cocacola www.healthfinder.gov Trang cung c p các thông tin v y t www.asd.com Trang thông tin v các trư ng h c M www.amazon.com C a hàng sách l n nh t th gi i. 100 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 100
  6. Câu h i ôn t p chương V 1. M ng Internet là gì? Các ch c năng chính c a m ng Internet. 2. ð m t máy tính các nhân k t n i ñư c vào m ng Internet c n có nh ng gì ? 3. Trình duy t Internet Explorer có nh ng ch c năng gì? 4. E-mail là gì? Các mô hình ho t ñ ng c a d ch v E-mail. 5. Cách t o hòm thư mi n phí v i Yahoo và v i Outlook Express. 101 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 101
  7. CHƯƠNG VI: GI I THU T 1. Khái ni m gi i thu t (Algorithms) - Khi c n gi i quy t m t bài toán trong th c t v i s tr giúp c a máy tính ñi n t ta thư ng ph i bi t d li u vào c a bài toán (Input) là gì? và bài toán yêu c u d li u ra (Output) là gì?. Bư c ti p theo ta ph i thi t l p ñư c các bư c thao tác c th ñ t Input ta có ñư c Output. Công vi c ñó trong tin h c ñư c g i là xây d ng gi i thu t. - Gi i thu t c a 1 bài toán là m t dãy các câu l nh (Statements) ch t ch và rõ ràng xác ñ nh m t trình t các thao tác trên m t s ñ i tư ng nào ñó sao cho sau m t s bư c h u h n th c hi n ta thu ñư c k t qu mong mu n. - V i ñ nh nghĩa như v y ta th y r ng ñ i v i m t bài toán c th có th có nhi u gi i thu t khác nhau nhưng t t nhiên là các gi i thu t ñó ph i cho cùng m t k t qu theo ñúng yêu c u c a bài toán. - Khi nghiên c u v gi i thu t thư ng ta ph i bi t ñư c gi i thu t ñó tác ñ ng lên d li u nào. Vi c l a ch n c u trúc d li u (Data structures) phù h p và vi c thi t l p ñư c các gi i thu t ñúng ñ n có c u trúc t t và hi u qu là nh ng v n ñ m u ch t c a công vi c thi t l p ph n m m. Chính vì v y mà Niklaus Wirth ngư i sáng l p ra ngôn ng l p trình Pascal ñã t ng k t: Gi i thu t+C u trúc d li u= Chương trình Ví d : Xây d ng gi i thu t tìm UCLN c a 2 s nguyên dương a và b, ký hi u (a,b) + ð i v i bài toán này ta có Input: 2 s nguyên dương a, b Output: (a,b) + Gi i thu t ñư c xây d ng d a trên tính ch t N u a=b thì (a,b)=a N u a>b thì (a,b)=(a-b,b) N u ab thì thay th a b i a-b, n u a
  8. 2. Các yêu c u v i gi i thu t Gi i thu t c a bài toán ph i tho mãn 3 yêu c u sau: Yêu c u 1: Tính d ng Gi i thu t ph i d ng sau m t s h u h n các thao tác, ñây là yêu c u h t s c quan tr ng v i m t gi i thu t Yêu c u 2: Tính ñúng ñ n Ta ph i ñ t câu h i "Li u gi i thu t có th hi n ñúng l i gi i c a bài toán không?" . Thông thư ng chúng ta cài ñ t gi i thu t dư i d ng chương trình và cho th c hi n trên máy tính v i m t s b d li u nào ñó, sau ñó so sánh v i nh ng k t qu mà ta ñã bi t. Nhưng cách th này ch kh ng ñ nh ñư c tính sai ch chưa th kh ng ñ nh ñư c tính ñúng ñ n c a gi i thu t. B ng cách s d ng các công c toán h c ta có th kh ng ñ nh ñư c tính ñúng ñ n c a 1 gi i thu t nhưng thư ng thì ñây là m t công vi c ph c t p. Yêu c u 3: Tính ñơn gi n và hi u qu Ta thư ng mong mu n xây d ng ñư c m t gi i thu t ñơn gi n, d hi u, d l p trình. Nhưng ñôi khi thu t gi i ñơn gi n l i gây ra s lãng phí th i gian và b nh . Do ñó m c tiêu là ph i xây d ng ñư c các gi i thu t có th i gian th c hi n nhanh, h n ch t i ña dung lư ng b nh dành cho vi c lưu tr nh ng k t qu trung gian. 3. Các cách di n t gi i thu t 3.1. Cách 1: Li t kê t ng bư c Ví d : Có 31 que diêm, ngư i và máy thay nhau b c. M i l n b c t 1 ñ n 4 que. Ai ph i b c sau cùng là thua. Hãy xây d ng thu t gi i sao cho máy b c trư c bao gi cũng thua. Bư c 1: Máy b c ng u nhiên x que diêm (1≤x≤4) Bư c 2: Ngư i b c (5- x) que, t ng s que diêm gi m ñi 5 que. N u s que diêm còn l i là 1 que thì chuy n sang bư c 3, n u không thì quay l i th c hi n bư c 1 Bư c 3: Tuyên b ngư i th ng cu c 3.2. Cách 2: S d ng lưu ñ S d ng phương ti n hình h c cũng là m t cách t t ñ minh ho gi i thu t c a 1 bài toán. Trong lưu ñ ngư i ta s d ng các hình sau, v i kí hi u + là ñúng, - là sai. - + Kh i l nh Kh i i u ki n Cung Kh i b t u và k t thúc 103 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 103
  9. a. C u trúc r nhánh - R nhánh d ng khuy t: if then (hình 1) - R nhánh d ng ñ : if then else (hình 2) - + - + K K L nh L nh 2 L nh 1 - C u l nh l a ch n: case Giá tr 1: Th c hi n l nh 1 Giá tr ình 1 c hi n l nh 2 H 2: Th Hình 2 .......................................... Giá tr n: Th c hi n l nh n else Th c hi n l nh (n+1) end - - - L nh (n+1) gt1 gt2 gtn + + + L nh 1 L nh 1 L nh n Hình 3 b. C u thúc l p + L p m t s l n ñ nh trư c: D ng 1: for i:=m to n do Th c hi n l nh v i i nh n các giá tr nguyên tăng t m t i n v i bư c nh y b ng 1 D ng 2: for i:=n downto m do Tương t như d ng 1 nhưng bư c nh y gi m b ng 1 + L p v i ñi u ki n trư c: while do < l nh> Khi ñi u ki n còn ñúng thì còn th c hi n l nh, quá trình l p k t thúc khi ñi u ki n sai (hình 1) + L p v i ñi u ki n sau: repeat until Khi ñi u ki n còn sai thì còn th c hi n l nh, quá trình l p k t thúc khi ñi u ki n ñúng (hình 2) - + K L nh LLnh L nh nh K - + 104 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 104
  10. 3.3 Cách 3: S d ng gi ngôn ng có c u trúc t a ngôn ng l p trình b c cao Là phương pháp di n t gi i thu t d a vào các c u trúc ñi u khi n, cùng v i các t khoá c a m t ngôn ng l p trình b c cao nào ñó. Trong giáo trình này ta s s d ng ngôn ng t a Pascal ñ di n t gi i thu t. Cách di n ñ t này ñã ti p c n g n hơn v i ngôn ng l p trình. Ví d : V i thu t gi i tìm UCLN trên ta có th di n ñ t như sau while a≠b begin if a>b then thay a b i a-b else thay b b i b-a end write ư c chung l n nh t là a 4. Thi t k gi i thu t 4.1. Mô-ñun hoá và vi c gi i quy t bài toán Nh ng bài toán ta g p trong th c t thư ng là ph c t p, trong trư ng h p ñó ngư i ta thư ng chia bài toán thành nh ng bài toán nh và d gi i quy t hơn. Nghĩa là coi bài toán ban ñ u là Mô- ñun chính, ta chia nó thành các Mô- ñun con, và m i Mô- ñun con này có th l i ñư c chia thành các Mô- ñun nh hơn... Cách gi i quy t bài toán như v y ngư i ta thư ng g i là chi n thu t "Chia ñ tr "(divide and conquer). Trong khi l p trình vi c chia chương trình chính thành các chương trình con th hi n tính có c u trúc c a ngôn ng l p trình v m t chương trình 4.2. Tinh ch nh t ng bư c gi i thu t Tinh ch nh t ng bư c là phương pháp thi t k gi i thu t g n li n v i l p trình. Bư c ñ u gi i thu t ñư c minh ho b ng ngôn ng t nhiên, càng các bư c sau ngôn ng t nhiên ñư c thay th b i ngôn ng t nhiên pha l n ngôn ng l p trình mà ta g i là gi ngôn ng . Ta có sơ ñ sau: Ngôn ng t nhiên→ Gi ngôn ng → Ngôn ng l p trình 4.3. Phân tích thu t gi i Phân tích gi i thu t ph i căn c vào 3 tiêu chu n ñ i v i m t gi i thu t: Tính d ng, tính ñúng ñ n, tính ñơn gi n và hi u qu . Vi c ki m tra gi i thu t là m t ph n h t s c quan tr ng, lý tư ng là khi có th kh ng ñ nh m t cách hình th c tính ñúng ñ n c a gi i thu t. Tuy nhiên trong th c t th i gian và công s c ñ vi t ra m t cách c n th n và ñ y ñ t t c nh ng chi ti t ch ng minh tính ñúng ñ n c a m t gi i thu t ph c t p thư ng là không cho phép. Ngư i l p trình thư ng áp d ng các bi n pháp sau: - Ch ng minh m t cách suy di n r ng nh ng bư c trong gi i thu t là ñúng ñ n. Nghĩa là gi i thu t b t ñ u b ng m t kh ng ñ nh (gi thi t) v d li u vào và dùng phương pháp suy lu n lôgic ñ ch ra r ng vi c th c hi n gi i thu t s cho m t kh ng ñ nh (k t lu n) v ñ u ra. - Th h ên gi i thu t b ng m t ngôn ng l p trình và th th c hi n chương trình v i các b d li u vào mà k t qu ta ñã bi t trư c. Thư ng thì các l i v cú pháp và l i lúc th c hi n chương trình thư ng d tìm và s a ch a còn các l i lôgic thư ng khó phát hi n hơn nhi u. 105 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 105
  11. - Có ñôi lúc viêc ki m tra chương trình ph i th c hi n th công, ki m tra t ng bư c, t ng th t c c a chương trình chính. K thu t này ñư c g i là “ñi b qua chương trình”(Walking through the program) - Quan tâm ñ c bi t t i th i gian th c hi n chương trình, th i gian th c hi n ph thu c r t nhi u vào vi c t ch c d li u ñưa vào (kích thư c d li u). 5. Gi i thu t s p x p (Sorting) S p x p là m t trong s yêu c u thư ng xuyên xu t hi n trong quá trình x lý s li u. B n ch t c a thu t gi i s p x p là b trí l i v trí c a s li u theo th t tăng d n ho c gi m d n. Có nhi u gi i thu t s p x p trong tin h c, trong giáo trình này chúng ta s ñ c p ñ n m t s thu t gi i ñơn gi n ñó là s p x p l a ch n (selection sort), s p x p chèn (insertion sort) và s p x p n i b t (bubble sort). ð ñơn gi n gi s yêu c u c a bài toán là: S p x p m t dãy s cho trư c a1, a2, ......, an theo th t tăng d n. 5.1 S p x p l a ch n (selection sort) Thu t gi i ch n ñư c di n t như sau: Tìm ph n t nh nh t trong dãy s và hoán v nó v i ph n t ñ u tiên, tìm ph n t nh nh t k ti p và hoán v nó v i ph n t th hai. Ti p t c quá trình này ñ n khi toàn b dãy s ñư c s p x p. procedure Selection_Sort; begin for i:=1 to n-1 do begin m:=i for j:=i+1 to n do if aj
  12. procedure Insertion_Sort begin for i:=2 to n do begin k:=ai j:=i while aj-1>k do begin aj:=aj-1, j:=j-1 end aj:=k end end Ví d Dãy s ban ñ u : 3 6 -2 7 5 i=2 3 6 -2 7 5 i=3 -2 3 6 7 5 i=4 -2 3 6 7 5 i=5 -2 3 5 6 7 5.3 S p x p n i b t (bubble sort) Thu t gi i này còn có tên g i khác là s p x p b ng cách ñ i ch tr c ti p (exchange sort), thu t gi i n i b t ñư c di n t như sau: Duy t dãy s theo th t t ph i sang trái n u hai ph n t k c n ngư c th t thì ñ i ch cho nhau. Như v y sau lư t duy t ñ u tiên ph n t ñ u tiên s là ph n t nh nh t, sau lư t th hai ph n t nh th hai ñư c chuy n lên v trí th hai...c như v y dãy s s ñư c s p x p tăng d n. procedure Bubble_Sort begin for i:=1 to n-1 do for j:=n downto i+1 do if aj
  13. 6.1 Tìm ki m tu n t (sequential searching) ðây là thu t gi i tìm ki m ñơn gi n nh t, ta s duy t tu n t dãy s , thu t gi i s k t thúc khi tìm th y ph n t b ng giá tr X ho c khi duy t h t dãy s nhưng không có ph n t nào có giá tr là X procedure Sequential_Searching begin i:=1 while ai≠ X do i:=i+1 if i=n+1 then không có ph n t c n tìm else v trí ph n t c n tìm là i end 6.2 Tìm ki m nh phân (binary searching) Gi s dãy s ñã ñư c s p x p tăng d n a1≤a2≤.....≤an (trư ng h p s p x p gi m d n thì tương t ), thu t gi i nh phân g n gi ng như khi ta tìm m t t trong t ñi n. ð tìm ph n t b ng X trư c tiên ta so sánh nó v i ph n t v trí gi a c a dãy s n u X nh hơn thì X ch có th trong m t n a trư c c a dãy n u ngư c l i thì X ch có th trong n a sau c a dãy. L p l i quá trình tìm ki m ñó ñ n khi tìm th y ho c dãy s tr nên r ng (không tìm th y). procedure Binary_Searching begin left:=1 right:=n repeat mid:=[(left+right)/2] (*Kí hi u [a] nghĩa là l y ph n nguyên c a s th c a*) if Xright) if X=amid then v trí c n tìm là mid else không có ph n t c n tìm end Ví d : Tìm ph n t 28 trong dãy s sau [4 15 28 33 67 99 103] L pl n1 [4 15 28] L pl n2 [28] 7. Gi i thu t ñ quy 7.1. Khái ni m ñ qui M t ñ i tư ng ñư c g i là ñ qui n u nó bao g m m t ph n c a chính nó hay ñư c ñ nh nghĩa b i chính nó. Trong khi thi t k gi i thu t ta thư ng thi t k dư i d ng các mô- ñun. Khi gi i thu t ñư c cài ñ t thành chương trình thí các mô- ñun s tương ng v i các chương trình con (hàm- function và th t c- procedure), Chương trình con ñư c g i là ñ qui n u trong thân c a nó có l i g i tr c ti p ho c gián ti p ñ n chính b n thân nó. ð qui có ý nghĩa ñ c bi t quan tr ng trong các ñ nh nghĩa toán h c 108 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 108
  14. Ví d 1: ð nh nghĩa s t nhiên + 0 là s t nhiên + S ti p theo c a m t s t nhiên là m t s t nhiên Ví d 2: ð nh nghĩa n! + 0!=1 + n!=n*(n-1)! n u n>0 - ð nh nghĩa m t phép ñ qui g m có 2 ph n + Trư ng h p suy bi n: Giúp cho quá trình ñ qui k t thúc + Ph n ñ qui (hay ph n qui n p): Trong ñó tác ñ ng c n ñư c th c hi n cho giá tr hi n th i c a các tham s ñư c ñ nh nghĩa b ng các tác ñ ng hay giá tr ñư c ñ nh nghĩa trư c ñây Trong ví d ñ nh nghĩa n! thì trư ng h p suy bi n ñ nh nghĩa 0!, ph n qui n p ñ nh nghĩa n! qua các giá tr c a n và giá tr c a (n-1)! D nh n xét, n u (n-1)! ñã tính ñư c thì n! s d dàng tính ñư c. V i cách suy di n tương t , (n-1)! s tính ñư c n u như (n-2)! ñã tính ñư c... cu i cùng 1! s tính ñư c n u 0! ñã tính ñư c. Ta th y r ng 0! ñã cho trong ñ nh nghĩa. Do v y ñi ngư c t cu i, vì 0! ñã tính ñư c nên 1! cũng tính ñư c,....,sau khi (n-1)! ñã có ta s nh n ñư c n! Minh ho : Tính 3! 3!=3*2!=3*2=6 2!=2*1!=2*1=2 1!=1*0!=1*1=1 0!=1 Gi i thu t ñư c vi t dư i d ng th t c hàm (t a Pascal) như sau: function giaithua(n) begin if n=0 then giaithua:=1 (* trư ng h p suy bi n*) else giaithua:=n*giaithua(n-1) (* ph n ñ qui*) end Chú ý: Không ph i lúc nào tính ñ qui trong cách gi i bài toán cũng th hi n rõ nét và d phát hi n như ví d trên. Do ñó mu n bi t gi i thu t c a m t bài toán có th thi t k dư i d ng gi i thu t ñ qui ñư c hay không? Có th th y câu tr l i qua vi c tr l i các câu h i sau : + Có th ñ nh nghĩa ñư c bài toán dư i d ng m t bài toán cùng lo i nhưng “nh ” hơn không? + Kích thư c c a bài toán s gi m ñi m i bư c g i ñ qui như th nào? + Trư ng h p nào c a bài toán ñư c coi là trư ng h p suy bi n? 7. 2. Ví d v gi i thu t ñ qui : Bài toán tháp Hà N i Bài toán Tháp Hà N i là m t ví d c ñi n cho th y thu t toán ñ qui là ñ c bi t thích h p. Có th gi i quy t bài toán m t cách d dàng n u dùng ñ qui, nhưng cách gi i không ñ qui là tương ñ i khó. N i dung bài toán: T i c c A có n chi c ñĩa, ñĩa to dư i, ñĩa nh trên. Chuy n các ñĩa t c c A sang c c C có th nh c c B làm v trí trung chuy n theo các quy t c sau: - M i l n ch ñư c chuy n m t ñĩa và ph i là ñĩa trên cùng - ðĩa l n không bao gi ñư c phép n m trên ñĩa nh 109 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 109
  15. - Khi chuy n m t ñĩa, nó ph i ñư c ñ t vào m t trong 3 c c trên Hãy ch ra th t các bư c chuy n. A B C M t truy n thuy t cho r ng các th y tu ði n Bramah ñư c cho m t bài toán ñ v i m t n n vàng có 3 kim vàng trên 1 c c có 64 ñĩa vàng. Khi h chuy n các ñĩa vàng theo các lu t c a bài toán trên, n u m i giây chuy n ñư c m t ñĩa và h b t ñ u công vi c t năm 0, ñ n khi hoàn thành công vi c thì s là ngày t n th . Nh ng ngư i m i b t ñ u có th gi i bài toán m t cách d dàng v i s các ñĩa là bé, nhưng h s r t khó khăn khi s ñĩa tăng lên 7,8 và l n hơn. Tuy nhiên v i m t nhà l p trình thì có th gi i bài toán m t cách không m y khó khăn. Cách gi i: N u có m t ñĩa, chuy n nó t c c A sang c c C. Bài toán gi i ñư c v i n=1 Gi s r ng bài toán có nghi m v i n-1 ñĩa , nghi m v i n ñĩa có th nh n ñư c m t cách d dàng nh dùng phép ñ quy: + Chuy n n-1 ñĩa trên cùng c c A sang c c B, dùng c c C làm trung chuy n + Chuy n ñĩa còn l i c c A sang c c C + Chuy n n-1 t c c B sang c c C, dùng c c A làm trung chuy n Ta có th vi t gi i thu t c a bài toán Tháp Hà N i như sau: procedure Move(n,A,B,C) (* Chuy n n ñĩa t c c A sang c c C, dùng c c B làm trung chuy n*) begin if n=1 then chuy n ñĩa t A sang C else begin Move(n-1,A,C,B) (* Chuy n n-1 ñĩa t A sang B, dùng C làm trung chuy n*) Move(1,A,’ ‘,C) (* Chuy n 1 ñĩa t c c A sang c c C*) Move(n-1,B,A,C) (* Chuy n n-1 ñĩa t B sang C, dùng A làm trung chuy n*) end end 110 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 110
  16. Bài t p chương VI: Thu t gi i Vi t gi i thu t cho các bài toán sau: 1. Tính n giai th a: n! =1.2...n v i n>1 2. Tính các t ng: S=1/2 + 1/4 +...+ 1/(2k) Q=1.1!+2.2!+...+n.n! 3. Tìm và in ra t t c các s chính phương nh hơn m t s cho trư c, cho bi t có bao nhiêu s chính phương như v y. 4. Vi t chương trình gi i bài toán c : " V a gà v a chó, bó l i cho tròn, ba mươi sáu con, m t trăm chân ch n. H i có bao nhiêu gà, bao nhiêu chó?" 5. Vi t chương trình tìm ư c s chung l n nh t c a 2 s nguyên dương cho trư c. x x2 xn + ... v i ñ chính xác ε=10-4 ( ABS(xn/n!) < ε ), giá tr x 6. Tính Ex= 1 + + + ...+ 1! 2 ! n! ñư c nh p vào t bàn phím khi ch y chương trình. 7. C n có 50000 ñ t các lo i gi y b c 1000ñ, 2000ñ và 5000ñ. Tìm t t c các phương án có th . 8. Chuy n m t s th p phân nguyên dương thành m t s nh phân, in ra màn hình d ng X10 = Y2 9. Tính tích phân xác ñ nh c a m t hàm s trên m t ño n cho trư c 10. Vi t chương trình tìm và in ra màn hình các s nguyên t nh hơn m t s cho trư c. 11. Cho dãy s sau: a1,a2,....,an . Vi t chương trình tìm ph n t l n nh t, ph n t nh nh t c a dãy s ñó. 12. Cho dãy s sau: a1,a2,....,an . Vi t chương trình s p x p dãy theo th t tăng d n . 13. Cho dãy s sau: a1,a2,....,an . Vi t chương trình ñ m s ph n t dương và xoá ñi ph n t th m trong dãy (m
  17. PH N II NGÔN NG L P TRÌNH TURBO PASCAL CHƯƠNG I: C U TRÚC C A CHƯƠNG TRÌNH PASCAL 1. Gi i thi u v ngôn ng l p trình 1.1. Ngôn ng l p trình là gì ? Ngôn ng l p trình là m t h th ng các kí hi u, h th ng các quy t c cú pháp và m t b các ch th (hay còn g i là câu l nh) dùng ñ vi t các thu t toán gi i các bài toán thành các chương trình máy tính. Nh ng chương trình này s ñư c ñưa vào máy "ch y" ñ tính toán, x lí bài toán. Ngôn ng l p trình ra ñ i cùng v i s ra ñ i c a MTðT vì khi MTðT ra ñ i ñương nhiên ngư i ta ph i nghĩ ñ n vi c xây d ng ngôn ng cho chúng. Các th h MTðT liên t c phát tri n, do ñó ngôn ng l p trình cũng phát tri n theo. Có nhi u lo i ngôn ng l p trình khác nhau, t ngôn ng b c th p chuy n lên ngôn ng b c cao. + Ngôn ng b c th p (ngôn ng máy): Ch s d ng 2 kí hi u 0 và 1 ñ mã hoá m i ñ i lư ng và phép toán. Ngôn ng này có ưu ñi m là chương trình ch y nhanh, không ph i qua khâu d ch. Tuy nhiên nh ng chương trình vi t b ng ngôn ng này r t c ng k nh, vi t m t r t nhi u th i gian, d sai sót, khó ki m tra; m t khác m i lo i máy có m t ngôn ng máy riêng. + Ngôn ng t p h p: Kh c ph c m t s như c ñi m trên ngư i ta nghĩ cách thay th m t s mã nh phân b ng các ch cái và cho ra ñ i ngôn ng t p h p (còn g i là ngôn ng kí hi u). Ưu ñi m là vi c l p trình ñã d dàng hơn, tuy nhiên c n ph i có chương trình d ch t ngôn ng t p h p ra ngôn ng máy, và v n còn ph thu c vào t máy. + Ngôn ng b c cao: Chương trình ñư c vi t g n v i ngôn ng t nhiên c a con ngư i, do ñó d dàng cho ngư i l p trình, tuy nhiên chương trình s ch y ch m hơn. Năm 1958, ALGOL - ngôn ng l p trình b c cao ñ u tiên ra ñ i. Năm 1960 nó ñư c b sung, ch nh lí và có nh hư ng sâu s c ñ n các ngôn ng l p trình b c cao sau này như FORTRAN, C, BASIC, PASCAL,... 1.2. Turbo Pascal PASCAL là ngôn ng l p trình b c cao c a tác gi Niklaus Wirth (giáo sư ngư i Thu sĩ), ñư c công b vào ñ u nh ng năm 1970. Tên PASCAL là ñ k ni m nhà Toán h c ngư i Pháp B. Pascal. PASCAL là ngôn ng l p trình có tính c u trúc và tính h th ng: các ki u d li u ña d ng, các c u trúc ñi u khi n ch t ch , các c u trúc kh i trong chương trình rõ ràng... PASCAL là ngôn ng l p trình có ñ nh ki u rõ ràng: các ñ i lư ng (bi n và h ng) ñã ñư c khai báo ñ s d ng v i ki u d li u này thì không th ñem dùng l n v i ki u khác. PASCAL ban ñ u ñư c sáng tác ñ làm ngôn ng d y h c cho nh ng ngư i m i h c l p trình. ð c tính sáng s a, d hi u, d ñ c c a nó giúp ngư i m i h c có th vi t m t chương trình máy tính m t cách d dàng. Sau khi ra ñ i, do có nhi u ưu ñi m,PASCAL ñã ñư c nhi u hãng máy tính phát tri n và cài ñ t cho nhi u h th ng máy tính, như: ISO PASCAL (PASCAL chu n ), ANSI PASCAL v.v. Ph bi n nh t hi n nay nư c ta cũng như trên th gi i là vi c cài ñ t TURBO PASCAL cho các h th ng máy tính. TURBO PASCAL ñư c hãng BORLAND INTERNATIONAL hoàn thi n v i các ưu ñi m là chương trình vi t g n, 112 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 112
  18. d ch nhanh, không ng ng ñư c c i ti n ñáp ng yêu c u c a ngư i s d ng. TURBO PASCAL ñã ñư c phát tri n qua các phiên b n ngày càng m r ng và ph c t p. Vi c khai thác sâu các tính năng c a t ng phiên b n là do kh năng và nhu c u c a ngư i l p trình. Giáo trình này ch n version 5.0 làm chu n ñ minh ho , tuy nhiên ngư i ñ c có th áp d ng cho các phiên b n sau này như 6.0, 7.0. 2. Yêu c u ph n m m và cách kh i ñ ng 2.1. Yêu c u ph n m m Ph n m m TURBO PASCAL có khá nhi u File, tuy nhiên ñ có th bư c ñ u h c và s d ng ñư c, trên ñĩa c n có t i thi u các file sau: TURBO.EXE file chính, ch a c chương trình d ch, h so n th o và các d ch v g r i... TURBO.TPL là thư vi n các chương trình m u có s n c a TURBO PASCAL N u có s d ng ñ ho thì c n chép thêm ñơn v GRAPH.TPU và m t s file ph tr khác tuỳ theo ki u màn hình và ki u ch s d ng. 2.2. Kh i ñ ng và thoát TURBO PASCAL Thông thư ng các file nói trên n m trong thư m c TP (ho c TURBO hay TP5, TP7 tuỳ theo phiên b n hay ngư i s d ng) Ta chuy n vào thư m c này b ng l nh CD TP↵, sau ñó gõ TURBO ↵ . Màn hình s hi n ra như sau: File Edit Run Compile Options Debug Break/Watch Line 1 Col 1 Insert Indent Unindent C:NONAME.PAS | F1-Help F5-Zoom F6-Switch F7-Trace F8-Step F9-Make F10-Menu Dòng 1: là dòng menu chính, trên ñó có ghi các m c cơ b n nh t ñ ngư i s d ng có th ch n b ng cách n ñ ng th i Alt+ ch cái ñ u c a m c. Ví d : Alt+F ñ m m c File. Dòng 2: là dòng tr ng thái, cho ngư i dùng bi t m t s thông s so n th o như to ñ con tr , ch ñ so n th o là vi t chèn hay vi t ñè, tên t p ñang làm vi c... Dòng cu i cùng là dòng hư ng d n, nh c ngư i s d ng m t s phím ch c năng chính. Ph n màn hình r ng gi a là ph n so n th o ñ ta nh p và ch y chương trình. Ngư i m i h c l p trình nên ghi nh ngay các phím ch c năng: F2 ghi t p ñang so n th o vào ñĩa. N u chưa ñ t tên s có thông báo ñ ta gõ tên vào (tên ñư c ñ t theo quy ñ nh c a MS-DOS ) 113 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 113
  19. F3 m t p m i Alt+F9 d ch chương trình Ctrl+F9 d ch và cho ch y chương trình Alt+X K t thúc PASCAL tr v h ñi u hành 3. Nh ng quy ñ nh v cách vi t bi u th c và chương trình 3.1. B kí t TURBO PASCAL s d ng b ch vi t như sau: - B 26 ch cái Latinh: A, B, ..., Z ; a, b, ..., z - B các ch s : 0, 1, ..., 9 - Các kí hi u Toán h c: +, -, * , /, =, , ... - D u g ch n i, d u ch m, d u ngo c và các kí hi u ñ c bi t khác: _ . , ; ? [ ] ( ) $ % ... 3.2 T khóa T khoá là m t s t dành riêng c a TURBO PASCAL, nh ng t này ñã ñư c gán s n nh ng ch c năng ñ c bi t, ta không ñư c dùng vào vi c ñ t tên hay các công vi c khác. Sau ñây là m t s t quan tr ng, b n ñ c s l n lư t bi t các t khoá và ch c năng c a t ng t qua các bài h c. - Các t khoá chung: Program, begin, end - Các t khoá ñ khai báo: uses, const, type, label, var procedure, function array, string, record, ... - Các t khoá l nh: if... then... else... case ...of .... for .... to ... do... while... do... repeat... until... - M t s tên chu n: Boolean, char, integer, real, read, readln, write, writeln, abs, cos, sin, sqrt, exp... 3.3 Tên Tên là m t dãy kí t dùng ñ ch tên các ñ i lư ng như tên h ng, tên bi n, tên ki u hay tên chương trình con. Tên ñư c ñ t theo quy t c sau: b t ñ u b i m t ch cái, r i ñ n ch s hay d u g ch n i và không dài quá 127 kí t (!). Tên thư ng ñư c ñ t mang tính g i nh . TURBO PASCAL không phân bi t ch hoa và ch thư ng khi vi t t khoá hay tên. Ví d : khi vi t chương trình gi i phương trình b c 2, ta có th ñ t tên chương trình là GIAI_PHUONG_TRINH_BAC2, ñ t tên bi n ch a bi t th c ∆ là delta (không ñư c dùng kí hi u ∆), ñ t tên các nghi m là X1 và X2,... - D u ch m ph y (;) dùng ñ ngăn cách các câu l nh trong m t chương trình - L i gi i thích ñư c ñ t trong c p d u (* ... *) ho c { ... }, các n i dung ñư c ch a trong c p d u này s b chương trình b qua trong khi d ch 114 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 114

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản