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

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

Một số ví dụ về thuật toán
Ví dụ1: 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.
? Học sinh xác định được bài toán và có
thể mô tả thuật toán bằng các bước.
Để 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.

*Chú ý: trong biểu diễn thuật toán, người ta thường dùng kí hiệu ← để gán một biểu thức cho một biến.
Để 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
Ví dụ2: Đổi giá trị của 2 biến x và y.
?Các em có thể mô tả các bước của thuật toán này như thế nào?
Đối với bài này ta không thể thực hiện trực tiếp phép gán x← y; y ←x vì sau phép gán thứ nhất, giá trị của x thay bằng giá trị y và kết quả của 2 phép gán này là cả 2 biến x và y cùng có giá trị ban đầu của biến y. Vì vậy cần dùng một biến trung gian z nào đó để lưu tạm thời giá trị của biến x.
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ụ 3: 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ước1. Max← a1; i ← 1.
Bước2. i← i +1
Bước3. Nếu i >n thì chuyển đến bước 5.
Bước4. Nếu a i > Max thì Max ← a i và quay lại bước 2
Bước5 . Kết thúc thuật toán.

Để hiểu rõ thuật toán này, ta minh hoạ với dữ liệu sau
Ví dụ4: Tìm giá trị lớn nhất của 3 số a,b,c
Yêu cầu HS tự mô tả và viết thuật toán cho bài toán
này
-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