Bài 5. Từ bài toán đến chương trình

15/11/2010
Design: Nguyễn Viết Diệu
1
NGUYEN VIET XUAN SCHOOL
GVGD: Nguyễn Viết Diệu
PHÒNG GD –ĐT KRÔNG BÔNG
15/11/2010
Design: Nguyễn Viết Diệu
2
Câu 2: Viết chương trình in ra màn hình chu vi và diện tích hình vuông.
Công thức tính chu vi và diện tích hình vuông ?
S = a x a;
P = a x 4
KI?M TRA
Open Turbo Pascal
Câu 1: Nêu khái niệm viết chương trình là gì ?
15/11/2010
Design: Nguyễn Viết Diệu
3
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
* BÀI TOÁN VÀ CHƯƠNG TRÌNH
Bài toán 1: Tính tổng hai số nguyên a và b được nhập vào từ bàn phím.
Lập trình
Mô tả
Var a,b,.. : kiểu dữ liệu
Readln(a,b,c..)
Tên biến:=Biểu thức
Writeln(“Xâu kí tự”,a,b,c,..)
15/11/2010
Design: Nguyễn Viết Diệu
4
Bài toán 2:
Tính giá trị của biểu thức P=(a*b-c)/d với a, b, c, d là các số thực tùy ý.
Tính biểu thức;
Bắt đầu
- Nhập giá trị cho a, b, c, d;
- Tính tích a*b nhớ kết quả vào P1;
- Tính hiệu P1 – c và nhớ kết quả vào P2;
- Tính thương P2/d và nhớ kết quả vào P
- In giá trị của P ra màn hình;
Kết thúc.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Mô tả
Lập trình
15/11/2010
Design: Nguyễn Viết Diệu
5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
a:=4
b:=5
c:=3
d:=2
4
5
3
2
20
17
8.50
2
3
5
4
6
1
0.25
1
4
3
0
4
1
Error
a:=2
b:=3
c:=5
d:=4
a:=1
b:=4
c:=3
d:=0
CHẠY BẰNG TAY
Write(‘Vay P=‘,P:8:2);
15/11/2010
Design: Nguyễn Viết Diệu
6
Bài toán là gì?
Là công việc hay một nhiệm vụ cần phải giải quyết
Để giải quyết được một bài toán cụ thể, ta cần phải xác định rõ điều gì̀?
* Xác định các điều kiện cho trước.
* Kết quả thu được
Xác định bài toán
1. Bài toán và xác định bài toán :
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
7
Bài toán là một công việc hay một nhiệm vụ cần giải quyết.
Muốn giải một bài toán trước hết phải xác định các điều kiện cho trước và kết quả cần thu được.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH

15/11/2010
Design: Nguyễn Viết Diệu
8
Ví dụ 1: Xét bài toán “Tính diện tích hình tam giác”.
Điều kiện cho trước
Kết quả cần thu được
Một cạnh và đường cao tương ứng
Diện tích hình tam giác
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
9
Ví dụ 2: Xét bài toán “Tìm đường đi tránh các điểm nghẽn giao thông”.
Điều kiện cho trước
Kết quả cần thu được
Vị trí điểm nghẽn giao thông.
Các con đường có thể đi từ vị trí hiện tại tới vị trí cần tới
Đường đi từ vị trí hiện tại tới vị trí cần tới mà không qua điểm nghẽn giao thông.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
10
Thế nào là giải bài toán trên máy tính?
* Là việc đưa cho máy tính dãy hữu hạn các thao tác đơn giản mà nó có thể thực hiện được, để từ các điều kiện cho trước ta nhận được kết quả cần tìm.
Em hiểu như thế nào là thuật toáǹ?
* Thuật toán: Là dãy hữu hạn các thao tác cần thực hiện
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
2. Quá trình giải bài toán trên máy tính


15/11/2010
Design: Nguyễn Viết Diệu
11
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Bài toán + Thuật toán = Chương trình
15/11/2010
Design: Nguyễn Viết Diệu
12
Quá trình giải bài toán trên máy tính như thế nào?
- Xác định bài toán
- Mô tả thuật toán
- Viết chương trình
Xác định thông tin đã cho (INPUT).
Tìm được thông tin cần tìm (OUTPUT)
Tìm cách giải bài toán
Diễn tả bằng các lệnh cần phải thực hiện
Dựa vào mô tả thuật toán, ta viết chương trình bằng một ngôn ngữ lập trình
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
13
- Bước 1: Xác định bài toán
+ Xác định thông tin đã cho (INPUT).
+ Tìm được thông tin cần tìm (OUTPUT)
- Bước 2: Mô tả thuật toán
+ Tìm cách giải bài toán
+ Diễn tả bằng các lệnh cần phải thực hiện
- Bước 3. Viết chương trình
Dựa vào mô tả thuật toán, ta viết chương trình bằng một ngôn ngữ lập trình


TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
* Quá trình giải bài toán trên máy tính gồm

15/11/2010
Design: Nguyễn Viết Diệu
14
VỀ NHÀ HỌC THUỘC
khái niệm bài toán là gì?
Muốn giải một bài toán phải xác định được cái gì?
Thế nào là giải bài toán trên máy tính? thuận toán là gì?
Quá trình giải bài toán trên máy tính qua mấy bước?


TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
THE END
15/11/2010
Design: Nguyễn Viết Diệu
15
Xét bài toáṇ 4 : Giải phương trình bậc nhất dạng tổng quát ax + b = 0
* Xác định bài toán
INPUT
OUTPUT
Các hệ số a và b
Nghiệm của phương trình bậc nhất
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
* Mô tả thuật toán
3. Thuật toán và mô tả thuật toán
15/11/2010
Design: Nguyễn Viết Diệu
16
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
B1: Nếu a = 0 chuyển tới B3. Ngược lại chuyển tới B2.
B2: Tính nghiệm x =-b/a và chuyển tới B4.
B3: Nếu b # 0, thông báo PT vô nghiệm. Ngược lại thông báo PT đã cho có vô số nghiệm.
B4: Kết thúc.
 Viết chương trình!!!
* Thuật toán: Là dãy hữu hạn các thao tác có trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước.
15/11/2010
Design: Nguyễn Viết Diệu
17
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 bán kính a.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
4. Một số ví dụ về thuật toán
Hình A
b
a
a
15/11/2010
Design: Nguyễn Viết Diệu
18
INPUT:
- Nhập số a là ½ chiều rộng của HCN và là bán kính của hình bán nguyệt.
- Nhập số b chiều dài của hình chữ nhật.
OUTPUT: Diện tích hình A
*Thuật toán:
+B1: S1  2ab {Tính diện tích HCN};
+B2: S2  Лa2/2 {Tính DT hình bán nguyệt};
+B3: S  S1 + S2 và kết thúc.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
19
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Ví dụ 2: Tính tổng của 100 số tự nhiên đầu tiên
liên tiếp S = 1 + 2 + 3 + 4 + ... + 100
- OUTPUT : Tổng của dãy số trên.
- INPUT: Dãy 100 số tự nhiên đầu tiên: 1, 2, ... 100.
15/11/2010
Design: Nguyễn Viết Diệu
20
NHẬN XÉT:
S = 0
S1 = S + 1
S2 = S1 + 2
S3 = S2 + 3


.....
Bắt đầu từ S1 việc tính S được lặp đi lặp lại 100 lần theo quy luật
Ssau = Strước+ i
với i tăng lần lượt từ 1 đến100
. . . . . . . . . . . . . . . . . . . .
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
21
Bước 1: S  0; i  0;
Bước 3: Nếu i <= 100 thì S  S + i và quay lại bước 2.

Bước 2: i  i + 1
THUẬT TOÁN
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Bước 4: Thông báo kết quả và kết thúc thuật toán.

15/11/2010
Design: Nguyễn Viết Diệu
22
Cốc A chứa nước màu vàng, cốc B chứa nước màu xanh. Làm cách nào để tráo đổi cốc A có nước màu xanh, cốc B có nước màu đỏ? (Giả thiết cốc A và cốc B có thể tích như nhau)
Làm cách nào đây?
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
23
Cốc A
Cốc B
Cốc C
1. Lấy một cốc C rỗng có thể tích như A và B
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
24
2. Đổ nước màu vàng ở cốc A sang cốc C
Cốc A
Cốc B
Cốc C
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
25
3. Đổ nước màu xanh ở cốc B sang cốc A
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
Cốc A
Cốc B
Cốc C
15/11/2010
Design: Nguyễn Viết Diệu
26
4. Đổ nước màu vàng ở cốc C sang cốc B
Cốc A
Cốc A
Cốc B
Cốc C
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
27
Ví dụ 3: Đổi giá trị hai biến x và y
Input: Hai biến x và y có giá trị tương ứng là a, b
Output: Hai biến x và y có giá trị tương ứng là b, a
Bước 1: z  x {Sau bước này giá trị của z sẽ bằng a}
Bước 2: x  y {Sau bước này giá trị của x sẽ bằng b}
Bước 3: y  z {Sau bước này giá trị của y sẽ bằng giá trị của z, chính là giá trị ban đầu a của biến x}
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
28
Ví dụ 4: Tìm số lớn nhất trong dãy A các số a1, a2,..., an.
INPUT: Dãy A các số a1, a2, …,an (n>=1)
OUTPUT: Giá trị MAX=max{a1, a2, …,an }.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
29
3
Người ta đặt 5 quả bóng có kích thước khác nhau trong hộp đã được đậy nắp như hình bên.Chỉ dùng tay hãy tìm ra quả bóng có kích thước lớn nhất .
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
30
Quả này lớn nhất
Quả này mới lớn nhất
ồ! Quả này lớn hơn
Tìm ra quả lớn nhất rồi!
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
31
ý tưởng:
- Đặt giá trị Max= a1
- Lần lượt cho i chạy từ 2 đến N, so sánh
giá trị ai với giá trị Max, nếu ai> Max thì
Max nhận giá trị mới là ai.
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
32
Bước 1: Max  a1 ; i  1
Bước 3: Nếu i > N, chuyển đến bước 5
THUẬT TOÁN
Bước 2: i i +1
Bước 4: Nếu ai > Max thì Max  ai rồi quay lại bước 2
trường hợp ngược lại giữ nguyên Max và quay
lại bước 2
Bước 5: Kết thúc thuật toán
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
15/11/2010
Design: Nguyễn Viết Diệu
33
Chúc các em học tốt