PHƯƠNG PHÁP DẠY HỌC
MÔN TIN HỌC
NHÓM 7 _
TIN HỌC BÌNH THẠNH
BÀI 4. B�I TỐN V� THU?T TỐN
I. BÀI TOÁN
1) Khái niệm bài toán
2) Các thành phần cơ bản của một bài toán
II. THUAÄT TOAÙN
1) Khái niệm thuật toán
2) Mô tả các thao tác trong thuật toán
III. VÍ DUÏ VEÀ THUAÄT TOAÙN
1) Thuaät toaùn : giaûi baøi toaùn theo caùch lieät keâ vaø theo sô ñoà khoái
2) Moâ phoûng vieäc thöïc hieän thuaät toaùn
3) Tính chaát cuûa thuaät toaùn




I.����Bài toán

1.���� Khái niệm bài toán
_ Học sinh gặp rất nhiều bài toán khí đến trường
Vd : bài toán vật lý, hóa học, hình học
H: Vaäy theá naøo laø 1 baøi toaùn ?
Vậy : Bài toán là một hệ thống những giả thiết ? dựa vào giả thiết đó người giải sẽ trả lời những câu hỏi theo yêu cầu
_ Có thể phân biệt hai loại bài toán sau:
Vd :1/ Giải phương trình bậc nhất : ax+b=0
2/ Viết một dòng chữ ra màn hình
H: Có nhận xét gì về 2 loại ví dụ trên ?
Kết luận : Trong phạm vi tin học, bài toán là việc nào đó mà ta muốn máy tính thực hiện.
2. Các thành phần cơ bản của một bài toán:
Bài toán thông thường
Giả thiết:


Kết luận:
Bài toán tin học�
Input:


Output:
Những thông tin được cung cấp
Những thông tin cần tìm

Người sử dụng đưa thông tin vào máy tính
Là kết quả nhận được từ máy tính
Vd 1 : Cộng 2 số a, b

Input ?

Output ?
Các số thực a, b
kết quả nhận được là c thỏa: c = a+b
Vd 2 : Tính tiền điện
Input:

Output:
Số điện sử dụng trong tháng, đơn giá
tiền cần thanh toán
II. Thuật toán

SƠ ĐỒ
Bài toán
�
�
GT (input) PP giải quyết KL (output )
Thuật toán
Caùc thao taùc, caáu truùc leänh nhaäp vaøo maùy
Máy xử lý thông tin

1) Khái niệm thuật toán:
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
S?p x?p cĩ th? t?
T? Input cho ra Output
----> Có thể nói thuật toán là một công cụ của người giải toán, một bài toán có thể có nhiều thuật toán. Nhiệm vụ của người giải bài toán là tìm ra được những thuật toán tối ưu nhất.
Vd: Có thể xem chặt cây là một bài toán. Người chặt có thể dùng cưa, dùng dao, dùng rìu để làm đổ cây.
2. Cách biểu diễn thuật toán
_ Cách 1: Liệt kê từng bước ( dùng cho người mới học vi tính)
Chỉ ra lần lượt các thao tác cần giải quyết
* Vd1 : Cộng 2 số a và b

B1 : Ta phải nhập hai số a và b
B2 : Thực hiện cộng 2 số: c= a+b
B3 : Ta thu được kết quả ( Output)
* Vd2 : Giải pt bậc nhất: ax+b = 0
B1 : Nhập a, b (Input)
B2 : Xét:
+ Nếu a # 0 thì thực hiện bước 3
+ Nếu a = 0 thì trở về bước 1

B3 : Gán giá trị x = - b/a
B4 : Nhận được kết quả X (output)
·        Nhaän xeùt
Öu ñieåm : Deã hieåu , deã thöïc hieän
Nhöôïc ñieåm: Daøi , Phuï thuoäc ngoân ngöõ ,Khoù laäp trình
Khoâng toång quan

_ Cách 2 : Dùng đoạn mã
Vd: Tính tổng: S = 1+2+..+50.
Begin
S: = 0
For n: = 1 to 50 do
S: = s+n
Writeln ( " Tong la s: " ,s );

Nhận xét:
Ưu điểm : Ngắn, Dễ lập trình
Nhược điểm : Khó hiểu
Cách 3: D�ng so d? kh?i:
C�c bi?u tu?ng trong so d? kh?i:
Hình ovan: nh?p, xu?t d? li?u.


- Hình ch? nh?t: c�c ph�p tốn


Hình thoi: thao t�c so s�nh.

C�c mui t�n : trình t? th?c hi?n c�c thao t�c.
Vd : Tổng 2 số a và b
Nhập a, b
a> 0
b >0
c =
a + b
Đưa ra giá trị c rồi kết thúc
sai
III. Ví d? v? thu?t toán
Bài toán: Tìm giá trị lớn nhất của dãy số
- Input: Số nguyên dương N và dãy 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 an , so sánh giá trị số hạng ai với giá trị Max, nếu Max < ai thì Max nhận giá trị mới là ai.

Cách 1: Giải bài toán theo cách 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 rồi kết thúc.
Bước 4:
- Nếu ai > Max thì Max = ai ;
- i = i+1 rồi quay lại bước 3;
Nhập N và dãy a1,…..aN
Cách 2 : Giải bài toán theo sơ đồ khối
Max:= a1, i=2
i<=N
Max < ai
Max =ai
i= i+ 1
Đưa ra Max, kết thúc
sai
Đúng
Đúng
sai
Dãy số 5 1 4 7 6 3 15 8 4 9
Mô phỏng việc thực hiện thuật toán trên với N=10 và dãy số 5,1,4,7,6,3,15,8,4,9.
i
Max
2
5
3
5
4
7
5
7
6
7
7
15
8
15
9
15
10
15
11
15
Tính chất của thuật toán:
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: Thuật toán kết thúc, ta phải nhận được Output cần tìm.

CỦNG CỐ và DẶN DÒ
_ Thế nào là một bai toán trong phạm vi tin học ? Input, output là gì ?
_ Hướng dẫn học sinh làm bài tập cuối bài trong sách giáo khoa.
_ Bài tập về nhà :Bài....