Tiết 21,22:TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH

4. Một số ví dụ về thuật toán
Ví dụ 2: 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 như hình 29 dưới đây:
? Xác định được bài toán và mô tả thuật toán.
+ INPUT: Số a là ½ chiều rộng HCN và là bán kính của hình bán nguyệt, b là chiều dài HCN
+ OUTPUT: Diện tích hình A.
S1=2ab
S=S1+S2

4. Một số ví dụ về thuật toán
Ví dụ 3: Tính tổng của 100 số tự nhiên đầu tiên.
+ Input: Dãy 100 số tự nhiên đầu tiên: 1,2,..., 100
+ Output: Giá trị tổng 1+2+....+100.
Để mô tả được thuật toán trên ta dùng biến S để lưu giá trị của tổng và thực hiện phép toán : cộng thêm vào biến tổng S lần lược các giá trị 1,2,3,..,100 tức là thao tác “cộng” được lặp đi lặp lại 100 lần . Mặc khác việc cộng thêm số i vào S khi biến i không vượt quá 100.
Vì vậy thuật toán tìm tổng S được mô tả như sau.
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ước2
Bước 4. Đưa kết quả ra màn hình và kết thúc thuật toán.

1
2
3
4
5
6
7
8
Để hiểu rõ hơn về thuật toán này, ta có thể minh hoạ bằng bộ dữ liệu cụ thể sau:
Tính tổng N số tự nhiên, với N=5
1
1
Đ
1
2
2
Đ
3
3
3
Đ
6
4
4
Đ
10
5
5
Đ
15
6
Sai
Kết thúc
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.
Em hãy cho biết ý nghĩa câu lệnh và cho biết kết quả ra màn hình?
{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}
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}

Ví dụ 4: Đổi giá trị của 2 biến x và y.
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>=0)
Output: Giá trị Max= Max {a1,a2,...,an }
Ta có thể thực hiện như sau:
+ Đầu tiên gán giá trị a1 cho biến Max .
+Sau đó lần lược so sánh các số a2,...an của dãy A với Max. Nếu a i > Max thì ta gán a i cho Max.
Do vậy ta có thuật toán như sau:
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.

Ví dụ4: Tìm giá trị lớn nhất của 3 số a,b,c
Em tự bài toán xác định và mô thuật toán cho bài toán
-Input: vào 3 số a,b,c.
-Output: Max của 3 số a,b,c
Hdẫn: Ta gán số a cho biến Max sau đó so sánh lần lược số b và c với Max. Nếu b> Max thì gán b cho max, còn nếu c> Max thì gán c cho max.
Bài toán xác định