Nmlt_chuong1_tong Quan Ve Lap Trinh.pdf

1/16/2018

NHẬP MÔN LẬP TRÌNH http://fit.hufi.edu.vn http://ittc.edu.vn

Chương 1. Tổng quan về lập trình

2

1

1/16/2018

Chương 1. Tổng quan về lập trình (2)

3

1.1.1. Chương trình Một chương trình (program) là một dãy các chỉ thị (instruction) điều khiển sự hoạt động của máy tính nhằm giải quyết một công việc nào đó. Người viết chương trình (còn gọi là lập trình viên) là những người tạo lập ra các chương trình điều khiển máy tính.

4

2

1/16/2018

1.1.2. Chương trình mã máy CPU của máy tính được thiết kế để có thể thực hiện được các chương trình mã máy (machine code program) đã được hệ điều hành (HĐH) nạp vào RAM của máy tính. Chương trình mã máy thường phải tương thích với từng họ máy cụ thể, bao gồm tập hợp các chỉ thị được viết bằng các lệnh CPU của họ máy đó, được lưu trên đĩa dưới dạng một tập tin mã thực thi (executable program file) của HĐH cụ thể.

5

1.1.2. Chương trình mã máy (2) Nhận xét  Khó có thể sản xuất ra phần mềm bằng cách viết trực tiếp các chương trình mã máy.  Nếu có làm được theo cách này thì: • Giá cả sẽ rất đắt do quá khó, tốn quá nhiều thời gian và công sức. • Khả năng dùng lại rất giới hạn do không thể bán cho người dùng trên họ máy tính khác hay người dùng sử dụng hệ điều hành khác. 6

3

1/16/2018

1.1.3. Hợp ngữ và trình hợp dịch Một trong những giải pháp khởi đầu để cải tiến năng suất lập trình đó là sử dụng hợp ngữ (assembly language) thay cho mã máy. Hợp ngữ là loại ngôn ngữ lập trình trừu tượng hơn so với ngôn ngữ máy. Do đó, chương trình viết bằng hợp ngữ dễ viết, dễ đọc và dễ chỉnh sửa hơn chương trình viết bằng ngôn ngữ máy.

7

1.1.3. Hợp ngữ và trình hợp dịch (2) Tuy nhiên, CPU máy tính không thể hiểu chương trình được viết bằng hợp ngữ, do đó trước khi chương trình hợp ngữ được thực thi cần phải nhờ một chương trình đặc biệt được gọi là trình hợp dịch (assembler) dịch chương trình hợp ngữ thành chương trình mã máy. Hợp ngữ cũng là một dạng ngôn ngữ lập trình (NNLT) và được gọi là NNLT cấp thấp.

8

4

1/16/2018

1.1.3. Hợp ngữ và trình hợp dịch (3) Đặc điểm của NNLT cấp thấp

 Phụ thuộc vào từng họ máy cụ thể, vì vậy không có tính tương thích.  Dễ viết, dễ đọc, chỉnh sửa hơn chương trình mã máy.  Tận dụng và khai thác được tính năng của mỗi họ máy cụ thể.

9

1.1.3. Hợp ngữ và trình hợp dịch (4)

10

5

1/16/2018

1.1.4. Ngôn ngữ lập trình Là ngôn ngữ được lập trình viên sử dụng để viết chương trình cho máy tính. Khi một chương trình được viết bằng một NNLT nào đó thì các chỉ thị, câu lệnh trong chương trình phải tuân theo các quy tắc, các luật do NNLT đó quy định. Người lập trình thường viết chương trình bằng các NNLT cấp cao vì tính dễ dùng, có thể diễn đạt được các ý tưởng trừu tượng và có tính tương thích cao. 11

1.1.4. Ngôn ngữ lập trình (2) Có nhiều NNLT cấp cao, chẳng hạn như: Ada, BASIC, C/C++, Pascal, Java, C#, Perl, Ruby, Python… Mỗi ngôn ngữ được thiết kế phù hợp với một số mục đích cụ thể.

12

6

1/16/2018

1.1.5. Chương trình dịch Là chương trình đặc biệt có chức năng chuyển đổi chương trình được viết bằng ngôn ngữ lập trình bậc cao thành chương trình thực hiện được trên máy tính. Chương trình dịch nhận đầu vào là chương trình viết bằng NNLT bậc cao (chương trình nguồn), thực hiện chuyển đổi sang ngôn ngữ máy (chương trình đích). Có 2 loại chương trình dịch là trình biên dịch (compiler) và trình thông dịch (interpreter) 13

1.1.5. Chương trình dịch (2) Các chương trình biên dịch  Toàn bộ mã nguồn được kiểm tra cú pháp theo quy định của ngôn ngữ.  Biên dịch thành mã thực thi (gồm mã máy và thông tin quản lý của hệ điều hành).  Ghi lên đĩa với dạng tập tin thực thi. Các chương trình thông dịch  Ở mỗi lệnh, kiểm tra cú pháp xem đúng không.  Nếu đúng thì lệnh sẽ được dịch thành mã máy và nạp vào RAM để thực thi ngay. 14

7

1/16/2018

Một số chương trình minh họa Chương trình xuất ra màn hình “Hello World”

Hợp ngữ

15

Một số chương trình minh họa (2) Chương trình xuất ra màn hình “Hello World”

Chương trình C

Chương trình C++

16

8

1/16/2018

Một số chương trình minh họa (2) Chương trình xuất ra màn hình “Hello World”

Chương trình Java

17

1.2. Tổng quan về NNLT C/C++ Giới thiệu Đặc điểm Môi trường lập trình C/C++ Quy trình viết, biên dịch và chạy một chương trình C/C++

18

9

1/16/2018

1.2.1. Giới thiệu NNLT C/C++ Ngôn ngữ C được phát triển bởi Dennis Ritchie và Ken Thompson vào đầu những năm 70 tại phòng thí nghiệm Bell. Năm 1983, viện chuẩn hóa quốc gia Mỹ (ANSI – American National Standards Organistion) tiến hành chuẩn hóa. Đến năm 1989, tổ chức chuẩn hóa quốc tế (ISO – International Standards Organisation) tiếp tục chuẩn hóa, đến năm 1990 thì việc chuẩn hóa được hoàn thành và được gọi là “C chuẩn”. 19

1.2.1. Giới thiệu NNLT C/C++ (2) Từ “C chuẩn”, các hãng phần mềm phát triển thành các phiên bản C riêng như: Microsoft C, Turbo C, Borland C… Ngôn ngữ C được sử dụng rộng rãi bởi các lập trình viên chuyên nghiệp để lập trình hệ thống, viết các hệ điều hành, các tính toán số trong các lĩnh vực khoa học… Ngôn ngữ C++ là ngôn ngữ lập trình hướng đối tượng được cải tiến từ ngôn ngữ C. Đây là một ngôn ngữ rất mạnh và đa dụng. 20

10

1/16/2018

1.2.2. Đặc điểm của NNLT C/C++ Tốc độ thực thi nhanh. Có tính khả chuyển: mã lệnh viết bằng C/C++ trên máy này có thể được biên dịch và chạy trên máy khác mà không cần thay đổi gì hoặc thay đổi rất ít. Là ngôn ngữ lập trình cấu trúc, cho phép tổ chức chương trình thành các đơn thể, dễ dàng tái sử dụng mã nguồn. Được sử dụng rộng rãi bởi các lập trình viên chuyên nghiệp, số lượng các phần mềm viết bằng C/C++ chiếm tỷ lệ rất lớn. 21

1.2.3. Quy trình viết, biên dịch và thực thi chương trình (CT) C/C++ Soạn và ghi CT vào đĩa thành một hay nhiều tập tin CT nguồn. Sử dụng trình biên dịch để dịch CT nguồn thành mã đối tượng (Object code), một loại mã trung gian chưa phải là mã máy nên chưa thể nạp vào bộ nhớ để thực thi. Các tập tin mã trung gian sinh ra ở bước trên được kết nối lại (dùng CT liên kết mã – link) thành một chương trình mã máy. Thực thi chương trình ngôn ngữ máy. 22

11

1/16/2018

1.2.3. Quy trình viết, biên dịch và thực thi chương trình (CT) C/C++ (2)

23

1.2.4. Môi trường lập trình C/C++ Toàn bộ quy trình viết, biên dịch và thực thi chương trình có thể thực hiện một cách dễ dàng và thuận tiện nhờ vào các công cụ do các hãng phần mềm cung cấp. Các công cụ này được gọi là môi trường phát triển tích hợp (IDE: Integrated Development Environment). Các IDE tích hợp nhiều chức năng như:  Soạn thảo chương trình nguồn;  Quản lý hệ thống tập tin mã nguồn; 24

12

1/16/2018

1.2.4. Môi trường lập trình C/C++ (2) Các IDE tích hợp nhiều chức năng như:  Soạn thảo chương trình nguồn;  Quản lý hệ thống tập tin mã nguồn;  Kiểm tra lỗi cú pháp;  Biên dịch, liên kết chương trình;  Chạy thử chương trình theo từng dòng lệnh để tìm lỗi … 25

1.2.4. Môi trường lập trình C/C++ (3) Một số IDE thông dụng hiện nay  Microsoft Visual Studio 2012: hỗ trợ nhiều ngôn ngữ (có C/C++).  Dev-C++: C/C++  Eclipse: hỗ trợ nhiều ngôn ngữ (có C/C++).  JBuilder: Java …

26

13

1/16/2018

1.3. Giới thiệu về thuật toán Khái niệm bài toán và thuật toán Các tính chất của thuật toán Mô tả thuật toán

27

1.3.1. Khái niệm bài toán và thuật toán Bài toán  Trong tin học, bài toán là một công việc nào đó mà ta muốn máy tính thực hiện.  Ví dụ: Giải phương trình bậc 2, xếp loại học tập của một lớp học…  Các bài toán được cấu tạo bởi 2 thành phần: • Input: các thông tin đã có • Output: các thông tin cần tìm từ input 28

14

1/16/2018

1.3.1. Khái niệm bài toán và thuật toán (2) Bài toán  Ví dụ: bài toán tìm ước số chung lớn nhất của 2 số nguyên dương • Input: 2 số nguyên dương M và N • Output: Ước số chung lớn nhất của M và N

29

1.3.1. Khái niệm bài toán và thuật toán (3) Thuật toán Làm như thế nào?

Output

Input

Thuật toán

30

15

1/16/2018

1.3.1. Khái niệm bài toán và thuật toán (4) Thuật toán  Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho thực hiện dãy thao tác đó, từ input của bài toán ta nhận được output cần tìm.

31

1.3.2. Các tính chất của thuật toán Một thuật toán được đề xuất để giải quyết một bài toán nào đó cần thỏa mãn các tính chất cơ bản sau: Tính hữu hạn: Thuật toán phải dừng sau một số lần hữu hạn thực hiện các thao tác. Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán dừng hoặc là có đúng một thao tác xác định để thực hiện tiếp theo. Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được output cần tìm. … 32

16

1/16/2018

1.3.3. Mô tả thuật toán Thuật toán thường được mô tả bằng 3 cách:  Mô tả bằng ngôn ngữ tự nhiên  Mô tả bằng lưu đồ  Mô tả bằng mã giả

33

1.3.3.1. Mô tả thuật toán bằng NNTN  Ví dụ: mô tả thuật toán tìm số lớn nhất trong một dãy số nguyên dương bằng ngôn ngữ tự nhiên.  Bước 1: Đặt số lớn nhất hiện tại bằng với số đầu tiên của dãy.  Bước 2: Nếu không còn số nguyên nào kế tiếp trong dãy thì chuyển sang Bước 4.  Bước 3: Nếu số nguyên kế tiếp lớn hơn số lớn nhất hiện tại thì đặt số lớn nhất hiện tại bằng số nguyên kế tiếp này. Quay về Bước 2.  Bước 4: Số lớn nhất hiện tại chính là số lớn nhất của cả dãy và là kết quả của thuật toán. 34

17

1/16/2018

1.3.3.2. Mô tả thuật toán bằng lưu đồ Một số ký hiệu trong lưu đồ Thể hiện thao tác so sánh Thể hiện các phép tính toán

Thể hiện thao tác nhập, xuất dữ liệu Quy định trình tự thực hiện các thao tác 35

1.3.3. Mô tả thuật toán bằng lưu đồ (2) Ví dụ 1: Thuật toán giải phương trình ax + b = 0

Nhập a, b S

a=0

x  -b/a Đ

b=0

S

Pt có nghiệm x

Đ Pt có vô số nghiệm

Pt có vô nghiệm 36

18

1/16/2018

1.3.3. Mô tả thuật toán bằng lưu đồ (3) Ví dụ 2: Cho dãy A gồm N số nguyên khác nhau: a1, a2, …,aN và một số nguyên k. Cho biết có hay không chỉ số i (1≤ i ≤ N) mà ai=k. Nếu có hãy cho biết chỉ số đó. Xác định bài toán:  Input: N, dãy gồm N số nguyên a1, a2, …,aN và số nguyên k.  Output: chỉ số i mà ai = k hoặc thông báo không có số nguyên nào của dãy A có giá trị bằng k. 37

1.3.3.2. Mô tả thuật toán bằng lưu đồ (4)

38

19

1/16/2018

1.3.3.3. Mô tả thuật toán bằng mã giả Dựa vào cú pháp của một hoặc một nhóm ngôn ngữ lập trình thông dụng nào đó để hình thành nên cú pháp của mã giả (pseudo-code), tương đối chính xác và cụ thể. Ngoài ra, mã giả còn sử dụng hệ thống ký hiệu toán học nên giải thuật được mô tả bằng công cụ này vừa gần gũi với con người vừa không quá xa lạ với ngôn ngữ lập trình.  Thuận tiện cho quá trình hiện thực giải thuật bằng ngôn ngữ lập trình cụ thể. 39

1.3.3.3. Mô tả thuật toán bằng mã giả (2)  Ví dụ 1: Thuật toán giải phương trình ax + b = 0 if a = 0 then if b = 0 then write(“Phương trình có vô số nghiệm”) else write(“Phương trình vô nghiệm”) endif else x  -b/a write(x) endif

40

20

1/16/2018

1.3.3.3. Mô tả thuật toán bằng mã giả (3) Ví dụ 2: Bài toán tìm kiếm i1 while i <=N do if ai = k then write(i) break else ii+1 endif endwhile write(“Không có giá trị k trong dãy”) 41

Câu hỏi và bài tập chương 1 1) Giải thích các khái niệm cơ bản về lập trình như: chương trình, chương trình mã máy, ngôn ngữ lập trình, trình biên dịch. 2) Nhận xét ưu khuyết điểm chương trình viết bằng các ngôn ngữ: ngôn ngữ máy, hợp ngữ, NNLT bậc cao. 3) Nêu tên và đặc điểm của ít nhất 5 NNLT bậc cao và anh/chị biết. 4) Thuật toán là gì? Phân tích các đặc điểm của thuật toán. 42

21

1/16/2018

Câu hỏi và bài tập chương 1 (2) Mô tả các thuật toán giải quyết các bài toán sau bằng lưu đồ: 5) Nhập vào số nguyên n và xuất ra màn hình giá trị bình phương của n. 6) Nhập vào số nguyên n, xuất giá trị n ra màn hình theo quy tăc: nếu n lớn hơn 0 thì giảm đi 1, ngược lại thì tăng lên 1. 7) Giải và biện luận phương trình bậc 2: ax2 + bx + c = 0 43

Câu hỏi và bài tập chương 1 (3) Mô tả các thuật toán giải quyết các bài toán sau bằng lưu đồ: 8) Nhập vào số nguyên n, xuất ra màn hình các số từ 1 đến n. 9) Tính tổng: S(n) = 1+2+3+…+n, với n>0. 10)Tính tổng: S(n) = 1+3+5+…+(2n+1), với n>0. 11)Tính tích: S(n) = 1.2.3.….n, với n>0. 12)Tính tích: S(n) = 1.3.5.….(2n+1), với n>0. 13)Tính tổng: S(n) = 12+22+32+…+n2, với n>0. 44

22

1/16/2018

Câu hỏi và bài tập chương 1 (4) Mô tả các thuật toán giải quyết các bài toán sau bằng lưu đồ: 14)Tính S(n)=1+1.2+1.2.3+…+1.2.3…n, với n>0 15)Đếm số lượng các ước số chẵn của số nguyên dương n. 16)Tính S(n) = 1+22+33+…+nn, với n>0. 1 2

2 3

17) Tính S(n) = + + ⋯ +

𝑛 𝑛+1

, với n>0.

45

Tài liệu tham khảo 1) Trần Đan Thư, Nguyễn Thanh Phương, Đinh Bá Tiến, Trần Minh Triết, Nhập môn lập trình, NXB Khoa học và Kỹ thuật, 2011. 2) Aptech WorldWide, Elementary Programming with C. 3) Ivor Horton, Beginning C (Fifth Edition), Apres . 4) Brian W. Kernighan, Dennis M. Ritchie, The C Programming Language, Prentice Hall, 1998. 46

23

1/16/2018

24