8. Thuật toán
Khi chúng ta học lập trình thì không chỉ cần học một ngôn ngữ lập trình nào đó mà cần phải học tư duy giải quyết vấn đề. Khi đã có tư duy giải quyết vấn đề thì chúng ta có thể sử dụng các ngôn ngữ lập trình khác nhau để xây dựng các ứng dụng. Hay nói cách khác, ngôn ngữ lập trình chính là công cụ để hiện thực hoá tư duy giải quyết vấn đề cho một bài toán cụ thể.
Thuật toán, còn gọi là giải thuật, là một tập hợp hữu hạn các chỉ thị hay cách thức được định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước. Chúng ta có thể sử dụng các cách khác nhau để mô tả thụât toán, chẳng hạn như bằng lời nói, bằng các hình vẽ hoặc bằng các ký hiệu khác.
Ví dụ:
Có hai bình A và B đựng hai loại chất lỏng khác nhau, chẳng hạn bình A đựng rượu, bình B đựng nước mắm. Yêu cầu hoán đổi (swap) chất lỏng đựng trong hai bình.
Thuật toán:
- Yêu cầu phải có thêm một bình thứ ba gọi là bình C
- Bước 1: Đổ rượu từ bình A sang bình C
- Bước 2: Đổ nước mắm từ bình B sang bình A
- Bước 3: Đổ rượu từ bình C sang bình B
Trong lập trình, có 2 cách phổ biến để mô tả các thuật toán đó là Mã giả và Lưu đồ.
9. Mô tả thuật toán bằng mã giả
Mã giả (pseudo-code) là cách mô tả thuật toán bằng ngôn ngữ tự nhiên. Thông thường chúng ta sử dụng các từ tiếng Anh để mô tả thuật toán. Mã giả là mã không thực thi được và thông thường cũng không có các quy định chặt chẽ về cú pháp của mã giả. Chúng ta có thể tuỳ biến cách sử dụng từ, miễn sao đạt được mục đích là các bên liên quan có thể hiểu được thuật toán của chúng ta. Ví dụ, sử dụng mã giả để mô tả thuật toán giải phương trình bậc nhất với các cơ số a và b:
1. BEGIN 2. INPUT a, b 3. IF a = 0 THEN 4. IF b = 0 THEN 5. PRINT “Phương trình vô số nghiệm” 6. ELSE 7. PRINT “Phương trình vô nghiệm” 8. END IF 9. ELSE 10. PRINT “Phương trình có nghiệm x = -b/a” 11. END IF 12. END
Giải thích:
Dòng 1: BEGIN đánh dấu nơi bắt đầu thuật toán
Dòng 2: INPUT đánh dấu nơi nhập vào cơ số a và b
Dòng 3: IF…THEN đánh dấu nơi xét điều kiện cơ số a bằng 0. Nếu a bằng 0 thì thực hiện tiếp các câu lệnh từ dòng số 4 đến dòng số 8, còn nếu a khác 0 thì thực hiện dòng số 9.
Dòng 4: IF…THEN đánh dấu nơi xét điều kiện cơ số b bằng 0. Nếu b bằng 0 thì thực hiện dòng số 5, còn nếu b khác 0 thì thực hiện dòng số 7.
Dòng 5: PRINT là chỉ thị để in ra thông điệp khi phương trình có vô số nghiệm.
Dòng 6: ELSE đánh dấu trường hợp ngược lại của dòng IF…THEN tương ứng trước đó (tức là trường hợp b bằng 0 ở dòng 4).
Dòng 7: PRINT là chỉ thị để in ra thông điệp khi phương trình vô nghiệm.
Dòng 8: END IF đánh dấu nơi kết thúc của khối lệnh IF bắt đầu ở dòng 4.
Dòng 9: ELSE đánh dấu trường hợp ngược lại của dòng IF…THEN tương ứng trước đó (tức là trường hợp b bằng 0 ở dòng 3).
Dòng 10: PRINT là chỉ thị để in ra thông điệp khi phương trình có nghiệm.
Dòng 11: END IF đánh dấu nơi kết thúc của khối lệnh IF bắt đầu ở dòng 3.
Dòng 12: END đánh dấu nơi kết thúc thuật toán.
Ưu điểm của việc sử dụng mã giả đó là gần với tự nhiên, ai cũng có thể sử dụng được. Nhược điểm của mã giả đó là nó không có các quy định chặt chẽ nên có thể dẫn đến tình huống là các bên không hiểu được nhau.
10. Mô tả thuật toán bằng lưu đồ
Lưu đồ là cách sử dụng các ký hiệu được quy định trước để mô tả thuật toán. Ưu điểm của lưu đồ là có các quy định chặt chẽ về từng ký hiệu, việc này giúp cho các bên thống nhất về cách sử dụng và dễ hiểu nhau hơn.
Ví dụ, lưu đồ sau đây mô tả thuật toán để tính tổng của hai số Number1 và Number2:
Giải thích
Khối lệnh 1: Hình eclipse mô tả nơi bắt đầu thuật toán
Khối lệnh 2: Hình bình hành mô tả nơi nhập vào giá trị của Number1 và Number2
Khối lệnh 3: Hình chữ nhật mô tả nơi thực hiện phép tính
Khối lệnh 4: Hình bình hành mô tả nơi hiển thị kết quả
Khối lệnh 5: Hình eclipse mô tả nơi kết thúc thuật toán.
11. Một số cấu trúc thường gặp trong thuật toán
Thông thường, trình tự các bước thực hiện của thuật toán là tuyến tính từ trên xuống dưới. Nhưng trong nhiều tình huống, chúng ta cần thay đổi luồng thực thi đó thay đổi, chẳng hạn như ra các quyết định dựa trên một điều kiện nào đó, hoặc lặp đi lặp lại các hành động giống nhau. Trong những tình huống như vậy, chúng ta sẽ sử dụng các cấu trúc đặc trưng như cấu trúc điều kiện hoặc cấu trúc lặp.
11.1. Cấu trúc điều kiện
Cấu trúc điều kiện, còn được biết đến với tên gọi cấu trúc lựa chọn, là dạng cấu trúc được sử dụng trong các tình huống chúng ta cần ra các quyết định dựa trên một điều kiện cho trước.
Có một số dạng cấu trúc điều kiện cơ bản như sau:
- Cấu trúc 1: Nếu < điều kiện> (đúng) thì thực hiện <công việc>
- Cấu trúc 2: Nếu < điều kiện> (đúng) thì thực hiện <công việc 1>, ngược lại (điều kiện sai) thì thực hiện <công việc 2>
- Cấu trúc 3: Trường hợp < i> thì thực hiện <công việc i>
Ví dụ 1:
Bài toán kiểm tra xem một số có phải là số chẵn hay không, nếu là số chẵn thì hiển thị thông báo.
Trong bài toán này chúng ta sử dụng dạng cấu trúc điều kiện Nếu < điều kiện> (đúng) thì thực hiện <công việc>. Trong đó, các bước thực hiện là:
- Nhập vào một số num
- Tính r là phần dư của phép chia num cho 2
- Kiểm tra xem r có bằng 0 hay không
- Nếu r bằng 0 thì hiển thị thông báo “Number is even”
Mã giả:
BEGIN INPUT num r = num MOD 2 IF r=0 DISPLAY “Number is even” END IF END
Lưu đồ
Giải thích
Ở trong lưu đồ trên, hình bình hành được sử dụng để kiểm tra trường hợp r bằng 0, có hai trường hợp xảy ra được mô tả bằng hai hướng Yes và No.
Ví dụ 2:
Bài toán kiểm tra xem một số là số chẵn hay là số lẻ, hiển thị thông báo tương ứng cho cả hai trường hợp.
Trong bài toán này chúng ta sử dụng dạng cấu trúc điều kiện Nếu < điều kiện> (đúng) thì thực hiện <công việc 1>, ngược lại (điều kiện sai) thì thực hiện <công việc 2>. Trong đó, các bước thực hiện là:
- Nhập vào một số num
- Tính r là phần dư của phép chia num cho 2
- Kiểm tra xem r có bằng 0 hay không
- Nếu r bằng 0 thì hiển thị thông báo “Number is Even”
- Nếu ngược lại (tức là r khác 0) thì hiển thị thông báo “Number is Odd”.
Mã giả:
BEGIN INPUT num r = num MOD 2 IF r = 0 DISPLAY “Number is Even” ELSE DISPLAY “Number is Odd” END IF END
Lưu đồ:
11.2. Cấu trúc lặp
Cấu trúc lặp cho phép thực hiện lặp đi lặp lại các công việc nào đó dựa vào một điều kiện cho trước. Chúng ta thường sử dụng cấu trúc lặp để tự động hoá những công việc có tính chất giống nhau, giúp cho mã nguồn trở nên ngắn gọn hơn.
Có hai dạng cấu trúc lặp cơ bản như sau:
- Lặp xác định: Là dạng lặp mà khi viết chương trình, người lập trình đã xác định được công việc sẽ lặp bao nhiêu lần. Chẳng hạn: hiển thị danh sách 100 khách hàng, tính tổng giá tiền của 10 sản phẩm, in bảng cửu chương (bảng tính nhân từ 1 đến 9) v.v.
- Lặp không xác định: là loại lặp mà khi viết chương trình người lập trình chưa xác định được công việc sẽ lặp bao nhiêu lần. Số lần lặp sẽ được xác định tuỳ thuộc vào một số yếu tố cụ thể khi chương trình thực thi. Chẳng hạn: sao chép một file từ nơi này sang nơi khác (chúng ta không biết trước dung lượng của file), cho một nhân vật trong trò chơi chuyển động (chúng ta không biết trước khi nào thì nhân vật dừng lại), kim đồng hồ chuyển động v.v.
Ví dụ 1:
Hiển thị 1000 lần dòng chữ “Scooby”.
Trong bài toán này, chúng ta đã biết trước số lần lặp là 1000, do đó chúng ta sử dụng dạng lặp thứ nhất. Các bước thực hiện là:
- Khai báo biến counter với giá trị ban đầu là 0
- Kiểm tra điều kiện xem liệu counter có nhỏ hơn 1000 hay không
- Nếu counter nhỏ hơn 1000 thì:
- Hiển thị dòng chữ “Scooby”
- Tăng giá trị của biến counter thêm 1 giá trị
- Quay lại Bước 2
- Nếu counter không nhỏ hơn 1000 (tức là bằng hoặc lớn hơn) thì kết thúc chương trình
Mã giả:
BEGIN counter = 0 WHILE (counter < 1000) DO DISPLAY “Scooby” counter = counter + 1 END DO END
Lưu đồ:
Ví dụ 2:
Cho phép người dùng lần lượt nhập vào các số tự nhiên, tính tổng tất cả các số mà người dùng đã nhập. Không hạn chế số lượng lần nhập. Khi người dùng nhập vào số 0 thì hiển thị kết quả và kết thúc chương trình.
Trong bài toán này, chúng ta không biết trước số lần lặp. Các bước thực hiện là:
- Khai báo một biến sum với giá trị ban đầu là 0
- Cho phép người dùng nhập vào một giá trị cho biến number
- Cộng dồn giá trị của biến number vào biến sum
- Kiểm tra xem biến number có bằng 0 hay không
- Nếu biến number khác 0 thì lặp lại Bước 2
- Nếu biến number bằng 0 thì hiển thị giá trị của biến sum và kết thúc
Mã giả:
BEGIN sum = 0 DO INPUT number sum = sum + number WHILE (number != 0) END
Lưu đồ:
12. Một ứng dụng JavaScript đơn giản
JavaScript là một ngôn ngữ lập trình được sử dụng phổ biến trên các trang web, có nghĩa là chúng thực thi được trên môi trường của các trình duyệt.
Lưu ý: Nếu trình duyệt bị vô hiệu hoá việc thực thi JavaScript thì chương trình JavaScript sẽ không được thực thi.
Mặc dù khởi nguồn của JavaScript là một ngôn ngữ để chạy trên các trình duyệt, chủ yếu là để gia tăng tính tương tác và trải nghiệm đối với người dùng web. Nhưng gần đây, JavaScript và hệ sinh thái của nó đã được cải tiến và phát triển để có thể chạy được trên các môi trường khác, chúng ta có thể sử dụng JavaScript để phát triển các ứng dụng phía back-end, mobile hay thậm chí là các ứng dụng desktop.
Trong phạm vi của cuốn sách này, chúng ta sẽ sử dụng JavaScript trên môi trường của trình duyệt. Để thực thi mã JavaScript, chúng ta cần tạo ra một trang web và nhúng mã JavaScript vào trang web đó.
Ứng dụng JavaScript đầu tiên của chúng ta sẽ có một chức năng là hiển thị một thông báo nhỏ lên trên trang web với nội dung “Hello. JavaScript is running.”.
Đoạn mã của file HTML:
1. <html>
2. <head>
3. <title>My First JavaScript Application</title>
4. </head>
5. <body>
6. <script>
7. alert("Hello. JavaScript is running.");
8. </script>
9. </body>
10. </html>
Kết quả khi mở file HTML ở trên bằng trình duyệt:
Điều gì đã diễn ra?
- Trong file HTML, chúng ta sử dụng thẻ <script> để nhúng các đoạn mã JavaScript vào, từ dòng 6 đến dòng 8
- Đoạn mã JavaScript ở trên chỉ bao gồm 1 dòng duy nhất, đặt ở dòng 7
- Khi mở trang trang web bằng trình duyệt, trình duyệt sẽ phiên dịch đoạn mã JavaScript đó và thực thi
- Hàm alert() là một hàm được sử dụng rất phổ biến trong JavaScript để hiển thị các thông báo.
Lưu ý: Cấu trúc của file HTML luôn luôn bao gồm các thẻ <html>, <head>, <title>, <body> như ví dụ trên. Chúng ta sẽ không đi tìm hiểu sâu về HTML ở giai đoạn này.
Xem tiếp: Cài đặt công cụ lập trình
Có thể bạn quan tâm: Giới thiệu về cuốn sách Cẩm nang lập trình căn bản
