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

GV: Đào Duy Biên - Trường THCS Vĩnh Thịnh
Kiểm tra bài cũ
Việc dùng máy tính để giải một bài toán là gỡ? Các bước để giải một bài toán trên máy tính?
Việc dùng máy tính để giải một bài toán nào đó có nghĩa là đư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ừ điều kiện cho trước ta nhận được kết quả cần tỡm.

Quá trỡnh giải bài toán trên máy tính gồm
các bước sau:
+ Xác định bài toán
+ Thiết lập phương án giải quyết (Xây dựng
thuật toán)
+ Viết chương trỡnh (lập trỡnh)
Tiết 22

Bài 5. Từ bài toán đến chương trình (Ti?p)
Ví d? 4. Đổi giá trị của hai biến X và Y.
Xác định bài toán:
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.
X
Y
Z
Z:= X;
Y:= Z;
X:= Y;
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}

Ta có thuật toán:
{Bài2 _ Bài thực hành số 3}
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ị đã lưu trong biến nhớ x vào biến nhớ z}
{gán giá trị đã lưu trong biến nhớ y vào biến nhớ x}
{gán giá trị đã lưu trong biến nhớ z vào biến nhớ y}
- Input: D�y A c�c s? a1, a2, ..., an (n ? 1).
- Output: S? l?n nh?t Max = max{a1, a2, ..., an }.
� t��ng:
Gi? s? a1 l� l?n nh?t, ta cho Max nh?n gi� tr? a1.
L?n lu?t so s�nh Max v?i c�c s? a1, a2, ...,an c�n l?i trong d�y, n?u ai>Max thì g�n ai cho Max.
Quả này lớn nhất
Còn phòng nào không nhỉ
A! còn
Quả ở phòng số 1 lớn nhất
Còn phòng nào không nhỉ
A! còn
Waa! Quả này là lớn nhất.
Còn phòng nào không nhỉ
A! còn
Waa! Lớn quá. Quả này lớn nhất
Còn phòng nào không nhỉ
A! còn
Quả ở phòng số 4 vẫn lớn nhất
Còn phòng nào không nhỉ
A! Hết rồi
Vậy, quả ở phòng số 4 là lớn nhất
Ví d? 6: Tìm s? l?n nh?t trong d�y A
c�c s? a1, a2, ..., an cho tru?c.
Thuật toán:
+ B1: Nhập số nguyên dương n và dãy a1,a2,…an.
+ B2: Max:=a1; i:=2; (hoặc max←a1; i←2;).
+ B3: Nếu i>n thì số lớn nhất là Max. Dừng.
+ B4: Nếu ai>Max thì Max:=ai (hoặc Max←ai).
+ B5: i:=i+1 (hoặc i←i+1) quay lại bước 3.
Ví d? 6: Tìm s? l?n nh?t trong d�y A
c�c s? a1, a2, ..., an cho tru?c.
Ví d? 6: Tìm s? l?n nh?t trong d�y A
c�c s? a1, a2, ..., an cho tru?c.
i>n
i>n
<
2
3
1
<
3
5
>
5
4
7
7
5
6
=
6
~
>
Sơ đồ:
Ghi nh?
Cho một bài toán (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 có nghĩa là giao cho máy tính cách thức (thuật toán) tỡm ra lời giải cụ thể của bài toán.
Quá trỡnh giải một bài toán trên máy tính có các bước: xác định bài toán; xây dựng thuật toán; lập chương trỡnh.
Bài tập 1. 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?
Max của 3 số a,b,c
Hướng dẫn: Ta gán số a cho biến Max (giả sử a là số lớn nhất), sau đó so sánh lần lượt số b và số c với Max.
Nếu b> Max thì gán b cho Max.
Nếu c> Max thì gán c cho Max.
Xác định bài toán
Bài tập áp dụng
* INPUT:
3 số a,b,c.
* OUTPUT:
* INPUT:
* OUTPUT:
Bài tập 2. S¾p xÕp d·y sè nguyªn N theo thø tù kh«ng gi¶m

N và dãy N số nguyên dương a1,a2,...,an.
Dãy số được sắp xếp theo trỡnh tự
không giảm.
Dùng thuật toán “nổi bọt”
3
2
9
7
6
Giả sử:
? Mỗi phần tử được xem như một bọt nước;
Lượt 1:
i chạy từ đầu dãy đến vị trí [cuối dãy -1]
Khi a[i]>a[i+1] tức là bọt nước bên trên nặng hơn bọt nước bên dưới => bọt nước trên chỡm xuống và bọt nước bên dưới nổi lên (tráo đổi vị trí).
Sau lượt thứ nhất, bọt nước có trọng lượng lớn nhất sẽ chỡm xuống đáy.
? Trọng lượng của bọt nước thứ i là giá trị của A[i].
Lượt 2:
i chạy từ đầu dãy đến vị trí [cuối dãy - 2] (bỏ qua phần tử cuối).Sau lượt thứ hai bọt nước có trọng lượng lớn thứ hai nằm sát trên bọt nước lớn nhất.
Quá trỡnh duyệt, tráo đổi được lặp đi lặp lại cho đến khi chỉ còn duyệt hai phần tử và thu được dãy không giảm.

VD: Cho dãy số gồm 5 phần tử sau: 3 2 9 7 6

Xác định bài toán và mô tả thuật toán của các bài toán sau:
1
Tìm phần tử nhỏ nhất của dãy số nguyên
2
Sắp xếp mảng dãy số nguyên theo thứ tự giảm dần
Thank you