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

Chương trình máy tính Cấu trúc dữ liệu Lưu đồ giải thuật Bài tập 1. Chương trình máy tính Lập trình là gì? Máy tính dùng để giải quyết một loạt các bài toán Mỗi bài toán có cách giải quyết khác nhau dựa vào thuật giải Lập trình viên thể hiện các thuật giải theo một ngôn ngữ lập trình cụ thể

pptx58 trang | Chia sẻ: candy98 | Ngày: 01/12/2020 | Lượt xem: 13 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Bài giảng Nhập môn lập trình - Chương 1: Tổng quan về lập trình - Trần Minh Thái, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CHƯƠNG 1 TỔNG QUAN VỀ LẬP TRÌNHTRẦN MINH THÁIEmail: minhthai@huflit.edu.vnWebsite: www.minhthai.edu.vn 1Chương trình máy tính?2Giải thuậtNgôn ngữLập trìnhLập trình là gì?Máy tính dùng để giải quyết một loạt các bài toánMỗi bài toán có cách giải quyết khác nhau dựa vào thuật giảiLập trình viên thể hiện các thuật giải theo một ngôn ngữ lập trình cụ thể3Lập trình là gì?Máy tính chỉ hiểu được ngôn ngữ máy, do đó cần phải có giai đoạn chuyển ngôn ngữ lập trình sang ngôn ngữ máy thông qua trình biên dịch của ngôn ngữ lập trình4Cá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ác5Tí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)6Các đặc điểm cần có của chương trìnhCác ngôn ngữ lập trình thông dụngFortranPascalJavaC7C++C#F#VB.Net.Các môi trường hỗ trợ lập trìnhBorland C++Microsoft Visual BasicMicrosoft Visual C++JbuiderEclipse SDKVisual studio .Net8Xác định bài toánGiả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?9inputProcessoutputXá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ể10Tì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ướcKhi 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án11Tí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á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ư nhau12Tính chất 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án13Các loại giải thuậtXử lý fileĐồ họaĐồ thịv.v14Tì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 gồm:Input - Đầu vàoOutput - Đầu ra / kết quảAlgorithm - Mô tả giải thuật15VD: 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 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 116Cách 2: Dùng mã giả (Pseudocode)WHILE a ≠ b DO IF a>b THEN a=a-b ELSE b=b-a ENDIFENDWHILE17Cách 3: Dùng lưu đồ (flowchart)18Mô tả giải thuật bằng pseudocodeDễ hiểu, không chi tiết về kỹ thuật lập trìnhỞ cấp độ tổng quát: gần ngôn ngữ tự nhiênGần tương tự ngôn ngữ lập trìnhIF THEN ENDIFIF THEN ... ELSE ... ENDIFWHILE DO ENDWHILEDO UNTIL DISPLAY RETURN 19Mô 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ải20Các ký hiệu flowchart21Điều kiệnBắt đầu/ kết thúcRẽ nhánhLuồng xử lýKhối xử lýNhập/ XuấtGiá trị trả vềĐiểm nốiBà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?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>0221. 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:23242. Giải & biện luận phương trình: ax+b=0Đầu vào: số nguyên a, bĐầu ra: Nghiệm của ptGiải thuật:EDGE Diagrammer – Pacestar Software Visio Crocodile Clips ICT Các công cụ hỗ trợ vẽ lưu đồ2627Giớ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ụEDGE Diagrammer – Pacestar Software Visio Crocodile Clips ICT Các công cụ vẽ lưu đồĐược phát triển bởi Crocodile Clips Ltd Bao 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ệuÝ nghĩaBắ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ệuÝ nghĩaGá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ệuÝ nghĩa1+Cộng2-Trừ3*Nhân4/Chia5()Gom nhóm các thành phầnNumber operations SttKý hiệuÝ nghĩa1+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ệuÝ nghĩa1Not hoặc !2And hoặc &&3Or hoặc ||4Xor hoặc ^^Logical operations Comparison operations SttKý hiệuÝ nghĩa1=Bằng2>Lớn hơn3=Lớn hơn hoặc bằng5Khác (không bằng)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 nhau Tá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ụ54Tìm số lớn nhất của hai số nguyên55Tính phần nguyên và phần dư của phép chia56Hàm tìm x 57Tìm kiếm phần tử có giá trị x xuất hiện trong mảng một chiềuQ&A58