[Ngôn ngữ lập trình C] Các phần tử cơ bản của ngôn ngữ C

Các thành phần cơ bản 


Bộ chữ viết trong C

Bộ chữ viết trong ngôn ngữ C bao gồm những ký tự, ký hiệu sau: (phân biệt chữ in hoa và in thường):
  • 26 chữ cái latinh hoa A,B,C...Z
  • 26 chữ cái latinh thường a,b,c ...z.
  • 10 chữ số thập phân 0,1,2...9.
  • Các ký hiệu toán học: +, -, *, /, =, <, >, (, )
  • Các ký hiệu đặc biệt: :. , ; " ' _ @ # $ ! ^ [ ] { } ...
  • Dấu cách hay khoảng trống, xuống hàng (\n) và tab (\t)

Các từ khoá trong C

Từ khóa là các từ dành riêng (reserved words) của C mà người lập trình có thể sử dụng nó trong chương trình tùy theo ý nghĩa của từng từ. Ta không được dùng từ khóa để đặt cho các tên của riêng mình. Các từ khóa của Turbo C 3.0 bao gồm:

asm  • auto  • break  • case  • cdecl  • char  • class  • const  • continue  • _cs  • default  • delete  • do double  • _ds  • else  • enum  • _es  • extern  • _export  • far  • _fastcall  • float  • for  • friend  • goto  • huge  • if  • inline  • int  • interrupt  • _loadds  • long  • near  • new  • operator  • pascal  • private  • protected  • public  • register  • return  • _saveregs  • _seg  • short  • signed  • sizeof  • _ss  • static  • struct  • switch  • template  • this  • typedef  • union  • unsigned  • virtual  • void  • volatile  • while

Cú pháp

- Là bộ quy tắc để viết chương trình, gồm những quy định viết từ và tổ hợp từ của mỗi ngôn ngữ

- Dựa vào cú pháp người lập trình và chương trình dịch biết tổ hợp nào của các kí tự trong bảng chữ cái là hợp lệ, nhờ đó có thể mô tả chính xác thuật toán để máy thực hiện

Cấu trúc chương trình C

Một chương trình C khi soạn thảo được chia thành các thành phần chính sau: Các chỉ thị tiền xử lý, Định nghĩa mới, Prototype, Khai báo biến ngoài, Chương trình chính, Cài đặt các hàm.



Các kiểu dữ liệu cơ sở

Được dùng để lưu các giá trị nguyên hay còn gọi là kiểu đếm được.



Kiểu số thực

Được dùng để lưu các số thực hay các số có dấu chấm thập phân

Kiểu void

Mang ý nghĩa là kiểu rỗng không chứa giá trị gì cả

Ví dụ:   void main(){

                ….}

Kích thước của các kiểu dùng sizeof

Kích thước 1 kiểu có thể được xác định lúc chạy chương trình (runtime), dùng sizeof:

Ví dụ:

            sizeof(double)           =>8(byte)

            sizeof(long double)=>10(byte)

Tên và hằng trong C

Tên (identifier): Được dùng để đặt cho chương trình, hằng, kiểu, biến, chương trình con, ... Có 2 loại:

§  Tên chuẩn: là tên do C đặt sẵn như tên kiểu: int, char, float,…; tên hàm: sin, cos...

§  Tên do người lập trình tự đặt.



 Ví dụ:

Tên đặt hợp lệ:  Chieu_dai, Chieu_Rong, Chu_Vi

Tên không hợp lệ: Do Dai, 1D101

Phải tuân thủ quy tắc:

Ø  Sử dụng bộ chữ cái, chữ số và dấu gạch dưới (_)

Ø  Bắt đầu bằng một chữ cái hoặc dấu gạch dưới.

Ø  Không có khoảng trống ở giữa tên.

Ø  Không được trùng với từ khóa.

Ø  Độ dài tối đa của tên là 32 ký tự, tuy nhiên cần đặt sao cho rõ ràng, dễ nhận biết và dễ nhớ.

Ø  Không cấm việc đặt tên trùng với tên chuẩn nhưng khi đó ý nghĩa của tên chuẩn không còn giá trị nữa.

Hằng (Constant): đại lượng không đổi trong suốt quá trình thực thi chương trình

Ví dụ về hằng trong C - tinhoccoban.net

Hằng có thể là: 1 con số, 1 ký tự, 1 chuỗi ký tự.

Hằng số thực: float, double, long double, 2 cách thể hiện

Cách 1: viết thông thường

§  Ví dụ: 123.34             -223.333  3.00  -56.0

Cách 2: viết theo số mũ hay số khoa học

§  Một số thực được tách làm 2 phần (phân cách bởi e/E)

Phần giá trị: như cách 1

Phần mũ: là một số nguyên

§  Ví dụ:

                                    1234.56e-3 = 1.23456 (là số 1234.56*10-3)

                                    -123.45E4 = -1234500 ( là -123.45*104)

Hằng số nguyên: Hằng số nguyên 2 byte (int) hệ thập phân. Sử dụng 10 ký số 0..9. Ví dụ:

                                    123 (một trăm hai mươi ba)

                                    -242 (trừ hai trăm bốn mươi hai)

Hằng số nguyên 2 byte (int) hệ bát phân Sử dụng 8 ký số 0..7. Cách biểu diễn: 0<các ký số từ 0 đến 7>.Số bát phân : 0dndn-1dn-2…d1d0  ( di có giá trị từ 0..7) => giá trị. Ví dụ:                020=2*81 + 0*80 =(16)10

 Hằng số nguyên 2 byte (int) hệ thập lục phân. Là kiểu số nguyên dùng:

§  10 ký số 0..9 và

§  6 ký tự A, B, C, D, E ,F

Cách biểu diễn:

            0x<các ký số từ 0 đến 9 và 6 ký tự từ A đến F>

Số thập lục phân : 0xdndn-1dn-2…d1d0    => Giá trị thập phân. Ví dụ:

            0x345=3*162 + 4*161 + 5*160 = (837)10

            0x2A9= 2*162 + 10*161 + 9*160= (681)10

Ví dụ về hằng số nguyên - tinhoccoban.net

Hằng số nguyên 4 byte (long). Được biểu diễn như số int trong hệ thập phân nhưng kèm theo ký tự l hoặc L. 

Ví dụ: 

                                    45345L   hay  45345l   hay 45345

Hằng ký tự (char) 

Ø  Ví dụ:   ‘a’, ‘A’,  ‘0’, ‘9’

Ø  Là 1 ký tự được viết trong cặp dấu nháy đơn (‘).

Ø  Mỗi một ký tự tương ứng với 1 giá trị trong bảng mã ASCII. ằng ký tự cũng được xem như trị số nguyên.

Ø  Chúng ta có thể thực hiện các phép toán số học trên 2 ký tự (dùng giá trị ASCII của chúng)

Ø  ASCII = American Standard Code for Information Interchange

Bảng mã ASII - tinhoccoban.net


Hằng chuỗi ký tự :

Ví dụ:  “Ngon ngu lap trinh C” Là 1 chuỗi hay 1 xâu ký tự được đặt trong cặp dấu nháy kép (“).

Chú ý:

§  “” :  chuỗi rỗng - không có nội dung

§  Khi lưu trữ trong bộ nhớ, một chuỗi được kết thúc bằng ký tự NULL (‘\0’: mã Ascii là 0).

§  Để biểu diễn ký tự đặc biệt bên trong chuỗi ta phải thêm dấu \ phía trước. Ví dụ: 

Viết “I\’m a student” cho “I’m a student”

Viết “Day la ky tu \“dac biet\”” cho “Day la ky tu “dac biet””

Câu lệnh – Biểu thức

Định nghĩa Biến: Biến dùng để chứa dữ liệu trong quá trình thực hiện chương trình. Giá trị của biến có thể bị thay đổi. Về bản chất, biến là một vùng nhớ được đặt tên.

Cú pháp khai báo biến:

<Kiểu dữ liệu> Danh sách các tên biến cách nhau bởi dấu phẩy;

Cách khai báo biến - tinhoccoban.net


Ví dụ:

Khởi tạo giá trị cho biến lúc khai báo

Cách viết giá trị cho biết luôn kiểu.

Viết giá trị cho biết luôn kiểu giá trị - tinhoccoban.net


Chú ý: 8864L có kiểu long, còn 8864 có kiểu int

Vị trí khai báo biến

Biến ngoài: Được đặt bên ngoài tất cả các hàm, ảnh hưởng đến toàn bộ chương trình (biến toàn cục)

Vị trí khai báo biến - tinhoccoban.net


Biến trong : Được đặt bên trong hàm, chương trình chính hay một khối lệnh. Nó ảnh hưởng đến hàm, chương trình hay khối lệnh chứa nó (biến cục bộ).


Biểu thức: Biểu thức là một sự kết hợp giữa, các toán tử (operator) và các toán hạng (operand)

Ví dụ:    (-b + sqrt(Delta))/(2*a)

Các loại toán tử trong C: Toán tử số học, Toán tử quan hệ và logic, Toán tử Bitwise, Toán tử?, Toán tử con trỏ & và *, Toán tử dấu phẩy

Các toán tử số học - tinhoccoban.net

Minh họa  các phép toán số học. - tinhoccoban.net



Tăng và giảm (++ & --)

   ++x hay x++ giống x = x + 1

    --x hay x-- giống x = x – 1

Tuy nhiên:

            x = 10;

            y = ++x;  //y = 11, x=11

            x = 10;

            y = x++;  //y = 10, x=11

Sự khác nhau giữa toán tử tăng/giảm đặt trước và sau toán hạng - tinhoccoban.net


Sự khác nhau giữa toán tử tăng/giảm đặt trước toán hạng và sau toán hạng

·        x++ trả về giá trị hiện hành của x và sau đó tăng x

·        ++x tăng x trước và sau đó trả về giá trị mới của x

Biểu thức Boolean (boolean expression)

Chú ý! Không có kiểu Boolean rõ ràng trong C. Thay vào đó C dùng các giá trị nguyên để tượng trưng cho giá trị Boolean, với qui ước:

false               Giá trị 0

true                 Bất kỳ giá trị nào ngoại trừ 0

Chú ý! C dùng “=” cho phép gán, và dùng “==“ cho phép so sánh. Nó trả về 1 nếu bằng và 0 nếu ngược lại

Các toán tử quan hệ và các toán tử Logic

Các phép so sánh sau tạo ra các biểu thức logic có giá trị kiểu Boolean

Toán tử quan hệ và các toán tử Logic - tinhoccoban.net


Các biểu thức logic trả về

            0 nếu false(sai)

            1 nếu true(đúng)

Các toán tử quan hệ và các toán tử Logic - tinhoccoban.net

Bảng chân trị cho các toán tử Logic - tinhoccoban.net


Thứ tự ưu tiên của các toán tử logic - tinhoccoban.net



Các toán tử Bitwise

Toán tử Bitwise giúp kiểm tra, gán hay thay đổi các bit thật sự trong 1 byte của word. Chỉ dùng cho kiểu charint.

Bảng chân lý toán tử AND -tinhoccoban.net



Trong lập trình máy tính kỹ thuật số. Phép toán bitwise hoạt động trên một hoặc nhiều số nhị phân (binary numerals), hoặc các chuỗi giống số nhị phân. Đây là một phép toán đơn giản và nhanh, được hỗ trợ trực tiếp bởi bộ xử lý (processor). Thông thường các phép tính bitwise nhanh hơn rất nhiều so với phép nhân, phép chia, đôi khi nhanh hơn đáng kể so với phép cộng. Các phép tính bitwise sử dụng ít năng lượng hơn bởi nó ít sử dụng tài nguyên.

Các toán tử Bitwise - tinhoccoban.net


Toán tử ?

Toán tử ? thực hiện như lệnh if-else. Cú pháp: E1 ? E2 : E3.

Ví dụ : X = (10 > 9) ? 100 : 200;    =>X=100

X = (10 >15 )? 100 : 200; =>X=200

Toán tử con trỏ & và *

Toán tử * trả về nội dung của ô nhớ mà một con trỏ đang chỉ vào.

Ví dụ 1:         

int *p;              //con tro so nguyen

int count=5, x;

p = &count;//  =>Đặt vào biến m địa chỉ bộ nhớ của biến count

Ví dụ 2: x = *p;         // x=5

Toán tử dấu phẩy

Được sử dụng để kết hợp các biểu thức với nhau.

Bên trái của dấu (,) luôn được xem là kiểu void. Biểu thức bên phải trở thành giá trị của tổng các biểu thức được phân cách bởi dấu phẩy.

Ví dụ 1 :        

x = (y=3,y+1);

Trước hết  gán 3 cho y rồi gán 4 cho x.

Ví dụ 2, kết quả in ra màn hình là 2.

#include <stdio.h>

#include <stdlib.h>

void main(int argc, char *argv[]) {

   int a;

   a=(1, 2),3;

   printf("%d", a);

   return 0;      

}

Phép toán được viết gọn. - tinhoccoban.net

Vào – ra dữ liệu trong C 

• C cung cấp 2 hàm vào ra cơ bản: – printf() – scanf() • Muốn sử dụng 2 hàm printf() và scanf() ta cần khai báo tệp tiêu đề stdio.h: #include Hoặc #include “stdio.h”
In dữ liệu ra màn hình:
printf("Xin chao cac ban!");
Một số đặc tả định dạng cơ bản:
%d: số nguyên hệ 10 có dấu
%u: số nguyên hệ 10 không dấu
%x: số nguyên hệ 16
%o: số nguyên hệ bát phân
%s: xâu kí tự
%c: một kí tự đơn
%f: số chấm động cố định
%e: số chấm động (ký hiệu có số mũ)
l : Tiền tố dùng kèm với %d, %x, %o để chỉ số nguyên dài (ví dụ %ld)

Cú pháp: printf(“xâu kí tự…”, <các biến và các số>);

Việc sử dụng đơn giản nhất là in ra một xâu kí tự: “Xin chao cac ban!”:

Để in giá trị của các biến, số ra màn hình, ta phải sử dụng các đặc tả định dạng bắt đầu với % như trên nhằm đại diện cho các biến, số (%d đại diện cho biến số nguyên number).  Các đặc tả định dạng này không được in ra màn hình mà được thay thế bởi các biến, các số đằng sau.

Nhập dữ liệu từ bàn phím:
Cú pháp: scanf (“xâu kí tự…”, <các con trỏ>);

Ví dụ ta muốn nhập một số nguyên vào biến a:

int a; scanf("%d", &a);
Lưu ý:ở đây &a là con trỏ trỏ tới biến a.

Chú ý khi nhập xâu kí tự chứa dấu cách (space):

Trước khi đọc xâu, chúng ta phải làm sạch bộ đệm bàn phím vì có thể quá trình đọc dữ liệu trước còn lưu lại. Trên Windows chúng ta có lệnh fflush(stdin); , tuy nhiên nó đã bộc lộ khá nhiều hạn chế, nhất là không thể dùng trên Linux nên tôi không sử dụng ở đây. Chúng ta sẽ dùng đoạn lệnh sau trước lệnh nhập vào một chuỗi:

int c;
while ( ( c = getchar() ) != EOF && c != '\n' );
Hoặc

scanf ( "%*[^\n]" );
scanf ( "%*c" );
Cách 1: Ta dùng lệnh:

fgets (name, 100, stdin);
với 100 là độ dài lớn nhất của xâu kí tự bạn muốn nhập vào (bạn có thể thay đổi nó) và name là tên biến xâu kí tự. Việc đọc này sẽ lưu vào biến name cả kí tự xuống dòng ở cuối xâu (khi bạn ấn enter để kết thúc nhập xâu là truyền vào bộ đệm kí tự xuống dòng).

Cách 2: Ta dùng lệnh:

scanf ("%[^\n]%*c", name);


Bài tập



[Ngôn ngữ lập trình C] Các khái niệm cơ bản về lập trình

Các khái niệm cơ bản

Khái niệm về lập trình  

Ngôn ngữ lập trình C - tinhoccoban.net



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 - Tinhoccoban.net
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đú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 đồ - tinhoccoban.net
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 - tinhoccoban.net
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 - tinhoccoban.net
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 - tinhcocoban.net
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 - tinhoccoban.net
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 - tinhoccoban.net
Đặ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 - tinhoccoban.net
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 - tinhoccoban.net
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
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.




Bài đăng phổ biến

Bài viết mới nhất

Tin học cơ bản - Nền tảng của mọi kỹ năng

Mọi thông tin trên blog đều được giữ bản quyền bởi Tin học cơ bản. Các bạn nếu muốn lấy thông tin từ blog vui lòng ghi rõ nguồn Tinhoccoban.net

TIN HỌC CƠ BẢN