Các khái niệm cơ bản
Khái niệm về lập trình
Lập trình là việc sử dụng cấu trúc dữ liệu và các lệnh của ngôn ngữ lập trình cụ thể để mô tả dữ liệu và diễn đạt các thao tác của thuật toán.
Ngôn ngữ lập trình:
Là ngôn ngữ dùng để diễn tả thuật toán sao cho máy tính hiểu và thực hiện được. Có 3 loại NNLT:
- Ngôn ngữ máy :
Các lệnh được mã hóa bằng các kí hiệu 0 – 1. Chương trình được viết trên ngôn ngữ máy có thể được nạp vào bộ nhớ và thực hiện ngay.
- Hợp ngữ:
Sử dụng các từ viết tắt tiếng Anh để diễn tả câu lệnh.
- Ngôn ngữ bậc cao :
Các lệnh được mã hóa bằng một ngôn ngữ gần với ngôn ngữ Tiếng Anh. Chương trình viết trên ngôn ngữ bậc cao phải được chuyển đổi thành chương trình trên ngôn ngữ máy mới có thể thực hiện được. Phải sử dụng một chương trình dịch để chuyển đổi. Lập trình bằng ngôn ngữ bậc cao dễ viết hơn vì các lệnh được mã hóa gần với ngôn ngữ tự nhiên. Lập trình trên ngôn ngữ máy rất khó, thường các chuyên gia lập trình mới lập trình được.
Những bước khác nhau của việc dịch một chương trình C từ mã nguồn thành mã thực thi được thực hiện như sau
Soạn thảo/Xử lý từ
Ta dùng một trình xử lý từ (word processor) hay trình soạn thảo (editor) để viết mã nguồn (source code). C chỉ chấp nhận loại mã nguồn viết dưới dạng tập tin văn bản chuẩn. Vài trình biên dịch (compiler) cung cấp môi trường lập trình (xem phụ lục) gồm trình soạn thảo.
Mã nguồn
Ðây là đoạn văn bản của chương trình mà người dùng có thể đọc. Nó là đầu vào của trình biên dịch C.
Bộ tiền xử lý C
Từ mã nguồn, bước đầu tiên là chuyển nó qua bộ tiền xử lý của C. Bộ tiền xử lý này sẽ xem xét những câu lệnh bắt đầu bằng dấu #. Những câu lệnh này gọi là các chỉ thị tiền biên dịch (directives). Điều này sẽ được giải thích sau. Chỉ thị tiền biên dịch thường được đặt nơi bắt đầu chương trình mặc dù nó có thể được đặt bất cứ nơi nào khác. Chỉ thị tiền biên dịch là những tên ngắn gọn được gán cho một tập mã lệnh.
Mã nguồn mở rộng C
Bộ tiền xử lý của C khai triển các chỉ thị tiền biên dịch và đưa ra kết quả. Ðây gọi là mã nguồn C mở rộng, sau đó nó được chuyển cho trình biên dịch C.
Trình biên dịch C (Compiler)
Trình biên dịch C dịch mã nguồn mở rộng thành ngôn ngữ máy để máy tính hiểu được.
Nếu chương trình quá lớn nó có thể được chia thành những tập tin riêng biệt và mỗi tập tin có thể được biên dịch riêng rẽ. Ðiều này giúp ích khi mà một tập tin bị thay đổi, toàn chương trình không phải biên dịch lại.
Bộ liên kết (Linker)
Mã đối tượng cùng với những thủ tục hỗ trợ trong thư viện chuẩn và những hàm được dịch riêng lẻ khác kết nối lại bởi Bộ liên kết để cho ra mã có thể thực thi được.
Bộ nạp (Loader)
Mã thực thi được thi hành bởi bộ nạp của hệ thống.
 |
| Biên dịch và thực thi chương trình |
Các bước xây dựng chương trình
Việc sử dụng máy tính điện tử (MTÐT) để giải quyết một vấn đề nào đó thường được quan niệm một cách không chuẩn xác, đơn giản đó chỉ là việc lập trình thuần túy. Thực ra, đó là cả một quá trình phức tạp bao gồm nhiều giai đoạn phát triển mà lập trình chỉ là một trong các giai đoạn đó (thậm chí chưa chắc đã là phần việc quan trọng nhất). Các bước quan trọng của toàn bộ quá trình được liệt kê dưới đây:
Bước 1. Xác định vấn đề - bài toán.
Bước đầu tiên của bước phân tích hệ thống là nhằm phát biểu chính xác vấn đề - bài toán, làm rõ những yêu cầu mà người sử dụng đòi hỏi. Sau khi nghiên cứu vấn đề được đặt ra, người phân tích viên thiết lập mối phụ thuộc giữa các dữ kiện và kết quả phải tìm. Trên cơ sở có được mô hình vấn đề - bài toán, người phân tích viên sẽ đánh giá, nhận định tính khả thi của vấn đề - bài toán được đặt ra có đáng phải giải quyết không?
Bước 2. Lựa chọn phương pháp giải.
Có thể có nhiều cách khác nhau để giải quyết vấn đề - bài toán đã thiết lập ở bước 1. Các phương pháp có thể khác nhau về thời gian thực hiện. chi phí lưu trữ dữ liệu, độ chính xác.... Nói chung không có phương pháp tối ưu về mọi phương diện. Tùy theo nhu cầu cụ thể mà lựa chọn phương pháp thích hợp. Việc lựa chọn trên cũng cần căn cứ vào khả năng xử lý tự động mà ta sẽ sử dụng.
Bước 3. Xây dựng thuật toán hoặc thuật giải.
Xây dựng mô hình chặt chẽ, chính xác hơn và chi tiết hóa hơn phương pháp đã lựa chọn. Xác định rõ ràng dữ liệu vào, ra cho các bước thực hiện cơ bản và trật tự thực hiện các bước cơ bản đó. Nên áp dụng phương pháp thiết kế có cấu trúc, từ thiết kế tổng thể tiến hành làm mịn dần từng bước.
Bước 4. Cài đặt chương trình.
Mô tả thuật giải bằng chương trình. Dựa vào thuật giải đã được xây dựng, căn cứ quy tắc của một ngôn ngữ lập trình để soạn thảo ra chương trình thể hiện giải thuật thiết lập ở bước 3.
Bước 5. Hiệu chỉnh chương trình.
Ở bước 4, nói chung chúng ta không tránh khỏi sai sót. Ở bước 5 này chúng ta cho chương trình chạy thử để phát hiện và điều chỉnh các sai sót nếu tìm thấy.
Có hai loại lỗi:
Lỗi cú pháp là lỗi do không tuân thủ đúng các quy tắc viết chương trình trên một ngôn ngữ lập trình cụ thể.
Lỗi ngữ nghĩa là lỗi làm sai lạc ý nghĩa hoặc dẫn đến bế tắc của chương trình. Lỗi cú pháp thường dễ phát hiện và hiệu chỉnh hơn lỗi ngữ nghĩa. Cần phải nói rằng việc hiệu chỉnh chương trình khá phức tạp, mất nhiều thời gian và công sức. Việc xây dựng tốt, phù hợp, đầy đủ các bộ dữ liệu để kiểm chứng chương trình là hết sức quan trọng, giúp phát hiện ra các lỗi ngữ nghĩa của chương trình cũng như có thể có vấn đề gì đó bị bỏ sót.
Bước 6. Thực hiện chương trình.
Cho máy tính điện tử thực hiện chương trình. Tiến hành phân tích kết quả thu được. Việc phân tích kết quả nhằm khẳng định kết quả đó có phù hợp hay không. Nếu không, cần kiểm tra lại toàn bộ các bước một lần nữa. Nói chung, dù thận trọng đến mức nào đi nữa thì sau mỗi bước thực hiện nêu trên cũng không khẳng định được kết quả thực hiện từng bước là đúng đắn tuyệt đối. Hơn nữa, như ở bước 5, ta chỉ hiệu chỉnh tất cả các lỗi đã được phát hiện. Còn có thể có sai sót khác của chương trình với một bộ dữ liệu nào khác phức tạp hơn mà ta chưa có cơ hội để phát hiện trước đó. Do đó, ta không thể khẳng định được rằng, chương trình đúng tuyệt đối, không còn sai sót nữa. Như vậy, việc giải quyết một vấn đề cụ thể thực hiện qua hai giai đoạn. Giai đoạn đầu là giai đoạn quan niệm, gồm các bước phân tích, lựa chọn mô hình, xây dựng thuật giải, cài đặt chương trình. Giai đoạn sau là khai thác và bảo trì chương trình. Trong quá trình sử dụng, nói chung thường có nhu cầu về cải tiến, mở rộng chương trình do các yếu tố của bài toán ban đầu có thể thay đổi.
Các thuật toán và chương trình
Khái niệm
Thuật toán là một khái niệm cơ sở của Toán học và Tin học. Hiểu một cách đơn giản, thuật toán là một tập các hướng dẫn nhằm thực hiện một công việc nào đó. Ðối với việc giải quyết một vấn đề - bài toán thì thuật toán có thể hiểu là một tập hữu hạn các hướng dẫn rõ ràng để người giải toán có thể theo đó mà giải quyết được vấn đề. Như vậy, thuật toán là một phương pháp thể hiện lời giải của vấn đề - bài toán.
Từ thuật toán (Algorithm) xuất phát từ tên một nhà toán học người Trung Á là Abu Abd - Allah ibn Musa al’Khwarizmi, thường gọi là al’Khwarizmi. Ông là tác giả một cuốn sách về số học, trong đó ông đã dùng phương pháp mô tả rất rõ ràng, mạch lạc cách giải những bài toán. Sau này, phương pháp mô tả cách giải toán của ông đã được xem là một chuẩn mực và được nhiều nhà toán học khác tuân theo. Từ algorithm ra đời dựa theo cách phiên âm tên của ông.
Việc nghiên cứu về thuật toán có vai trò rất quan trọng trong khoa học máy tính vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không thể giải đúng được bài toán. Trong khoa học máy tính, thuật toán được định nghĩa là một dãy hữu hạn các bước không mập mờ và có thể thực thi được, quá trình hành động theo các bước này phải dừng và cho được kết quả như mong muốn.
Các đặc trưng khác của thuật toán
Tính "thực thi được"
Là một tính chất khá hiển nhiên. Rõ ràng nếu trong "thuật toán" tồn tại một bước không thể thực thi được thì làm sao ta có được kết quả đúng như ý muốn? Tuy nhiên, cần phải hiểu là "thực thi được" xét trong điều kiện hiện tại của bài toán. Chẳng hạn, khi nói "lấy căn bậc hai của một số âm" là không thể thực thi được nếu miền xác định của bài toán là số thực, nhưng trong miền số phức thì thao tác "lấy căn bậc hai của một số âm" là hoàn toàn thực thi được. Tương tự, nếu ta chỉ đường cho một người đi xe máy đến một bưu điện nhưng con đường ta chỉ là đường cụt, đường cấm hoặc đường ngược chiều thì người đi không thể đi đến bưu điện được.
Tính "dừng"
Là tính chất dễ bị vi phạm nhất, thường là do sai sót khi trình bày thuật toán. Dĩ nhiên, mọi thuật toán đều nhằm thực hiện một công việc nào đó nên sau một thời gian thi hành hữu hạn thì thuật toán phải cho chúng ta kết quả mong muốn. Khi không thỏa tính chất này, ta nói rằng "thuật toán" bị lặp vô tận hoặc bị quẩn.
Bên cạnh đặc trưng chính là xác định, hữu hạn và đúng, thuật toán còn có thêm 3 đặc trưng phụ khác.
Ðầu vào và đầu ra (input/output) :
Mọi thuật toán, dù có đơn giản đến mấy cũng phải nhận dữ liệu đầu vào, xử lý nó và cho ra kết quả cuối cùng.
Tính hiệu quả (effectiveness) :
Tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán, không gian và thời gian khi thuật toán được thi hành. Tính hiệu quả của thuật toán là một yếu tố quyết định để đánh giá, chọn lựa cách giải quyết vấn đề-bài toán trên thực tế. Có rất nhiều phương pháp để đánh giá tính hiệu quả của thuật toán. Trong mục 3 của chương , ta sẽ tìm hiểu một tiêu chuẩn được dùng rộng rãi là độ phức tạp của thuật toán.
Tính tổng quát (generalliness) :
Thuật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. Chẳng hạn giải phương trình bậc hai sau đây bằng Delta đảm bảo được tính chất này vì nó luôn giải được với mọi giá trị số thực a,b,c bất kỳ. Tuy nhiên, không phải thuật toán nào cũng đảm bảo được tính tổng quát. Trong thực tế, có lúc người ta chỉ xây dựng thuật toán cho một dạng đặc trưng của bài toán mà thôi.
Phương pháp biểu diễn thuật toán
Ngôn ngữ tự nhiên
Trong cách biểu diễn thuật toán theo ngôn ngữ tự nhiên, người ta sử dụng ngôn ngữ thường ngày để liệt kê các bước của thuật toán (Các ví dụ về thuật toán trong mục 1 của chương sử dụng ngôn ngữ tự nhiên). Phương pháp biểu diễn này không yêu cầu người viết thuật toán cũng như người đọc thuật toán phải nắm các quy tắc. Tuy vậy, cách biểu diễn này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, đôi lúc gây hiểu lầm hoặc khó hiểu cho người đọc. Gần như không có một quy tắc cố định nào trong việc thể hiện thuật toán bằng ngôn ngữ tự nhiên. Tuy vậy, để dễ đọc, ta nên viết các bước con lùi vào bên phải và đánh số bước theo quy tắc phân cấp như 1, 1.1, 1.1.1, ... Bạn có thể tham khảo lại ba ví dụ trong mục 1 của chương để hiểu cách biểu diễn thuật toán theo ngôn ngữ tự nhiên.
Lưu đồ - sơ đồ khối
Lưu đồ hay sơ đồ khối là một công cụ trực quan để diễn đạt các thuật toán. Biểu diễn thuật toán bằng lưu đồ sẽ giúp người đọc theo dõi được sự phân cấp các trường hợp và quá trình xử lý của thuật toán. Phương pháp lưu đồ thường được dùng trong những thuật toán có tính rắc rối, khó theo dõi được quá trình xử lý.
 |
| Các ký pháp lưu đồ |
Mã giả
Tuy sơ đồ khối thể hiện rõ quá trình xử lý và sự phân cấp các trường hợp của thuật toán nhưng lại cồng kềnh. Ðể mô tả một thuật toán nhỏ ta phải dùng một không gian rất lớn. Hơn nữa, lưu đồ chỉ phân biệt hai thao tác là rẽ nhánh (chọn lựa có điều kiện) và xử lý mà trong thực tế, các thuật toán còn có thêm các thao tác lặp .
Khi thể hiện thuật toán bằng mã giả, ta sẽ vay mượn các cú pháp của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Tất nhiên, mọi ngôn ngữ lập trình đều có những thao tác cơ bản là xử lý, rẽ nhánh và lặp. Dùng mã giả vừa tận dụng được các khái niệm trong ngôn ngữ lập trình, vừa giúp người cài đặt dễ dàng nắm bắt nội dung thuật toán. Tất nhiên là trong mã giả ta vẫn dùng một phần ngôn ngữ tự nhiên. Một khi đã vay mượn cú pháp và khái niệm của ngôn ngữ lập trình thì chắc chắn mã giả sẽ bị phụ thuộc vào ngôn ngữ lập trình đó. Chính vì lý do này, chúng ta chưa vội tìm hiểu về mã giả trong bài này (vì chúng ta chưa biết gì về ngôn ngữ lập trình!).
 |
| Giả mã giải phương trình bậc 2 |
Giới thiệu ngôn ngữ lập trình C
C có một số từ khóa, chính xác là 32. Những từ khóa này kết hợp với cú pháp của C hình thành ngôn ngữ C. Nhưng nhiều trình biên dịch cho C đã thêm vào những từ khóa dùng cho việc tổ chức bộ nhớ ở những giai đoạn tiền xử lý nhất định.
Vài quy tắc khi lập trình C như sau :
Tất cả từ khóa là chữ thường (không in hoa)
Ðoạn mã trong chương trình C có phân biệt chữ thường và chữ hoa. Ví dụ : do while thì khác với DO WHILE
Từ khóa không thể dùng cho các mục đích khác như đặt tên biến (variable name) hoặc tên hàm (function name)
Hàm main() luôn là hàm đầu tiên được gọi đến khi một chương trình bắt đầu chạy
Cài đặt IDE cho ngôn ngữ lập trình C
Cài đặt CodeBlocks trên HĐH Windows, hệ điều hành
nhân Linux tương tự, hoặc sử dụng Terminal để cài đặt CodeBlocks.
Để cài đặt CodeBlocks, tới trang chủ của dự án CodeBlock:
http://www.codeblocks.org/ và
lựa chọn mục Download. Tại đây có 3 lựa chọn để download CodeBlocks về
máy tính. Chọn Download the Binary Release (Tải về bản cài đặt phát hành
chính thức).
Khởi động CodeBlocks lần đầu, phần mềm sẽ hỏi bạn sử
dụng bộ dịch gì cho chương trình. Hãy để mặc định (GNU CCC Complier) và
click Next.
 |
| Giao diện khi khởi động CodeBlocks |
Tạo chương trình C++ mới với CodeBlock
Tạo project mới bằng đường dẫn hiển thị ở màn hình khởi động
(Create a new project), hoặc bằng việc lựa chọn File/New/Project…
Trên thanh công cụ.
 |
| Tạo chương trình C++ mới với CodeBlock |
Màn hình tạo project mới hiển thị, lựa chọn loại chương
trình. Trong phạm vi cuốn sách này này, chúng ta sẽ sử dụng chương trình màn
hình console (Console application). Click chọn vào Console
application -> Go, hoặc click đúp chuột vào Console
application.
 |
| Cửa sổ lựa chọn ngôn ngữ lập trình |
Ở mục ngôn ngữ, ta chọn C và ấn Next.
 |
| Đặt tên và chọn đường dẫn cho Project đầu tiên |
 |
| Thiết lập môi trường biên dịch |
Ta nhấn Next để tiếp tục. Ở mục tiếp theo chứa các cài đặt về
trình dịch và môi trường làm việc của dự án, click Finish.
 |
| Bố cục của dự án vừa được tạo ra |
Dịch và chạy chương trình
 |
| Biểu tượng chạy chương trình trong CodeBlock |
Bên cạnh nút build và chạy chương trình như trên, còn có hai
nút quan trọng khác là chỉ build và chỉ chạy chương trình:
Nút đầu tiên từ trái qua sẽ build chương trình, nhưng không
chạy. Nếu chương trình không có thay đổi, sẽ không có gì xảy ra (Không báo lỗi).
Nút thứ hai sẽ chạy chương trình, theo như lần cuối cùng chương
trình được build. Có nghĩa là mọi thay đổi từ lần build cuối sẽ không có ảnh hưởng
gì tới chương trình chạy.
Nút thứ ba, là nút build và chạy chương trình vừa được build
xong.
Quá trình build khá là lâu, mất vài giây. Khi chỉ muốn kiểm
tra chương trình mà cũng phải mất thời gian chờ đợi dự án build xong.
Bài tập thực hành
Bài 1. Viết một đoạn mã giả và vẽ một lưu đồ để nhập một giá trị là độ 0C (Celsius) và chuyển nó sang độ 0F (Fahrenheit). [Hướng dẫn: C/5 = (F-32)/9]
Bài 2. Viết một đoạn mã giả và vẽ một lưu đồ để nhập điểm của một sinh viên cho các môn : Vật lý, Hóa học, và Sinh học. Sau đó hiển thị điểm trung bình và tổng của những điểm này.
Bài 3. Hãy cài đặt phần mềm và thiết lập môi trường CodeBlock trên máy tính cá nhân.
