Cho dãy A gồm N số nguyên dương. Cần biết trong dãy có hay không có số chẵn? Nếu có hãy cho biết số chẵn lớn nhất trong dãy?
Ví dụ 1: Cho N = 5 và dãy A gồm: 3, 2, 6, 9, 12, 5.
Số chẵn lớn nhất là 12.
Ví dụ 2: Cho N = 7 và dãy A gồm: 1, 3, 5, 7, 9, 11, 13.
Dãy không có chứa số chẵn.
Ví dụ 3: Cho N = 1000.
Dãy A gồm các giá trị trong tập tin Baitap.txt
BÀI 6: GIẢI BÀI TOÁN TRÊN MÁY TÍNH
CÁC BƯỚC GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Bước 2: Lựa chọn hoặc thiết kế thuật toán.
Bước 1: Xác định bài 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
Mỗi bài toán được đặc tả bởi hai yếu tố: Input & Output
==> Xác định bài toán là công việc xác định chính xác Input, Output, mối quan hệ giữa chúng và xác định các thông số liên quan khác.
VD1: Xác định bài toán: Giải phương trình bậc nhất: ax + b=0 (1)
+ Input: các số thực a, b;
+ Output: giá trị x thỏa mãn phương trình (1);
1. Xác định bài toán
VD2: Xác định bài toán: Tính điểm trung bình cả năm của một lớp học:
+ Input: Danh sách học sinh, điểm của 10 môn học;
+ Output: Danh sách học sinh điểm trung bình cả năm của 10 môn học và điểm trung bình chung cả năm.
==> Như vậy việc xác định bài toán chính xác quyết định đến việc giải bài toán đó thành công hoặc không thành công.
Cho dãy A gồm N số nguyên dương. Cần biết trong dãy có hay không có số chẵn? Nếu có hãy cho biết số chẵn lớn nhất trong dãy?
Input: Số nguyên dương N và dãy A gồm N số
nguyên dương a1,a2,…,an.
Output: Số chẵn lớn nhất của dãy A
hoặc thông báo “dãy không có số chẵn”.
2. Lựa chọn hoặc thiết kế thuật toán
a. Lựa chọn thuật toán
- Mỗi bài toán có nhiều thuật toán khác nhau ngược lại mỗi thuật toán chỉ để giải quyết cho một bài toán.
- Cần phải thiết kế, lựa chọn thuật toán sao cho phù hợp nhất với từng yêu cầu của mỗi bài toán cụ thể.
2. Lựa chọn hoặc thiết kế thuật toán
a. Lựa chọn thuật toán
VD: Bài toán tìm kiếm.
+ Một số điểm lưu ý khi thiết kế hoặc lựa chọn thuật toán.
Yêu cầu về tài nguyên (thời gian thực hiện, bộ nhớ...)
Độ phức tạp của thuật toán.
== > Tiêu chí quan trọng nhất của lựa chọn, thiết kế thuật toán là tính hiệu quả.
2. Lựa chọn hoặc thiết kế thuật toán
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
- Cần chọn những cách diễn tả thuật toán phù hợp và đáp ứng được số đông người lập trình.
+ Biểu diễn thuật toán bằng liệt kê các bước:
+ Biểu diễn thuật toán bằng sơ đồ khối:
== > Để mô phỏng cách chạy của bài toán, để chạy thử trước khi viết chương trình, để cung cấp tài liệu cho người lập trình, người học.
2. Lựa chọn hoặc thiết kế thuật toán
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
VD: Bài toán giải phương trình bậc nhất: ax+b=0
Cách liệt kê:
Bước 1: Nhập giá trị a, b;
Bước 2: Nếu a=0, b≠0 thì thông báo vô nghiệm, rồi kết thúc;
Bước 3: Nếu a=0 và b=0 thì thông báo phương trình nghiệm đúng với mọi giá trị rồi kết thúc;
Bước 4: Nếu a ≠0 thì x-b/a, thông báo phương trình có nghiệm duy nhất là x rồi kết thúc.
2. Lựa chọn hoặc thiết kế thuật toán
a. Lựa chọn thuật toán
b. Diễn tả thuật toán
Thuật toán bài toán tìm số chẵn lớn nhất trong dãy số.
3. Viết chương trình
? S? d?ng ngụn ng? l?p trỡnh d? di?n d?t dỳng thu?t toỏn.
Là tổng hợp giữa việc:
 Lựa chọn cách tổ chức dữ liệu.
4. Hiệu chỉnh(sửa chữa chương trình)
Tại sao cần phải hiệu chỉnh
chương trình?
Sau khi viết chương trình có thể gặp một số lỗi sau:
Lỗi về mặt cú pháp
Lỗi về mặt logic(thuật toán chưa chính xác, chưa quét hết các trường hợp đặc biệt…)
==> Do vậy cần kiểm tra lại và test các bộ test đặc biệt của bài toán
==> Quá trình test và sửa lỗi bài toán được gọi là hiệu chỉnh (Maintenance).
VD:
5. Viết tài liệu
Viết tài liệu là làm
những công việc gì?
Tài liệu môt tả bài toán.
Tài liệu mô tả thuật toán.
Tài liệu thiết kế chương trình.
Các kết quả thử nghiệm.
Tài liệu hướng dẫn sử dụng hướng dẫn sử dụng.
Mục đích viết tài liệu là gì?
==>Thể hiện tính chuyên nghiệp của sản phẩm.
BÀI TẬP VẬN DỤNG
Bài 1: Tiêu chuẩn lựa chọn thuật toán là gì ?
a. Thuật toán phải phù hợp với bài toán đã cho.
b. Thời gian thực hiện nhanh, ít tốn bộ nhớ.
c. Khi viết chương trình ít phức tạp nhất.
d. Cả 3 ý trên đều đúng.
d
BÀI TẬP VẬN DỤNG
Bài 2: Nội dung và mục đích của bước hiệu chỉnh?
a. Kiểm tra lỗi về thuật toán.
b. Kiểm tra lỗi cú pháp của ngôn ngữ lập trình dùng viết chương trình.
c. Dùng các bộ Test khác nhau để kiểm tra.
d. Cả 3 ý trên đều đúng.
d
CỦNG CỐ
Bước 2: Lựa chọn hoặc thiết kế thuật toán.
Bước 1: Xác định bài 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.
Giải bài toán trên máy tính
gồm bao nhiêu bước?
Chi tiết các bước?
Bước 2: Lựa chọn hoặc thiết kế thuật toán.
Trong năm bước trên
bước nào là bước
quan trọng nhất
BÀI TẬP VỀ NHÀ
Hãy viết thuật toán giải phương trình bậc hai ax2 + bx +c = 0 và đề xuất các bộ Test tiêu biểu?