Module 1 : Thuật toán
1. Khái niệm thuật toán :
- Là một hệ thống các quy tắc chặt chẽ, rõ ràng, nhằm thao tác lên một đối tượng sao cho sau một số hữu hạn bước thực hiện các thao tác đó thì nhận được một kết quả mong muốn
VD : xét bài toán ax2 + bx + c = 0
B1 : Nhập hệ số a, b, c
B2 : Tính Delta=b*b – 4*a*c
B3 : Biện luận : nếu Delta <0 thì “Phương trình vô nghiệm”
nếu Delta = 0 thì “Phương trình có nghiệm kép”
nếu Delta >0 thì “Phương trình có 2 nghiệm phân biệt”
B4 : Kết thúc
- Các quy tắc của thuật toán phải tuân theo quy định của một ngôn ngữ lập trình nào đó
Vd : để in ra dòng chữ “Hello”
Pascal : Write(‘Hello’);
C : Printf(“Hello”)
- Có thể hiểu là thuật toán + cấu trúc dữ liệu = chườn trình
* Activity : Indentifying Parts of an Application- tính tương tác, mở rộng của ứng dụng
- Các thành phần tương tác, hỗ trợ lẫn nhau
2. Các tính chất cơ bản :
a, Tính đơn điệu : Các kết quả trung gian của thuật toán sau mỗi bước thực hiện một thao tác của thuật toán, nhận được một kết quả đơn trị. Hay nói cách khác là cùng một bộ dữ liệu đầu vào thì hai máy tính khác nhau hoặc hai người khác nhau cũng thực hiện một thao tác của thuật toán phải cho cùng một kết quả
VD : Xét đoạn trình tính tổng hai số a,b :
B1 : Nhập a, b
B2 : Tong=a+b
B3 : In kết quả
B4 : Kết thúc
b, Tính đúng đắn
- Thuật toán phải thực hiện chính xác nhiệm vụ, chức năng định trước. Tính đúng đắn của thuật toán được chứng minh bằng các biểu thức toán học và các bộ TEST
* TEST : là quá trình đưa vào các bộ dữ liệu cụ thể để kiểm tra tính đúng đắn, chính xác của chương trình
* Thế nào là 1 bộ TEST đầy đủ ? - Nếu nó phủ kín môi trường của bài toán
-à Trở thành chuyên viên TEST : Còn phải học lâu dài
VD : Tìm MAX giữa 3 số a, b, c
B1 : Nhập a, b, c
B2 : Giả sử MAX là a : max=a
B3 : Tiếp tục kiểm tra
Nếu Max < b thì MAX là b ( max =b )
Nếu Max < c thì MAX là C ( max =c )
B4 : In MAX
B5 : Kết thúc
-à Một bộ TEST phủ kín gồm 6 bộ :
a = b = c
a > b > c
a > c > b
c > a > b
c > b > a
b > c > a
c, Tính dừng :
- Thuật toán phải dừng lại sau một số hữu hạn bước và trả lại kết quả đầu ra của bài toán
d, Tính phổ dụng :
- Thuật toán phải giải được tất cả các bài toán của một dạng đã cho
e, Tính có đại lượng vào ra :
- Ban đầu thuật toán nhận bộ giữ liệu vào (đầu vào ). Dữ liệu đầu vào là đối tượng thao tác của thuật toán . Khi kết thúc, thuật toán phải đưa ra một kết quả gọi là đầu ra của bài toán
3. Câu lệnh :
- Câu lệnh được quy định theo ngôn ngữ lập trình nhằm thực hiện một nhiệm vụ nào đó của thuật toán
- Có 2 loại câu lệnh :
* Câu lệnh đơn giản : Không chứa câu lệnh con
* Câu lệnh phức tạp : Lệnh thử, vòng lặp, rẽ nhánh
- Khối lệnh : là một nhóm các câu lệnh đơn được nhóm lại vào nhau để thực hiện 1 nhiệm vụ nào đó. Khối lệnh ít nhất là 1 lệnh
4. Biểu thức :
- Biểu thức nhằm thực hiện một biểu thức toán học nào đó, trong đó có toán tử và toán hạng
- Biểu thức = toán hạng + toán tử
VD : Delta = b*b – 4*a*c
5. Ngôn ngữ lập trình :
- Ngôn ngữ lập trình dùng để viết chương trình máy tính
- Chương trình máy tính là một thể hiện cụ thể của thuật toán bằng các câu lệnh của một ngôn ngữ lập trình nào đó
6. Một số cấu trúc điều khiển :
a, Cấu trúc tuần tự :
- Là các lệnh được thực hiện theo đúng thứ tự trong khối lệnh
b, Cấu trúc rẽ nhánh :
- Cú pháp : IF < điều kiện > THEN < việc 1 >
ELSE IF < điều kiện 2 > THEN < việc 2 >
……….
ELSE IF < điều kiện n > THEN < việc n >
ELSE < việc n + 1 >
END IF
--à Nếu biểu thức điều kiện 1 nhận giá trị đúng thì thực hiện việc 1
Ngược lại nếu biểu thức điều kiện 2 nhận giá trị đúng thì thực hiện việc 2
Còn lại nếu tất cả các điều kiện đều sai thì thực hiện việc ( n + 1 )
Biểu thức điều kiện nói chung là biểu thức logic chỉ nhận giá trị True or False
Trong trường hợp biểu thức điều kiện nhận giá trị không phải là True or False thì được quy về giá trị sau :
· Điều kiện <> 0 -à TRUE
· Điều kiện = 0 -à FALSE
c, Cấu trúc lặp :
- Trong chương trình đôi khi chúng ta phải thực hiện một công việc nào đó lặp đi lặp lại nhiều lần và có quy luật. Khi đó dùng vòng lặp để thực hiện công việc và làm cho chương trình sáng sủa
- Có 2 loại vòng lặp :
1. Vòng lặp xác định trước bước lặp For
2. Vòng lặp không xác định trước bước lặp ( còn gọi là vòng lặp không xác định ). Có 2 loại : Repeat & While
* Cấu trúc lặp For :
Khai báo trung gian : giai thừa
Nếu n = 0 hoặc n = 1 thì gt = 1
For i=1 to n
Gt=gt*1
In ra giai thừa :gt
* Cấu trúc lặp Do While
Cú pháp : Do While < điều kiện >
Công việc
Loop
- Quy trình thực hiện : chừng nào còn đúng thì vòng lặp còn thực hiện
* Cấu trúc Do Until
Cú pháp : Do
< công việc >
Until