Bài toán là gì ?
Bài toán là một công việc mà con người muốn máy tính thực hiện.
Thuật toán là gì ?
Thuật 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 khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.
Máy tính thật thông minh, làm được mọi công việc kể cả việc giải toán.


Không đúng đâu. Máy tính làm một công việc hay giải một bài toán là do con người đã đưa vào trong máy các cách thức làm việc để hướng dẫn cho máy thực hiện công việc.
Việc giải toán trên máy tính được thực hiện như thế nào ?
Để giải bài toán trên máy tính ta thường tiến hành theo 5 bước như sau :
Bài 6: GiẢI BÀI TOÁN TRÊN MÁY TÍNH
Việc giải bài toán trên máy tính thường có 5 bước :
Bước 1: Xác định bài toán
Bước 2 : Lựa chọn hoặc thiết kế thuật toán
Bước 3 : Viết chương trình
Bước 4 : Hiệu chỉnh
Bước 5: Viết tài liệu.
1/ Xác định bài toán :

? Với một bài toán thì trước tiên cần phải xác định hai yếu tố cần thiết, đó là hai yếu tố nào ?
Phải xác định input và output của bài toán


Xác định bài toán là xác định Input và Output
của bài toán.
Ví dụ1 : Xét bài toán tìm kiếm sau

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 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ố đó.
? Hãy xác định Input và Output của bài toán trên ?
Input : dãy A 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.
Khi đã xác định được input và output ta sẽ lựa chọn hoặc thiết kế thuật toán cho bài toán.

? Bài toán ở ví dụ 1 có mấy thuật toán để giải ?
Có 2 thuật toán để giải :
-Thuật toán tìm kiếm tuần tự.
-Thuật toán tìm kiếm nhị phân.
? Ta nên chọn thuật toán nào để giải ? Tại sao ?
Nên chọn thuật toán tìm kiếm nhị phân. Vì thuật toán này nhanh hơn, tốn ít thời gian hơn.
Vậy: khi giải toán ta phải lựa chọn một thuật toán tối ưu nhất. Tại sao phải lựa chọn thuật toán ? và thế nào là một thuật toán tối ưu ?



2/ Lựa chọn hoặc thiết kế thuật toán

Một bài toán có thể có nhiều thuật tóan để giải nhưng mỗi thuật toán chỉ giải được cho một bài toán. Vì vậy ta phải chọn thuật toán tối ưu nhất trong các thuật toán đã có.
Một thuật toán tối ưu phải có các tiêu chuẩn sau :
-Thời gian thực hiện nhanh.
-Ít tốn bộ nhớ.
-Trình bày dễ hiểu, dễ nhìn.
b/ Diễn tả thuật toán :
Có 2 cách diễn tả một thuật toán
* Diễn tả bằng cách liệt kê.
* Diễn tả bằng sơ đồ khối.


a/ Lựa chọn thuật toán

Vd2:Tìm ƯCLN của hai số dương M và N
Xác định bài toán :
Input : hai số M và N;
Output : ƯCLN (M,N).
Ý tưởng : ta có ý tưởng sau:
+ Nếu M=N thì ƯCLN ( M,N) là M hoặc N;
+Nếu M+Nếu M>N thì ƯCLN (M,N)=ƯCLN (M-N,N);
Bước 2:
lựa chọn
hoặc thiết
kế thuật
toán
Thuật toán :
* Diễn tả thuật toán bằng cách liệt kê :
Bước 1: Nhập M và N;
Bước 2 : Nếu M=N thì lấy giá trị chung này làm ƯCLN rồi chuyển đến bước 5;
Bước 3:Nếu M >N thì M ← M-N rồi quay lại bước 2;
Bước 4: N ← N-M rồi quay lại bước 2;
Bước 5: Đưa ra kết quả ƯCLN rồi kết thúc.

Bước 2:
lựa chọn
hoặc thiết
kế
thuật toán
Nhập M và N
M=N?
M>N ?
N←N-M
* Sơ đồ khối
M←M-N
Đ
S
S
Đ
Kết quả ƯCLN (25,10) = 5
Tìm ƯCLN (25,10)
Đưa ra M rồi kết thúc
3/ Viết chương trình :
-Là lựa chọn cách tổ chức dữ liệu và lựa chọn ngôn ngữ lập trình (NNLT) phù hợp với thuật toán.
-Có nhiều loại NNLT,vì vậy khi viết chương trình trong ngôn ngữ nào thì phải tuân theo những quy định đó.




4/ Hiệu chỉnh :
?Khi ta giải một bài toán có phải lúc nào cũng kết quả cũng đúng không ? Tại sao cần phải có bước hiệu chỉnh ? Thế nào là hiệu chỉnh ?
Một chương trình đã viết xong có thể có nhiều lỗi và sẽ cho kết quả không đúng. Nên ta cần thử chương trình bằng vài bộ số Input tiêu biểu để phát hiện ra sai sót và sửa chương trình,rồi thử lại. Quá trình này gọi là hiệu chỉnh.
Vd3: Để kiểm chứng tính đúng đắn của chương trình giải pt bậc hai ax2 +bx +c =0, ta sử dụng vài bộ số Input để thấy rõ bước hiệu chỉnh của bài toán.

Bài toán này có Input là gì ?
Input là bộ ba số a,b,c.
a=1,b= -3,c=2 ; ∆ =1>0(chương trình đưa ra hai nghiệm).
a=1,b= -4,c=4; ∆ =0 (chương trình đưa ra một nghiệm).
a=1,b=3,c=4; ∆= -7 <0 (chương trình thông báo pt vô nghiệm).
Bước hiệu chỉnh giúp cho người lập trình thấy những sai sót để sửa sai, giúp cho kiểm tra tính đúng đắn của chương trình để có được một chương trình hoàn chỉnh.
5/ Viết tài liệu :
Mô tả chi tiết toàn bộ bài toán, thuật toán, thiết kế chương trình, kết quả thử nghiệm và hướng dẫn sử dụng.

Ví dụ 4:
Bài toán: viết thuật toán giải pt bậc nhất ax+b=0 và sử dụng vài bộ Input để kiểm chứng tính đúng đắn của chương trình.
Xác định bài toán :
- Input : các hệ số a,b
- Output : các kết luận về nghiệm của pt.
Ý tưởng : nghiệm của bài toán phụ thuộc vào các số a và b như sau:
-Nếu a=0 :
+Nếu b=0 :kết luận pt có vô số nghiệm;
+Nếu b≠ 0 : kết luận pt vô nghiệm;
-Nếu a ≠ 0 : kết luận pt có một nghiệm x = -b/a.





S
Đ
Thuật toán :


- Sơ đồ khối
Nhập a và b
a=0?
b=0 ?
Pt vn rồi
kết thúc
Pt vsn rồi
kết thúc
Đ
S
nghiệm x=-b/a
rồi kết thúc
Giải pt: 8x+96=0
Pt có nghiệm :x=-12
Hãy chọn đáp án đúng trong các câu sau:
Câu 1: Các bước cần phải có khi giải bài toán trên máy tính là :
a. Xác định bài toán,lựa chọn hoặc thiết kế thuật toán,diễn tả thuật toán,hiệu chỉnh, viết tài liệu.
b. Xác định bài toán,lựa chọn hoặc thiết kế thuật toán,viết chương trình, viết tài liệu.
c. Xác định bài toán,lựa chọn hoặc thiết kế thuật toán, viết chương trình,hiệu chỉnh, viết tài liệu.
d. Xác định bài toán, viết thuật chọn, viết chương trình, viết tài liệu.

Đáp án : C
Đáp án : b


Câu 2: Thuật toán tốt là thuật toán :
Dễ hiểu và dễ nhìn.
b. Thời gian chạy nhanh.
c. Ít tốn bộ nhớ.
d. Cả a,b,c đều đúng.

Đáp án : d
Câu 3: Mục đích của việc hiệu chỉnh là :
a. Xác định lại Input và Output của bài toán.
b. Phát hiện và sửa sai sót.
c. Mô tả chi tiết bài toán.
d. Để tạo ra một chương trình mới.



Về nhà học bài, trả lời các câu hỏi sau bài học. Chuẩn bị bài phần mềm máy tính cho tiết sau.