Kiểm tra bài cũ
Câu 1: Em cho biết có mấy loại ngôn ngữ lập trình? Em hiểu ngôn ngữ máy là gì?
Trả lời câu 1:
- Có 3 loại ngôn ngữ lập trình chính đó là: ngôn ngữ máy, hợp ngữ, ngôn ngữ bậc cao.
- Ngôn ngữ máy là ngôn ngữ duy nhất mà máy tính có thể trực tiếp hiểu được và thực hiện.
Câu 2: Em hiểu ngôn ngữ bậc cao là gì:
Là ngôn ngữ gần với ngôn ngữ tự nhiên, có tính độc lập cao, ít phụ thuộc vào loại máy. Được nhiều người sử dụng.
giải bài toán trên máy tính

1) xác định bài toán.
* Bài toán: Tìm nghiệm thực của phương trình bậc hai: ax2 + bx + c = 0
- Input: Các hệ số a, b, c nhập từ bàn phím.
- Output: Đưa ramàn hình các nghiệm thực hoặc đưa ra thông báo:
Phương trình vô nghiệm.
- Các thao tác đi từ Input đến Output:
Trước tiên tính ? = b2 - 4ac.
Sau đó xét các trường hợp của ? để đưa ra nghiệm thực
hoặc đưa ra câu thông báo: Phương trình vô nghiệm.
* Cách thức để xác định một bài toán:
- Phát biểu lại btoán một cách chính xác theo ngôn ngữ của riêng mình.
- Xác định các thông tin Input và Output, nếu có thể được thì xác định
luôn các thao tác được phép sử dụng để đi từ Input đến Output.











giải bài toán trên máy tính
Hãy chỉ ra Input, Output trong bài toán trên ? Cho biết các thao tác đi từ Input đến Output ?
Xác định bài toán ta cần xác định cài gì?
Xác định phần INPUT và OUTPUT của bài toán. Từ đó xác định ngôn ngữ lập trình và tổ chức dữ liệu một cách thích hợp


giải bài toán trên máy tính
a) Lựa chọn thuật toán:
Bài toán: Tìm UCLN của hai số nguyên dương a và b
- Input: Hai số nguyên dương a, b.
- Output: UCLN của chúng.
* Thuật toán liệt kê 1
- Bước 1: Nhập a, b.
- Bước 2: Nếu a = b thì lấy giá trị chung này làm UCLN, chuyển B5.
- Bước 3: Nếu a > b thì thay a bằng a - b , quay lại B2.
- Bước 4: Thay b bằng b - a , quay lại B2.
- Bước 5: Đưa ra kết quả UCLN ; Kết thúc.
giải bài toán trên máy tính
a) Lựa chọn thuật toán:
Bài toán: Tìm UCLN của hai số nguyên dương a và b
* Thuật toán liệt kê 2
- Bước 1: Nhập a, b.
- Bước 2: Lấy số dư r của a chia cho b.
- Bước 3: Kiểm tra điều kiện r = 0 đúng, chuyển bước 5.
- Bước 4: Lấy b gán cho a, lấy r gán cho b, chuyển bước 5.
- Bước 5: Thông báo đáp số là b ; Kết thúc.
Ngoài thuật giải trên em hãy xây dựng một thuật giải khác cho bài toán ?
Với bộ dữ liệu vào a = 17 ; b = 13. Ta có thể mô phỏng việc thực hiện hai thuật giải trên như sau:
* Thuật giải 1:









* Thuật giải 2:














a = 17
b = 13
Lần duyệt 1
a ? a - b
a = 4
b = 13
a = 4
b = 9
L. duyệt 2
b ? b - a
L. duyệt 3
b ? b - a
a = 4
b = 5
a = 4
b = 1
L. duyệt 5
a ? a - b
a = 3
b = 1
a = 2
b = 1
L. duyệt 6
a ? a - b
L. duyệt 7
a ? a - b
a = 1
b = 1
L. duyệt 4
b ? b - a
a = 17

b = 13

L. duyệt 1
r = 4 ? 0
a = 13

b = 4

L. duyệt 2
r = 1 ? 0
a = 4

b = 1

L. duyệt 3
r = 0
ƯCLN = 1

2) lựa chọn và xây dựng thuật toán.
Kết luận:











giải bài toán trên máy tính
* Các em về nhà xem 2 ví dụ đã giải ở bài 5 để minh hoạ thêm:
+ Ví dụ 1: Thuật toán tìm kiếm tuần tự.
+ Ví dụ 2: Thuật toán tìm kiếm nhị phân:

* Mỗi thuật toán chỉ giải 1 bài toán, nhưng một bài toán có thể có nhiều thuật toán để giải. Vậy ta phải chọn thuật toán tối ưu nhất trong những thuật toán đưa ra.
* Thuật toán tối ưu: là thuật toán có các tiêu chí sau:
+ Dễ hiểu, Trình bày dễ nhìn, Thời gian chạy nhanh, tốn ít bộ nhớ.
* Bước lựa chọn và xây dựng thuật toán bước quan trọng nhất để giải một bài toán.
2) lựa chọn và xây dựng thuật toán.
b) Diễn tả thuật toán:
Có thể diễn tả thuật toán bằng hai cách:
- Dùng ngôn ngữ liệt kê từng bước.
- Dùng sơ đồ khối.
* Ví dụ 1: Biểu diễn thuật toán: Tìm nghiệm của PT bậc nhất: ax + b = 0
- Dùng ngôn ngữ liệt kê từng bước:
Bước 1: Nhập giá trị a, b.
Bước 2: Nếu a = 0, b ? 0 thì thông báo PT vô nghiệm, kết thúc.
Bước 3: Nếu a = 0, b = 0, thông báo PT có vô số nghiệm, kết thúc.
Bước 4: Nếu a ? 0, thông báo PT có nghiệm là -b/a, kết thúc.











giải bài toán trên máy tính
2) lựa chọn và xây dựng thuật toán.
b) Diễn tả thuật toán:
* Ví dụ 1: Biểu diễn thuật toán: Tìm nghiệm của PT bậc nhất: ax + b = 0
- Dùng sơ đồ khối:

















giải bài toán trên máy tính
Hãy chuyển thuật toán trên từ dạng liệt kê từng bước sang sơ đồ khối ?
2) lựa chọn và xây dựng thuật toán.
b) Diễn tả thuật toán:











giải bài toán trên máy tính
Xét bài toán giải phương trình bậc hai
ax2 + bx + c = 0 (a ? 0).
Ví dụ 2:
Em h·y x¸c ®inh:
+ Input:
+ Output:
Cña bµi to¸n
+ Input:

+ Output:
C¸c hÖ sè a,b,c (a  0)
Nghiệm của phương trình
B6: Kết thúc.
B1: Nhập a, b, c;
B2: Tính ? = b2 - 4ac;
B3: Nếu ? < 0 => PT vô nghiệm => KT;
B4: Nếu ? = 0
=> PT có nghiệm kép x = -b/2a => KT;
B5: Nếu ? > 0
=> PT có hai nghiệm x1, x2 = (-b ? ??)/2a
=> KT;
Thuật toán giải phương trình bậc hai
ax2 + bx + c = 0 (a ? 0).
Ví dụ 2:
Đây là thuật toán của bài toán theo kiểu liệt kê từng bước
đ
s
Sơ đồ thuật toán giải phương trình bậc hai
2
B1
B2
B3
B4
B5
s
đ
B6
3) viết chương trình.
- Viết chương trình là dùng một ngôn ngữ máy tính cụ thể nào đó để diễn tả thuật toán, cấu trúc dữ liệu thành các câu lệnh để máy tính có thể thực hiện được và giải quyết đúng bài toán mà người lập trình mong muốn.
- Ngôn ngữ máy tính để viết chương trình là một ngôn ngữ bậc cao hoặc hợp ngữ, hoặc ngôn ngữ máy hoặc một phần mềm chuyên dụng thích hợp cho thuật toán đã lựa chọn.
- Viết chương trình trong ngôn ngữ nào ta cần phải tuân theo đúng quy định ngữ pháp của ngôn ngữ đó.











giải bài toán trên máy tính
4) Hiệu chỉnh.
Sau khi được viết xong, chương trình vẫn còn có thể có nhiều lỗi khác chưa phát hiện được nên có thể không cho kết quả đúng. Vì vậy, cần phải thử chương trình bằng cách thực hiện nó với một bộ Input tiêu biểu. Các bộ Input này gọi là các Test. Nếu có sai sót ta phải chỉnh sửa chương trình rồi thử lại, quá trình này được gọi là hiệu chỉnh.
* Ví dụ: Để 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 có thể sử dụng 3 bộ Input như sau:
- ? > 0 : a = 1, b = -5, c = 6 (chương trình đưa ra hai nghiệm)
- ? = 0 : a = 1, b = -4, c = 4 (chương trình đưa ra một nghiệm)
- ? < 0 : a = 1, b = 4, c = 8 (chương trình thông báo PT vô nghiệm)











giải bài toán trên máy tính
a,b,c= 1 3 5
D = 3*3 - 4*5 = - 11
-11 < 0
PT vô nghiệm

KT
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phương trình bậc hai
Bộ TEST 1:
a,b,c= 1 -5 6
D = 25 - 24 = 1
PT vô nghiệm

PT có nghiệm x=-b/2a
KT
S
PT có 2 nghiệm
x1, x2 = (-b ??? )/2a
Đ
S
D = b*b - 4*a*c
nhËp vµo a,b,c
 < 0
Mô phỏng thuật toán giải phương trình bậc hai
Bộ TEST 2:
Đ
 = 0
PT có nghiệm x1 = 3
x2 = 2
5) vIếT TàI LIệU.
Viết tài liệu là mô tả lại chi tiết toàn bộ bài toán, thuật toán, chương trình, kết quả thử nghiệm và hướng dẫn sử dụng. Tài liệu này rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm.











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 các em phải nhớ các bước sau:
Bước 1: Xác định bài toán: xác định Input, Output và quan hệ của giữa chúng.
Bước 2: Lựa chọn và xây dựng thuật toán: Lựa chọn thuật toán và tổ chức dữ liệu.
Bước 3: Viết chương trình: Chọn ngôn ngữ phù hợp với thuật toán và tổ chức dữ liệu.
Bước 4. Hiệu chỉnh: Kiểm tra để phát hiện lỗi.
Bước 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.
Câu 1:
Bài toán: "Nhập từ bàn phím ba số nguyên dương a, b, c. Kiểm tra xem 3 số này có thể là 3 cạnh của một tam giác hay không ? "
a) Hãy chỉ ra Input và Output của bài toán.
b) Đề xuất các Test tiêu biểu để kiểm thử chương trình giải bài toán trên.
Củng cố
Input: 3 số nguyên dương a, b, c
Output: a, b, c có phải là 3 cạnh của một tam giác không.
Cho chương trình chạy với một số bộ dữ liệu kiểm thử sau:
- Ba số a, b, c có một số không phải là số nguyên dương.
- Ba số a, b, c mà một trong ba đẳng thức sau bị vi phạm:
a + b > c, a + c > b, b + c > a
A. Số - 5

C. Số nguyên lớn
bất kỳ
D. Một vài hợp số

Câu 2:
Giả sử có chương trình kiểm tra tính nguyên tố của một số nguyên dương nhập từ bàn phím. Em hãy cho biết không nên chọn những giá trị nào trong các phương án dưới đây để làm dữ liệu kiểm thử chương trình ?

B. Số 3

Hoan hô
bạn trả lời đúng
Củng cố
bài tập về nhà
Bài 1:
Hãy chỉ ra Input và Output của các bài toán dưới đây:
a) Năm nhuận là năm chia hết cho 400 hoặc không tròn năm nhưng chia hết cho 4. Hãy cho biết có bao nhiêu năm nhuận trong khoảng thời gian từ năm 1 đến năm 2000.
b) Cho số nguyên dương N và N số nguyên dương. Tìm số trong dãy có tổng các ước số lớn nhất.
Ví dụ : N = 5 , dãy số là : 12 , 10 , 15 , 8 , 14 . Trả lời là 12.
Bài 2:
Có một chương trình giải bài toán: Tìm nghiệm PT bậc nhất ax + b = 0. Em hãy nêu một vài bộ dữ liệu kiểm thử để kiểm định tính đúng đắn của chương trình đó.