Bài giảng Nhập môn lập trình - Chương 1: Tổng quan về giải thuật

(6 tiết)1CHƯƠNG 1TỔNG QUAN VỀ GIẢI THUẬT2LẬP TRÌNH ?Giải thuậtNgôn ngữLập trìnhCÁC ĐẶC ĐIỂM CẦN CÓ CỦA CHƯƠNG TRÌNHĐúng đắn, chính xác (correctness).Chắc chắn (robustness).Thân thiện (user friendliness).Khả năng thích nghi (adapability): Chương trình có khả năng để phát triển tiến hóa theo yêu cầu.Tính tái sử dụng (reuseability): Chương trình có thể dùng để làm một phần trong một chương trình lớn khác.3CÁC ĐẶC ĐIỂM CẦN CÓ CỦA CHƯƠNG TRÌNH (tt)Tính hiệu quả (efficiency).Tính khả chuyển (porability): Khả năng chuyển đổi giữa các môi trường.Tính an toàn (security).Tính dừng (halt).4CÁC NGÔN NGỮ LẬP TRÌNHFortranPascalJavaC5C++C#F#VB.Net.CÁC MÔI TRƯỜNG HỖ TRỢ LẬP TRÌNHBorland C++Microsoft Visual BasicMicrosoft Visual C++JbuiderEclipse SDKVisual .Net67XÁC ĐỊNH BÀI TOÁNInput -> Process -> OutputGiải quyết vấn đề gì?Giả thiết, thông tin được cung cấpĐạt được những yêu cầu nào?8XÁC ĐỊNH CẤU TRÚC DỮ LIỆUPhải biểu diễn đầy đủ được thông tin nhập và xuất của bài toánPhù hợp với giải thuật được chọnCài đặt được trên ngôn ngữ lập trình cụ thể9TÌM GIẢI THUẬTGiải thuật là một tập hợp hữu hạn của các chỉ thị hay phương cách được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán.10TÍNH CHẤT CỦA GIẢI THUẬTTính chính xác: để đảm bảo kết quả tính toán hay các thao 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â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ườ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ài toán nhất định mà có thể áp dụng cho một lớp các bài toán có đầu vào tương tự 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ước tính toán. CÁC LOẠI GIẢI THUẬTXữ lý file.Đồ họa.Đồ thị.V. v11Tìm kiếmSắp xếp.Đệ quy.Xữ lý chuỗi ký tự.CÁC PHƯƠNG PHÁP CHÍNH BIỂU DIỄN GIẢI THUẬTMã tự nhiênPseudocode (mã giả)Flowchart (lưu đồ)Khi thiết kế giải thuật phải mô tả rõ:Input - Đầu vàoOutput - Đầu ra (kết quả)Process - Mô tả giải thuật1213Ví dụ: Tìm ước số chung lớn nhất của 2 số nguyên dương a và bĐầu vào: 2 số nguyên dương a và bĐầu ra: ước số chung lớn nhất của a và bGiải thuật:Cách 1: Dùng mã tự nhiênBước 1: Nếu a = b thì kết luận a là ước số chung lớn nhất, kết thúcBước 2: Nếu a > b thì a = a – b; Ngược lại thì b = b – a;Bước 3: Quay trở lại Bước 114Cách 2: Dùng mã giả (Pseudocode)WHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIFENDWHILE15Cách 3: Dùng lưu đồ (flowchart)16MÔ TẢ GIẢI THUẬT BẰNG PSEUDOCODEDễ hiểu, không chi tiết đến các kỹ thuật lập trìnhỞ cấp độ hết sức tổng quát: gần ngôn ngữ tự nhiênHoặc rất chi tiết: như dùng ngôn ngữ tựa Pascal, C++, Các từ khóaIF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL WRITE RETURN 17MÔ TẢ GIẢI THUẬT BẰNG LƯU ĐỒ (FLOWCHART)Lưu đồ thuật toán là công cụ dùng để biểu diễn thuật toán, việc mô tả nhập (input), dữ liệu xuất (output) và luồng xữ lý thông qua các ký hiệu hình họcPhương pháp duyệt lưu đồDuyệt từ trên xuốngDuyệt từ trái sang phảiCÁC KÝ HIỆU FLOWCHARTBắt đầu/ kết thúcRẽ nhánhLuồng xử lýKhối xử lýNhập/ XuấtĐiều kiệnGiá trị trả vềĐiểm nối1819CÁC VÍ DỤ Cho số nguyên n. Tính trị tuyệt đối của n Giải và biện luận phương trình bậc I: ax+b=0Nhập và số nguyên k (k>0), Xuất ra màn hình k dòng chữ “Xin chào”Tính tổng: ,với n>0Tính tổng: ,với n>0Nhập vào ba cạnh a, b, c của tam giác. Xuất ra màn hình tam giác đó thuộc loại tam giác gì? (Thường, cân, vuông, đều hay vuông cân).20HƯỚNG DẪN VÍ DỤ 1 Cho số nguyên n. Tính trị tuyệt đối của n Đầu vào: Số nguyên nĐầu ra: |n|Giải thuật (Pseudocode): IF n<0 THEN n=n*(-1) ENDIF WRITE nGiải thuật (Flowchart):2122HƯỚNG DẪN VÍ DỤ 2 Giải và biện luận phương trình bậc I: ax+b=0Đầu vào: Hai số nguyên a và bĐầu ra: Nghiệm của ptGiải thuật (Pseudocode): IF a=0 THEN IF b=0 THEN WRITE “PT VSN” ELSE WRITE “PT VN” ENDIF ELSE x = -b:a WRITE “Nghiệm :”+x ENDIF2324HƯỚNG DẪN SỬ DỤNG CÔNG CỤ VẼ LƯU ĐỒ GIẢI THUẬT Microsoft VisioCrocodile Clips 6.05Cách sử dụng các ký hiệuChạy từng bước và kiểm tra kết quả2526