Bai 4. bai toan va thuât toán

BÀI TOÁN VÀ THUẬT TOÁN
(tiết 10,11 ppct)
Ngày soạn:..../....; ngày dạy:..../...../.....

I. MỤC TIÊU
1. Kiến thức
Biết khái niệm bài toán và thuật toán.
Hiểu cách biểu diễn thuật toán bằng liệt kê các bước.
Hiểu một số thuật toán thông dụng.
2. Kĩ năng
Xác định được Input và Output của một bài toán.
Biết xây dựng thuật toán của một số bài toán thông dụng.
thái độ
Luyện khả năng tư duy lôgic khi giải quyết một vấn đề nào đó.
II. ĐỒ DÙNG DẠY HỌC
1. Chuẩn bị của giáo viên
Sách giáo khoa, sách giáo viên, giáo án.
2. Chuẩn bị của học sinh
Sách giáo khoa, vở ghi bài.
III. HOẠT ĐỘNG DẠY-HỌC
1. Hoạt động 1: Hình thành khái niệm bài toán.
HOẠT ĐỘNG CỦA GIÁO VIÊN
HOẠT ĐỘNG CỦA HỌC SINH

Giáo Viên đặt vấn đề: Trong toán học, để giải một bài toán, trước tiên ta quan tâm đến giả thiết và kết luận của bài toán. Vậy khái niệm "bài toán" trong tin học có gì khác không. Vậy bài toán trong tin học là gì?

Tương tự bài toán trong toán học, đối với bài toán tin học, trước tiên ta cần quan tâm đến các yếu tố nào?
Cho các nhóm tìm Input, Output của các bài toán.
VD 1: Tìm UCLN của 2 số M, N.
VD 2: Tìm nghiệm của pt
ax2 + bx + c = 0 ( a ≠ 0)

VD3: Kiểm tra số nguyên dương n có phải là một số nguyên tố không?

VD 4: Xếp lạo học tập của một lớp.
Suy nghĩ và trả lời:

Trong tin học, bài toán là một việc mà ta muốn máy tính thực hiện.



Các nhóm thảo luận, trả lời:
+ Input.
+ output.
Các nhóm thảo luận, trả lời:
Input: 2 số nguyên dương M, N.
Output: Ước chung lớn nhất của M, N.
Input: Các số thực a, b, c (a≠0).
Output: Các nghiệm của pt (có thể không có)
Input: Số nguyên dương n.
Output: "n là số nguyên tố" hoặc "n không là số nguyên tố"
Input: Bảng điểm của HS trong lớp.
Output:Bảng xếp loại học lực.


2. Hoạt động 1: Hình thành khái niệm thuật toán.
HOẠT ĐỘNG CỦA GIÁO VIÊN
HOẠT ĐỘNG CỦA HỌC SINH

Trong toán học, việc giải một bài toán theo qui trình nào?
- Trong tin học, để giải một bài toán, ta phải chỉ ra một dãy các thao tác nào đó để từ Input tìm ra được Output. Dãy thao tác đó gọi là thuật toán.
Giáo viên: Cho các nhóm thảo luận tìm hiểu khái niệm thuật toán là gì?

Suy nghĩ và trả lời:






Các nhóm thảo luận và đưa ra câu trả lời:
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.


3. Hoạt động 3: Hướng dẫn tìm thuật toán giải bài toán: "Tìm GTLN của một dãy số nguyên".
HOẠT ĐỘNG CỦA GIÁO VIÊN
HOẠT ĐỘNG CỦA HỌC SINH

Bài toán: Tìm giá trị lớn nhất của một dãy số nguyên cho trước.
Giáo viên: Hãy xác định Input và Output của bài toán?



Hướng dẫn học sinh tìm thuật toán (có thể lấy ví dụ thực tế để minh hoạ: tìm quả cam lớn nhất trong N quả cam)




- Giáo viên giải thích các kí hiệu.
Thuật toán: Bằng phương pháp liệt kê.
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 và kết thúc.
Bước 4: Nếu ai > max
thì Max ( ai
Bước 5: i ( i+1, quay lại Bước 3.



Suy nghĩ và trả lời:
Input: – số nguyên dương N.
– N số a1, a2, …, aN.
Output: giá trị Max.

Các nhóm thảo luận và trình bày ý 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.



4. Hoạt động 4: Mô