Home Home » lop10lythuyet » Lớp 10 - BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN

Lớp 10 - BÀI 4: BÀI TOÁN VÀ THUẬT TOÁN

Friday, August 16, 2013

Mức độ cần đạt

Kiến thức
  • Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán.
  • Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng liệt kê các bước.
  • Hiểu một số thuật toán thông dụng.
Kĩ năng
  • Xây dựng được thuật toán giải một số bài toán đơn giản bằng sơ đồ khối hoặc liệt kê các bước.
1. Khái niệm bài toán:
  • Trong phạm vi Tin học, ta có thể quan niệm bài toán là việc nào đó ta muốn máy tính thực hiện.
  • Các yếu tố xác định một bài toán:
+ Input (thông tin đưa vào máy): dữ liệu vào
+ Output (thông tin muốn lấy ra từ máy): dữ liệu ra
Ví dụ 1. Bài toán tìm ước chung lớn nhất của hai số nguyên dương.
Input: Hai số nguyên dương M và N;
Output: Ước chung lớn nhất của M và N.
Ví dụ 2. Bài toán tìm nghiệm của phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0)
Input: Các số thực a, b, c (a ≠ 0);
Output: Số thực x thoả mãn ax2 + bx + c = 0.
Ví dụ 3. Bài toán kiểm tra tính nguyên tố.
Input: Số nguyên dương N;
Output: "N là số nguyên tố" hoặc "N không là số nguyên tố".
Ví dụ 4. Bài toán xếp loại học tập của một lớp.
Input: Bảng điểm của học sinh trong lớp;
Output: Bảng xếp loại học lực.
2. Khái niệm thuật toán:
Al-KhwarizmiAl-Khwarizmi
  • Việc cho một bài toán là mô tả rõ Input và Output cần tìm. Vấn đề là: Làm thế nào để tìm ra Output?
  • Trước hết cần lưu ý rằng trong Toán học có một xu hướng nghiên cứu định tính các bài toán, có nghĩa là người ta có thể chỉ cần chứng minh sự tồn tại của lời giải và không cần chỉ ra một cách tường minh cách tìm lời giải đó.
  • Việc chỉ ra tường minh một cách tìm Output của bài toán được gọi là một thuật toán (algorithm) của bài toán đó. Có nhiều định nghĩa khác nhau về thuật toán, dưới đây là một định nghĩa thường dùng
  • Al-Khwarizmi, nhà toán học thế kỉ thứ IX - người có ảnh hưởng lớn đến sự hình thành thuật ngữ "Algorithm"
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 sắp xếp theo một trình tự xác định sao cho sau 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.
  • Có 2 cách diễn tả thuật toán: Liệt kê và  Sơ đồ khối:
 Liệt kêSơ đồ khối 
Ghi lại các thao tác thực hiện theo dạng
Bước 1: ...
Bước 2 ...
...
...
Bước: ...
Vẽ hình gồm: hình thoi, hình chữ nhật, hình ô van, mũi tên
Hình thoi hinhthoi thể hiện thao tác so sánh;
Hình chữ nhật hinhcn thể hiện các phép tính toán;
Các mũi tên → quy định trình tự thực hiện các thao tác;
Hình ô van ovan thể hiện thao tác nhập, xuất dữ liệu.
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 N 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ị Max = 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ị Max, nếu ai > Max thì Max nhận giá trị mới là ai.
 Liệt kêSơ đồ khối 
Bước 1. Nhập N và dãy a1,..., aN;


Bước 2. Max ← a1, i ← 2;

Bước 3. Nếu i > N thì đưa ra giá trị Max rồi 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ước 3;
sodokhoi
  • Thực hiện thuật toán trên với N = 11 và dãy A: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12.
Dãy A5147631584912
i23456789101112
Max5557771515151515

Thuật toán có các tính chất chính sau

  • 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ực 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ực 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.
Các ví dụ khác xem SGK trang từ trang 36 đến 44

CÂU HỎI VÀ BÀI TẬP 
  1. Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.
  2. Hãy phát biểu một bài toán và chỉ rõ Input và Output của bài toán đó.
Dãy các thao tác sau:
Bước 1. Xoá bảng;
Bước 2. Vẽ đường tròn;
Bước 3. Quay lại bước 1;
có phải là thuật toán không? Tại sao?
Hãy mô tả thuật toán giải các bài toán sau bằng cách liệt kê hoặc bằng sơ đồ khối.
  1. Cho N và dãy số a1,..., aN, hãy tìm giá trị nhỏ nhất (Min) của dãy đó.
  2. Tìm nghiệm của phương trình bậc hai tổng quát: ax2 + bx + c = 0.
  3. Cho N và dãy số a1,..., aN, hãy sắp xếp dãy số đó thành dãy số không tăng (số hạng trước lớn hơn hay bằng số hạng sau).
  4. Cho N và dãy số a1,..., aN, hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0.
Chia sẻ bài viết
Bài liên quan

Comments[ 0 ]


Post a Comment