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

Kiểm Tra Bài Cũ
1. Thuật toán là gì?
2. Trình bày các bước để giải một bài toán?
Thuật toán là một dãy hữu hạn các thao
tác cần thực hiện để giải một bài toán.
+ Xác định bài toán.
+ Mô tả thuật toán.
+ Viết chương trình (lập trình).
Ví dụ: Tìm số lớn nhất trong dãy A gồm
các số a1, a2, ..., an cho trước.
Muốn giải bài toán này trên máy tính ta cần giải mấy bước?
Vậy để tìm số lớn nhất của dãy số này ta làm bằng cách nào?
Bài 5
TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH
03/11/09-Tiết 22
(Tiết 4)
Bài 2 trang 36: Cho chương trình:
Program hoan_doi;
Var x,y,z: integer;
begin
read(x,y);
Writeln(x ,’ ’,y);
z:=x;
x:=y;
y:=z;
Writeln(x ,’ ’,y);
readln
end.
{gán giá trị biến nhớ x vào biến nhớ z}
{gán giá trị biến nhớ y vào biến nhớ x}
{gán giá trị biến nhớ z vào biến nhớ y}
4. Một số ví dụ về thuật toán
Bài 2 trang 36: Cho chương trình:
Program hoan_doi;
Var x,y,z: integer;
begin
read(x,y);
Writeln(x ,’ ’,y);
z:=x;
x:=y;
y:=z;
Writeln(x ,’ ’,y);
readln
end.
Bài toán được xác định
Input: hai biến x, y có giá trị tương ứng là a và b.
Output: hai biến x, y có giá trị tương ứng là b và a.
Ta có thuật toán:
Bước 1: z ← x { giá trị của z sẽ bằng a}
Bước 2: x ← y { giá trị của x sẽ bằng b}
Bước 3: y ← z { giá trị của y sẽ bằng a}
c. Ví dụ 4: Đổi giá trị của 2 biến x và y.
4. Một số ví dụ về thuật toán
1
2
3
x=b
y=a
4. Một số ví dụ về thuật toán
d. Ví dụ 5: 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”, “a bằng b”.
INPUT: Hai số thực a và b
OUTPUT: Kết quả so sánh.
So sánh hai mô hình trên
Mô hình 1:

Mô hình 2:
Bước 1: Nếu a > b, kết quả là “a lớn hơn b”.
Bước 1: Nếu a > b, kết quả là “a lớn hơn b”. Và chuyển đến bước 3.
Bước 2: Nếu a < b, kết quả là “a nhỏ hơn b”. Ngược lại, kết quả là “a bằng b” và kết thúc thuật toán.
Bước 2: Nếu a < b, kết quả là “a nhỏ hơn b”. Ngược lại, kết quả là “a bằng b” và kết thúc thuật toán.

Bước 3: Kết thúc thuật toán.
Ví dụ: Tìm giá trị lớn nhất của 3 số a, b, c
Em hãy xác định bài toán và mô tả thuật toán cho bài toán?
- Input: 3 số a, b, c.
Hướng dẫn:
+ Ta gán số a cho biến Max sau đó so sánh lần lượt số b và c với Max.
Bài toán xác định
4. Một số ví dụ về thuật toán
- Output: Max của 3 số a, b, c
+ Nếu b > Max thì gán b cho max, còn nếu c > Max thì gán c cho max.
e.Ví dụ 6: Tìm số lớn nhất trong dãy A gồm các số a1, a2, ..., an cho trước.
+ Input: dãy A các số a1, a2,..., an (n>=1)

Ta có thể thực hiện như sau:

Do vậy ta có thuật toán như sau:
4. Một số ví dụ về thuật toán
+ Đầu tiên gán giá trị a1 cho biến Max .

+ Sau đó lần lượt so sánh các số a2,...an của dãy A với Max. Nếu ai > Max thì ta gán ai cho Max.
+ Output: Giá trị Max = Max {a1, a2,..., an }
Bước 1. Max ← a1; i ← 1.
Bước 2. i ← i + 1
Bước 3. Nếu i > n thì chuyển đến bước 5.
Bước 4. Nếu a i > Max thì Max ← ai và quay lại bước 2
Bước 5. Kết thúc thuật toán.
Dưới đây minh họa trên với trường
hợp chọn thỏ lớn nhất trong 4 chú thỏ
* Mô tả thuật toán tìm số lớn nhất trong dãy số với n=8, tương ứng với dãy: 5,3,4,7,6,3,15,9
Sai
Sai
Sai
Sai
Sai
Sai
Sai
Sai
Đúng
Sai
Sai
Đúng
Sai
Sai
Đúng
Sai
Kết thúc
5
5
5
7
7
7
15
15
1
2
3
4
5
6
7
8
9
ai
SMAX
Củng Cố
Để giải được bài toán trên máy tính ta cần thực
hiện các bước:
Xác định bài toán


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


3. Viết chương trình

+ Điều kiện cho trứớc (Input).
+ Kết quả thu được (Output).

+ Tìm cách giải bài toán.
+ Diễn ta bằng các lệnh cần thực hiện.

+ Dựa vào mô tả thuật toán, ta viết chương trình
bằng ngôn ngữ lập trình.
Ghi Nhớ
Về Nhà
1. Học bài và hiểu được thuật toán của
3 bài toán trong tiết học này.
2. Trả lời câu hỏi và làm bài tập 4, 5, 6
(SGK – trang 45).
3. Học thuộc phần ghi nhớ.