SGK Tin Học 8 - Bài 5. TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH

BÀI 5
TỪ BÀI TOÁN ĐẾN
CHƯƠNG TRÌNH
Bài toán và xác định bài toán
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 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 tốc độ 60km/giờ 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ề bài toán. Như vậy, có thể hiểu:
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 được 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.
Ví dụ 1. Xét các bài toán tính diện tích hình tam giác, tìm đường đi tránh các điểm nghẽn giao thông trong giờ cao điểm và nấu một món ă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.
Đối với bài toán tìm đường đi tránh các điểm nghẽn giao thông:
Đ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.
Đối với bài toán nấu một món ăn:
Điểu kiện cho trước: Các thực phẩm hiện có (trứng, mỡ, mắm, muối, rau,...);
- Kết quả cần thu được: Một món ăn.
Xác định bài toán là bước đầu tiên và là bước rất quan trọng trong việc giải bài toán.
Quá trình giải 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 chính là đưa cho máy tính dãy hữu hạn các thao tác đon giản mà nó có thể thực hiện được để từ các điều kiện cho trước ta nhận được kết quả cần tìm.
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 được gọi là
thuật toán.
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. Cách giải của một bài toán cụ thể, tức 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à 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ưong trình và cho ta lời giải của bài toán (h. 28).
Hình 28
Nói một cách khác, 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:
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).
Mô tả thuật toán: Diễn tả cách giải bài toán bằng dãy các thao tác cần phải thực hiện.
Viết chương trình: Dựa vào mô tả thuật toán ở trên, viết chương trình bằng một ngôn ngữ lập trình thích hợp.
Cần phải lưu ý rằng, để 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ể. Vì vậy, khi mô tả thuật toán, người ta thường chỉ ra cả điều kiện cho trước và kết quả cần nhận được để dễ nhận biết thuật toán đó dùng để giải bài toán nào.
Thuật toán và mô tả thuật toán
Trong phần này chúng ta sẽ tìm hiểu sâu hơn về khái niệm thuật toán.
Nhiều công việc chúng ta thường làm mà không phải suy nghĩ nhiều, tuy nhiên, nếu hệ thống lại, ta có thể thấy thực chất đó là những thuật toán. Đơn giản như việc pha trà mời khách có thể mô tả dưới dạng thuật toán như sau:
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.
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ách tuần tự theo trình tự như đã được chỉ ra.
Mặc dù không được nêu rõ trong khái niệm thuật toán, 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. Đê’ minh hoạ, chúng ta xét thêm một vài ví dụ:
Bài toán “Giải phương trình bậc nhất dạng tổng quát bx + c = 0”:
INPUT: Các số b và c.
OUTPUT: Nghiệm của phương trình bậc nhất.
Bước 1. 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 = 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ô 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.
Bài toán “Làm món trứng tráng”
INPUT: Trứng, dầu ăn, muối và hành.
OUTPUT: Trứng tráng.
Bước 7. Đập trứng, tách vỏ và cho trứng vào bát.
Bước 2. Cho một chút muối và hành tươi thái nhỏ vào bát trứng. Dùng đũa quấy mạnh để trộn đều trứng, muối, hành.
Bước 3 Cho một thìa dầu ăn vào chảo, đun nóng rồi đổ trứng đã trộn 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
1 phút.
Bước 5. Lấy trứng ra đĩa.
Rõ ràng, bất kì ai biết về các phép toán số học hay hiểu biết một chút vê' làm bếp, theo đúng trình tự và chỉ dẫn ở các bước trong các thuật toán nêu trên đều có thể tính ra nghiệm của phương trình đã cho hay tự làm cho mình món trứng tráng.
Tóm lại, có thể hiểu:
Thuật toán là dãy hữu hạn 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.
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 29 dưới đây:
INPUT: Số a là y chiều rộng của 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.
Thuật toán đơn giản để tính diện tích hình A có thể gồm các bước sau:
Bước 7. 5, <- 2ab {Tính diện tích hình chữ nhật}; na2
Bước 2. s2 <- {Tính diện tích hình bán nguyệt};
Bước 3 s <- 51 + s2 và kết thúc.
Bước 1. Bước 2. Bước 3. Bước 4.
Lưu ý; Trong biểu diễn thuật toán, người ta cũng thường sử dụng kí hiệu <- để chỉ phép gán giá trị của một biểu thức cho một biến.
Ví dụ 3. Tính tổng của 100 số tự nhiên đầu tiên.
INPUT: Dãy 1 00 sô' tự nhiên đầu tiên: 1, 2, ..., 1 00.
OUTPUT: Giá trị của tổng 1 + 2 + ...+ 100.
Ý tưởng để giải bài toán trên là dùng một biến SUM để lưu giá trị của tổng. Việc tính SUM có thể được thực hiện như sau: Đầu tiên gán cho SUM giá trị bằng 0. Tiếp theo lần lượt thêm các giá trị 1,2,3, ..., 1 00 vào SUM. vấn đề là ở chỗ tổ chức việc “lần lượt thêm vào” như thê' nào? Cách dễ nhận thấy nhất là thực hiện liên tiếp 100 phép cộng:
Bước 1. SUM <- 0.
Bước 2. SUM <- SUM + 1.
Bước 101. SUM SUM + 100.
Tuy nhiên, việc mô tả thuật toán như trên là quá dài dòng (nhất là khi không chỉ tính tổng của 100 số mà sô' các sô' cần tính tổng lớn hơn nhiều). Đê’ ý một chút ta có thể thấy trong tất cả các bước nêu trên đểu chỉ có một phép toán được thực hiện: cộng thêm vào SUM lần lượt các giá trị 1, 2, 3,..., 1 00. Tức là chỉ có một thao tác “cộng” được lặp đi lặp lại 100 lần. Mặt khác, việc cộng thêm sô' i vào SUM chỉ được thực hiện khi / không vượt quá 100. Vì vậy, thuật toán tìm SUM có thể được mô tả ngắn gọn hơn như sau:
SUM <— 0; / <— 1.
SUM <- SUM + /;/<-/ + 1.
Nếu /< 100 thì quay lại bước 2.
Thông báo giá trị SUM và kết thúc thuật toán.
Ví dụ 4. Đổi giá trị của hai biến X và y.
INPUT: Hai biến X, y có giá trị tương ứng là a và b.
OUTPUT: Hai biến X, / có giá trị tương ứng là b và a.
Trong bài 2 của bài thực hành 3, chúng ta đã tìm hiểu và viết chương trình hoán đổi các giá trị của hai biến X và y. Ví dụ này sẽ mô tả thuật toán để viết chương trình đó.
Ta không thể thực hiện trực tiếp hai phép gán: X <- / và / <- X, bởi sau phép gán thứ nhất, giá trị của X đã bị thay bằng giá trị của / và kết quả của hai phép gán này là cả hai biến X và / cùng có giá trị ban đầu của biến /. Vì thế, cần dùng một biến trung gian, ví dụ biến 2, để lưu tạm thời giá trị của biến X. Do vậy, ta có thuật toán sau:
Bước 1. z<— X {Sau bước này giá trị của 2 sẽ bằng a} ;
Bước 2. X <- y {Sau bước này giá trị của X sẽ bằng b} ;
Bước 3. y<r- 2 {Sau bước này giá trị của / sẽ bằng giá trị của 2, chính là a, giá trị ban đầu của biến x}
Hình 31
Ví dụ 5. Cho hai số thực a và b. Hãy cho biết kết quả so sánh 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ài toán rất đơn giản. Nhìn qua, thuật toán sau đây dường như có thể giải quyết bài toán này:
Bước 1. 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 nhỏ hơn ô”; Ngược lại, kết quả là “a bằng b” và kết thúc thuật toán.
Tuy nhiên, nếu thử lại các bước với a = 6 và b = 5, ta sẽ thấy sau bước 1 có kết quả “a lớn hơn b”, nhưng đến bước 2, khi kiểm tra a < b không thoả mãn ta lại có tiếp kết quả “a bằng b" và như thế ta nhận được hai kết quả.
Vì vậy, để có kết quả đúng, cần mô tả chính xác hơn điểu kiện kết thúc thuật toán như sau:
Bước 7. 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 ô”; Ngược lại, kết quả là “a bằng b”.
Bước 3. Kết thúc thuật toán.
Ví dụ 6. Tìm số lớn nhất trong dãy A các sô' ap a2	an cho trước.
Ta sẽ dùng biến MAX để lưu số lớn nhất của dãy A. Việc xác định MAX có thể được thực hiện như sau: Đầu tiên gán giá trị a, cho biến MAX. Tiếp theo, lần lượt so sánh các số a2, ..., an của dãy A với MAX. Nếu a, > MAX, ta gán aị cho MAX.
Từ đó, ta có thuật toán sau:
INPUT: Dãy A các sô' ap a2, ..., an (n >1).
OUTPUT: Giá trị MAX = max{ap a2, ..., an}.
Thuật toán 1
Bước 1. MAX <- a1; / <- 1.
Bước 2. Nếu a( > MAX, MAX <- a(-.
Bước 3. i <r-i + 1.
Bước 4. Nếu i<n thì quay lại bước 2.
Bước 5. Thông báo giá trị MAX và kết thúc thuật toán.
Dưới đây minh hoạ thuật toán trên với trường hợp chọn thỏ nặng nhất trong bốn chú thỏ có trọng lượng tương ứng là 2, 1, 5, 3 ki-lô-gam.
à) Trước hết, ta gán MAX là trọng lượng của thỏ sô' 1, tức MAX = 2.
MAX = 2
MAX = 5
MAX = 5
h) So sánh MAXvớị trọng lượng của thỏ số 2. Vì trọng lượng của thỏ số 2 nhẹ hơn trọng lượng của thỏ số 1, do đó MAX vẫn bằng 2.
c) Tiếp theo, so sánh MAXvớị trọng lượng của thỏ số 3. Vì trọng lượng của thỏ số 3 lớn hơn MAX, do đó MAX được đặt lại bằng 5.
d) Cuối cùng, so sánh MAX với trọng lượng của thỏ số 4. MAX lớn hơn trọng lượng của thỏ số 4, do đó MAX vẫn bằng 5. Kết quả, thỏ nặng nhất có trọng lượng là 5kg.
GHI NHÓ
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 nghĩa là đưa ra dãy hữu hạn các thao tác đơn giản (thuật toán) để máy tính thực hiện và cho kết quả.
Quá trình giải một bài toán trên máy tính gồm 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.
Thuật toán là dãy hữu hạn các thao tác cần thực hiện theo một trình tự xác định để nhận được kết quả cần tìm từ những điều kiện cho trước.
Câu hỏi và bài tập
Hãy chỉ ra INPUT và OUTPUT của các bài toán sau:
Xác định số học sinh trong lớp cùng mang họ Trần.
Tính tổng của các phần tủ lớn hon 0 trong dãy n số cho trước.
Tìm số các số có giá trị nhỏ nhốt trong n số đã cho.
Già sử X và y là các biến số. Hãy cho biết kết quở của việc thục hiện thuật toán sau:
Bước 1. x<- x + y Bước 2. y<r- X— y Bước 3. x<r- X— y
Cho trước ba số dưong a, b và c. Hãy mô tà thuật toán cho biết ba số đó có thể là độ dài ba cạnh của một tam giác hay không.
Cho hai biến X và y. Hãy mô tà thuật toán đổi giá trị của hai biến nói trên (nếu cần) để X và y theo thú tụ có giá trị không giâm.
Hãy cho biết kết quà của thuật toán sau:
Bước 1. SUM <- 0; i <- 0.
Bước 2. Nếu i > 100 thì chuyển tới bước 4.
Bước 3. i <-i+1; SUM <- SUM + /'. Quay lại bước 2.
Bước 4. Thông báo giá trị SUM và kết thúc thuật toán.
Hãy mô tả thuật toán giải bài toán tính tổng các phần tử của dãy số
A = Id], a2	cnì cho trước.