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

GV: Lê Phước Hòa
Tổ: Lý – Tin - Công Nghệ
Bài cũ:

C1: Nêu khái niệm về biến nhớ?
Từ khóa khai báo biến trong Pascal là gì?
1. Bài toán và xác định bài toán
Xét ví dụ về bài toán sau:
Bài toán 1: Tính diện tích của đường tròn khi biết bán kính của đường tròn đó là R.
Bài toán 2: Tính vận tốc của người đi bộ đi hết đoạn đường dài 20km thì cần mất 4 giờ?
Bài toán 3: Tìm các cách khắc phục tắc nghẽn giao thông trong giờ cao điểm tại ngã tư?
Vậy bài toán là gì?
 Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết
Lấy vài ví dụ về bài toán?
1. Bài toán và xác định bài toán
 Để giải quyết một bài toán cụ thể , ta cần xác định:
+ Điều kiện cho trước: (Input)
+Kết quả thu được: (Output)
Bài toán 1 :
Điều kiện cho trước: Bán kính của đường tròn
Kết quả thu được: Diện tích hình tròn.

Để giải quyết bài toán cụ thể ta cần xác định cái gì?
 Xác định bài toán là bước đầu tiên và là bước rất quan trọng trong việc giải bài toán.
1. Bài toán và xác định bài toán
 Kết luận
Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết.
Xác định bài toán là: xác định điều kiện cho trước và kết quả cần thu được.
 Xác định bài toán là bước đầu tiên và là bước rất quan trọng trong việc giải bài toán.
2. Giải bài toán trên máy tính
 Để máy tính có thể giải các bài toán, ta cần hướng dẫn máy tính thực hiện một dãy hữu hạn các thao tác, từ các điều kiện cho trước ta nhận được kết quả cần thu được.

Dãy hữu hạn các thao tác để giải một bài toán được gọi là thuật toán
Máy tính có thể tự giải các bài toán được hay không?
Vậy thì làm thế nào máy có thể giải được?
2. Giải bài toán trên máy tính
Các bước giải bài toán trên máy tính
 Xác định bài toán: xác định điều kiện ban đầu (input) và kết quả cần xác định (output).
 Xây dựng thuật toán: Lựa chọn và mô tả các thao tác sẽ thực.
Viết chương trình: Diễn đạt thuật toán bằng một ngôn ngữ lập trình sao cho máy tính có thể hiểu và thực hiện được.

2. Giải bài toán trên máy tính
Vận dụng: tính diện tích của hình chữ nhật có chiều dài là a chiều rộng là b.
? Xác định bài toán:
+ Xác định Input
+ Xác định Output
? Công thức tính diện tích
? Xây dựng thuật toán
? Viết chương trình
3. Mô tả thuật toán
Thuật toán pha trà mời khách
Input: Trà, nước sôi, ấm và chén
Output: Chén trà đã pha để mời khách
 Mô tả
B 1: Tráng ấm chén bằng nước sôi;
B 2: Cho một nhúm trà vào ấm;
B 3: Tráng trà;
B 4: Rót nước sôi vào ấm và đợi 3 – 4 phút;
B 5: Rót trà ra chén để mời khách



3. Mô tả thuật toán
Thuật toán giải phương trình bậc nhất tổng quát bx + c = 0
B1: Nếu b = 0 chuyển tới B3;
B2: Tính nghiệm của phương trình x = -c/b rồi chuyển tới B4;
B3: Nếu c 0 thông báo phương trình vô nghiệm, ngược lại (c = 0) thông báo phương trình vô số nghiệm.
B4: Kết thúc thuật toán.
3. Mô tả thuật toán
3. Mô tả thuật toán
Là việc liệt kê trình tự hữu hạn các bước để chỉ dẫn máy tính thực hiện và thu được kết quả.
Việc mô tả thuật toán có thể mô tả bằng ngôn ngữ tự nhiên hoặc mô tả theo sơ đồ khối.
Tuy nhiên mô tả theo sơ đồ khối sẻ trực quan hơn, dễ mô tả hơn và có tính chuyên nghiệp hơn
Mô tả thuật toán là gì?
C1: Bài toán là gì? Đề giải bài toán ta cần xác định các điều kiện gì?


C2: Để giải bài toán trên máy tính gồm mấy bước đó là những bước nào?
Bài cũ:
Bài 5
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
(T3) (t21-ppct)
4. Một số ví dụ về thuật toán
4.1 Thuật toán tính diện tích
(Bài toán) 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 như hình dưới đây:
Xác định Input và Output của bài toán
4. Một số ví dụ về thuật toán
4.1 Thuật toán tính diện tích
a. Xác định bài toán
- INPUT: Số a, b.
- OUTPUT : Diện tích của hình A.

b. Mô tả thuật toán

B1: Nhập a và b;
B2. Tính S1  2*a * b {(Tính S hình CN)};
B3. Tính S2  a*a*3.14{(S hình bán nguyệt)};
B4. Tính S  S1 + S2 và kết thúc.
Thuật toán
Tính diện tích
4. Một số ví dụ về thuật toán
C. Kiểm tra thuật toán
4. Một số ví dụ về thuật toán
4.2 Tính tổng của 100 số tự nhiên đầu tiên liên tiếp S = 1 + 2 + ... + 100

- INPUT: Dãy 100 số tự nhiên đầu tiên: 1, 2, ... 100.
- OUTPUT : Tổng của dãy số trên.
Xác định Input và Output của bài toán
Thuật toán
Tính tổng các số
4. Một số ví dụ về thuật toán
NHẬN XÉT:
S = 0
S1 = S + 1
S2 = S1 + 2
Si = Si-1 + i


.....
S100 = S99 + 100
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
. . . . . . . . . . . . . . . . . . . .
Thuật toán
Tính tổng các số
4. Một số ví dụ về thuật toán
4.2 Tính tổng của 100 số tự nhiên đầu tiên liên tiếp S = 1 + 2 + ... + 100
a. Xác định bài toán
- INPUT: Dãy số tự nhiên đầu tiên: 1, 2, ... 100.
- OUTPUT : Tổng của dãy số trên.

b. Mô tả thuật toán
Bước 1: S  0; i  0;
Bước 2: i  i + 1 ;
Bước 3: Nếu i <= 100 thì S  S + i; và quay lại bước 2. trong trường hợp ngược lại thông báo kết quả rồi kết thúc thuật toán.
Thuật toán
Tính tổng các số
4. Một số ví dụ về thuật toán
c. Kiểm tra thuật toán
4. Một số ví dụ về thuật toán
Kiểm tra thuật toán
4. Một số ví dụ về thuật toán
4.3 Thuật toán so sánh hai giá trị
Cho hai số thực a và 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”
a. Xác định bài toán
Input: Hai số thực a và b
Output: Kết quả so sánh
b. Mô tả thuật toán
Bước 1: Nhập 2 số a,b
Bước 2: So sánh a và b. Nếu a>b, cho kết quả “a lớn hơn b” và chuyển đến bước 4
Bước 3: Nếu aBước 4: Kết thúc thuật toán
Thuật toán
so sánh giá trị
Làm thế nào để biết bạn Sơn nặng hay nhẹ hơn bạn Hoàng nhỉ ?
4. Một số ví dụ về thuật toán
Bài cũ
Bài cũ
Thuật toán là gì? Có mấy cách mô tả thuật toán?
Làm thế nào để biết thuật toán vừa mô tả là đúng hay sai?
Bài 5
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
(T4) (t22-ppct)

Em hãy nêu cách tráo đổi nước ở cốc A và B ?
Cốc A
Cốc B
4. Một số ví dụ về thuật toán
Cốc A chứa nước màu đỏ, 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)
Cốc A
Cốc B
Cốc C
4. Một số ví dụ về thuật toán
Mô tả cách làm
Cốc A
Cốc B
Cốc C
4. Một số ví dụ về thuật toán
Mô tả cách làm
Nước của 2 cốc đã được hoán đổi
Cốc A
Cốc B
Cốc C
4. Một số ví dụ về thuật toán
Mô tả cách làm

Em hãy xác định Input, Output ?
INPUT
OUTPUT
Hai biến x và y có
giá trị tương ứng là a, b
Hai biến x và y có
giá trị tương ứng là b, a
a. Xác định bài toán
4. Một số ví dụ về thuật toán
4.4Thuật toán đổi giá trị của 2 biến
x
Z
x
y
Z
y
Input:
Output:
Em hãy mô tả thuật toán đổi giá trị của x và y ?
b. Mô tả thuật toán
4. Một số ví dụ về thuật toán
4.4 Thuật toán đổi giá trị của 2 biến
4. Một số ví dụ về thuật toán
4.4 Đổi giá trị của hai biến x và y
a. Xác định bài toán
Input: Nhập hai biến x và y
Output: Hai biến x và y sau khi hoán đổi:

b. Mô tả thuật toán

Bước 1: Nhập x,y
Bước 2: z  x
Bước 3: x  y
Bước 4: y  z
Thuật toán
đổi giá trị
4. Một số ví dụ về thuật toán
4. Một số ví dụ về thuật toán
Cách đây khoảng 2500 về trước có cuộc khảo sát của Weights về các thanh niên trong khoảng từ 18-22 tuổi của toàn thành phố. Và trao giải cho người có cân nặng nhất. (Nhưng tại thời điểm đó người ta chưa biết sử cận để đo lường).
Làm thế nào để tìm ra người có cân nặng nhất?
Thảo luận:
Cho biết cách giải quyết vấn đề trên
4. Một số ví dụ về thuật toán
Ý tưởng:
Lấy ra một người đầu tiên làm móc
Lấy ra người tiếp theo để so sánh với móc, nếu nặng hơn, thì móc là người này.
Cứ tiếp tục cho đến cuối hàng ta sẻ tìm ra được người nặng nhất.
4. Một số ví dụ về thuật toán
4.5 Tìm số lớn nhất trong dãy A các số a1, a2, a3, …, an

Ý 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.
Thuật toán
tìm giá trị lớn nhât
4. Một số ví dụ về thuật toán
4.5 tìm số lớn nhất trong dãy số
a. Xác định bài toán
Input: Dãy số a1, a2, a3, …, an
Output: Số lớn nhất
b. Mô tả thuật toán
Bước 1: Nhập dãy số a1, a2, , an
Bước 2: Max  a1 ; i  2
Bước 3: Nếu i > N, Thông báo Max và kết thúc chương trình.
Bước 4: Nếu ai > Max thì Max ai
Bước 5: i  i +1 Quay lại Bước 3
Thuật toán
tìm giá trị lớn nhât
4. Một số ví dụ về thuật toán
4. Một số ví dụ về thuật toán
Thuật toán
tìm giá trị lớn nhât
5. Vận dụng
Vận dụng 1:
Hãy lập bản kiểm tra thuật toán sau và cho biết thuật toán này dùng để làm gì?

Bước 1: x=50, y=70
Bước 2: x  x+y
Bước 3: y  x-y
Bước 4: x  x-y
Làm việc
theo cặp
Vậy kết thúc ta có x=70 và y=50, đây là thuật toán đổi giá trị hai biến mà không cần dùng biến trung gian
5. Vận dụng
Vận dụng 2:Cho thuật toán sau. B1: nhập P
B2: nếu P<=0 chuyển B4
B3: k  k*10 + P mod 10,
P  P div 10
B4: In kết quả K rồi kết thúc
Lập bảng
để kiểm tra
thuật toán
rồi cho biết
thuật toán này
làm công
việc gì?
Thảo luận
theo nhóm
2 bàn
5. Vận dụng
Cho dãy số a1, a2, a3 …. An và một số k
Hãy mô tả thuật toán tìm số k có xuất hiện trong dãy số trên hay không?
6. Cũng cố
Ghi nhớ
Về nhà:
Đọc thuộc phần ghi nhớ SGK.
Làm các bài tập 3,4,5,6 (SGK)
Làm các bài tập từ 5.1 đến 5.20 (SBT).
Tiết học sau chữa các bài tập trên.
Dặn dò