Trắc nghiệm: Tiêu chuẩn lựa chọn thuật toán
A. Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép
B. Độ phức tạp của thuật toán
C. Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…
D. Cả 3 ý trên đều đúng
Đáp án đúng D. Cả 3 ý trên đều đúng
Giải thích :
Khi lựa chọn thuật toán để giải một bài toán cụ thể cần căn cứ vào các tiêu chí sau:
+ Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép
+ Độ phức tạp của thuật toán
+ Các tài nguyên như thời gian thực hiện, số lượng ô nhớ…
Tìm hiểu về thuật toán để hiểu rõ hơn về câu hỏi trên cùng THPT Đông Thụy Anh nhé!
1. Cách giải quyết một bài toán liên quan đến thuật toán
Có thể tóm tắt các bước để giải một bài toán liên quan đến thuật toán như sau:
– Tìm hiểu kỹ về yêu cầu
– Tìm ra cách giải
– Phân ra từng bước thực hiện
– Biểu diễn
a. Tìm hiểu kỹ về yêu cầu
Đây làm bước đọc đề, bạn cần đọc kỹ để nắm bắt được yêu cầu và đảm bảo hiểu được yêu cầu.
b. Tìm ra cách giải
Bước này khó nhất, tùy thuật vào kỹ năng tư duy và kinh nghiệm của bạn. Phần lớn phụ thuộc nhiều và khả năng làm toán của bạn. Tuy nhiên, nếu bạn chịu khó đọc kỹ các bài toán liên quan hoặc lập trình nhiều kỹ năng này cũng tăng lên.
c. Phân ra từng bước thực hiện
Lập trình là quá trình chia nhỏ các bước thực hiện của một thuật toán đến mức có thể viết thành các lệnh trong ngôn ngữ lập trình. Nên bạn cần chia nhỏ các bước thực hiện của thuật giải ra thành từng bước nhỏ nhất có thể biểu diễn.
d. Biểu diễn
Tùy theo nhu cầu mà bạn có thể biểu diễn thuật toán theo các hình thức đã nêu ở trên.
e. Ví dụ minh họa
Ví dụ 1: Một hình A được ghép từ một hình chữ nhật với chiều rộng 2a, chiều dài b và một hình bán nguyệt ban kính a như hình dưới đây:
Xác định bài toán:
Input: Số a là 1212chiều rộng của hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của hình chữ nhật
Output: Diện tích của hình A
Mô tả thuật toán:
Bước 1.Tính S1=2a×bS1=2a×b {Tính diện tích hình chữ nhật}
Bước 2.Tính S2=πa2/2S2=πa2/2 {Tính diện tích hình bán nguyệt}
Bước 3.Tính kết quả S=S1+S2S=S1+S2; Và kết thúc
Ví dụ 2: Viết thuật toán tính tổng 100 số tự nhiên đầu tiên
S = 0;
S1 = S + 1;
S2 = S1 + 2;
S3 = S2 + 3;
S100 = S99 + 100
Xác định bài toán:
Input: Dãy 100 số tự nhiên đầu tiên
Output: Giá trị của tổng 1 + 2 + … + 100
Mô tả thuật toán:
Bước 1.SUM ← 0; i ← 0
Bước 2.i ← i + 1
Bước 3.Nếu i ≤ 100, thì SUM ← SUM + 1 và quay lại Bước 2
Bước 4.Thông báo kết quả và kết thúc thuật toán
Mô phỏng thuật toán với số liệu cụ thể:
| Bước | 1 | 2 | 3 | 4 | 5 | 6 |
| i | 1 | 2 | 3 | 4 | 5 | 6 |
| i≤Ni≤N | Đ | Đ | Đ | Đ | Đ | S |
| SUM | 1 | 3 | 6 | 10 | 15 | Kết thúc |
Với N=5:
Ví dụ 3: Đổi giá trị của hai biến x, y
Xác định bài toán:
Input: Hai biến x, y có giá tri tương ứng là a và b
Output: Hai biến x, y có giá trị tương ứng là b và a
Mô tả thuật toán:
Bước 1.z←az←a {Sau bước này giá trị của z sẽ bằng a}
Bước 2.x←yx←y {Sau bước này giá trị của x sẽ bằng b}
Bước 3.y←zy←z {Sau bước này giá trị của y sẽ bằng giá trị của z, chính là a, giá trị ban đầu của biến x}
Ví dụ 4: Cho hai số thực a, b. Hãy cho biết kết quả so sánh hai số đó dưới dạng “a lớn hơn b”, “a nhỏ hơn b” hoặc “a bằng b”
Xác định bài toán:
Input: hai số thực a và b
Output: kết quả so sánh
Mô tả thuật toán:
Bước 1.Nếu a >b, kết quả là “a lớn hơn b” và chuyển đến Bước 3
Bước 2. Nếu a < b, kết quả là “a nhỏ hơn b”; ngược lại, kết quả là “a bằng b”
Bước 3. Kết thúc thuật toán
2. Khái niệm thuật toán
a. Khái niệm
Thuật toán/Thuật giải/Giải thuật/Algorithm nói chung đó là cách giải một bài toán bằng chương trình máy tính. Kỹ năng về thuật toán là nền tảng trong lập trình nên các lập trình viên phải nắm vững phần này thì mới làm việc tốt được.
Ví dụ: Để giải một phương trình bật nhất ax+b =0. Cần các bước:
Khai báo các biến a, b và x
Nhập hai tham số a và b
Kiểm tra a:
Nếu a =0
Kiểm tra b
Nếu b= 0 thì in ra phương trình có vô số nghiệm
Nếu b0 thì in ra phương trình vô nghiệm
Nếu a0
In ra phương trình có một nghiệm x=-b/a
Cái trên gọi là thuật toán để giải phương trình bậc nhất ax+b=0
b. Cách biểu diễn thuật toán
Có 2 cách để biểu diễn thuật toán:
Cách dùng phương pháp liệt kê: Nêu ra tuần tự các thao tác cần tiến hành
Ví dụ: Cho bài toán Tìm nghiệm của phương trình bậc 2: ax + bx + c = 0 (a≠0)?
Xác định bài toán
Input: Các số thực a, b, c
Output: Các số thực x thỏa mãn ax + bx + c = 0 (a≠0)
Thuật toán:
Bước 1: Nhập a, b, c (a≠0)
Bước 2: Tính Δ = b – 4ac
Bước 3: Nếu Δ>0 thì phương trình có 2 nghiệm là ; rồi kết thúc
Bước 4: Nếu Δ = 0 thì phương trình có nghiệm kép rồi kết thúc thuật toán. Nếu không chuyển sang bước tiếp theo
Bước 5: Kết luận phương trình vô nghiệm rồi kết thúc
– Cách dùng sơ đồ khối
Hình thoi : thể hiện thao tác so sánh;
Hình chữ nhật : thể hiện các phép tính toán;
Hình ô van : thể hiện thao tác nhập, xuất dữ liệu;
Các mũi tên : qui định trình tự thực hiện các thao tác.
3. Khái niệm bài toán
a. Khái niệm
Bài toán là một việc nào đó mà con người muốn máy tính thực hiện
Các yếu tố của một bài toán:
Input: Thông tin đã biết, thông tin đưa vào máy tính
Output: Thông tin cần tìm, thông tin lấy ra từ máy tính
b. Ví dụ
Tìm USCLN của 2 số nguyên dương
Tìm số lớn nhất trong 3 số nguyên dương a,b,c
Tìm nghiệm của phương trình bậc nhất: ax + b = 0 (a≠0)
Tác giả: Trường THPT Đông Thụy Anh
Chuyên mục: Giáo Dục
