Lập trình căn bản - Tổng quan

 8: In S và kết thúc chương trình. 
Chí tiết giải thuật bằng lưu đồ: 
 Nhập số các số hạng n 
 i<=n Sai 
 Đúng 
 Nhập số ai In S 
 S=0 
 i=1
End S=S+ai
 i=i+1 
Begin 
Ví dụ 2: Viết chương trình cho phép nhập vào 2 giá trị a, b mang ý nghĩa là các 
hệ số a, b của phương trình bậc nhất. Dựa vào các giá trị a, b đó cho biết nghiệm của 
phương trình bậc nhất ax + b = 0. 
Mô tả giải thuật bằng ngôn ngữ tự nhiên: 
- Bước 1: Nhập 2 số a và b 
- Bước 2: Nếu a = 0 thì thực hiện bước 3, ngược lại thực hiện bước 4 
Trang 6 
Lập trình căn bản 
- Bước 3: Nếu b=0 thì thông báo phương trình vô số nghiệm và kết thúc chương 
trình, ngược lại thông báo phương trình vô nghiệm và kết thúc chương trình. 
- Bước 4: Thông báo nghiệm của phương trình là –b/a và kết thúc. 
 Nhập hai số a,b 
 a=0 Đúng b=0 Đúng 
 Sai Sai 
 Nghiệm x=-b/a PT vô nghiệm PT vô định 
Ví dụ 3: Viết chương trình cho phép nhập vào 1 số n, sau đó lần lượt nhập vào n 
giá trị a1, a2,…,an. Hãy tìm và in ra giá trị lớn nhất trong n số a1, a2, …, an. 
 End 
Begin 
Để giải quyết bài toán trên, chúng ta áp dụng phương pháp “thử và sửa”. Ban 
đầu giả sử a1 là số lớn nhất (được lưu trong giá trị max); sau đó lần lượt xét các ai còn 
lại, nếu ai nào lớn hơn giá trị max thi lúc đó max sẽ nhận giá trị là ai. Sau khi đã xét hết 
các ai thì max chính là giá trị lớn nhất cần tìm. 
Mô tả giải thuật bằng ngôn ngữ tự nhiên: 
- Bước 1: Nhập số n 
- Bước 2: Nhập số thứ nhất a1 
- Bước 3: Gán max=a1 
- Bước 4: Gán i=2 
- Bước 5: Nếu i<=n thì thực hiện bước 6, ngược lại thực hiện bước 9 
- Bước 6: Nhập ai 
- Bước 7: Nếu max < ai thì gán max=ai. 
- Bước 8: Tăng i lên một đơn vị và quay lại bước 5 
- Bước 9: In max - kết thúc 
Phần mô tả giải thuật bằng lưu đồ, sinh viên tự làm xem như bài tập. 
Ví dụ 4: Viết chương trình cho phép nhập vào 1 số n, sau đó lần lượt nhập vào n 
giá trị a1, a2,…,an. Sắp theo thứ tự tăng dần một dãy n số a1, a2,...an nói trên. Có rất 
Trang 7 
Lập trình căn bản 
nhiều giải thuật để giải quyết bài toán này. Phần trình bày dưới đây là một phương 
pháp. 
Giả sử ta đã nhập vào máy dãy n số a1, a2,..., an. Việc sắp xếp dãy số này trải 
qua (n-1) lần: 
- Lần 1: So sánh phần tử đầu tiên với tất cả các phần tử đứng sau phần tử đầu 
tiên. Nếu có phần tử nào nhỏ hơn phần tử đầu tiên thì đổi chỗ phần tử đầu tiên với 
phần tử nhỏ hơn đó. Sau lần 1, ta được phần tử đầu tiên là phần tử nhỏ nhất. 
- Lần 2: So sánh phần tử thứ 2 với tất cả các phần tử đứng sau phần tử thứ 2. 
Nếu có phần tử nào nhỏ hơn phần tử thứ 2 thì đổi chỗ phần tử thứ 2 với phần tử nhỏ 
hơn đó. Sau lần 2, ta được phần tử đầu tiên và phần tử thứ 2 là đúng vị trí của nó khi 
sắp xếp. 
- … 
- Lần (n-1): So sánh phần tử thứ (n-1) với phần tử đứng sau phần tử (n-1) là 
phần tử thứ n. Nếu phần tử thứ n nhỏ hơn phần tử thứ (n-1) thì đổi chỗ 2 phần tử này. 
Sau lần thứ (n-1), ta được danh sách gồm n phần tử được sắp thứ tự. 
Mô tả giải thuật bằng ngôn ngữ tự nhiên: 
- Bước 1: Gán i=1 
- Bước 2: Gán j=i+1 
- Bước 3: Nếu i <=n-1 thì thực hiện bước 4, ngược lại thực hiện bước 8 
- Bước 4: Nếu j <=n thì thực hiện bước 5, ngược lại thì thực hiện bước 7. 
- Bước 5: Nếu ai > aj thì hoán đổi ai và aj cho nhau (nếu không thì thôi). 
- Bước 6: Tăng j lên một đơn vị và quay lại bước 4 
- Bước 7: Tăng i lên một đơn vị và quay lại bước 3 
- Bước 6: In dãy số a1, a2,..., an - Kết thúc. 
Mô tả giải thuật sắp xếp bằng lưu đồ 
Trang 8 
j<=n-1 
 j<=n 
aj<ai 
tam=ai
ai=aj
aj=tam 
In dãy số : a1, a2, …,an 
End
Sai 
Đúng 
Đúng 
Đúng 
j=i+1 
j=j+1 
Sai 
i=i+1 
i=1 
Lập trình căn bản 
II.4 Các cấu trúc suy luận cơ bản của giải thuật 
Giải thuật được thiết kế theo ba cấu trúc suy luận cơ bản sau đây: 
II.4.1 Tuần tự (Sequential): Các công việc đượ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. 
II.4.2 Cấu trúc lựa chọn (Selection) 
Lựa chọn một công việc để thực hiện căn cứ vào một điều kiện nào đó. Có một 
số dạng như sau: 
- Cấu trúc 1: Nếu (đúng) thì thực hiện 
- Cấu trúc 2: Nếu (đúng) thì thực hiện , ngược lại 
(điều kiện sai) thì thực hiện 
- Cấu trúc 3: Trường hợp thực hiện 
II.4.3. Cấu trúc lặp (Repeating) 
Thực hiện lặp lại một công việc không hoặc nhiều lần căn cứ vào một điều kiện 
nào đó. Có hai dạng như sau: 
- Lặp xác định: là loại lặp mà khi viết chương trình, người lập trình đã xác định 
được công việc sẽ lặp bao nhiêu lần. 
- Lặp không xác định: là loại lặp mà khi viết chương trình người lập trình chưa 
xác định được công việc sẽ lặp bao nhiêu lần. Số lần lặp sẽ được xác định khi chương 
trình thực thi. 
Trong một số trường hợp người ta cũng có thể dùng các cấu trúc này để diễn tả 
một giải thuật. 
III. KIỂU DỮ LIỆU 
Các số liệu lưu trữ trong máy tính gọi là dữ liệu (data). Mỗi đơn vị dữ liệu 
thuộc một kiểu dữ liệu nào đó. 
Kiểu dữ liệu là một tập hợp các giá trị có cùng một tính chất và tập hợp các 
phép toán thao tác trên các giá trị đó. Người ta chia kiểu dữ liệu ra làm 2 loại: kiểu dữ 
liệu sơ cấp và kiểu dữ liệu có cấu trúc. 
III.1 Kiểu dữ liệu sơ cấp 
Kiểu dữ liệu sơ cấp là kiểu dữ liệu mà giá trị của nó là đơn nhất. 
Ví dụ: Trong ngôn ngữ lập trình C, kiểu int gọi là kiểu sơ cấp vì kiểu này bao 
gồm các số nguyên từ -32768 đến 32767 và các phép toán +, -, *, /, %… 
III.2 Kiểu dữ liệu có cấu trúc 
Kiểu dữ liệu có cấu trúc là kiểu dữ liệu mà các giá trị của nó là sự kết hợp của 
các giá trị khác. 
Trang 9 
Lập trình căn bản 
Ví dụ : Kiểu chuỗi ký tự trong ngôn ngữ lập trình C là một kiểu dữ liệu có cấu 
trúc. 
Các ngôn ngữ lập trình đều có những kiểu dữ liệu do ngôn ngữ xây dựng sẵn, 
mà ta gọi là các kiểu chuẩn. Chẳng hạn như kiểu int, char… trong C; integer, array… 
trong Pascal. Ngoài ra, hầu hết các ngôn ngữ đều cung cấp cơ chế cho phép người lập 
trình định nghĩa kiểu của riêng mình để phục vụ cho việc viết chương trình. 
IV. NGÔN NGỮ LẬP TRÌNH 
IV.1. Khái niệm ngôn ngữ lập trình 
Ngôn ngữ lập trình là một ngôn ngữ dùng để viết chương trình cho máy tính. Ta 
có thể chia ngôn ngữ lập trình thành các loại sau: ngôn ngữ máy, hợp ngữ và ngôn ngữ 
cấp cao. 
Ngôn ngữ máy (machine language): Là các chỉ thị dưới dạng nhị phân, can 
thiệp trực tiếp vào trong các mạch điện tử. Chương trình được viết bằng ngôn ngữ máy 
thì có thể được thực hiện ngay không cần qua bước trung gian nào. Tuy nhiên chương 
trình viết bằng ngôn ngữ máy dễ sai sót, cồng kềnh và khó đọc, khó hiểu vì toàn những 
con số 0 và 1. 
Hợp ngữ (assembly language): Bao gồm tên các câu lệnh và quy tắc viết các 
câu lệnh đó. Tên các câu lệnh bao gồm hai phần: phần mã lệnh (viết tựa tiếng Anh) chỉ 
phép toán cần thực hiện và địa chỉ chứa toán hạng của phép toán đó. Ví dụ: 
INPUT a ; Nhập giá trị cho a từ bàn phím 
LOAD a ; Đọc giá trị a vào thanh ghi tổng A 
PRINT a; Hiển thị giá trị của a ra màn hình. 
INPUT b 
ADD b; Cộng giá trị của thanh ghi tổng A với giá trị b 
Trong các lệnh trên thì INPUT, LOAD, PRINT, ADD là các mã lệnh còn a, b là 
địa chỉ. Để máy thực hiện được một chương trình viết bằng hợp ngữ thì chương trình 
đó phải được dịch sang ngôn ngữ máy. Công cụ thực hiện việc dịch đó được gọi là 
Assembler. 
Ngôn ngữ cấp cao (High level language): Ra đời và phát triển nhằm phản ánh 
cách thức người lập trình nghĩ và làm. Rất gần với ngôn ngữ con người (Anh ngữ) 
nhưng chính xác như ngôn ngữ toán học. Cùng với sự phát triển của các thế hệ máy 
tính, ngôn ngữ lập trình cấp cao cũng được phát triển rất đa dạng và phong phú, việc 
lập trình cho máy tính vì thế mà cũng có nhiều khuynh hướng khác nhau: lập trình cấu 
trúc, lập trình hướng đối tượng, lập trình logic, lập trình hàm... Một chương trình viết 
bằng ngôn ngữ cấp cao được gọi là chương trình nguồn (source programs). Để máy 
tính "hiểu" và thực hiện được các lệnh trong chương trình nguồn thì phải có một 
chương trình dịch để dịch chuơng trình nguồn (viết bằng ngôn ngữ cấp cao) thành 
dạng chương trình có khả năng thực thi. 
IV.2 Chương trình dịch 
Như trên đã trình bày, muốn chuyển từ chương trình nguồn sang chương trình 
đích phải có chương trình dịch. Thông thường mỗi một ngôn ngữ cấp cao đều có một 
chương trình dịch riêng nhưng chung quy lại thì có hai cách dịch: thông dịch và biên 
dịch. 
Trang 10 
Lập trình căn bản 
Thông dịch (interpreter): Là cách dịch từng lệnh một, dịch tới đâu thực hiện tới 
đó. Chẳng hạn ngôn ngữ LISP sử dụng trình thông dịch. 
Biên dịch (compiler): Dịch toàn bộ chương trình nguồn thành chương trình đích 
rồi sau đó mới thực hiện. Các ngôn ngữ sử dụng trình biên dịch như Pascal, C... 
Giữa thông dịch và biên dịch có khác nhau ở chỗ: Do thông dịch là vừa dịch 
vừa thực thi chương trình còn biên dịch là dịch xong toàn bộ chương trình rồi mới thực 
thi nên chương trình viết bằng ngôn ngữ biên dịch thực hiện nhanh hơn chương trình 
viết bằng ngôn ngữ thông dịch. 
Một số ngôn ngữ sử dụng kết hợp giữa thông dịch và biên dịch chẳng hạn như Java. 
Chương trình nguồn của Java được biên dịch tạo thành một chương trình đối tượng 
(một dạng mã trung gian) và khi thực hiện thì từng lệnh trong chương trình đối tượng 
được thông dịch thành mã máy. 
V. BÀI TẬP 
V.1 Mục đích yêu cầu 
 Làm quen và nắm vững các cách mô tả giải thuật; từ đó đứng trước một bài 
toán cụ thể, sinh viên có thể mô tả thật chi tiết các bước để giải quyết vấn đề. 
V.2 Nội dung 
Bằng ngôn ngữ tự nhiên và lưu đồ, anh (chị) hãy mô tả giải thuật cho các bài toán sau: 
1. Giải phương trình bậc 2 dạng với a, b, c là các số sẽ nhập từ bàn 
phím. 
02 =++ cbxax
2.Tính tổng bình phương của n số nguyên có dạng sau: S= , với n và a22221 naaa +++ L i 
(i=1..n) là các số sẽ nhập từ bàn phím.
3. Tính tổng có dạng sau: S= , với n và a2232221 )1(1 nn aaaa −++−+− L i (i=1..n) là các số 
sẽ nhập từ bàn phím.
4. Trình bày kết quả qua các bước lặp (được mô tả ở trên) để sắp xếp dãy số sau theo 
thứ tự tăng dần. 
a) 12 13 11 10 10 9 8 7 6 5 
b) 11 12 13 14 3 4 5 6 7 11 8 
Trang 11