Bài giảng Tin học 8 - Bài 5: Từ bài toán đến chương trình

ÀI TOÁN TRÊN MÁY TÍNH 
Thê ́ nào là giải b ài toán trên máy tính ? 
Là việc nào đó ta muốn máy tính thực hiện để từ các điều kiện cho trước ta nhận được kết quả cần thu được 
Ví dụ : Tìm ước số chung lớn nhất của hai số nguyên dương M va ̀ N 
	 Điều kiện cho trước : hai số nguyên dương M và N . 
	 Kết quả cần thu được : Ước số chung lớn nhất của M và N. 
Em hiểu như thê ́ nào là thuật toán ̀ ? 
* Các bước đê ̉ giải một bài toán 
1. Xác định bài toán 
2. Mô ta ̉ thuật toán 
3. Viết chương trình 
 Xác định thông tin đa ̃ cho (INPUT) . 
 Tìm được thông tin cần tìm (OUTPUT) 
 Tìm cách giải bài toán 
 Diễn ta ̉ bằng các lệnh cần phải thực hiện 
 Dựa vào mô ta ̉ thuật toán , ta viết chương trình bằng một ngôn ngư ̃ lập trình 
 2. QUÁ TRÌNH GIẢI BÀI TOÁN TRÊN MÁY TÍNH 
Lưu ý: Để giải 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ể . 
 3. THUẬT TOÁN VÀ MÔ TẢ THUẬT TOÁN 
Xét thuật toán pha trà mời khách . 
1. Xác định bài toán 
 INPUT 
 OUTPUT 
Trà , nước sôi , ấm và chén 
Chén trà đã pha để mời khách 
2. Mô ta ̉ thuật toán 
Bước1 : 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 . 
 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 bx + c = 0 
1. Xác định bài toán 
 INPUT 
 OUTPUT 
Các hê ̣ sô ́ b va ̀ c 
Nghiệm của phương trình bậc nhất 
2. Mô ta ̉ thuật toán 
Bước1 : Nếu b=0 chuyển tới bước 3; 
Bước 2 : Tính nghiệm của phương trình x=- c/b và chuyển tới bước 4; 
Bước 3 : Nếu c ≠ 0 , thông báo phương trình đã cho vô số nghiệm . Ngược lại (c=0), thông báo phương trình có vô số nghiệm . ; 
Bước 4 : Kết thúc . 
 3. THUẬT TOÁN VÀ MÔ TẢ THUẬT TOÁN 
 3. THUẬT TOÁN VÀ MÔ TẢ THUẬT TOÁN 
Xét ba...̀ a 
Diện tích S của hình A 
2. Mô ta ̉ thuật toán 
Bước1 : xác định hệ số b, a; 
Bước 2 : Tính S1 ← 2ab ; 
Bước 4 : S ← S1 + S2 
Bước 5 : Kết thúc . 
Bước 3 : Tính S2 ← ; 
Ví du ̣ 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 
Gia ́ trị của tổng 1+2++100 
2. Mô ta ̉ thuật toán 
Bước1 : SUM ← 0; i ← 0; 
Bước 2 : i ← i + 1; 
Bước 3 : Nếu i ≤ 100, thi ̀ SUM ← SUM + i va ̀ quay lại bước 2 ; 
Bước 4 : Thông báo kết quả va ̀ kết thúc bài toán . 
Ví du ̣ 3: Đổi gia ́ trị của hai biến x va ̀ y 
1. Xác định bài toán 
 INPUT 
 OUTPUT 
Hai biến x va ̀ y có gia ́ trị tương ứng là a va ̀ b 
Hai biến x va ̀ y có gia ́ trị tương ứng là b va ̀ a 
2. Mô ta ̉ thuật toán 
Bước1 : z ← x; 
Bước 2 : x ← y; 
Bước 3 : y ← z; 
Ví du ̣ 4: Cho hai sô ́ thực a va ̀ b. Hãy cho biết kết quả so sánh hai sô ́ đo ́ dưới dạng “a lớn hơn b”, “a nho ̉ hơn b”, “a bằng b”, 
1. Xác định bài toán 
 INPUT 
 OUTPUT 
Hai sô ́ thực a va ̀ b 
Kết quả so sánh 
2. Mô ta ̉ 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 nho ̉ 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 
MAX 
Ví du ̣ 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) 
Gia ́ trị MAX = max{a1, a2, ,an} 
2. Mô ta ̉ thuật toán 
Bước1 : MAX ← a1; i ← 1; 
Bước 2 : i ← i + 1; 
Bước 3 : Nếu i > n, thi ̀ 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) va ̀ các kết quả câ