Bài giảng Lập trình C - Chương 1: Tổng quan về lập trình - Trần Minh Thái

Lập trình CChương 1. Tổng quan về lập trình(3 tiết)Trần Minh TháiEmail: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn Cập nhật: 16/10/2016 1Mục tiêuHiểu được quá trình tổng quát để viết một chương trình trên máy tínhNắm được khái niệm cơ bản về tổ chức dữ liệu và giải thuậtBiết được các phương pháp để mô tả giải thuậtĐọc hiểu các giải thuật cơ bảnCó thể sử dụng công cụ hỗ trợ mô tả giải thuật bằng FlowChartChương trình máy tính?Mục đích?Cần những giai đoạn nào?Những gì cần có để hiện thực chương trình máy tính?Chương trình máy tính?CTDLGiải thuậtNgôn ngữLập trìnhPhân tích, tìm kiếm lời giảiLập trìnhThực thi chương trình và kiểm thửCá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ầuTí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ácCác đặc điểm cần có của chương trìnhTính hiệu quả (efficiency)Tính khả chuyển (porability): Khả năng chuyển đổi giữa các môi trườngTính an toàn (security)Tính dừng (halt)Các ngôn ngữ lập trìnhFortranPascalJavaCC++C#F#VB.Net.Các môi trường hỗ trợ lập trình (IDE)Borland C++Microsoft Visual BasicMicrosoft Visual C++JbuiderEclipse SDKVisual .NetXác định bài toánInput -> Process -> OutputInput: Giả thiết, thông tin được cung cấp?Process: Giải quyết vấn đề gì? Giải quyết như thế nào?Output: Đạt được những yêu cầu nào?Kết quả có đưa vào xử lý tiếp hay không???Xá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 giải) được chọnCó thể cài đặt được trên ngôn ngữ lập trình cụ thểTìm giải thuậtTậ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ánCó thể là công thức, các bước cần phải thực hiệnTính chất quan trọng 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ácTí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ư nhauTính chất quan trọng của giải thuậtTí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ự nhauTí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ánCác loại giải thuậtXử lý fileĐồ họaĐồ thịv.vTìm kiếmSắp xếpĐệ quyXử lý chuỗi ký tựCác phương pháp chính mô tả giải thuậtMã tự nhiênPseudocode (mã giả)Flowchart (lưu đồ)Khi mô tả giải thuật phải bao gồm:Input - Đầu vàoOutput - Đầu ra / kết quảProcess - Mô tả xử lý của giải thuậtĐầu vào: 2 số nguyên dương a và bĐầu ra: USCLN của a và bCách 1: Dùng mã tự nhiênBước 1: Nếu a = b thì kết luận a là USCLN và 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 1Ví dụ: Tìm ước số chung lớn nhất (USCLN) của 2 số nguyên dương a và bCách 2: Dùng mã giả (Pseudocode)WHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIFENDWHILEVí dụ: Tìm ước số chung lớn nhất (USCLN) của 2 số nguyên dương a và bLà sự lai ghép giữa ngôn ngữ lập trình và ngôn ngữ tự nhiênCách 3: Dùng lưu đồ (flowchart)Ví dụ: Tìm ước số chung lớn nhất (USCLN) của 2 số nguyên dương a và bMô 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 chi tiết: như dùng ngôn ngữ tựa Pascal, C++, IF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL DISPLAY RETURN Mô 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úcĐiều kiệnĐiểm nốiRẽ nhánhLuồng xử lýKhối xử lýNhập/ XuấtGiá trị trả vềBài tập mô tả giải thuật 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ào độ dài của a, b và c. Kiểm tra xem a, b, c có tạo thành 3 cạnh của tam giác không?Nhậ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>0Đầu vào: Số nguyênn nĐầu ra: |n|Cho số nguyên n. Tính trị tuyệt đối của n Đầu vào: Hai số nguyên a và bĐầu ra: Nghiệm của ptGiải và biện luận phương trình bậc I: ax+b=0Phần đọc thêm: Hướng dẫn 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ảMục tiêuCác công cụ vẽ lưu đồGiới thiệu Crocodile ClipsCác ký hiệu lưu đồCác kiểu dữ liệuCác biểu thứcCác hàm thư việnMinh họa thao tác vẽCác ví dụSử dụng Crocodile Clips ICTEDGE Diagrammer – Pacestar Software Visio Crocodile Clips ICT Các công cụ vẽ lưu đồĐược phát triển bởi Crocodile Clips LtdBao gồm nhiều phần mềm hỗ trợ mô phỏng phục vụ cho giáo dục:Vật lýHóa họcToán họcĐiện – điện tửTin họcGiới thiệu crocodile clipsGiao diện chínhHỗ trợ vẽ lưu đồ giải thuậtMinh họa từng bước thực hiện của lưu đồHỗ trợ nhiều loại kiểu dữ liệuCung cấp sẵn nhiều hàm thư việnCho phép mô tả thêm các hàm khácHướng dẫn, mô tả chi tiết từng thành phầnNhiều ví dụ minh họa Đặc điểmCác ký hiệu lưu đồCác ký hiệu bắt đầu, kết thúc giải thuật hoặc hàmCác ký hiệu phép gán, gọi thực hiện hàmKý hiệu kiểm tra điều kiện rẽ nhánhKý hiệu nhập, xuấtCửa sổ quan sát kết quả từng bước và biến toàn cụcCông cụ nhập dữ liệu và hiển thị kết quảKý hiệuDiễn giảiBắt đầu giải thuậtKết thúc giải thuậtBắt đầu hàm conTrả về giá trị của hàm con, hoặc kết thúc hàm conCác ký hiệu lưu đồKý hiệuDiễn giảiGán giá trị vào biếnTăng hoặc giảm giá trị của biếnGọi thực hiện hàm conKiểm tra điều kiệnCác ký hiệu lưu đồKý hiệuDiễn giảiNhận giá trị nhập, kết hợp với Edit box để lấy giá trịXuất giá trị, kết hợp với Text box để hiển thị kết quả Cửa sổ quan sát kết quả thực hiện từng bước của giải thuậtCửa sổ quan sát biến toàn cụcCác ký hiệu lưu đồNumber String Boolean Map List Các kiểu dữ liệuNumber operations String operations Logical operations Comparison operations Các biểu thứcSttKý hiệuMô tả1+Cộng2-Trừ3*Nhân4/Chia5()Gom nhóm các thành phầnNumber operationsSttKý hiệuMô tả1+Nối 2 chuỗi hoặc nối chuỗi và sốVí dụ 1: “abc”+”xyz”  “abcxyz”Ví dụ 2: “Tổng =“+ 8  “Tổng =8”String operations SttKý hiệuMô tả1Not hoặc !2And hoặc &&3Or hoặc ||4Xor hoặc ^^Logical operations SttKý hiệuMô tả1=Bằng2>Lớn hơn3=Lớn hơn hoặc bằng5Khác (không bằng)Comparison operations Cung cấp các hàm định nghĩa sẵn, bao gồm: Các hàm lượng giác: sin, cos, tan, Các hàm toán học khác: tính căn, logarit, làm tròn số, tính mũ, Các hàm thư viện Hàm thư việnHàm thư việnChọn ký hiệu tương ứngNhấn chuột trái và kéo rê vào cửa sổ vẽ giải thuậtĐưa ký hiệu vào đúng điểm nối cần nối với ký hiệu có trong cửa sổDi chuyển ký hiệu đến vị trí thích hợpMinh họa thao tác vẽĐiểm nốiChọn đường nối cần xóaNhấn phím DeleteMinh họa thao tác vẽ - tách hai ký hiệu đang nối với nhauTáchKéo rê ký hiệu (cần nối) vào sơ đồ, sao cho hai điểm nối 1 và 2 khớp nhau, nhả chuột ra và chỉnh lại vị trí ký hiệuMinh họa thao tác vẽ nối nhiều ký hiệu vào một ký hiệu21Nhấn chuột vào tên biến hoặc giá trị để thay đổiNhấn chuột phải vào ký hiệu chọn Properties để thay đổi thuộc tính cho ký hiệuKhung thuộc tính sẽ xuất hiện bên tráiMinh họa thao tác vẽLấy giá trị và hiển thị kết quả trong giải thuậtDùng ký hiệu nhập (get) kết hợp với editbox để nhận giá trị nhập bên ngoàiDùng ký hiệu xuất (set) kết hợp với editbox hoặc textbox để hiển thị kết quả của giải thuậtMinh họa thao tác vẽXem kết quả cuối cùng – Quick StepXem tự động kết quả thực hiện từng bước – Auto Step (Có thể chính tốc độ)Xem lần lượt kết quả thực hiện từng bước khi nhấn phím – Manual StepKiểm tra giải thuậtChỉnh tốc độChế độ xem toàn màn hìnhChọn chế độ xem kết quảChọn tốc độ thực hiệnKéo của sổ Monitor box vào cửa sổ vẽ giải thuật để quan sát giá trị từng bướcNhấn vào nút play ở ký hiệu bắt đầu giải thuật để bắt đầu minh họaKiểm tra giải thuậtNhấn vào để chạy bước tiếp theo (nếu chọn chế độ xem kết quả là Manual step)Vẽ lưu đồ giải thuật không dùng hàm conTìm số lớn nhất của hai số nguyênTính phần nguyên và phần dư của phép chiaVẽ lưu đồ giải thuật có dùng hàm conTìm kiếm phần tử có giá trị x xuất hiện trong mảng một chiều số nguyênCác ví dụTìm số lớn nhất của hai số nguyênTính phần nguyên và phần dư của phép chiaHàm tìm x trong mảng 1 chiều a Tìm kiếm phần tử có giá trị x xuất hiện trong mảng một chiềuQ&A