SỞ GIÁO DỤC & ĐÀO TẠO TP.HỒ CHÍ MINH
TRƯỜNG THPT
TRẦN KHAI NGUYÊN
Nhóm Tin Học
Năm học : 2006-2007
BÀI TOÁN
& THUẬT TOÁN
Chương 1
Bài 4
Tin học 10
?????
Nội dung
Khái niệm Bài Toán
Khái niệm Thuật Toán
Khái niệm
Ví dụ : Tìm giá trị lớn nhất của một dãy số nguyên.
Một số ví dụ về thuật toán
Ví dụ 1 : Kiểm tra tính nguyên tố của một số nguyên dương.
Ví dụ 2 : Bài toán sắp xếp
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort).
Ví dụ 3 : Bài toán tìm kiếm
Thuật toán tìm kiếm tuần tự (Sequential Search).
Thuật toán tìm kiếm nhị phân (Binary Search).
Giải phương trình bậc 2 : ax2 + bx + c = 0 với (a?0).
Viết một dòng chữ nào đó ra màn hình máy vi tính.
Tìm ước chung lớn nhất (UCLN) của 2 số nguyên dương a,b.
Quản lí các cán bộ, nhân viên trong một cơ quan.
Hãy thảo luận một số vấn đề sau :
Tổng kết
Trong toán học :
(a) là bài toán.
(b) không là bài toán.
(c) là bài toán.
(d) không là bài toán.
Trong tin h ọc :
tất cả các yêu cầu trên đều được xem là bài toán.
Kết luận
Trong phạm vi Tin học, bài toán là việc nào đó ta muốn máy tính thực hiện.
Vấn đề thảo luận
Trong Toán học, chúng ta cần quan tâm những yếu tố nào của bài toán khi tiến hành giải bài toán đó?
giả thiết bài toán ( thông tin đã có).
kết luận ( thông tin cần tìm).
Trong Tin học thì thế nào? Chúng ta quan tâm đến những yếu tố nào của bài toán ?
giả thiết bài toán (thông tin đã có)? Input.
kết luận (thông tin cần tìm) ? Output.
Kết luận
Các 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ó
(hay các thông tin đưa vào máy).

Output : các thông tin cần tìm
(thông tin muốn lấy từ máy).
Xác định Input và Output của bài toán
Ví dụ 1 :
Giải phương trình bậc 2:
ax2 + bx + c = 0 (a # 0)
---------------
Input : các số thực a, b, c với a # 0.
Output : * tất cả số thực x thoả mãn
ax2 + bx + c = 0
* không có số thực nào.

Ví d? 2 :
Tìm UCLN c?a 2 s? nguyên duong a về b.
---------
Input : 2 s? nguyên duong a,b.
Output : UCLN c?a a và b .
Ví d? 3 :
X?p lo?i h?c t?p c?a c�c h?c sinh trong l?p. ---------
Input : b?ng di?m c?a h?c sinh.
Output : b?ng x?p lo?i h?c t?p c?a h?c sinh.
Bài toán
Input
Output
Bằng cách nào ?
giải bài toán
Hướng dẫn các thao tác cho đối tượng giải toán thực hiện để tìm lời giải.
THUẬT 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 này đượ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 của bài toán ta nhận được Output cần tìm.
Các tính chất của Thuật toán
Tính dừng : Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.

Tính xác định : Sau khi thưck hiện một 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 để được thưck 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
Diễn tả thuật toán
Cách liệt kê :
Nêu ra tuần tự các thao tác cần tiến hành.

Ví dụ : Tìm nghiệm phương trình bậc nhất tổng quát: ax + b = 0
----------------
Bước 1: nhập a, b.
Bước 2: nếu a = 0 thì quay lại bước 1.
Bước 3: gán cho x= -b/a.
Bước 3: đưa ra kết quả x và kết thúc.
b) Dùng sơ đồ khối
Các biểu tượng trong sơ đồ khối:
Hình ôvan : thể hiện các thao tác nhập, xuất dữ liệu.
Hình chữ nhật : thể hiện các phép tính toán.
Hình thoi : thể hiện thao tác so sánh.
Các mũi tên : trình tự thực hiện các thao tác
Diễn tả thuật toán
Ví dụ : biểu diễn thuật toán giải phương trình bậc nhất bằng sơ đồ khối
Nhập a,b
a < > 0
sai
x  -b/a
Xuất x và kết thúc
đúng
Ví dụ: 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 và dãy số nguyên a1 ,. , aN.
Output : Giá trị lớn nhất Max của dãy số .
Ý tưởng :
Khởi tạo giá trị Min = 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ị Min, nếu ai < Min thì Min nhận giá trị mới là ai.
Thuật toán
Bước 1: Nhập N và dãy số a1,a2, . , aN .
Bước 2: Max ? a1, i ? 2.
Bước 3: Nếu i > N thì đưa ra Max và kết thúc.
Bước 4:
Bước 4.1 : Nếu ai > Max thì Max? ai.
Bước 4.2 : i? i+1 rồi quay lại bước3.
Sơ đồ thuật toán:
Tìm giá trị lớn nhất của một dãy số nguyên
Thực hiện thuật toán với dãy số sau:
5, 2, 4, 7, 6, 3, 15, 1, 4, 9, 12
Phân tích các tính chất của thuật toán
tính dừng: Vì giá trị của i mỗi lần tăng lên 1 nên sau N lần thì i > N, khi đó kết quả phép so sánh ở bước 3 xác định việc đưa ra giá trị Max rồi kết thúc.

tính xác định : Thứ tự thực hiện mặc định là tuần tự nên sau bước 1 là bước 2, sau bước 2 là bước 3. Kết quả các phép so sánh trong bước 3 và bước 4 đều xác định duy nhất bước tiếp theo cần thực hiện.

tính đúng đắn : vì thuật toán so sánh Max với từng số hạng của dãy số và thực hiện Max? ai nếu ai > Max nên sau khi so sánh hết N số hạng của dãy thì Max là giá trị lớn nhất.
Một số ví dụ về thuật toán
Ví dụ 1 : Kiểm tra tính nguyên tố của một số nguyên dương (phương pháp dùng sàng Erathosten)
-----------
Xác định bài toán:
Input : N là 1 số nguyên dương.
Output : " N là số nguyên tố" hoặc "N không là số nguyên tố"
Sơ đồ thuật toán:
Kiểm tra tính nguyên tố của một số nguyên dương
Thực hiện thuật toán với số N = 37
N = 37 ( )
? 37 là số nguyên tố
Thực hiện thuật toán với số N = 55
N = 55 ( )
? 55 không là số nguyên tố
Phân tích các tính chất của thuật toán
tính dừng: Vì giá trị của I mỗi lần tăng lên 1 và nếu N chia hết cho I hoặc nếu i > thì kết thúc.

tính xác định : thứ tự thực hiện các bước trong thuật toán mặc định là tuần tự nên sau bước 1 là bước 2. Kết quả so sánh ở bước 2 và 3 đều xác định duy nhất bước tiếp theo cần thực hiện. Sau bước 4 là bước 5. Kết quả so sánh ở bước 5 và 6 đều xác định duy nhất bước tiếp theo cần thực hiện. Sau bước là 7 là quay lại bước 5.

tính đúng đắn : vì thuật toán xác định ước số của số cần kiểm tra N trong khoảng từ 2? nên :
nếu có 1 ước x trong khoảng này thì N có ước khác 1 và chính nó. Vì thế N không là số nguyên tố . Và chắc chắn trong khoảng ?N, N sẽ có 1 ước y để x*y = N.
ngược lại nếu N không có ước trong khoảng này thì khoảng còn lại ?N (trừ N) cũng không có ước nào. Vì thế N là số nguyên tố.
Bài toán sắp xếp
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 thành dãy không giảm
Sơ đồ thuật toán:
sắp xếp bằng tráo đổi
(Exchange Sort)
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6, 11
Duyệt lần
1
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6 , 11
Duyệt lần 2
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6 , 11
Duyệt lần 3
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6 , 11
Duyệt lần 4
Phân tích các tính chất của thuật toán
tính dừng: Vì giá trị của M mỗi lần giảm 1 và nếu M<2 thì thuật toán kết thúc.

tính xác định : thứ tự thực hiện các bước trong thuật toán mặc định là tuần tự nên sau bước 1 là bước 2, bước 3. Kết quả so sánh ở bước 3 xác định duy nhất bước tiếp theo cần thực hiện. Sau bước 4 là bước 5, bước 6. Kết quả so sánh ở bước 6 và 7 đều xác định duy nhất bước tiếp theo cần thực hiện. Sau bước là 8 là quay lại bước 5.

tính đúng đắn : vì thuật toán cứ duyệt để kiểm tra xem nếu ai > ai+1 thì tráo đổi vị trí chúng cho đến khi mọi phần tử của dãy thoả điều kiện ai < = ai+1, nên cuối cùng ta sẽ được dãy số không giảm.
Bài toán tìm kiếm
Thuật toán tìm kiếm tuần tự
(Sequential Search)

Xác định bài toán:
Input : Dãy A gồm N số nguyên 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.
Sơ đồ thuật toán:
tìm kiếm tuần tự (Sequential Search)
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6, 11
K = 14 , N = 9
Với i = 4 và a4 = 14
K = 20 , N = 9
Với mọi i từ 1? 9 không có ai có giá trị bằng 20
Phân tích các tính chất của thuật toán
tính dừng: Vì giá trị của i mỗi lần tăng 1 và nếu ai=k hoặc i> N thì kết thúc.

tính xác định : thứ tự thực hiện các bước trong thuật toán mặc định là tuần tự nên sau bước 1 là bước 2, bước 3. Kết quả so sánh ở bước 3 xác định duy nhất bước tiếp theo cần thực hiện. Sau bước 4 là bước 5. Kết quả so sánh ở bước 5 xác định duy nhất bước tiếp theo cần thực hiện. Sau bước là 6 là quay lại bước 3.

tính đúng đắn : vì thuật toán cứ duyệt từ đầu đến cuối dãy để kiểm tra xem nếu ai =k thì kết thúc hoặc cho đến khi i>N, nên cuối cùng ta sẽ được có hoặc không có số cần tìm.
Bài toán tìm kiếm
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à 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.
Sơ đồ thuật toán:
tìm kiếm nhị phân (Binary Search)
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6, 11
K = 14 , N = 9
Ở lần duyệt thứ 3 thì agiữa= k. Vậy chỉ số cần tìm là i = Giữa=6
Thực hiện thuật toán với dãy số sau:
5, 7, 9, 14, 23, 5, 8, 6, 11
K = 20 , N = 9
Tại lần duyệt thứ 4 Dau > Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị là 20 cả.
Phân tích các tính chất của thuật toán
tính dừng: Vì sau mỗi lần duyệt giá trị Dau=Giua+1, hoặc Cuoi=Giua-1 có nghĩa là thu hẹp phạm vi tìm kiếm. Cho nên hoặc ta tìm được số cần tìm (nếu có) và kết thúc hoặc kết thúc khi Dau>Cuoi.

tính xác định : thứ tự thực hiện các bước trong thuật toán mặc định là tuần tự nên sau bước 1 là bước 2, bước 3, bước 4. Kết quả so sánh ở bước 4 và bước 5 đều xác định duy nhất bước tiếp theo cần thực hiện. Sau bước 6 là bước 7. Kết quả so sánh ở bước 7 xác định duy nhất bước tiếp theo cần thực hiện. Sau bước là 8 là quay lại bước 3

tính đúng đắn : vì dãy số đã được sắp xếp tăng dần, trong mỗi lần duyệt thuật toán xác định các giá trị Dau, Cuoi, Giua của dãy cần duyệt. Sau đó so sánh giá trị k với Giua, nếu Giua = k thì kết thúc, ngược lại thu hẹp phạm vi tìm kiếm bằng cách tăng giá trị Dau hoặc giảm giá trị Cuoi và lập lại quá trình duyệt cho đến khi tìm được k = Giua hoặc Dau>Cuoi (không có số k) thì kết thúc.
KẾT THÚC
?????