Kỹ thuật lập trình - Tuần 1 - Tổng quan về Kỹ thuật lập trình

18/08/2016 1 Tuần 1 - Tổng quan về KTLT Giáo viên: Hà Đại Dương duonghd@mta.edu.vn Kỹ thuật lập trình 18/08/2016 1 A bit about me • Hà Đại Dương, Phòng LV: 1901, tòa nhà S1 • Mail: duonghd@mta.edu.vn • Quan tâm về: – Thị giác máy (Computer Vision): Kết hợp với trang bị vũ khí như MBT03, Hiệu chỉnh súng; Phát hiện cháy (Vision-based Fire Detection) – Hệ thông tin quản lý (Management Information System): Hệ quản lý đào tạo; Hệ thống quản lý bảo hiểm xã hội 18/08/2016 2 18/08/2016 2 Nội dung 1. Giới thiệu chung  Mục đích, yêu cầu  Nội dung môn học  Tài liệu học tập, tham khảo  Kiểm tra đánh giá 2. Bài toán và việc giải bài toán trên máy tính  Bài toán  Phương pháp giải bài toán trên máy tính  Cấu trúc dữ liệu và giải thuật 18/08/2016 3 Nội dung  Chương trình phần mềm 3. Công cụ lập trình  Ngôn ngữ lập trình  Microsoft Visual studio 4. Ngôn ngữ lập trình C/C++  Những khái niệm cơ bản  Chương trình AB 5. Bài tập 18/08/2016 4 18/08/2016 3 Giới thiệu chung 18/08/2016 5 Mục đích • Kiến thức: – Trang bị cho sinh viên kiến thức cơ bản về phân tích bài toán, cách thức lập trình giải bài toán; – Mô tả về cấu trúc dữ liệu, các cấu trúc lệnh trong lập trình để giải bài toán. • Kỹ năng: – Sử dụng thành thạo công cụ lập trình C – Biết gỡ rối chương trình. 18/08/2016 6 18/08/2016 4 Yêu cầu • Có hiểu biết cơ bản về cấu trúc máy tính; • Có hiểu biết cơ bản về hệ điều hành; • Biết sử dụng các phần mềm hệ thống trong việc quản lý tài nguyên, sao chép/copy dữ liệu; • Biết sử dụng các phần mền ứng dụng như công cụ soạn thảo văn bản, truy cập internet, web. • Nghe giảng và làm bài tập 18/08/2016 7 Nội dung môn học 1. Tổng quan – Ngôn ngữ lập trình C: mô tả dữ liệu đơn giản 2. Cấu trúc điều kiểm: Chọn, lặp 3. Cấu trúc dữ liệu: Mảng, Xâu, Con trỏ, Tệp 4. Tổ chức chương trình: Hàm 5. Cấu trúc dữ liệu nâng cao: Danh sách, stack 6. Một số thuật toán: Sắp xếp, Tìm kiếm 18/08/2016 8 18/08/2016 5 Tài liệu học tập • Slides bài bảng • Hà Đại Dương, Nguyễn Mậu Uyên, Tập Bài giảng Lập trình cơ bản, HVKTQS 2010; • Trần Đức Huyên, Phương pháp giải các bài toán trong tin học, Nhà xuất bản giáo dục 1997; • Đào Thanh Tĩnh, Hà Đại Dương, Tin học đại cương, Học viện KTQS, 2003; 18/08/2016 9 Tài liệu học tập • Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Giáo dục, 1997; • Robert Sedgewick, Algorithns in C++, Addison- Wesley 1992; • Niklaus Wirth Bản dịch của Nguyễn Quốc Cường, Cấu trúc dữ liệu + Giải thuật = Chương trình, NXB KHKT, 2001; • 18/08/2016 10 18/08/2016 6 Kiểm tra đánh giá • Chuyên cần: 10% • Thường xuyên (Kiểm tra bài tập trong giờ BT và TH): 20% • Thi kết thúc môn (vấn đáp): 70% 18/08/2016 11 Bài toán và việc giải quyết bài toán trên máy tính 18/08/2016 12 18/08/2016 7 Bài toán (thực tế) • Đơn giản: – Giải phương trình bậc 2 (quá quen) – Tính tiền điện, tính thuế thu nhập cá nhân (???) – Đổi số tiến dạng số -> Chữ (???) – • Phức tạp: – Kiểm soát giáo thông – Chương trình quản lý sinh viên – 18/08/2016 13 Bài toán (thực tế) • Khái quát chung: • Trong đó: – Dữ liệu vào: A – Kết quả ra: B – Biến đổi: => từ đầu vào A thành kết quả ra B 18/08/2016 14 A => B 18/08/2016 8 Bài toán (thực tế) • Khái quát chung: • Ví dụ: Giải phương trình bậc 2: ax2+bx+c=0 – Dữ liệu vào: A - Các hệ số a, b, c và ??? – Kết quả ra: B - Nghiệm x1, x2 và ??? – Biến đổi: => từ đầu vào A thành kết quả ra B: Tính  = b2-4ac, tùy thuộc vào  để tính nghiệm 18/08/2016 15 A => B Bài toán (thực tế) • Khái quát chung: • Ví dụ: Kiểm soát giáo thông: Các xe vi phạm – Dữ liệu vào: A - Hình ảnh thu được từ camera – Kết quả ra: B - Xe đi đúng, xe vượt đèn đỏ – Biến đổi: => từ đầu vào A thành kết quả ra B: 18/08/2016 16 A => B 18/08/2016 9 1. Cụ thể hóa các yêu cầu của bài toán 2. Mô tả dữ liệu: Xác định dữ liệu dùng cho BT 3. Mô tả cách thức xử lý: Xác định các bước xử lý (thuật toán) 4. Soạn thảo chương trình và kiểm tra. 5. Biên dịch 18/08/2016 17 Bài toán thực tế Chương trình trên máy tính Phương pháp giải BT trên MT Cụ thể hóa bài toán • Bài toán thực tế • Bài toán (sẽ giải quyết) trên máy tính • Có thể: A’  A , A’  A, B’  B , B’  B • Khó khăn: – Thông tin về A, B thường không rõ ràng và không đầy đủ; – Thông báo về điều kiện đặt ra cho cách giải (=>) thường không được nêu ra một cách minh bạch 18/08/2016 18 A => B A’ B’ 18/08/2016 10 Mô tả A’, B’ • A’ dữ liệu vào (Input): – Đơn giản: Số nguyên, số thực, ký tự – Phức tạp: Mảng, xâu ký tự, bản ghi • B’ kết quả ra (Output): – Giá trị cụ thể – Kết luận khác 18/08/2016 19 A’, B’: Dữ liệu (Cấu trúc dữ liệu) Mô tả  • Cách thức xử lý : Thuật toán (giải thuật) • Thuật toán: Các chỉ dẫn rõ ràng để 1 máy (tính), hoặc 1 người có thể thực hiện được để từ dữ liệu vào A’ đưa ra được kết quả B’. • Tính chất: – Chính xác – Rõ ràng – Khách quan – Kết thúc 18/08/2016 20 18/08/2016 11 Ví dụ • Giải phương trình bậc 2: ax2 + bx + c = 0 – Thuật toán: • Bước 1: Tính Delta D • Bước 2: Nếu D Vô nghiệm • Bước 3: Ngược lại (D<0), – Bước 3.1: Nếu D = 0: Có nghiệm kép – Bước 3.2: Ngược lại: Có 2 nghiệm phân biệt • Tìm số lớn nhất trong ba số a, b, c: T.Toán ??? • Nấu cơm: Thuật toán ??? 18/08/2016 21 • Thuật toán được thiết kế dựa trên ba cấu trúc logic về thứ tự thực hiện câu lệnh sau đây: – Tuần tự (Sequential): Các công việc (lệnh) được thực hiện một cách tuần tự, công việc này nối tiếp công việc kia (từ trên xuống dưới). – Lựa chọn (Selection) : Lựa chọn một công việc (lệnh) để thực hiện căn cứ vào một điều kiện nào đó. – Lặp (Repeating): Thực hiện lặp lại một công việc (lệnh) không hoặc nhiều lần căn cứ vào một điều kiện nào đó. Trình tự logic của thuật toán 18/08/2016 22 18/08/2016 12 Biểu diễn thuật toán • Bằng ngôn ngữ tự nhiên. Ví dụ thuật toán giải phương trình ax+b=0. – Bước 1: Nhận giá trị của các tham số a, b – Bước 2: Xét giá trị của a xem có bằng 0 hay không? Nếu a=0 thì làm Bước 3, nếu a  0 thì làm Bước 4. – Bước 3: (a=0) Nếu b=0 thì ta kết luận phương trình vô số nghiệm, nếu b  0 thì ta kết luận phương trình vô nghiệm. – Bước 4: (a  0) Ta kết luận phương trình có nghiệm x=-b/a 18/08/2016 23 Biểu diễn bằng sơ đồ khối • Ví dụ: So sánh 2 số 18/08/2016 24 18/08/2016 13 18/08/2016 25 Sử dụng giả mã (Pseudocode) • Dùng ngôn ngữ tự nhiên kết hợp với 1 ngôn ngữ lập trình nào đó (C, Pascal ..). • Ví dụ: Giải pt bậc 2: 18/08/2016 26 Vào: a,b,c Ra: Kết luận về nghiệm BEGIN Delta: = b*b – 4*a*c; If Delta=0 Then Phương trình có nghiệm kép x=-b/(2*a); else begin if Delta<0 then Phương trình Vô nghiệm Else Begin Phương trình có 2 nghiệm x1=(-b+sqrt(Delte))/(2*a) x2=(-b+sqrt(Delte))/(2*a) end end END. 18/08/2016 14 Cấu trúc dữ liệu và Thuật toán 18/08/2016 27 Thuật toán + Cấu trúc dữ liệu = Chương trình Niklaus Emil Wirth In 1975 he wrte the book "Algorithms + Data Structures = Programs", which gained wide recognition and is still useful today. Was born in Winterthur, Switzerland, in 1934 Professor of Informatics at ETH Zürich in 1968 Chief designer of the programming languages Euler, Algol W, Pascal He received the ACM Turing Award for the development of these languages and in 1994 Chương trình (phần mềm) • Chương trình (nguồn): – Là một thể hiện Cấu trúc dữ liệu và Thuật toán nhằm thực hiện một công việc nào đó trên 1 ngôn ngữ lập trình. – Là 1 dãy các chỉ lệnh nhằm thực hiện 1 công việc. • Phần mềm: – Chương trình nguồn được biên dịch => Phần mềm. • Ví dụ: Sử dụng Visual Studio viết chương trình giải pt bậc 2, biên dịch thành file dạng EXE. 18/08/2016 28 18/08/2016 15 Công cụ lập trình 18/08/2016 29 Ngôn ngữ lập trình • Ngôn ngữ lập trình (Programming language) – Ngôn ngữ dùng để viết chương trình cho máy tính. – Được thiết kế với 1 mục đích nào đó – Có nhiều ngôn ngữ lập trình đã được phát minh ra và sử dụng: • Pascal, C • Java, PHP, • 18/08/2016 30 18/08/2016 16 Công cụ lập trình • Là môi trường tích hợp (IDE - Integrated development environment), cho phép: – Soạn thảo văn bản chương trình = ngôn ngữ LT nào đó. – Kiểm tra lỗi cú pháp, kiểm tra lỗi logic (debug) – Biên dịch chương trình nguồn (source) thành chương trình thực thi được trên máy tính (executable program) • Một số công cụ: điểm hình – Microsoft Visual Studio – Eclipse (), NetBeans – QT, 18/08/2016 31 Microsoft Visual studio • Cho phép với nhiều ngôn ngữ: – C, C++, C# – Visual Basic – ASP • Có đủ các tính năng: – Soạn thảo văn bản chương trình – Kiểm tra lỗi, debug, biên dịch • Được dùng tương đối phổ biến 18/08/2016 32 18/08/2016 17 Ngôn ngữ lập trình C/C++ 18/08/2016 33 18/08/2016 34 18/08/2016 18 The C programming language • Là một ngôn ngữ mệnh lệnh • Phát triển từ đầu thập niên 1970 bởi Dennis Ritchie để dùng trong hệ điều hành UNIX. • Từ đó, ngôn ngữ này đã lan rộng ra nhiều hệ điều hành khác và trở thành một những ngôn ngữ phổ dụng nhất. • C là ngôn ngữ rất có hiệu quả và được ưa chuộng nhất để viết các phần mềm hệ thống. • Cũng được dùng cho việc viết các ứng dụng. • C cũng thường được dùng làm phương tiện giảng dạy trong khoa học máy tính 18/08/2016 35 Ví dụ • Chương trình “Hello World” 18/08/2016 36 18/08/2016 19 Bộ ký tự (Characters) • 26 chữ cái latinh HOA A,B,C...Z • 26 chữ cái latinh thường a,b,c ...z • 10 chữ số thập phân 0,1,2...9 • Các ký hiệu toán học: +, -, *, /, =, , (, ) • Các ký hiệu đặc biệt: :. , ; " ' _ @ # $ ! ^ [ ] { } ... • Dấu cách (space bar) 18/08/2016 37 C phân biệt chữ HOA và chữ thường, Aa Từ khóa (Keyword) • Là các từ dành riêng (reserved words) của C với mục đích đã được xác định trước. • Các từ khóa cơ bản 18/08/2016 38 18/08/2016 20 Tên (Identifier) • Dùng để định danh (đặt tên) cho các thành phần của chương trình: Biến, Hàm, Hằng • Tên là một dãy các kí tự gồm các chữ cái [a-z, A- Z, 0-9] và gạch nối “_” • Lưu ý: – Tên không đuợc chứa kí tự trống, – Tên không được bắt đầu bằng một chữ số, – Tên không được trùng với từ khóa • Nên đặt các tên gợi nhớ, có ý nghĩa, không quá dài. 18/08/2016 39 Kiểu dữ liệu cơ bản (Data Types) • Fundamental Types of the C/C++ Language – Kiểu nguyên (Integral) – Kiểu thực (Floating point) Tham khảo: https://msdn.microsoft.com/en-us/library/cc953fe1.aspx • Kích thước bộ nhớ, miền giá trị của các kiểu dữ liệu. Tham khảo: https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx 18/08/2016 40 18/08/2016 21 18/08/2016 41 https://msdn.microsoft.com/en-us/library/cc953fe1.aspx 18/08/2016 42 https://msdn.microsoft.com/en-us/library/cc953fe1.aspx 18/08/2016 22 18/08/2016 43 https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx 18/08/2016 44 https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx 18/08/2016 23 Câu lệnh (Statement) • Lệnh đơn – Thực hiện 1 công việc nào đó, kết thúc bằng dấu ; • Khối lệnh – Các lệnh nằm giữa cặp dấu {} • Lệnh điều khiển – Lựa chọn: if , switch – Lặp: for, while, do .. while 18/08/2016 45 Biến (Variable) • Dùng để mô tả dữ liệu trong chương trình. • Có thể thay đổi giá trị trong khi chương trình đang chạy. • Khai báo biến: – Cú pháp (Syntax): Kiểu_dữ_liệu Tên_biến (, ); – Ví dụ: int a, b, c; char ch; 18/08/2016 46 18/08/2016 24 Hằng (Constant) • Dùng để mô tả dữ liệu trong chương trình. • Không thể thay đổi giá trị trong khi chương trình đang chạy. • Khai báo biến: – Cú pháp (Syntax): const Kiểu_dữ_liệu Tên_hằng = Giá trị; – Ví dụ: const float Pi = 3.14; 18/08/2016 47 Chú thích (Comment) • Dùng để ghi nhớ, diễn giải vấn đề gì đó trong văn bản chương trình mà không ảnh hưởng đến chương trình. • Chú thích dòng: sau dấu // – Ví dụ: const int Pi = 3.14; //Khai báo hằng • Chú thích đoạn: giữa cấp /* và */ (cho phép viết chú thích trên nhiều dòng) – Ví dụ: /* Đoạn chương trình tính nghiệm phương trình bậc 2 */ 18/08/2016 48 18/08/2016 25 Nhập dữ liệu • Nhập dữ liệu từ bàn phím. • Hàm scanf() (stdio.h) – Cú pháp: scanf(“chuỗi định dạng”, danh sách địa chỉ biến); Ví dụ: scanf(“%d %d”, &a, &b); • Hàm scanf() hoạt động thế nào??? • Có thể dùng các hàm nhập khác 18/08/2016 49 Xuất dữ liệu • Xuất dữ liệu ra màn hình. • Hàm printf() (stdio.h): – Cú pháp: printf(“chuỗi hiển thị và định dạng”, DS biểu thức); Ví dụ: printf(“Tong %d + %d = %d”, a, b, a+b); • Hàm printf() hoạt động thế nào??? • Có thể dùng các hàm xuất khác 18/08/2016 50 18/08/2016 26 Chương trình AB • Nhập vào 2 số (từ bán phím), tính tổng 2 số đó và in kết quả ra màn hình. 18/08/2016 51 18/08/2016 52 F5 18/08/2016 27 Bài tập 18/08/2016 53 Bài tập 1. Mô tả thuật toán giải phương trình bậc 2. a.x2 + b.x + c = 0 2. Mô tả thuật toán giải hệ phương trình bậc nhất 2 ẩn (x, y) a.x + b.y - c = 0 d.x + e.y - f = 0 3. Mô tả thuật toán tìm USCLN của hai số. 4. Mô tả thuật toán tìm số lớn nhất trong ba số. 5. Mô tả thuật toán tìm số lớn nhất trong 10 số. 18/08/2016 54 18/08/2016 28 Bài tập 6. Giá điện sinh hoạt tháng được tính như sau: – Từ 0-50kWh giá 92% giá trung bình (GTB) – Từ 51-100kWh giá 95% GTB – Từ 101-200kWh giá 110% GTB – Từ 201-300kWh giá 138% GTB – Từ 301-400 kWh giá 154% GTB, – Từ 401 trở lên giá 159% GTB Mô tả thuật toán tính tiền điện sinh hoạt tháng khi biết số điện tiêu thụ tháng và giá trung bình. 18/08/2016 55 Bài tập về nhà 1. Diễn giải về kiểu int trong VS C/C++ 2. Diễn giải về kiểu char trong VS C/C++ 3. Diễn giải về kiểu float trong VS C/C++ 4. Diễn giải về hàm scanf() trong VS C/C++ 5. Diễn giải về hàm printf() trong VS C/C++ 6. Diên giải về biểu thức và phép toán trong VS C/C++ 18/08/2016 56 18/08/2016 29 Bài tập về nhà 7. Hoàn thiện các bài tập trên lớp Chuẩn bị 1 bản báo cáo trên word, nộp cho giáo viên vào buổi học tiếp theo. 18/08/2016 57