zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Hệ điều hành

Tin học cơ sở - Chương 7

Chia sẻ: Nguyễn Văn Thành | Ngày: | Loại File: DOC | Số trang:8

Báo xấu

105
lượt xem 7
download

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

Trước khi xem xét đặc trưng của “bài toán” ta xét một số ví dụ. Ví dụ 1. Bài toán kiểm tra tính nguyên tố. Cho: Số nguyên dương N; Cần biết: N có là số nguyên tố hay không? Ví dụ 2. Bài toán quản lý hồ sơ cán bộ. Cho: Hồ sơ gốc của các cán bộ trong cơ quan

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tin học cơ sở - Chương 7

Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin CHƯƠNG 7. GIẢI THUẬT 7.1. KHÁI NIỆM BÀI TOÁN VÀ GIẢI THUẬT Trước khi xem xét đặc trưng của “bài toán” ta xét một số ví dụ. Ví dụ 1. Bài toán kiểm tra tính nguyên tố. Cho: Số nguyên dương N; Cần biết: N có là số nguyên tố hay không? Ví dụ 2. Bài toán quản lý hồ sơ cán bộ. Cho: Hồ sơ gốc của các cán bộ trong cơ quan Cần biết: Bảng thống kê, phân loại cán bộ theo trình đ ộ văn hoá Qua các ví dụ trên, ta thấy các bài toán được cấu tạo bởi hai thành phần c ơ b ản: • Thông tin vào (input): cái cho trước • Thông tin ra (output): cái cần tìm Như vậy, việc cho một bài toán có nghĩa là mô t ả rõ input và output c ủa nó. Cho bài toán nghĩa là làm rõ câu hỏi "Có các dữ ki ện gì và phải làm gì?" nh ưng không cho biết "Phải làm thế nào". Việc giải bài toán có nghĩa là xu ất phát t ừ input dùng một số hữu hạn số lần thực hiện các thao tác thích h ợp đ ể tìm đ ược output theo yêu cầu của bài toán đã đề ra. Lưu ý rằng trong toán học có một xu hướng nghiên c ứu đ ịnh tính các bài toán. Theo xu hướng này, khi xem xét các bài toán, người ta ch ỉ cần ch ứng t ỏ s ự t ồn t ại của output khi cho input và nếu có thể, xét xem có bao nhiêu "l ời gi ải" và nghiên cứu tính chất của chúng. Trong các nghiên c ứu nh ư v ậy, nhi ều khi ta không c ần tìm ra lời giải một cách tường minh nhưng bằng cách dùng các công c ụ toán h ọc khác nhau một cách thích hợp ta vẫn có th ể ch ứng minh chặt ch ẽ các đi ều kh ẳng định liên quan đến lời giải. Chẳng hạn, định lý c ủa gi ải tích kh ẳng đ ịnh r ằng n ếu hàm f(x) liên tục trên đoạn [a, b] và f(a). f(b)
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Ví dụ, cho hai số nguyên dương a, b. Cần xây d ựng gi ải thu ật đ ể tìm ước s ố chung lớn nhất (UCLN) của a và b. D ưới đây là gi ải thu ật Euclid đ ề xu ất cho bài toán nêu trên dựa trên một tính chất hiển nhiên là : Nếu a = b thì chính b là USCLN của a và b. Ngược lại thì USCLN(a,b) = USCLN(b-a, a) n ếu a < b và USCLN(a,b) = USCLN(b, a-b) nếu a>b. Bài toán • input : a, b nguyên dương • output: UCLN của a và b Giải thuật Euclid Bước 1: Nhập a và b Bước 2: Nếu a = b thì lấy giá trị chung này làm USCLN rồi kết thúc. Bước 3: Nếu a> b thì bớt a đi một lượng là b rồi chuyển bước 5. Bước 4: Bớt b đi một lượng là a rồi quay trở lại bước 2. Bước 5: Kết thúc. Các thao tác bao gồm: • Phép gán trị: xây dựng các giá trị c ủa đ ối t ượng (ví d ụ b ớt a đi m ột l ượng là b hay cho USCLN là a). • Phép dừng, kết thúc quá trình xử lý. • Phép chuyển có hoặc không có điều kiện cho phép th ực hi ện ti ếp t ừ m ột bước nào đó ví dụ sau bước 2 quay trở lại bước 1. Ở cuối bước 3 của giải thuật trên ta gặp thao tác "trở lại bước 2". Trong tr ường hợp này bộ xử lý sẽ chuyển sang thực hiện bước 2 của giải thu ật. Khi di ễn đ ạt giải thuật ta ngầm qui định rằng nếu không gặp phép chuy ển đi ều khi ển thì b ộ x ử lý sẽ thực hiện tuần tự: sau bước thứ i sẽ chuy ển sang b ước th ứ i + 1. Nh ư v ậy bước 3 nếu không quay về bước 2 thì sẽ thực hiện tiếp bước 4. 7.2. MỘT SỐ ĐẶC TRƯNG CỦA GIẢI THUẬT Người ta thường liệt kê các đặc trưng sau đây của giải thuật: 7.2.1. Tính kết thúc (tính dừng) Giải thuật phải đưa ra được output sau một số hữu hạn bước thực hi ện. Gi ải thuật Euclid tìm UCLN thoả mãn tính dừng vì sau m ỗi b ước ta th ấy t ổng a+b gi ảm thực sự nhưng không được hơn 2. Vì vậy quá trình trên nh ất đ ịnh ph ải d ừng sau một số hữu hạn bước. Lưu ý rằng số bước của một quy tắc thao tác có thể là h ữu hạn nh ưng quy t ắc đó không có tính dừng. Ví dụ, Xét quy tắc sau: Bước 1: Xoá bảng Bước 2: Vẽ hình tròn Bước 3: Quay lại bước 1 Quy tắc đó có 3 bước nhưng không có tính dừng 53
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin 7.2.2. Tính xác định Tính xác định của giải thuật đòi hỏi ở mỗi b ước các thao tác ph ải hoàn toàn xác định, đơn trị không có sự nhập nhằng, lẫn lộn, tuỳ ti ện. Nói cách khác, trong cùng một điều kiện, các chủ thể xử lý dù là người hay máy thực hi ện cùng m ột b ước của giải thuật thì phải cho cùng một kết quả. Nhờ tính chất này mà việc thực hiện thuật toán thuần tuý mang tính c ơ h ọc, không cần bất kỳ một sự chỉ dẫn nào về cách giải bài toán cả. 7.2.3. Tính phổ dụng Tính phổ dụng có nghĩa là một giải thuật có thể được áp dụng v ới m ột l ớp các bài toán với input thay đổi chứ không chỉ áp d ụng cho m ột tr ường h ợp c ụ th ể. Gi ải thuật Euclid nói trên có thể áp dụng cho bất kỳ cặp hai s ố t ự nhiên Cần lưu ý là trong khi tính dừng và tính xác đ ịnh là đi ều ki ện c ần đ ể m ột quá trình là một giải thuật thì tính phổ dụng chỉ là một tính chất th ường th ấy vì có nhi ều bài toán có input hoàn toàn xác định, không t ồn t ại m ột l ớp các bài toán t ương t ự. 7.2.4. Đại lượng vào Mỗi giải thuật có một hoặc nhiều đại lượng vào. Ví dụ, Gi ải thu ật Euclid ở trên có đại lượng vào là a và b. 7.2.5. Đại lượng ra Sau khi giải thuật đã được thực hiện xong nó phải cho ra kết qu ả: Ví d ụ, Gi ải thuật Euclid cho UCLN của 2 số a và b 7.3. CÁC PHƯƠNG PHÁP DIỄN TẢ GIẢI THUẬT Người ta thường diễn tả giải thuật bằng một trong ba cách thức sau đây: 7.3.1. Liệt kê từng bước Liệt kê ra các thao tác, các chỉ thị thực hiện bằng ngôn ng ữ t ự nhiên. Ví dụ, có N que diêm. Hai người chơi luân phiên b ốc diêm. M ỗi l ượt, m ỗi ng ười bốc từ 1 đến 3 que diêm. Người nào bốc cuối cùng s ẽ th ắng cu ộc. Giải thuật để người đi trước luôn thắng cuộc được diễn tả bằng cách liệt kê từng b ước nh ư sau: Bước 1: Nhập N. Bước 2: Bốc 3 que rồi đợi đối phương đi. Bước 3: Đối phương bốc (giả sử x que, 0
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Hình 7.1. Các loại biểu diễn hình học trong sơ đồ khối Khối tính toán được biểu diễn bằng hình chữ nhật. Trong kh ối này ta vi ết m ột hoặc một dãy các thao tác như tạo giá trị, hoặc là một nhóm công vi ệc. N ếu đ ể thể hiện việc tính giá trị ta sẽ dùng dấu gán := v ới ý nghĩa đ ại l ượng đ ứng bên trái dấu gán được gán giá trị cho biểu thức phía ph ải d ấu gán. Kh ối tính toán có nhiều đường đi đến và 1 đường đi ra. Khối điều kiện được biểu diễn bằng hình thoi. Trong khối này ta viết một điều kiện. Tuỳ theo điều kiện này thoả mãn hay không mà vi ệc th ực hi ện ti ếp theo s ẽ được chỉ dẫn bởi một trong hai đường đi ra mang dẫu + (cho tr ường h ợp đúng) hoặc dấu - (cho trường hợp sai). Như vậy khối điều kiện có một đ ường đi đến và hai đường đi ra. Hai khối đặc biệt là khối bắt đầu và khối kết thúc đ ược bi ểu di ễn b ằng hình tròn chỉ rõ điểm bắt đầu và điểm kết thúc của giải thuật. Kh ối bắt đầu không có đường đi đến và có 1 đường đi ra. Khối kết thúc không có đ ường đi ra, có th ể có một hoặc nhiều đường đi tới. Trong khối input ghi rõ các đại lượng vào, và ở kh ối output ghi các đ ại l ượng ra. Khối input có thể đặt kế tiếp khối bắt đầu, còn khối output có thể đ ặt li ền tr ước khối kết thúc. Chúng ta dùng lưu đồ ở Hình 7.2 di ễn t ả l ại gi ải thu ật Euclid tìm UCLN c ủa hai s ố nguyên dương. Nhập a, b đúng d := a In d a=b ? sai đúng sai a>b ? a:= a - b b := b-a 55
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Hình 7.2. Lưu đồ cho giải thuật Euclid 56
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Hình 7.3 là lưu đồ cho bài toán bốc diêm. Trong các ô thao tác không ch ỉ là phép gán mà có thể là mô tả một hành động nào đó. Lấy 3 que Người đầu sai Số diêm Tuyên bố còn >0 ? thắng đúng cuộc Đối phương lấy x que diêm Ta lấy 4-x que Người đầu Hình 7.3. Lưu đồ giải thuật trò chơi bốc diêm 7.3.3.Ngôn ngữ thuật toán Cách thức này dựa trên hệ thống dùng các ký hi ệu và quy t ắc đ ể mô t ả, gi ải thu ật một cách nhất quán, tựa một ngôn ngữ tự nhiên nào đó bằng m ột s ố cách nói như “trong khi một điều kiện thoả mãn thì lặp l ại m ột nhóm thao tác “ hay “nếu một điều kiện thoả mãn thì thực hiện nhóm thao tác này ng ược lại th ực hi ện nhóm thao tác kia” hay “sau thao tác này thì thực hiện thao tác kia ”. Như vậy, các diễn đạt đó chỉ rõ cách thiết lập thứ tự các thao tác và đ ược g ọi là cấu trúc điều khiển. Cấu trúc điều khiển chính là cách thể hi ện giải thuật c ủa các ngôn ng ữ l ập trình bậc cao mà ta sẽ thảo luận kỹ hơn trong phần ngôn ng ữ l ập trình. Ví dụ, thuật giải Euclid có thể thể hiện như sau: Trong khi a ≠ b thì lặp lại khối sau Nếu a > b thì Bớt a đi một lượng là b Nếu không thì Bớt b đi một lượng là a Cho tới khi a= b thì tuyên bố USCLN chính là giá trị chung c ủa a và b 57
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Hình 7.4. Thể hiện thuật toán Euclid bằng các cấu trúc điều khi ển 7.4. SƠ LƯỢC VỀ ĐÁNH GIÁ GIẢI THUẬT Đối với một bài toán, có thể có nhiều giải thuật nh ưng chúng ph ải cho cùng m ột output đối với một input. Tuy nhiên chúng có thể khác nhau v ề hi ệu qu ả: • Hiệu quả thời gian: Tốc độ xử lý là nhanh hay ch ậm. Ta có th ể đánh giá căn cứ vào số bước thực hiện. • Hiệu quả không gian: Có thể đánh giá không gian lưu trữ theo s ố các đ ối tượng dùng để ghi nhớ các kết quả (kể cả kết quả trung gian). Ví dụ: Để tìm USCLN có thể có nhiều giải thuật như: Giải thuật 2: Bước 1: Nhập a và b. Bước 2: Phân tích các số a và b thành tích của các thừa số nguyên t ố. Bước 3: Lấy tích của các thừa số chung với số mũ nhỏ nhất làm USCLN. Bước 4: Kết thúc xử lý. Giải thuật 3 : Giải thuật Euclid cải tiến Bước 1: Nhập a và b. Bước 2: Chia a cho b tìm số dư r. Bước 3: Nếu r = 0 thì thông báo kết quả: UCLN là b rồi chuy ển b ước 5. Bước 4: Gán giá trị b cho a, gán giá trị r cho b r ồi quay tr ở l ại th ực hi ện b ước 2. Bước 5: Kết thúc. Ta thấy xét về hiệu quả cả về không gian và thời gian thì gi ải thu ật 2 kém hi ệu quả hơn giải thuật Euclid đã trình bày ở trên. Gi ải thu ật 3 th ực s ự là m ột c ải ti ến so với giải thuật Euclid mà ta đã trình bày tr ước đây vì phép chia l ấy ph ần d ư th ực tế đã thay cho hàng loạt phép trừ nói trong gi ải thu ật Euclid. Vì v ậy trong tr ường hợp chung nó tìm được USCLN với số bước xử lý ít hơn nhiều. Trong Tin học có cả một ngành chuyên đánh giá đ ộ ph ức t ạp c ủa gi ải thu ật, ch ủ yếu là đánh giá về hiệu quả thời gian. Thực tế sử dụng cho thấy thách th ức v ề không gian lưu trữ có thể giải quyết dễ hơn thách thức về thời gian thực hi ện. Bài tập 1. Giải thuật là gì? Cho ví dụ? 2. Hãy viết giải thuật vẽ đồ thị của hàm số y = a/x (v ới a khác 0) thông qua đ ồ th ị của hàm số y = ax? 3. Cho tam giác ABC có góc vuông A và cho bi ết cạnh a và góc B. Hãy vi ết gi ải thuật để tính góc C, cạnh b và cạnh c? 4. Trình bày tính chất xác định của giải thuật và nêu rõ nghĩa c ủa tính ch ất này? 5*. Hãy phát biểu giải thuật để giải bài toán sau: "Có m ột s ố qu ả táo. Dùng cân hai đĩa (không có quả cân) để xác định quả táo nặng nhất"? 6. Quy tắc chơi sau đây có phải là một giải thuật hay không? 58
Ch¬ng 7 - Gi¶i thuËt xö lý th«ng tin Giả sử cho trước một cuốn sách tiếng Việt. a) Hãy mở một trang có chữ số tận cùng bằng 5. b) Hãy lấy từ đầu tiên của trang đó. c) Hãy xem chữ cái đầu tiên của từ đó nếu ch ữ cái đó là m ột ch ữ t ừ A đ ến H thì bạn thắng, ngoài ra thì bạn thua. 7. Hãy xác định input và output cho các bài toán sau đây: a) Rút gọn một phân số. b) Kiểm tra xem ba số cho trước a, b và c có th ể là đ ộ dài ba c ạnh c ủa m ột tam giác hay không? c) Tính trung bình cộng của hai số. d) Dùng một cốc phụ để tráo nước ở hai cốc cho trước. e) Tìm chu vi và diện tích của hình tròn có bán kính cho tr ước. 59

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.