Bài giảng Tin học cơ sở - Chương 6: Giải thuật

Chương 6: Giải thuật (Algorithms)
I-Phương pháp giải quyết vấn đề bằng máy tính
Bài toán => Giải thuật => Chương trình => 
Ngôn ngữ máy => Máy thực hiện
Chương 6: Giải thuật (Algorithms)
I-Phương pháp giải quyết vấn đề bằng máy tính
Bài toán => Giải thuật => Chương trình => 
Ngôn ngữ máy => Máy thực hiện
II-Khái niệm về giải thuật
1. Khái niệm
2. Các tính chất của giải thuật
Chương 6: Giải thuật (Algorithms)
II-Khái niệm về giải thuật
1. Khái niệm
2. Các tính chất của giải thuật
- Tính thực hiện được:
- Tính kết thúc:
- Tính kết quả:
- Tính hiệu quả:
- Tính duy nhất:
- Tính tổng quát:
- Tính hình thức:
Chương 6: Giải thuật (Algorithms)
III-Các cách diễn đạt giải thuật
1. Liệt kê các bước bằng lời
2. Lưu đồ giải thuật
3. Giả mã
Chương 6: Giải thuật (Algorithms)
III-Các cách diễn đạt giải thuật
1. Liệt kê các bước bằng lời
Ví dụ: Giải thuật tìm USCLN(a,b)
B1: Nhập vào hai số nguyên a, b
B2: Đem a chia nguyên cho b, lấy phần dư để trong 
r.
B3: Nếu r = 0 thì chuyển sang B4. Nếu r ¹ 0 thì a 
lấy giá trị của b, b lấy giá trị của r và quay lại B2.
B4: Đưa ra USCLN là b
B5: Kết thúc
Chương 6: Giải thuật (Algorithms)
III-Các cách diễn đạt giải thuật
2. Lưu đồ giải thuật
Bắt đầu Kết thúc
Vào/ra 
dữ liệu
A
Thực hiện 
công việc A
B
Đúng
Sai
Bắt đầu
Kết thúc
Nhập a, b
r := a mod b
r = 0
Đưa ra b
Đúng
Sai
a := b
b := r
Chương 6: Giải thuật (Algorithms)
III-Các cách diễn đạt giải thuật
3. Dùng giả mã
Chương 6: Giải thuật (Algorithms)
III-Các cách diễn đạt giải thuật
3. Dùng giả mã
• Vào: a, b
• Ra: USCLN(a,b)
1) Read(a,b);
2) r := a mod b;
3) While r ¹ 0 do
begin
a := b; b := r; r:=a mod b;
end;
4) Write(b);
5) Kết thúc
Chương 6: Giải thuật (Algorithms)
IV-Một số giải thuật cơ bản
1. Hoán đổi nội dung 2 ô nhớ (đổi chỗ)
Ví dụ: Hoán đổi nội dung 2 ô nhớ a và b
1) tg := a;
2) a : = b;
3) b := tg;
Sau này, viết gọn là DoiCho(a,b) hoặc a :=: b 
hoặc a « b
Chương 6: Giải thuật (Algorithms)
IV-Một số giải thuật cơ bản
2. Tìm giá trị lớn nhất/nhỏ nhất trong 1 dãy số
Ví dụ: Cho dãy số a1, a2,, an. Tìm giá trị lớn 
nhất
Chương 6: Giải thuật (Algorithms)
1) read(n);
2) read(a[1], a[2],, a[n]);
3) max:=a[1];
4) For i:=2 to n do
If a[i] > max then max:=a[i];
5) write(max);
6) Kết thúc
Chương 6: Giải thuật (Algorithms)
IV-Một số giải thuật cơ bản
3. Sắp xếp dãy số tăng/giảm dần
Ví dụ: Cho dãy số a1, a2,, an. Sắp xếp dãy số 
tăng dần từ trái qua phải.
Chương 6: Giải thuật (Algorithms)
Giải thuật 1:
1) Read(n);
2) Read(a[1], a[2],, a[n]);
3) For i:=1 to n-1 do
For j:=i+1 to n do
If a[j] < a[i] then a[i] « a[j]
4) Write(a[1], a[2],, a[n]);
5) Kết thúc
Chương 6: Giải thuật (Algorithms)
Giải thuật 2:
1) Read(n);
2) Read(a[1], a[2],, a[n]);
3) For i:=1 to n-1 do
begin
+) k:=i;
+) For j:=i+1 to n do
If a[j] < a[k] then k:=j;
+ If k ¹ i then a[i] « a[k];
end;
4) Write(a[1], a[2],, a[n]);
5) Kết thúc
Chương 6: Giải thuật (Algorithms)
IV-Một số giải thuật cơ bản
4. Tìm giá trị x trong dãy số
Ví dụ: Cho dãy số a1, a2,, an. Tìm xem có phần 
tử nào bằng x không?
Chương 6: Giải thuật (Algorithms)
1) Read(n);
2) Read(a[1], a[2],, a[n]);
3) Read(x);
4) Co:=FALSE; {Ban dau la khong co}
5) For i:=1 to n do
If a[i] = x Then
begin
Co:=TRUE; break;
end;
6) If Co = TRUE Then write(‘Co phan tu bang x’) Else 
write(‘Khong co phan tu bang x’);
7) Kết thúc