BÀI 4:
BÀI TOÁN VÀ THUẬT TOÁN
Xét các yêu cầu sau :
1. Giải phương trình bậc hai ax2+bx+c=0
2. Viết một dòng chữ ra màn hình máy tính.
3. Quản lý các cán bộ trong một cơ quan.
4. Tìm ước chung lớn nhất của hai số nguyên
dương a và b.
5. Xếp loại học tập các học sinh trong lớp.
->Trong các yêu cầu trên yêu cầu nào được xem như là một bài toán
Trong Toán học
Trong Tin học
Yêu cầu 1 và 4 được xem là bài toán
Tất cả các yêu cầu trên được xem là bài toán
Khái niệm bài toán
trong tin học
Bài toán là một việc nào
đó mà ta muốn máy
tính thực hiện
TOÁN HỌC?
Các yếu tố cần quan tâm khi giải một bài toán
Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó.
CÁC VÍ DỤ
VD1 : Giải phương trình bậc hai
ax2 + bx + c = 0 (a ≠ 0).
Input : Các số thực a,b,c (a ≠ 0)
Output : x1, x2 hoặc vô nghiệm
VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.
Input : Các số trong dãy số.
Output : Giá trị nhỏ nhất trong dãy số.
VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b.
Input :
Output :
VD4 : Xếp loại học tập các học sinh trong lớp.
Input :
Output :
UCLN của a và b.
Hai số nguyên dương a và b.
?
?
?
?
Bảng điểm của học sinh.
Bảng xếp loại học tập.
CÁC VÍ DỤ
Nêu một bài toán và chỉ rõ Input, Output của bài toán đó?
Xem thêm các ví dụ trong SGK/24, 25
TÓM LẠI
Một bài toán được cấu tạo bởi 2 thành phần cơ bản :
Input (Các thông tin đã có)
Output (Các thông tin cần tìm từ Input)
II. THUẬT TOÁN
Hướng dẫn các thao tác cho máy thực hiện để tìm ra lời giải
Bài toán
Input
Output
Bằng cách nào?
Giải bài toán
Thuật toán
Input
Output
THUẬT TOÁN
(Thao tác 1Thao tác 2...Thao tác 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 sau khi thực hiện dãy thao tác đó, từ Input của bài toán này, ta nhận được Output cần tìm.
BÀI 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ác thao tác được sắp xếp theo một trình tự xác định.
Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.
MÔ TẢ CÁC THAO TÁC
TRONG THUẬT TOÁN
Có 2 cách mô tả
Liệt kê các bước
Dùng sơ đồ khối
Nêu ra tuần tự các thao tác cần tiến hành
Dùng một số biểu tượng thể hiện các thao tác
12
: Thể hiện các thao tác so sánh
DÙNG SƠ ĐỒ KHỐI
Trong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như :
: Thể hiện các phép toán
: Quy định trình tự thực hiện các thao tác
: Thể hiện các thao tác nhập, xuất dữ liệu
Ví dụ 1: Tìm giá trị lớn nhất của một dãy số nguyên
Xác định bài toán:
+ Input: – số nguyên dương N.
– N số a1, a2, …, aN.
+ Output: giá trị Max.
Ý tưởng:
– Khởi tạo giá trị Max = a1.
– Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
Thuật toán: (Liệt kê)
B1: Nhập N và dãy a1, …, aN
B2: Max a1; i 2
B3: Nếu i > N thì đưa ra giá trị Max và kết thúc.
B4: Nếu ai > max thì Max ai
B5: i i+1, quay lại B3.
Ghi chú: Trong thuật toán trên, i là biến chỉ số và có giá trị nguyên thay đổi trong khoảng 2->N+1
Mũi tên <- trong thuật toán trên được hiểu là gán giá trị của biểu thức bên phải cho biến ở bên trái mũi tên. Ví dụ i<-i+1 được hiểu là đặt cho biến i giá trị mới bằng giá trị trước đó tăng thêm 1
Sơ đồ khối
Đưa ra Max rồi kết thúc
Qua định nghĩa trên ta thấy thuật toán có các tính chất sau:
*Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần các thao tác
*Tính xác định: Sau khi thực hiện các thao tác thì hoặc là thuật toán kết thúc 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
III. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN
Ví dụ 2: Kiểm tra tính nguyên tố của một số nguyên dương
*Xác định bài toán
+ Input: N Z+
+ Output: " N là số nguyên tố " hoặc "N không là số nguyên tố“
*ý tưởng:
+ Nếu N=1 thì N không là số nguyên tố;
+ Nếu 1 < N < 4 thì N là số nguyên tố.
+ Nếu N ≥ 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố.
Thuật toán:a) Cách liệt kê:
B1: Nhập số ng.dương N;
B2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
B3: Nếu N< 4 thì thông báo N là nguyên tố rồi kết thúc;
B4: i <- 2 ;
B5: Nếu i> thì thông báo N là nguyên tố rồi kết thúc.
B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
B7: i<- i + 1 rồi quay lại B5
đúng
Nhập N
N=1 ?
Thông báo N là số nguyên tố rồi kết thúc
i<-2
i>[ ]
i <- i + 1
N chia hết cho i
N<4?
Thông báo N không là số nguyên tố rồi kết thúc
đúng
Sai
Sai
đúng
Sai
đúng
Sai
sơ đồ khối
Ví dụ 3: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2, …, aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
Xác định bài toán:
- Input: Dãy A gồm N số nguyên a1, a2, …, aN.
- Output: Dãy A được sắp xếp lại thành dãy không giảm.
Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
Thuật toán:
a) Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, …, aN ;
- B2: M =N ;
- B3: Nếu M< 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
- B4: M= M–1; i= 0;
- B5: i =i+1;
- B6: Nếu i > M thì quay lại bước 3;
- B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
- B8: Quay lại bước 5
Nhận xét: Sau mỗi lần đổi chỗ, giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí là ở cuối dãy. Và sau mỗi lượt chỉ thực hiện với dãy đã bỏ bớt số hạng cuối dãy (M <-M–1). Trong thuật toán trên, i là biến chỉ số có giá trị nguyên từ 0 ->M+1
Sơ đồ khối
Mô phỏng : N = 10 và dãy A: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4
Ví dụ 3: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau: a1, a2, …, aN và một số nguyên k. Cần 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ố đó.
Tìm kiếm là một việc thường xảy ra trong cuộc sống.
Cho dãy A gồm: 5, 7, 1, 4, 2, 9, 8, 11, 25, 51. Tìm i với ai = 2 ?
Thuật toán tìm kiếm tuần tự
Xác định bài toán
- Input: Dãy A gồm N số nguyên khác nhau 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ố hạng nào của dãy A có giá trị bằng k.
Ý tưởng:
- Tìm kiếm tuần tự là lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp một số hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.
Thuật toán:Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, …, aN và khoá k;
- B2: i <-1;
- B3: Nếu ai = k thì thông báo chỉ số i, kết thúc;
- B4: i <-i + 1;
- B5: Nếu i >N thì thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc.
- B6: Quay lại bước 3.
Sơ đồ khối
Nhập N và a
1
,
a
2
,
…
,
a
N
;
k
i
¬
1
a
i
=
k
i
¬
i
+
1
i
>
N
Đa ra i
rồii kết thúc
Thông báo dãy A không có
số hạng nào có giá trị bằng k
rồii kết thúc
Đ
S
Đ
S
b) Thuật toán tìm kiếm nhị phân (Binary Search)
Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, …, aN và một số nguyên k
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
Ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vị tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn, ta chọn số hạng aGiữa ở " giữa dãy" để so sánh với k, trong đó Giưa =[(N+1)/2]. Khi đó:
- Nếu aGiưa = k thì Giưa là chỉ số cần tìm.
- Nếu aGiưa> k thì do dãy A là dãy đã sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2, …, aGiưa-1 .
- Nếu aGiưa < k thì thực hiện tìm kiếm trên dãy aGiưa+1, aGiưa+2, …, aN.
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.
Thuật toán:
* Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, …, aN và khoá k
- B2: Dau <-1,Cuoi <- N;
- B3: Giưa <- [(Dau+cuoi)/2];
- B4: Nếu aGiưa = k thì thông báo chỉ số Giưa, rồi kết thúc;
.
- B5: Nếu aGiưa > k thì đặt Cuoi = Giưa - 1, rồi chuyển đến bước 7;
- B6: Dau<- Giưa +1;
- B7: Nếu Dau > cuoi thì thông báo dãy A không có số hạng nào có giá trị bằng k, kết thúc;
- B8: Quay lại bước 3
Sơ đồ khối
nguon VI OLET
