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

Bài toán và xác định bài toán
Quá trình giải bài toán trên máy tính
Thuật toán và mô tả thuật toán
Một số ví dụ về thuật toán
(TT)
4. MỘT SỐ VÍ DỤ VỀ THUẬT TOÁN
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 là 2a, chiều dài là b và một hình bán nguyệt bán kính a như hình sau. Tính diện tích hình A
Tính S1 ← 2ab
S ← S1 + S2
1. Xác định bài toán
INPUT
OUTPUT
Các hệ số a và b
Diện tích S của hình A
2. Mô tả thuật toán
Bước1 : xác định hệ số a, b;
Bước 2 : Tính S1 ← 2ab;
Bước 4 : S ← S1 + S2
Bước 5 : Kết thúc.
Ví dụ 2: Tính tổng của 100 số tự nhiên đầu tiên
1. Xác định bài toán
INPUT
OUTPUT
Dãy 100 số tự nhiên đầu tiên: 1, 2, …, 100
Giá trị của tổng 1+2+…+100
NHẬN XÉT:

S = 0
S1 = S + 1
S2 = S1 + 2
S3 = S2 + 3


.....
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

. . . . . . . . . . . . . . . . . . . .
Cùng tìm thuật toán
2. Mô tả thuật toán
Bước1 : SUM ← 0; i ← 0;
Bước 2 : i ← i + 1;
Bước 3 : Nếu i ≤ 100, thì SUM ← SUM + i và quay lại bước 2 ;
Bước 4 : Thông báo kết quả và kết thúc bài toán.
Ví dụ 3: Đổi giá trị của hai biến x và y
1. Xác định bài toán
INPUT
OUTPUT
Hai biến x và y có giá trị tương ứng là a và b
Hai biến x và y có giá trị tương ứng là b và a
Bước 1: Z  X
Bước 1: Z  X
Bước 2: XY
Bước 1: Z  X
Bước 2: X  Y
Bước 3: Y  Z
Z
x
y
x
y
b
a
Bước 1: z  x {Sau bước này giá trị của z bằng a}
Bước 2: x  y {Sau bước này giá trị của x bằng b}

a
b
Bước 3: y  z {Sau bước này giá trị của y bằng a}
2. Mô tả thuật toán
Ví dụ 4: 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”,
1. Xác định bài toán
INPUT
OUTPUT
Hai số thực a và b
Kết quả so sánh
2. Mô tả thuật toán
Bước1 : Nếu a > b, kết quả là “a lớn hơn b”;
Bước 2 : Nếu a < b, kết quả là “a nhỏ hơn b”; ngược lại là “a bằng b”;
Bước 3 : Kết thúc thuật toán;
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
Ví dụ 5: Tìm số lớn nhất trong dãy số A các số a1, a2, …,an
1. Xác định bài toán
INPUT
OUTPUT
dãy số A các số a1, a2, …,an (n≥1)
Giá trị MAX = max{a1, a2, …,an}
2. Mô tả thuật toán
Bước1 : 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 ai > MAX, MAX ← ai, Quay lại bước 2;
Bước 5 : Kết thúc thuật toán;
MEMORIZE
Xác định bài toán là việc xác định các điều kiện ban đầu (thông tin vào – INPUT) và các kết quả cần thu được (thông tin ra – OUTPUT).
Giải bài toán trên máy tính là đưa cho máy tính dãy hữu hạn các thao tác đơn giản (thuật toán) mà nó có thể thực hiện được để cho ta kết quả.
Quá trính giải một bài toán trên máy tính gồm các bước: xác định bài toán; mô tả thuật toán; viết chương trình.
Thuật toán là dãu hữu hạn các thao tác cần thực hiện theo một trình tự xác định để nhận được kết quả cần tìm từ những điều kiện cho trước.
TIN HỌC 8
GV thực hiện: ĐOÀN NGỌC HUY
Bài 1.
Hãy thực hiện và cho biết giá trị của biến Sum trong thuật toán sau
Bước1 : SUM ← 0; i ← 0;
Bước 2 : i ← i + 2;
Bước 3 : Nếu i ≤ 100, thì SUM ← SUM + i và quay lại bước 2 ;
Bước 4 : Thông báo kết quả và kết thúc bài toán.
Thực hiện thuật toán (chạy tay)
Bước1 : SUM = 0; i = 0;
Bước 4 : Thông báo kết quả và kết thúc bài toán.
Vậy sum=2+4+6+…+100
1
i=0+2=2
sum=0+2=2
2
3
i=2+2=4
sum=2+4
i=4+2=6
sum=2+4+6
2 ≤ 100
4 ≤ 100
6 ≤ 100
51
i=100+2=102
102 ≤ 100
50
i=98+2=100
sum=2+4+6+…+100
100 ≤ 100
Điều kiện sai
…
…..
………
Bước 2 : i ← i + 2
Bước 3 : Nếu i ≤ 100, thì SUM ← SUM + i và quay lại bước 2
Bài 2.
Hãy thực hiện và cho biết giá trị của biến Sum trong thuật toán sau
Bước1 : SUM ← 1; i ← 1;
Bước 2 : i ← i + 2;
Bước 3 : Nếu i ≤ 100, thì SUM ← SUM + i và quay lại bước 2 ;
Bước 4 : Thông báo kết quả và kết thúc bài toán.
Thực hiện thuật toán (chạy tay)
Bước1 : SUM = ; i = ;
Bước 4 : Thông báo kết quả và kết thúc bài toán.
Vậy sum=
1
i=
sum=
2
3
i=
sum=
i=
sum=
≤ 100
≤ 100
≤ 100
51
i=
≤ 100
50
i=
sum=
≤ 100
Điều kiện sai
…
…..
………
Bước 2 : i ← i + 2
Bước 3 : Nếu i ≤ 100, thì SUM ← SUM + i và quay lại bước 2
Bài 3
Mô tả thuật toán tìm giá trị nhỏ nhất trong dãy n số a1,a2,…,an
Gợi ý :
Dựa vào thuật toán tìm giá trị lớn nhất mà em đã học
Bước1 : 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 ai > MAX, MAX ← ai, Quay lại bước 2;
Bước 5 : Thông báo kết quả và kết thúc bài toán.
Thực hiện thuật toán (chạy tay)
Bước1 : max = a1=10 ; i =1
Bước 5 : Thông báo kết quả và kết thúc bài toán.
Vậy max=20
Cho n=5: a1=10, a2=8, a3=13. a4=5, a5=20
B2 : i ← i + 1
B3 : Nếu i > n, thì chuyển đến bước 5
B4 : Nếu ai > MAX, MAX ← ai, Quay lại bước 2
1
i=1+1=2
2>5 ?
a2=8>10 ?
2
i=2+1=3
3>5 ?
a3=13>10 ?
3
i=3+1=4
4>5 ?
a4=5>13 ?
4
i=4+1=5
5>5 ?
a5=20>13 ?
5
i=5+1=6
6>5 ?
Max=a3=13
Max=a5=20
Đúng
Chuyển đến bước 5
Bài 3
Mô tả thuật toán tìm giá trị nhỏ nhất trong dãy n số a1,a2,…,an
Bước1 : MIN ← 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 ai < MIN, MIN ← ai, Quay lại bước 2;
Bước 5 : Thông báo kết quả và kết thúc bài toán.
Thực hiện thuật toán (chạy tay)
Bước1 : MIN = a1=10 ; i =1
Bước 5 : Thông báo kết quả và kết thúc bài toán.
Vậy MIN=5
Cho n=5: a1=10, a2=8, a3=13. a4=5, an=20
B2 : i ← i + 1
B3 : Nếu i > n, thì chuyển đến bước 5
B4 : Nếu ai > MAX, MAX ← ai, Quay lại bước 2
1
i=1+1=2
2>5 ?
a2=8<10 ?
2
i=2+1=3
3>5 ?
a3=13<8 ?
3
i=3+1=4
4>5 ?
a4=5<8 ?
4
i=4+1=5
5>5 ?
a5=20<8 ?
5
i=5+1=6
6>5 ?
MIN=a2=8
Đúng
Chuyển đến bước 5
MIN=a4=5
Cảm ơn sự chú ý theo dõi của quý thầy cô và các em học sinh.