Bài giảng Kỹ thuật lập trình: Tổng quan về KTLT

18/08/2016

Kỹ thuật lập trình

Tuần 1 - Tổng quan về KTLT

Giáo viên: Hà Đại Dương duonghd@mta.edu.vn

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

Nội dung

1. Giới thiệu chung

Tài liệu học tập, tham khảo

 Mục đích, yêu cầu  Nội dung môn học   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

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

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

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

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

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:

A => B

• 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

18/08/2016

Bài toán (thực tế)

• Khái quát chung:

A => B

• 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

Bài toán (thực tế)

• Khái quát chung:

A => B

• 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

18/08/2016

Phương pháp giải BT trên MT Bài toán thực tế

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

Chương trình trên máy tính

18/08/2016 17

Cụ thể hóa bài toán

A => B

• Bài toán thực tế • Bài toán (sẽ giải quyết) trên máy tính

A’  B’

• 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

18/08/2016

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 …

A’, B’: Dữ liệu (Cấu trúc dữ liệu)

18/08/2016 19

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

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<0 -> 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

Trình tự logic của thuật toán

• 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 đó.

18/08/2016 22

18/08/2016

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

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ụ:

Vào: a,b,c Ra: Kết luận về nghiệm BEGIN

Giải pt bậc 2:

Delta: = bb – 4a*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))/(2a) x2=(-b+sqrt(Delte))/(2a)

end

18/08/2016 26

END.

18/08/2016

Cấu trúc dữ liệu và Thuật toán

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

Niklaus Emil Wirth In 1975 he wrte the book "Algorithms + Data Structures = Programs", which gained wide recognition and is still useful today. Thuật toán + Cấu trúc dữ liệu = Chương trình

18/08/2016 27

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

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

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

Ngôn ngữ lập trình C/C++

18/08/2016 33

18/08/2016 34

18/08/2016

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

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)

C phân biệt chữ HOA và chữ thường, Aa

18/08/2016 37

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

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

https://msdn.microsoft.com/en-us/library/cc953fe1.aspx

18/08/2016 41

18/08/2016 42

18/08/2016

https://msdn.microsoft.com/en-us/library/s3f49ktz.aspx

18/08/2016 43

18/08/2016 44

18/08/2016

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

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

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

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

F5

18/08/2016 52

18/08/2016

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

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