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

? Tính tổng các số tự nhiên từ 1 đến 100.
Áp dụng công thức S=n(n+1)/2
Thay số vào công thức trên ta có: S=100(100+1)/2=5050
? Tính quãng đường ô tô đi được trong 3 giờ với tốc độ 60 km/giờ.
Áp dụng công thức: S=vt. (1)
Thay số vào công thức (1) ta có: S=60.3=180 (km)
Vậy ta có thể lập trình để giải hai bài toán trên hay không?
Có thể lập trình để giải những bài toán trên.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Bài toán là một công việc hay một nhiệm vụ cần phải giải quyết.
Để giải quyết một bài toán cụ thể, người ta cần xác định bài toán, tức là xác định rõ các điều kiện cho trước và kết quả cần thu được.
Bài toán là khái niệm quen thuộc trong các môn học như Toán, Vật lý,…chẳng hạn như bài toán tính tổng của các số tự nhiên từ 1 đến 100, tính quảng đường ô tô đi được trong 3 giờ với vận tốc 60 km/giờ ở trên là những ví dụ về bài toán
Tuy nhiên, hằng ngày ta thường gặp và giải quyết các công việc đa dạng hơn nhiều. Ví dụ, lập bảng cửu chương, lập bảng điểm của các bạn trong lớp hoặc so sánh chiều cao của hai bạn Long và Trang,…cũng là những ví dụ về toán.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Ví dụ 1 . Xét bài toán nấu một món ăn.
- Điều kiện cho trước: Các phụ phẩm cần để có thể nấu được một món ăn thích hợp.(trứng, mỡ, mắm, muối, rau,…)
- Kết quả cần thu được: Một món ăn.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Ví dụ 2. Xét bài toán tìm đường đi tránh các điểm tắc nghẽn giao thông trong giờ cao điểm
- Điều kiện cho trước: Vị trí điểm nghẽn giao thông và các con đường có thể đi từ vị trí hiện tại tới vị trí cần tới.
- Kết quả cần thu được: Đường đi từ vị trí hiện tại tới vị trí cần tới mà không qua điểm nghẽn giao thông.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Ví dụ 3. Xét bài toán tính diện tích hình tam giác.
- Điều kiện cho trước: Một cạnh và đường cao tương ứng với cạnh đó.
- Kết quả cần thu được: Diện tích hình tam giác.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Ví dụ 3. Xét bài toán tính diện tích hình tam giác.
- Điều kiện cho trước: Ba cạnh của tam giác
- Kết quả cần thu được: Diện tích hình tam giác.
a, b, c là ba cạnh của tương ứng của tam giác)
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Xác định bài toán là bước đầu tiên và là rất quan trọng trong việc giải quyết bài toán.
Tức là tìm điều kiện cho trước và kết quả cần thu được
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Hãy xác định bài toán: Tính tổng các số tự nhiên từ 1 đến 100 ở trên
- Điều kiện cho trước:
các số tự nhiên từ 1 đến 100
- Kết quả cần thu được:
tổng các số tự nhiên từ 1->100
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Hãy xác định bài toán: tính quảng đường ô tô đi được trong 3 giờ với vận tốc 60 km/giờ.
- Điều kiện cho trước:
Thời gian và vận tốc
- Kết quả cần thu được:
Quảng đường đi được trong 3 giờ với vận tốc 60 km/giờ
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
1. Bài toán và xác định bài toán
Bài 5:
Vậy khi xác định được bài toán biết được: Điều kiện cho trước và kết quả cần thu được ta đưa vào máy tính là giải được bài toán hay sao?
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
Khi đã xác định được bài toán và chúng ta sử dụng ngôn ngữ lập trình thích hợp để giải bài toán trên máy tính và giải như thế nào?
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
Mặc dù có nhiều tính năng ưu việt, song máy tính chỉ là một công cụ trợ giúp con người trong xử lí thông tin. Máy tính chỉ có thể thực hiện các công việc tiếp nhận , xử lí, biến đổi, tính toán, lưu trữ và biểu diễn thông tin thành dạng cấn thiết dưới sự chỉ dẫn của con người thông qua các câu lệnh cụ thể.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
Do vậy, việc dùng máy tính giải một bài toán nào đó chính 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ừ các điều kiện cho trước mà ta nhận được kết quả cần thu được.
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 thường được gọi là thuật toán.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
Máy tính không thể tự mình tìm ra lời giải của các bài toán. Lời giải của một bài toán cụ thể, tức là thuật toán, là tư duy sáng tạo của con người. Tuy nhiên, việc mô tả thuật toán chưa đủ đối với máy tính mà cần diễn đạt thuật toán dưới dạng máy tính có thể hiểu và thực hiện được. Kết quả diễn đạt thuật toán là chương trình được viết trong một ngôn ngữ lập trình nào đó.
Máy tính sẽ chạy chương trình và cho ta lời giải của bài toán
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
Thuật toán là các bước để giải một bài toán, còn chương trình là thể hiện của thuật toán trong một ngôn ngữ lập trình cụ thể.
Quá trình giải bài toán trên máy tính gồm các bước sau:
B1. Xác định bài toán: Từ phát biểu của bài toán, ta xác định đâu là thông tin đã cho (INPUT) và đâu là thông tin cần tìm (OUTPUT)
B2. Mô tả thuật toán: Tìm cách giải bài toán và diễn tả bằng các lệnh cần phải thực hiện.
B3. Viết chương trình: Dựa vào mô tả thuật toán ở trên, ta viết chương trình bằng một ngôn ngữ lập trình mà ta biết.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
Để giải một bài toán có phải chỉ có một thuật toán không?
Lưu ý: Một bài toán có thể có nhiều thuật toán khác nhau, song mỗi thuật toán chỉ dùng để giải một bài toán cụ thể. Vì vậy, khi mô tả thuật toán, người ta thường chỉ ra điều kiện cho trước và kết quả cần nhận được kèm theo để dễ nhận biết thuật toán đó dùng để giải bài toán nào?
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
Trở lại với bài toán: Tính diện tích của tam giác khi biết cạnh đáy và đường cao tương ứng với nó.
B1. Xác định bài toán: tìm đâu là thông tin đã cho(INPUT) và đâu là thông tin cần tìm(OUTPUT)
Thông tin đã cho(INPUT): Cạnh đáy (a), đường cao (h).
Thông tin cần tìm(OUTPUT): Diện tích của tam giác (s).
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
2. Quá trình giải bài toán trên máy tính
B2. Mô tả thuật toán:
Bước 2. kết thúc.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
B3. Viết chương trình(trong ngôn ngữ lập trình Pascal)
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
Trở lại với bài toán: tính diện tích của tam giác khi biết độ dài ba cạnh.
INPUT:
OUTPUT:
Các cạnh a, b, c
Diện tích của tam giác.
Bước 1:
Bước 2:
Kêt thúc.
Việc liệt kê bài toán theo trên là một cách dùng để mô tả thuật toán.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
3. Thuật toán và mô tả thuật toán
Xét bài toán pha trà mời khách:
INPUT: Trà, nước sôi, ấm và chén.
OUTPUT: chén trà đã pha để mời khách.
Bước 1: Tráng ấm, chén bằng nước sôi.
Bước 2: Cho trà vào ấm.
Bước 3: Rót nước sôi vào ấm và đợi khoảng 3 đến 4 phút.
Bước 4: Rót trà ra chén để mời khách.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
3. Thuật toán và mô tả thuật toán
Việc liệt kê các bước như trên là một cách thường dùng để mô tả thuật toán. Nếu không có mô tả gì khác trong thuật toán, các bước của thuật toán được thực hiện một các tuần tự theo trình tự đã được chỉ ra.
Mặc dù trong thuật toán không được nêu rõ, song thuật toán phải được mô tả đủ cụ thể để bất kì đối tượng nào, với cùng khả năng và điều kiện như nhau, khi thực hiện thuật toán cũng đều đạt được kết quả như nhau.
INPUT: Các số a và b.
OUTPUT: Nghiệm của phương trình bậc nhất.
Bước 1: nếu a=0 chuyển tới bước 3.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
3. Thuật toán và mô tả thuật toán
Xét bài toán :”Giải phương trình bậc nhất dạng tổng quát ax+b=0”
Bước 2: Tính nghiệm của phương trình và chuyển tới bước 4.
Bước 3: Nếu , thông báo phương trình đã cho vô nghiệm. Ngược lại (b=0), thông báo phương trình có vô số nghiệm.
Bước 4: Kết thúc.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
3. Thuật toán và mô tả thuật toán
Xét bài toán: “Làm món trứng tráng”
INPUT: Trứng, dầu ăn, muối, bột ngọt, hành.
OUTPUT: Trứng tráng.
Bước 1: Đập trứng, tách võ và cho trứng vào bát.
Bước 2: Cho một chút muối, bột ngọt và hành tươi thái nhỏ vào bát trứng. Dùng đũa quấy mạnh cho đến khi đều..
Bước 3: Cho một thìa dầu ăn vào chảo, đun nóng đều rồi đổ trứng vào đun tiếp trong khoảng 1 phút.
Bước 4: Lật mặt trên của miếng trứng úp xuống dưới, Đun tiếp trong khoảng một phút.
Bước 5: Lấy trứng ra đĩa.(kết thúc)
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
3. Thuật toán và mô tả thuật toán
Thuật toán là dãy các thao tác cần thực hiện theo một trình tự xác định để thu được kết quả cần thiết từ những điều kiện cho trước.
Tóm lại, có thể hiểu:
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
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 bán kính a như hình dưới đây:
Hãy xác định:
- INPUT: số a là ½ chiều rộng hình chữ nhật và là bán kính của hình bán nguyệt, b là chiều dài của hình chữ nhật.
- OUTPUT: Diện tích của hình A.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
4. Một số ví dụ về thuật toán
Thuật toán đơn giản:
- Bước 1: S1<- 2ab (hình chữ nhật có cạnh 2a và b)
(diện tích hình bán nguyệt)
- Bước 2:
- Bước 3: S<- s1+s2
- Bước 4: kết thúc.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
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.
Hãy xác định:
- INPUT: Dãy 100 số tự nhiên đầu tiên: 1, 2, …, 100.
-OUTPUT: Giá trị của tổng 1+ 2+ 3…+ 100.
Thực hiện liên tiếp 100 phép cộng
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
4. Một số ví dụ về thuật toán
…
Đối với thuật toán trên chúng ta phải viết bao nhiêu bước?
Đối với thuật toán trên chúng ta phải viết 101 bước.
Vậy liệu có cách nào khác viết ngắn gọn hơn không?
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
4. Một số ví dụ về thuật toán
Ta có thể viết lại ngắn gọn như sau:
- Bước 4: Thông báo kết quả và kết thúc thuật toán.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
4. Một số ví dụ về thuật toán
Ví dụ 4: Đổi giá trị của hai biến x và y.
Hãy xác định:
INPUT: Hai biến x và y có giá trị tương ứng là a và b.
OUTPUT: Hai biến x và y có giá trị tương ứng là b và a.
Bước 1:
Bước 2:
Bước 3:
(sau bước này giá trị của z sẽ bằng a)
(sau bước này giá trị của y sẽ bằng a)
(sau bước này giá trị của x sẽ bằng b)
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
4. Một số ví dụ về thuật toán
Ví dụ 5: cho hai số thực a và b hãy cho biết kết quả so sánh của hai số đó dưới dạng “a lớn hơn b”, “a nhỏ hơn b”, hoặc “a bằng b”.
INPUT: Hai số thực a và b.
OUTPUT: kết quả so sánh.
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”
Bước 3: Kết thúc thuật toán.
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài 5:
4. Một số ví dụ về thuật toán
Ví dụ 6: Tìm số lớn nhất trong dãy A các số a1, a2, …, an cho trước.
INPUT: Dãy A các số a1, a2, …, an (n>=1).
OUTPUT: Giá trị MAX = max{a1, a2, …, an }.
Bước 1:
Bước 2:
Bước 3: Nếu i> n, chuyển đến bước 5.
Bước 4: Nếu
quay lại bước 2
Bước 5: kêt thúc thuật toán.