Kĩ thuật lập trình - Thuật toán

Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán v 1.0 - 10/2012 Thuật toán 1 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán chúng ta đã học... 2 1. Lập trình là gì ? 1.1. Lập trình và ngôn ngữ lập trình 1.2. Lịch sử và các hướng lập trình 1.3. Chương trình và thuật toán 1.4. Các bước trong lập trình 2. C# và .NET Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Giải bài toán trên máy tính 1. Xác định bài toán 2. Thiết kế thuật toán 3. Phân tích thuật toán 4. Cài đặt thuật toán 5. Kiểm tra / Bắt lỗi 6. [ Sửa lỗi ] 3 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Nội dung 1. Thuật toán 1.1. Khái niệm 1.2. Các tính chất 1.3. Phát triển thuật toán 2. Mô tả thuật toán 3. Các dạng thuật toán cơ bản 4. Ví dụ 4 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Thuật toán 5 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Thuật toán • Một tập các chỉ thị / lệnh đơn giản được xác định rõ ràng để giải quyết một bài toán nào đó • Nhận một tập các giá trị ở đầu vào (input) • Tính toán và trả ra một hoặc một tập các giá trị ở đầu ra (output) • Thuật toán = Logic + Điều khiển • Logic - trả lời câu hỏi “Thuật toán làm gì ? Giải quyết vấn đề gì ? Những yếu tố trong bài toán có quan hệ với nhau thế nào ?...” • Gồm các kiến thức chuyên môn mà bạn phải biết để có thể giải bài toán • Để giải bài toán tính diện tích hình cầu, bạn phải biết công thức tính diện tích hình cầu • Điều khiển - trả lời câu hỏi “Giải thuật phải làm như thế nào ?” 6 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Thuật toán • Có thể được mô tả bằng... • Ngôn ngữ tự nhiên • Ngôn ngữ lập trình • Mã giả • Lưu đồ • Cấu trúc dữ liệu - Phương pháp tổ chức dữ liệu • Chương trình = Thuật toán + Cấu trúc dữ liệu 7 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ - giải p.t bậc nhất 8 ax + b = 0 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ - giải p.t bậc nhất 9 Nếu a ≠ 0: x = -b/a Ngược lại, a = 0: Nếu b = 0: pt có vô số nghiệm Nếu b ≠ 0: pt vô nghiệm ax + b = 0 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ - tìm số lớn nhất 10 Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ - tìm số lớn nhất 11 Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Các câu hỏi về thuật toán • Thuật toán đã giải quyết được bài toán được phát biểu ? • Thuật toán đã được định nghĩa tốt ? • Thuật toán đưa ra được một kết quả ? • Thuật toán kết thúc sau thời gian tính toán hợp lý ? 12 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Tính chất Tính kết thúc (tính dừng) • ... quá trình thực hiện thuật toán phải kết thúc sau khi thực hiện một số hữu hạn các bước công việc 13 Bước 1 : Cho s = 0, i = 1 Bước 2 : Cộng thêm i vào s ( s = s + i ) Bước 3 : Tăng i thêm 1 ( i = i + 1 ) Bước 4 : Quay lại bước 2 Bước 5 : Nhận s là kết quả giải bài toán Bước 6 : Dừng Thuật toán tính tổng các số tự nhiên Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Tính chất Tính xác định • ... nếu trong những điều kiện như nhau thì kết quả thực hiện không phụ thuộc vào đối tượng thực hiện thuật toán • thuật toán phải rõ ràng, không nhập nhằng, không thể hiểu theo nhiều nghĩa 14 Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Tính chất Tính tổng quát • ... nếu thuật toán được dùng để giải cả một lớp bài toán cùng loại 15 Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Tính chất Tính xác định đầu vào - đầu ra • ... nếu xác định rõ các dữ liệu đầu vào và các dữ liệu đầu ra • đầu vào, đầu ra được xác định càng chính xác thì quá trình xây dựng thuật toán càng thuận lợi và thuật toán càng có chất lượng cao hơn 16 Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Tính chất Tính hiệu quả • ... nếu cho ra kết quả đúng trong mức chi phí ít nhất về thời gian, không gian 17 Thuật toán tìm giá trị lớn nhất Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Phát triển thuật toán • Xác định đầu vào (Input) • Xác định các bước xử lý (Process) • Xác định đầu ra (Output) • Vẽ biểu đồ HIPO • Xác định các chương trình con (Module) 18 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Xác định đầu vào • Chúng ta cần dữ liệu gì ? • Chúng ta lấy dữ liệu đó như thế nào ? • Dữ liệu tồn tại ở dạng nào ? 19 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Xác định đầu ra • Những kết quả nào chương trình phải trả ra cho người sử dụng ? • Kết quả phải được trả ra ở dạng nào ? 20 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Xác định các bước xử lý • Cách xử lý dữ liệu để đạt được kết quả có ý nghĩa ? • Áp dụng công thức gì ? 21 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Vẽ biểu đồ HIPO 22 Hierarchy of Inputs Processes & Outputs Bài toán Đầu vào Xử lý Đầu ra C.t. con C.t. con C.t. con C.t. con C.t. con C.t. con Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Xác định các c.t. con • Cách nào để chia các vấn đề lớn thành các vấn đề nhỏ hơn, dễ quản lý hơn ? • Các chương trình con cần những đầu vào nào ? • Các xử lý nào là cần thiết cho mỗi chương trình con ? • Đầu ra nào là được chờ đợi tại mỗi chương trình con ? 23 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Mô tả thuật toán 24 Lê Viết Mẫn - lvman@hce.edu.vn Nếu a ≠ 0: x = -b/a Ngược lại, a = 0: Nếu b = 0: pt có vô số nghiệm Nếu b ≠ 0: pt vô nghiệm Thuật toán Ngôn ngữ tự nhiên 25 • Sử dụng ngôn ngữ thường ngày (tiếng mẹ đẻ) • Dễ trình bày vấn đề • Dài dòng, không trình bày rõ cấu trúc thuật toán, khó hiểu ax + b = 0 Lê Viết Mẫn - lvman@hce.edu.vn If a ≠ 0 then x = -b/a else a = 0: If b = 0 then pt có vô số nghiệm If b ≠ 0 then pt vô nghiệm Thuật toán Mã giả 26 • Dùng kết hợp ngôn ngữ tự nhiên với các cú pháp của một/nhiều ngôn ngữ lập trình nào đó • Diễn tả được cấu trúc thuật toán, dễ viết • Phụ thuộc vào ngôn ngữ lập trình ax + b = 0 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Lưu đồ • Còn được gọi là sơ đồ khối • Sử dụng các khối hình để thể hiện một bước công việc / thao tác nào đó • Thứ tự thực hiện các công việc được chỉ định bằng các cạnh có hướng nối liền các khối với nhau • Trình bày thuật toán bằng hình vẽ trực quan, dễ nhìn, dễ hiểu và dễ thấy được tổng thể của thuật toán • Độc lập ngôn ngữ 27 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ - lưu đồ p.t bậc nhất 28 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ngôn ngữ lưu đồ 29 Thực hiện công việc A Vào / ra dữ liệu Một phép kiểm tra B, tùy thuộc vào trạng thái của B là đúng hay sai mà rẻ nhánh thích hợp Bắt đầu hay kết thúc một thuật toán Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Các dạng thuật toán cơ bản 30 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Thuật toán tuần tự 31 statement 1 ; entry statement 2 statement 3 statement n exit ; ; { } Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 1 32 Tính tiền lương công nhân nếu biết lương căn bản và số ngày công Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 1 33 Đầu vào : lương căn bản, số ngày công Đầu ra : tiền lương công nhân Xử lý : tính theo công thức Lương = Lương căn bản * Ngày công Tính tiền lương công nhân nếu biết lương căn bản và số ngày công Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 1 34 Tính tiền lương công nhân nếu biết lương căn bản và số ngày công Nhập LCB, NC Begin Lương = LCB * NC End In Lương Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Thuật toán lựa chọn 35 statementexpression true fa ls e statement_1 expression true false statement_2 entry exit Dạng 1 Dạng 2 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 2 36 Bước 1 : Cho Max = a Bước 2 : So sánh b với Max. Nếu b > Max thì cho Max = b Bước 3 : So sánh c với Max. Nếu c > Max thì cho Max = c Bước 4 : Trả ra Max là giá trị lớn nhất Bước 5 : Dừng Cho ba số a, b, c. Tìm số lớn nhất trong ba số đó Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán37 Nhập a, b, c Begin b > Max Max = a Max = b c > Max Max = c End In Max true true false false Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 3 38 Nhập vào số nguyên n. Kiểm tra nếu n > 0 thì tăng n lên 1 đơn vị. Xuất kết quả ra màn hình Đầu vào : số nguyên n Đầu ra : giá trị của n Xử lý : kiểm tra n > 0, nếu đúng tăng n lên 1 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 3 39 Nhập vào số nguyên n. Kiểm tra nếu n > 0 thì tăng n lên 1 đơn vị. Xuất kết quả ra màn hình Nhập n Begin n > 0 n = n + 1 End In n true false Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 4 40 Nhập vào số nguyên n. Kiểm tra nếu n chẵn xuất ra màn hình câu “n chẵn”, ngược lại xuất “n lẻ” Đầu vào : số nguyên n Đầu ra : giá trị của n Xử lý : kiểm tra n chẵn hoặc lẻ thì xuất ra dòng tương ứng Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 4 41 Nhập vào số nguyên n. Kiểm tra nếu n chẵn xuất ra màn hình câu “n chẵn”, ngược lại xuất “n lẻ” Nhập n Begin n % 2 = 0 End In “n chẵn” true false In “n lẻ” Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Thuật toán lặp 42 statement_1 condition true false statement_2 statement_3 condition true false statement condition true false statement Dạng 1 Dạng 2 Dạng 3 Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 5 43 Nhập vào điểm thi ( ∈ [0..10]). Nếu nhập sai thì yêu cầu nhập lại Đầu vào : số nguyên n ∈ [0..10] Đầu ra : Xử lý : nếu n ∉ [0..10] thì yêu cầu nhập lại Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 5 44 Nhập vào điểm thi ( ∈ [0..10]). Nếu nhập sai thì yêu cầu nhập lại Nhập n Begin n ∉ [0..10] End true false Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán Ví dụ 6 45 Tính tổng S = 1 + 2 + ... + n (với n > 0). Nhập n vào từ bàn phím Đầu vào : số nguyên n (n > 0) Đầu ra : S Xử lý : i = i + 1 và S = S + i Lê Viết Mẫn - lvman@hce.edu.vn Thuật toán46 Nhập n Begin i > n S = 0 i = 1 End In S false S = S + i i = i + 1 true Lê Viết Mẫn - lvman@hce.edu.vn Cảm ơn sự chú ý Câu hỏi ? Thuật toán47