Bài giảng Tin học đại cương (Tài liệu dùng cho sinh viên khối ngành kĩ thuật) - Trần Thị Mỹ Tiên

ThS. Trần Thị Mỹ Tiên BÀI GIẢNG TIN HỌC ĐẠI CƯƠNG (Tài liệu dùng cho sinh viên khối ngành kĩ thuật) THÀNH PHỐ HỒ CHÍ MINH – NĂM 2013 1 MỤC LỤC PHẦN 1 ĐẠI CƯƠNG VỀ TIN HỌC ...................................................................................................... 2 Chương 1 CÁC KIẾN THỨC CƠ BẢN VỀ TIN HỌC ...................................................................... 3 1.1 Giới thiệu về máy tính điện tử ...................................................................................................... 3 1.2 Thông tin và xử lí thông tin .......................................................................................................... 7 1.3 Hệ đếm và biểu diễn thông tin trong máy tính .............................................................................. 9 1.4 Cấu trúc cơ bản của máy tính...................................................................................................... 16 1.5 Phần mềm máy tính .................................................................................................................... 20 Chương 2 HỆ ĐIỀU HÀNH VÀ CÁC CHƯƠNG TRÌNH TIỆN ÍCH ........................................... 22 2.1 Khái niệm và các chức năng chính của hệ điều hành .................................................................. 22 2.2 Phân loại hệ điều hành ................................................................................................................ 29 2.3 Một số hệ điều hành phổ biến ..................................................................................................... 29 2.4 Các chương trình tiện ích của hệ điều hành Windows ................................................................ 30 Chương 3 THUẬT TOÁN .................................................................................................................. 34 3.1 Giới thiệu .................................................................................................................................... 34 3.2 Khái niệm thuật toán ................................................................................................................... 34 3.3 Các phương pháp biểu diễn thuật toán ........................................................................................ 35 3.4 Các cấu trúc cơ bản ..................................................................................................................... 38 PHẦN 2 NGÔN NGỮ LẬP TRÌNH C ................................................................................................... 45 Chương 1 TỔNG QUAN VỀ NGÔN NGỮ LẬP TRÌNH C ............................................................. 47 1.1 Giới thiệu ngôn ngữ C ................................................................................................................ 47 1.2 Các thành phần cơ bản của ngôn ngữ C ...................................................................................... 48 1.3 Cấu trúc cơ bản của một chương trình C .................................................................................... 65 1.4 Biên dịch và thực thi chương trình C .......................................................................................... 67 Chương 2 NHẬP XUẤT DỮ LIỆU VÀ CÁC LỆNH ĐIỀU KHIỂN ............................................... 70 2.1 Nhập xuất dữ liệu ....................................................................................................................... 70 2.2 Các lệnh điều khiển .................................................................................................................... 81 Chương 3 HÀM VÀ TỔ CHỨC CHƯƠNG TRÌNH ...................................................................... 100 3.1 Tổ chức chương trình thành các chương trình con .................................................................... 100 3.2 Định nghĩa hàm và khai báo nguyên mẫu hàm ......................................................................... 101 3.3 Lời gọi hàm .............................................................................................................................. 104 3.4 Truyền đối số cho hàm ............................................................................................................. 107 3.5 Phạm vi của biến....................................................................................................................... 110 3.6 Hàm đệ quy .............................................................................................................................. 113 Chương 4 MẢNG VÀ CON TRỎ .................................................................................................... 118 4.1 Mảng......................................................................................................................................... 118 4.2 Con trỏ ...................................................................................................................................... 132 2 PHẦN 1 ĐẠI CƯƠNG VỀ TIN HỌC 3 Chương 1 CÁC KIẾN THỨC CƠ BẢN VỀ TIN HỌC 1.1 Giới thiệu về máy tính điện tử Máy tính là một trong những công cụ mạnh nhất mà con người đã tạo ra. Nó hiện diện ở khắp mọi nơi, từ trường học cho đến các cơ quan, ngân hàng, bệnh viện, siêu thị, căn nhà của chúng ta,Với sự phát triển vượt bậc trong lĩnh vực công nghệ thông tin, máy tính hiện nay rất đa dạng về tính năng và kích cỡ, đáp ứng được nhu cầu của nhiều người tiêu dùng khác nhau. Thông qua máy tính, xã hội có thể tiếp cận ngay lập tức thông tin từ khắp mọi nơi trên thế giới như tin tức, thông tin dự báo thời tiết, tỉ số của các trận đấu, lịch trình các chuyến bay, danh bạ điện thoại, bản đồ và đường đi, . Mọi người cũng có thể gửi những tin nhắn, chia sẻ sách, hình ảnh, nhạc, video, thực hiện các cuộc gọi, kết bạn mới, chia sẻ ý kiến, đặt vé máy bay, mua sắm, hoặc tham gia các khóa học chỉ với một chiếc máy tính có kết nối mạng internet. Hình 1.1 - Ứng dụng của tin học Dù ở nhà hay đang đi trên đường, mọi người đều có thể sử dụng máy tính để quản lí lịch biểu, kiểm tra tài khoản, chuyển tiền, thanh toán hóa đơn hoặc mua bán cổ phiếu. Khi công nghệ càng phát triển thì máy tính trở thành một phần trong cuộc sống hàng ngày. Nhiều người tin rằng, có kiến thức và kinh nghiệm sử dụng máy tính hiệu quả sẽ góp phần tạo nên thành công cho họ. Vậy máy tính điện tử là gì? Máy tính là một thiết bị điện tử hoạt động dưới sự điều khiển của các chỉ thị được lưu trữ trong bộ nhớ. Nó có khả năng đọc, xử lí, xuất và lưu trữ dữ liệu. Rất nhiều kiểu dữ liệu khác nhau có thể được xử lí bởi máy tính bao gồm dữ liệu số (số nguyên, số thực), dữ liệu kí tự (tên, địa chỉ,), dữ liệu đồ họa (hình vẽ, biểu đồ, .), và âm thanh. Trong đó, hai kiểu dữ liệu phổ biến nhất là dữ liệu số và dữ liệu kí tự. 4 1.1.1 Lịch sử phát triển của máy tính Năm 1945, Von Neumann là người đề xuất ra nguyên lý làm việc của máy tính số, Theo đó, máy tính làm việc theo chương trình được lưu trữ trong bộ nhớ chính của nó cùng với các dữ liệu liên quan. Và chiếc máy tính điện tử đầu tiên “ENIAC” đã ra đời năm 1946 được phát triển bởi Eckert và Mauchly. Từ đó đến nay, sự phát triển của máy tính đã trải qua nhiều thế hệ. Thế hệ thứ nhất (1940-1956): sử dụng một số lượng lớn bóng đèn chân không. UNIVAC và ENIAC là ví dụ điển hình của thiết bị tính toán nhanh nhất thời kì này. Tuy nhiên, chúng là một thiết bị rất khổng lồ, chiếm diện tích lớn, tiêu thụ nhiều điện năng và độ tin cậy thấp, thường xuyên bị trặc do lỗi phần cứng. Tốc độ tính toán cũng chỉ từ vài nghìn đến vài chục nghìn phép tính trên một giây. Phần mềm chưa phát triển, chủ yếu là sử dụng ngôn ngữ máy để lập trình. Dữ liệu được đưa vào máy sử dụng thẻ đục lỗ. Thế hệ máy tính này đắt đến mức chỉ có các chính phủ hay các viện nghiên cứu lớn mới có đủ điều kiện để duy trì hoạt động của chúng. Thế hệ thứ hai (1956-1963): Bóng bán dẫn (Transistor) được sử dụng để thay thế cho bóng đèn chân không. Bóng bán dẫn giúp máy tính trở nên nhỏ gọn hơn, tiêu thụ điện năng ít hơn, bộ nhớ có dung lượng lớn hơn, và tin cậy hơn. Ở thế hệ này đã bắt đầu chuyển từ mã nhị phân sang sử dụng kí tự và ngôn ngữ bậc thấp cho phép lập trình viên viết các chỉ thị bằng các từ. Một số ngôn ngữ bậc cao cũng được phát triển trong thời gian này, chẳng hạn như COBOL, FORTRAN, ALGOL, SNOBOL. Thế hệ thứ 3 (1964-1971): Phát triển mạch tích hợp (IC) là một sự cải tiến lớn trong giai đoạn này. Các bóng bán dẫn được thu nhỏ và tích hợp trên một con chip đơn, làm tăng đáng kể tốc độ và hiệu suất của máy tính. Các ngôn ngữ bậc cao như COBOL và FORTRAN được chuẩn hóa theo chuẩn ANSI. Ngoài ra, một số ngôn ngữ mới cũng được giới thiệu trong thời gian này như PL/I PASCAL và BASIC. Các tiến bộ khác cần phải kể đến: người dùng có thể tương tác với máy tính thông qua bàn phím và màn hình, hệ điều hành bắt đầu xuất hiện cho phép máy tính có thể chạy nhiều ứng dụng cùng một lúc. Thế hệ thứ 4 (1971-1989): Hàng ngàn mạch tích hợp được xây dựng trên một con chip đơn gọi là bộ vi xử lí (microprocessor). Con chip Intel 4004 được phát triển năm 1971 có thể chứa tất cả các thành phần của máy tính, từ CPU, bộ nhớ, cho đến các điều khiển xuất/nhập. Bên cạnh sự nhỏ gọn, máy tính trở nên mạnh mẽ hơn với khả năng liên kết với nhau qua hình thức kết nối mạng, đánh dấu sự phát triển của Internet. Máy tính ở thế hệ thứ 4 cũng cho thấy sự phát triển của giao diện đồ họa, chuột và các thiết bị cầm tay. Đĩa mềm đã được sử dụng thay thế cho đĩa từ, các hệ điều hành mới được giới thiệu như MS-DOS, MS-WINDOWS UNIX và hệ điều hành độc quyền của hãng Apple. Thế hệ thứ 5 (ngày nay): Lĩnh vực nghiên cứu hiện nay chủ yếu tập trung vào việc phát triển những máy tính biết suy nghĩ, có khả năng tự học, tự xử lí gọi là trí tuệ nhân tạo. Một số ứng dụng của nó đã được dùng rộng rãi, chẳng hạn như nhận dạng hình ảnh, nhận dạng giọng nói, dịch thuật, 5 1.1.2 Phân loại máy tính Dựa trên kích thước, kiến trúc vật lý, dung lượng bộ nhớ, tốc độ xử lí, máy tính có thể được chia làm nhiều loại như trong sơ đồ dưới đây: Siêu máy tính: Là loại máy tính mạnh nhất, nhanh nhất và đắt nhất, nên thường được sử dụng vào các lĩnh vực quan trọng, những bài toán cần xử lí dữ liệu lớn và tính toán phức tạp như dự báo thời tiết, nghiên cứu sự biến đổi của khí hậu, nghiên cứu năng lượng hạt nhân, khai thác dầu khí, thiết kế tên lửa, thiết kế máy bay, Hình 1.2 – Siêu máy tính Máy tính lớn: Điểm khác biệt chính giữa một siêu máy tính và một máy tính lớn là trong khi siêu máy tính tận dụng sức mạnh của nó để thực hiện một vài chương trình nhanh nhất có thể, thì một máy tính lớn lại tập trung khả năng để thực hiện nhiều chương trình đồng thời cùng lúc. Máy tính lớn chủ yếu được sử dụng bởi các cơ quan, và doanh nghiệp lớn như các ngân hàng, hàng không, các tổ chức của chính phủ để chạy những ứng dụng cần xử lý khối lượng dữ liệu lớn. Máy tính mini: Là máy tính với kích cỡ, tốc độ và khả năng tầm trung. Nó thuộc lớp máy tính đa người dùng, nằm trong khoảng giữa máy tính lớn(hệ thống đa người dùng) và máy tính cá nhân(hệ thống đơn người dùng). Máy tính mini thường được dùng trong các doanh nghiệp vừa và nhỏ. Máy vi tính: Là máy tính có kích thước nhỏ và giá thành rẻ hơn các loại máy trên, phù hợp với nhiều người, nên đã dần được sử dụng rộng rãi ở khắp nơi từ hộ gia đình, trường học, các công ty nhỏVào năm 1981, công ty IBM đã phát triển phiên 6 bản máy vi tính đầu tiên có tên là máy tính cá nhân (PC – Personal Computer). Hiện nay, có rất nhiều loại máy vi tính khác nhau gồm desktop, laptop, thiết bị cầm tay và hệ thống nhúng. o Desktop: là mô hình PC phổ biến nhất hiện nay, chủ yếu được sử dụng tại nhà hoặc ở các văn phòng. Nó được thiết kế phù hợp với kích thước mặt bàn và sử dụng cố định tại một vị trí. o Laptop: là một loại máy tính cá nhân, tích hợp hầu hết các thành phần cơ bản giống như Desktop, nhưng nó có kích thước nhỏ gọn hơn, có thể mang xách được, có thể hoạt động bằng pin, và năng lực xử lí tốt nên rất được ưa chuộng. Hiện nay, rất nhiều thương hiệu laptop ra đời với tính năng, độ tin cậy, kích thước, và giá cả khác nhau như: Apple, Sony, Dell, HP, Acer, đã mang lại sự đa dạng hóa cho thị trường máy tính giúp người dùng dễ dàng chọn lựa sản phẩm phù hợp với nhu cầu và khả năng của mình. Bên cạnh đó, loại máy tính này còn có nhiều dạng khác cũng cần phải kể đến như: netbook, tablet PC, subnotebook, ultrabook, o Các thiết bị cầm tay: là những thiết bị được thiết kế nhỏ gọn, có thể để gọn trong túi. Toàn bộ dữ liệu và các chương trình được lưu trữ trên vùng nhớ với dung lượng nhỏ của thiết bị hoặc thẻ nhớ ngoài. Một số loại thiết bị cầm tay phổ biến nhất hiện nay như: PDA, smartphone, mobile phone, chủ yếu phục vụ nhu cầu giải trí, đọc sách, truy cập internet của người dùng, hoặc thực thi những ứng dụng đơn giản. o Máy tính nhúng: được thiết kế để thực hiện một chức năng nhất định nào đó và được nhúng vào trong các sản phẩm như ô tô, ti vi, robot, ATM, máy bán vé tự động,Ưu điểm của hệ thống nhúng là có thể được tối ưu để giảm thiểu chi phí, chẳng hạn như nó không đòi hỏi bàn phím, chuột, màn hình. Hình 1.3 – Máy tính nhúng Lưu ý: Cách phân loại trên chỉ mang tính tương đối. Trong tương lai, các loại máy tính sẽ có khả năng vượt trội hơn so với hiện tại. 7 1.2 Thông tin và xử lí thông tin 1.2.1 Thông tin và dữ liệu Trước khi tìm hiểu thông tin được xử lí như thế nào trong máy tính, ta cần phân biệt hai khái niệm cơ bản đó là dữ liệu và thông tin. Dữ liệu là tập hợp tất cả những thứ gì mà chúng ta thu thập được, chưa qua xử lí bao gồm văn bản, số liệu, hình ảnh, audio và video. Thông tin là dữ liệu đã được xử lí, được tổ chức, có ý nghĩa và hữu dụng với con người. Thông tin có thể được sinh ra, được lưu trữ, được truyền đi, được sao chép và cũng có thể bị biến dạng. Ta xét một ví dụ sau: Một khách hàng đến siêu thị Co.op Mart Phan Văn Trị mua hàng, sau đó ra quầy tính tiền. Nhân viên tại quầy sẽ nhập dữ liệu về các mặt hàng vào máy tính. Sau khi các dữ liệu đó được xử lí xong thì khách hàng sẽ nhận được hóa đơn tính tiền chứa các thông tin gồm tổng số tiền cần thanh toán, số tiền thừa,.Thông tin tổng số tiền đã thu được sẽ được lưu trong bộ nhớ máy tính và siêu thị có thể sử dụng chúng làm dữ liệu đầu vào để thực hiện quá trình thống kê, báo cáo trong tương lai. Hình 1.4 – Ví dụ minh họa về thông tin và dữ liệu 1.2.2 Xử lí thông tin Máy tính xử lí dữ liệu (đầu vào) thành thông tin (đầu ra). Dữ liệu và thông tin thường được lưu trữ trong bộ nhớ máy tính để sử dụng trong tương lai. Do đó, ta có 8 thể xem chu kỳ xử lí thông tin là một tiến trình bao gồm ghi nhận dữ liệu đầu vào, xử lí nó, xuất ra thông tin có ý nghĩa và các hoạt động lưu trữ. Hình 1.5 – Quá trình xử lí thông tin Thông tin là kết quả của quá trình xử lí các dữ liệu và sau đó thông tin có thể trở thành dữ liệu mới để thông qua quá trình xử lí khác tạo ra những thông tin mới hơn. 1.2.3 Đơn vị đo thông tin Máy tính điện tử được xây dựng từ các bóng bán dẫn có hai trạng thái là tắt hoặc mở. Vì vậy, để biểu diễn thông tin trong máy tính người ta sử dụng các chữ số nhị phân 0 và 1. Việc xử lí trên hai chữ số 0 và 1 sẽ đơn giản hơn, rẻ hơn và đáng tin cậy hơn so với việc sử dụng 10 chữ số trong hệ thập phân. Mỗi chữ số nhị phân mang một lượng thông tin nào đó về đối tượng và được xem là một đơn vị thông tin. Đơn vị đó được gọi là “bit” và ta có thể gọi 0 hoặc 1 là một bit. Tuy nhiên, để dễ dàng hơn trong việc biểu diễn thông tin, người ta đã nhóm dãy 8 bit thành 1byte (B). Số lượng 8 bit được chọn vì đó là số lượng cần thiết để biểu diễn hoặc mã hóa một kí tự đơn. Như vậy, thuật ngữ “byte” được dùng để chỉ một đơn vị lưu trữ dữ liệu trên máy tính. Ngoài ra, người ta còn dùng nhiều đơn vị khác là bội của byte như sau: Đơn vị đo dung lượng lưu trữ thông tin Kilobyte (KB) 1 KB = 1,024 B = 2 10 B Megabyte (MB) 1 MB = 1,024 KB Gigabyte (GB) 1 GB = 1,024 MB Terabyte (TB) 1 TB = 1,024 GB Petabyte (PB) 1 PB = 1,024 TB Exabyte (EB) 1 EB = 1,024 PB Zettabyte (ZB) 1 ZB = 1,024 EB Yottabyte (YB) 1 YB = 1,024 ZB Bảng 1.1 - Các đơn vị đo dung lượng lưu trữ thông tin 9 1.3 Hệ đếm và biểu diễn thông tin trong máy tính 1.3.1 Hệ đếm Hệ đếm xác định phương pháp biểu diễn các con số sử dụng những ký hiệu khác nhau. Một số có thể được biểu diễn khác nhau ở những hệ đếm khác nhau. Chẳng hạn như, hai số (2A)16 và (52)8 đều có cùng giá trị là (42)10. Hệ đếm được chia ra làm hai loại gồm hệ đếm theo vị trí và hệ đếm không theo vị trí. Trong phần này chúng ta chỉ xem xét hệ đếm theo vị trí. Trong hệ đếm này, giá trị của mỗi ký hiệu sẽ được tính dựa vào bản thân ký hiệu đó, vị trí của nó trong một số, và cơ số của hệ. Giả sử, mỗi số được biểu diễn ở dạng: Số này sẽ có giá trị là: (*) Trong đó, S là tập hợp các ký hiệu, các chỉ số k-1, k-2,, 2, 1, 0 chính là vị trí của của các ký hiệu ở phần nguyên của số, còn các chỉ số -1, -2, , -l là vị trí của các ký hiệu ở phần thập phân của số đó. Mỗi hệ đếm theo vị trí đều cơ số riêng, ký hiệu là b và tập hợp các ký hiệu nhất định. Sau đây, ta sẽ xem xét 4 hệ đếm theo vị trí gồm hệ thập phân, hệ nhị phân, hệ thập lục phân, và hệ bát phân. Để phân biệt một số I ở các hệ đếm khác nhau ta sử dụng dấu ngoặc đơn và cơ số làm chỉ số: (I)b. a. Hệ thập phân (hệ cơ số 10) Hệ thập phân là hệ đếm có cơ số b là 10 và sử dụng 10 ký hiệu sau để biểu diễn: S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Ngoài các ký hiệu từ tập S, người ta còn sử dụng dấu -, dấu thập phân để biểu diễn số thập phân. Dựa vào công thức (*) ta có thể đánh giá được giá trị của một số trong hệ thập phân. Ví dụ: I = 224 b. Hệ nhị phân (hệ cơ số 2) Hệ nhị phân là hệ đếm có cơ số b là 2 và sử dụng bộ 2 ký hiệu S = {0, 1}. Hai ký hiệu 0 và 1 còn được gọi là bit. Đây là hệ đếm mà máy tính sử dụng để biễu diễn thông tin. Với một số ở hệ nhị phân ta có thể tính được giá trị của nó ở hệ thập phân dựa vào công thức (*). 10 Ví dụ 1: I = (11001)2 Ví dụ 2: R = (101.11)2 c. Hệ thập lục phân (hệ cơ số 16) Ngoài hệ nhị phân, các máy tính hiện đại thường dùng hệ đếm khác là hệ thập lục phân. Với những số nhị phân có giá trị càng lớn, thì chúng càng trở nên quá cồng kềnh. Khi đó, hệ thập lục phân cho phép biểu diễn số nhị phân ở dạng nhỏ gọn và dễ đọc hơn nhiều. Chẳng hạn như, một số nhị phân 8 bits (8 chữ số) có thể được biểu diễn bằng 2 chữ số ở hệ thập lục phân. Hệ thập lục phân có cơ số b là 16 và sử dụng 16 ký hiệu để biểu diễn: S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F} Sự tương đương về giá trị của các ký hiệu trong hệ thập lục phân với hệ thập phân được thể hiện trong bảng dưới đây: Hệ 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Hệ 16 0 1 2 3 4 5 6 7 8 9 A B C D E F Bảng 1.2 – Các kí hiệu tương ứng giữa hệ 10 và hệ 16 Tương tự như các hệ đếm trước, giá trị của một số thập lục phân được đánh giá dựa vào vị trí của các ký hiệu. Ví dụ: I = (2AE)16 11 d. Hệ bát phân (hệ cơ số 8) Hệ đếm này được sử dụng rộng rãi ở những máy tính lớn đời đầu, nhưng càng về sau nó đã trở nên ít phổ biến hơn so với hệ nhị phân và hệ thập lục phân. Hệ bát phân có cơ số b là 8 và sử dụng bộ ký hiệu S = {0, 1, 2, 3, 4, 5, 6, 7} để biểu diễn. Để tính được giá trị của một số ở hệ bát phân ta có thể sử dụng công thức (*). Ví dụ: I = (1256)8 Bảng dưới đây thể hiện các số từ 0 15 được biểu diễn ở các hệ đếm khác nhau: Thập phân Nhị phân Bát phân Thập lục phân 0 0 0 0 1 1 1 1 2 10 2 2 3 11 3 3 4 100 4 4 5 101 5 5 6 110 6 6 7 111 7 7 8 1000 10 8 9 1001 11 9 10 1010 12 A 11 1011 13 B 12 1100 14 C 13 1101 15 D 14 1110 16 E 15 1111 17 F Bảng 1.3 – Chuyển đổi giữa các hệ đếm 1.3.2 Chuyển đổi giữa các hệ đếm Hệ thập phân là hệ đếm cơ bản mà con người sử dụng hàng ngày. Trong khi đó, máy tính lại sử dụng các hệ nhị phân, hệ bát phân và hệ thập lục phân. Cho nên, cần phải có thuật toán để chuyển đổi một số từ hệ đếm này sang hệ đếm khác. Ở phần giới thiệu về các hệ đếm, chúng ta đã làm quen với cách chuyển đổi một số từ hệ đếm bất kỳ sang hệ thập phân. Sau đây là một số cách chuyển đổi từ hệ thập phân sang một hệ đếm bất kỳ, và giữa các hệ nhị phân, hệ bát phân và hệ thập lục phân với nhau. 12 a. Chuyển đổi từ hệ 10 sang hệ đếm bất kỳ Khi chuyển đổi một số từ hệ 10 sang hệ đếm cơ số b, ta không cần phải quan tâm tới vị trí của các ký hiệu trong số đó. Giả sử một số ở hệ thập phân có dạng: (N)10 = I.F, với I là phần nguyên và F là phần thập phân của số N. Trước hết, ta cần tách 2 phần ra và chuyển đổi chúng riêng biệt sang hệ đếm cơ số b. Sau đó, ta ghép nối 2 kết quả lại với nhau thu được số cần tìm. Để chuyển đổi phần nguyên I, ta lấy I chia cho cơ số b được phần thương Q1 và phần dư R1. Sau đó, tiếp tục lấy phần thương Q1 chia cho cơ số b được phần thương Q2 và phần dư R2. Tiếp tục lặp lại như trên cho đến khi phần thương Qn bằng 0 thì dừng lại và được phần dư Rn. Kết quả thu được ở hệ đếm cơ số b có dạng là: RnRn- 1R3R2R1. Ví dụ 1: Đổi số (35)10 sang hệ nhị phân Ta được kết quả (35)10 = (100011)2 Ví dụ 2: Đổi số (126)10 sang hệ bát phân Ta được kết quả (126)10 = (176)8 Để chuyển đổi phần thập phân 0.F của số N, ta lấy 0.F nhân với cơ số b, tích nhận được có dạng D1.F1, lưu lại phần nguyên D1. Sau đó, lại tiếp tục lấy 0.F1 nhân với cơ số b, tích nhận được có dạng D2.F2, lưu lại phần nguyên D2. Cứ tiếp tục quá trình này cho đến khi phần thập phân Fn bằng 0 thì dừng. Nếu trường hợp lặp vô hạn thì ta lấy kết quả gần đúng tùy theo yêu cầu. Kết quả thu được ở hệ đếm cơ số b có dạng là: 0.D1D2D3Dn Ví dụ 1: Đổi số (35.625)10 sang hệ nhị phân 13 Phần thập phân sau khi được chuyển đổi là (0.625)10 = (0.101)2 Vậy, kết hợp với kết quả ở ví dụ 1 ta thu được (35.625)10 = (100011.101)2 Ví dụ 2: Đổi số (126.175)10 sang hệ bát phân Phần thập phân sau khi được chuyển đổi là (0.175)10 = (0.13146)8 Vậy, kết hợp với kết quả ở ví dụ 2 ta thu được (126.175)10 = (176.13146)8 b. Chuyển đổi giữa hệ 2 và hệ 16 Để biến đổi một số từ hệ 2 về hệ 16, ta thực hiện nhóm 4 bit từ phải sang trái, sau đó lần lượt chuyển từng nhóm 4 bit sang hệ 16 (tra theo bảng chuyển đổi giữa các hệ đếm) và ghép lại với nhau sẽ thu được kết quả. Ngược lại, khi chuyển từ hệ 16 về hệ 2, ứng với mỗi ký hiệu (chữ số) trong số 16 sẽ được biểu diễn dưới dạng 4 bit tương đương ở hệ 2. Hình 1.6 – Chuyển đổi giữa hệ 2 và hệ 16 14 Ví dụ 1: Đổi số (10011100010)2 sang hệ cơ số 16 Kết quả là: (10011100010)2 = (4E2)16 Ví dụ 2: Đổi số (24C)16 sang hệ cơ số 2 Kết quả là: (24C)16 = (001001001100)2 c. Chuyển đổi giữa hệ 2 và hệ 8 Để biến đổi một số từ hệ 2 về hệ 8, ta thực hiện nhóm 3 bit từ phải sang trái, sau đó lần lượt thay thế từng nhóm 3 bit thành số tương ứng ở hệ 8 (tra theo bảng chuyển đổi giữa các hệ đếm) và ghép lại với nhau sẽ thu được kết quả. Ngược lại, khi chuyển từ hệ 8 về hệ 2, ứng với mỗi ký hiệu (chữ số) trong số 8 sẽ được biểu diễn dưới dạng 3 bit tương đương ở hệ 2. Hình 1.7 – Chuyển đổi giữa hệ 2 và hệ 8 Ví dụ: Đổi số (101110010)2 sang hệ cơ số 8 Kết quả là: (101110010)2 = (562)8 d. Chuyển đổi giữa hệ 16 và hệ 8 Để chuyển đổi giữa hai hệ đếm này, ngoài việc sử dụng hệ 10 làm trung gian, ta có thể sử dụng hệ 2 làm trung gian. Tức là, chuyển số từ hệ 8 sang hệ 2, kết quả thu được sẽ tiếp tục chuyển sang hệ 16. 1.3.3 Biểu diễn thông tin trong máy tính Máy tính sử dụng hệ đếm nhị phân để biểu diễn tất cả các loại thông tin khác nhau. Khi các dữ liệu được đưa vào máy tính dù ở dạng số hoặc phi số, thì chúng đều được mã hóa thành các dãy nhị phân gồm các bit 0 và 1. Thiết bị xuất sẽ nhận dữ liệu dạng nhị phân và biến đổi chúng trở lại dạng dữ liệu có chứa số hoặc phi số như ban đầu trước khi hiển thị hoặc in ra. Mặc dù mọi dữ liệu trong máy tính đều ở dạng nhị 15 phân, song do bản chất của chúng, người ta thường phân ra làm 2 dạng: dữ liệu cơ bản (số nguyên, số thực, kí tự) và dữ liệu có cấu trúc được xây dựng từ dữ liệu cơ bản. Một dữ liệu cơ bản thường được biểu diễn bằng N bits. Trong đó, N có thể là 4 bits, 8 bits, 16 bits, a. Biểu diễn số nguyên Số nguyên được phân ra làm 2 loại là số nguyên không dấu và số nguyên có dấu. Nó thường được biểu diễn bằng dấu +/- và độ lớn. Nhưng khi chuyển sang dạng số nhị phân, ta không thể sử dụng dấu +/- nữa mà phải sử dụng bit 0 hoặc 1 để biểu diễn dấu của số nguyên và bit này được gọi là bit dấu. o Số nguyên không dấu Để biểu diễn số nguyên không dấu, ta thực hiện chuyển số nguyên sang hệ nhị phân. Nếu số lượng bit của số nhị phân nhận được nhỏ hơn N, thì cần phải thêm vào bên trái của nó các bit “0” cho đủ N bits. Ví dụ: Biểu diễn số 7 trong máy tính sử dụng 8 bits như sau: Chuyển (7)10 sang hệ nhị phân  1 1 1 Thêm 5 bits vào bên trái  0 0 0 0 0 1 1 1 Đối với số nguyên không dấu, mọi bit đều được sử dụng để biểu diễn giá trị số. Với 8 bits, có thể biểu diễn được 28 = 256 số có giá trị từ 0 (00000000)  255 (11111111). Vậy với N bits, có thể biểu diễn các số có giá trị từ 0  2N – 1. o Số nguyên có dấu Trong biểu diễn số nguyên có dấu, ta sử dụng bit đầu tiên bên trái nhất làm bit dấu: 0 là số dương, 1 là số âm. Với N – 1 bits còn lại, ta sử dụng để biểu diễn độ lớn của nó giống như số nguyên không dấu. Ví dụ 1 : Biểu diễn số +28 trong máy tính sử dụng 8 bits như sau: Chuyển (28)10 sang hệ nhị phân dùng 7 bits  0 0 1 1 1 0 0 Thêm 1 bit dấu vào bên trái  0 0 0 1 1 1 0 0 Ví dụ 2 : Biểu diễn số -28 trong máy tính sử dụng 8 bits như sau: Chuyển (28)10 sang hệ nhị phân dùng 7 bits  0 0 1 1 1 0 0 Thêm 1 bit dấu vào bên trái  1 0 0 1 1 1 0 0 Vậy, với N bits ta có thể biểu diễn các số nằm trong miền từ -2N-1 2N-1 – 1 . Với N = 8, có thể biểu diễn các số nguyên từ -128  127 (-27  27 – 1) N = 16, có thể biểu diễn các số nguyên từ -32768  32767 (-215  215 – 1) b. Biểu diễn số thực Để biểu diễn số thực trong máy tính sử dụng N bits, có hai cách là biểu diễn dấu phẩy tĩnh và dấu phẩy động. 16 o Biểu diễn dấu phẩy tĩnh Trong N bits dùng để biểu diễn thì bit đầu tiên bên trái dùng làm bit dấu (0 là số dương, 1 là số âm), còn lại dùng một số bit để biểu diễn phần nguyên và một số khác cho phần thập phân. Do đó, dấu phẩy nằm ở vị trí cố định. Ví dụ: trong dãy 8 bits ta sử dụng 4 bits cho phần nguyên, 3 bits cho phần thập phân và 1 bit dấu để biểu diễn số 10011.101 1 0 0 1 1 1 0 1 Bit dấu Phần nguyên Phần thập phân Tuy nhiên, việc cố định số lượng bit cho phần nguyên và phần thập phân khi biểu diễn sẽ gây thiếu chính xác, cũng như làm hạn chế miền giá trị mà nó có thể biểu diễn được. o Biểu diễn dấu phẩy động Đây là phương pháp biểu diễn đảm bảo được độ chính xác cần thiết. Mỗi số thực sẽ được đưa về dạng như sau: N = M x RE Trong đó, M: phần định trị, R: là cơ số của hệ đếm hiện thời, E: phần số mũ. Ví dụ 1: Số thực +7,452,000,000,000,000,000,000.00 = +7.452 x 1021. Ví dụ 2: Số thực ở hệ nhị phân (101001000000000000000000000000000.00)2 Để biểu diễn số thực này ở dạng dấu phẩy động, ta giữ lại một chữ số khác 0 cho phần nguyên: + (101001000000000000000000000000000.00)2 = + 1.01001 x 232 c. Biểu diễn ký tự Máy tính xử lí cả những dữ liệu phi số như các ký tự chữ cái, ký tự số, ký tự phân cách và các ký tự đặc biệt khác. Bảng mã được dùng để biểu diễn ký tự. Mỗi ký tự sẽ được gán với một mã nhị phân duy nhất để phân biệt với các ký tự còn lại. Mỗi bảng mã khác nhau sẽ dùng số lượng bit khác nhau để biểu diễn một ký tự. Hiện nay, có nhiều bảng mã khác nhau được dùng để mã hóa các ký tự: - BCD: sử dụng 6 bits và biểu diễn được 26 = 64 ký tự - ASCII: đầu tiên sử dụng 7 bits, nhưng về sau mở rộng ra 8 bits. Bảng mã này được chia làm hai phần: phần đầu gồm 128 ký tự chuẩn dùng chung, phần sau là phần mở rộng dùng để mã hóa ký tự đặc biệt, ký tự riêng của từng nước. - UNICODE: là bảng mã toàn cầu chứa tất cả các ký tự của các nước trên thế giới. Nó sử dụng 16 bits và biểu diễn được 216 = 65536 ký tự Ví dụ: Ký tự A trong bảng mã ASCII có mã là 1000001, nhưng mã nhị phân khó nhớ nên ta thường chuyển sang hệ thập phân là 65. 1.4 Cấu trúc cơ bản của máy tính Về cơ bản, máy tính bao gồm những thành phần chính như: thiết bị nhập, thiết bị xuất, bộ nhớ, và bộ xử lí trung tâm. Các thành phần này được tổ chức theo cấu trúc như hình dưới đây: 17 Hình 1.8 – Cấu trúc logic của máy tính Trong đó, thể hiện luồng dữ liệu và chỉ thị ----- biểu diễn các lệnh điều khiển được thực hiện bởi bộ điều khiển 1.4.1 Thiết bị nhập Là thiết bị được sử dụng để đọc dữ liệu và các chỉ thị vào trong máy tính. Thiết bị nhập sẽ thực hiện chuyển đổi dữ liệu nhập thành dạng nhị phân để máy có thể hiểu được. Sau đây là một số thiết bị nhập phổ biến: 1.4.2 Thiết bị xuất Là thiết bị nhận thông tin ở dạng nhị phân từ máy tính và chuyển đổi nó sang dạng ngôn ngữ con người có thể hiểu được. Thông tin được hiển thị ở nhiều dạng khác nhau như dạng in trên giấy, dạng điện tử được lưu trên đĩa cứng, CD và được hiển thị trên màn hình máy tính, hoặc dạng âm thanh. Một vài thiết bị xuất phổ dụng cần phải kể đến như màn hình, máy chiếu, loa, tai nghe, máy in, máy vẽ (plotters), 18 1.4.3 Thiết bị nhập xuất Bên cạnh những thiết bị chỉ có khả năng xuất hoặc nhập, hiện nay còn có nhiều thiết bị tích hợp cả hai chức năng này. Chẳng hạn như màn hình cảm ứng, máy FAX, headset, modem, 1.4.4 Bộ nhớ Bộ nhớ máy tính dùng để lưu trữ các dữ liệu và các chỉ thị được đưa vào máy tính thông qua các thiết bị nhập trước khi bắt đầu xử lí. Bên cạnh đó, các kết quả đầu ra sau khi xử lí cũng cần được lưu trữ trong bộ nhớ trước khi truyền sang các thiết bị xuất. Bộ nhớ được chia làm hai loại gồm bộ nhớ trong và bộ nhớ ngoài. Bộ nhớ trong gồm một dãy các ô được đánh số gọi là ô nhớ. Mỗi máy tính có số lượng ô nhớ khác nhau, từ vài ngàn đến hàng tỷ ô nhớ. Trong hầu hết các máy tính thì mỗi ô nhớ thường chứa một hoặc nhiều byte tùy thuộc vào dữ liệu cần lưu trữ. Mỗi byte gồm 8 bit 0 và 1 liên tiếp nhau. Như vậy, mỗi byte có thể lưu trữ 28 = 256 giá trị khác nhau(các giá trị nằm trong khoảng từ 0255 hoặc là từ -127128). CPU có thể truy xuất hoặc thay đổi giá trị của byte bất kỳ và mỗi byte được xác định thông qua địa chỉ của nó. Đôi lúc máy tính cần lưu trữ dữ liệu có giá trị lớn mà 1 byte không thể chứa đủ, khi đó nó sẽ gộp một số byte liền kề nhau để lưu trữ. Địa chỉ của ô nhớ chứa nhiều byte sẽ chính là địa chỉ của byte đầu tiên. Do vậy, ta có thể hiểu bộ nhớ trong của máy tính là danh sách các ô nhớ có kích thước khác nhau. Bộ nhớ trong được chia làm 2 loại gồm bộ nhớ truy xuất ngẫu nhiên (RAM) và bộ nhớ chỉ đọc (ROM). Bộ nhớ RAM (Random Access Memory): được gọi là truy xuất ngẫu nhiên bởi vì máy tính có thể truy xuất dữ liệu ngay lập tức tại ô nhớ bất kì. Thời gian truy xuất dữ liệu hoàn toàn không phụ thuộc vào vị trí lưu trữ dữ liệu. RAM là nơi lưu trữ tạm thời các dữ liệu và chương trình trong quá trình xử lí. Chúng ta có thể ghi/đọc/xóa dữ liệu trên RAM, tuy nhiên toàn bộ dữ liệu này sẽ bị mất khi tắt máy. Bộ nhớ ROM (Read Only Memory): chứa những dữ liệu và các chỉ thị cơ bản mà máy tính sử dụng khi khởi động. Dữ liệu trên ROM được ghi sẵn bởi nhà sản xuất và sẽ không bị mất khi tắt máy. ROM là bộ nhớ chỉ đọc nên người sử dụng không thể thay đổi dữ liệu trên nó. Tuy có tốc độ truy xuất cao nhưng bộ nhớ trong thường có kích thước nhỏ và chỉ để lưu trữ tạm thời, nên khi cần sao lưu lượng dữ liệu lớn để sử dụng về sau thì cần phải ghi chúng vào các thiết bị lưu trữ (bộ nhớ ngoài). Thiết bị lưu trữ truy xuất dữ liệu một cách tuần tự, tức là tìm qua từng ô nhớ cho đến khi tìm thấy dữ liệu. Vì thế, thời gian truy xuất lâu hơn nhiều so với bộ nhớ trong. Tuy vậy, các thiết bị lưu trữ rẻ hơn nhiều so với bộ nhớ trong, và đặc biệt là dữ liệu được lưu trữ trên chúng có thể dễ dàng được mang chuyển, được sao chép từ máy tính này sang máy tính khác. Hiện nay, các thiết bị lưu trữ rất đa dạng gồm băng từ, đĩa mềm, đĩa cứng, bộ nhớ dùng công nghệ flash (thẻ nhớ, đĩa USB flash), các đĩa quang (CD-R, CD-RW, DVD-R, DVD-RW, Blu-ray Disc-ROM), . 19 1.4.5 Bộ xử lí trung tâm (CPU) CPU (còn được gọi là bộ vi xử lí) là bộ não của máy tính. Chức năng của CPU là thực thi các chương trình và điều khiển mọi hoạt động của các thành phần khác như bộ nhớ, thiết bị xuất/nhập. CPU gồm 4 phần chính là bộ điều khiển, bộ số học-logic (ALU) các thanh ghi và đồng hồ. Bộ điều khiển thực hiện kiểm soát và điều phối hoạt động của tất cả các đơn vị khác nên nó được xem như là thành phần quan trọng nhất của CPU. Bộ điều khiển có chức năng nạp các chỉ thị từ bộ nhớ, giải mã các chỉ thị, điều khiển đưa dữ liệu đến các vị trí chính xác và đúng thời điểm. Chức năng của bộ số học –logic là thực hiện các phép tính toán số học cơ bản (cộng, trừ, nhân, chia) và phép tính logic ( and, or, not). Nó cũng thực hiện các phép so sánh, tăng, giảm, và dịch trái. Còn thanh ghi dùng để lưu trữ tạm thời các dữ liệu và chỉ thị. Nó là bộ nhớ có kích thước nhỏ và tốc độ truy xuất cao. Bộ vi xử lí chứa nhiều loại thanh ghi khác nhau, mỗi loại có chức năng riêng của mình. Bên cạnh đó, CPU còn chứa một bộ phận phát sinh xung nhịp nhằm đồng bộ hóa các hoạt động của nó gọi là đồng hồ. Tốc độ của CPU chính là nhịp của đồng hồ trong mỗi giây, và được đo bằng gigahertz (GHz). Tốc độ càng cao thì hiệu suất của máy tính càng cao. CPU sẽ xử lí mỗi chỉ thị theo chu kỳ gồm bốn thao tác cơ bản là nạp, giải mã, thực thi và lưu trữ. Hình 1.9 – Quá trình xử lí một chỉ thị của CPU Ngoài các bộ phận đã nêu trên, máy tính còn có các bộ phận khác như bo mạch chủ dùng để kết nối các bộ phận của máy tính lại với nhau, các khe cắm mở rộng, card mạng, card âm thanh, card màn hình, các cổng giao tiếp với các thiết bị ngoại vi, đường truyền (bus), bộ nguồn, 20 1.5 Phần mềm máy tính Phần cứng của máy tính không thể suy nghĩ, phân tích dữ liệu hoặc tự mình đưa ra quyết định được. Sự ra đời của phần mềm (tập hợp các chương trình) khiến cho hiệu quả sử dụng phần cứng được nâng cao, rất nhiều công việc của con người được tự động hóa và vận hành nhanh chóng. Một chương trình là tập hợp các chỉ thị được sắp xếp theo một trình tự có logic để chỉ dẫn cho máy tính giải quyết các vấn đề. Quá trình viết chương trình được gọi là lập trình. Một tập hợp các qui ước để viết một chỉ thị(lệnh) để đưa vào máy, cho máy có thể nhận diện và thi hành gọi là ngôn ngữ lập trình. Một phần mềm có thể được viết bằng một hoặc nhiều ngôn ngữ lập trình khác nhau bởi lập trình viên. Phần mềm được chia ra làm hai loại là phần mềm hệ thống và phần mềm ứng dụng. 1.5.1 Phần mềm hệ thống Là phần mềm điều khiển và quản lí phần cứng, cho phép người dùng tương tác với chúng một cách hiệu quả. Để viết phần mềm hệ thống, lập trình viên cần phải hiểu rõ kiến trúc của máy tính và các chi tiết về phần cứng. Phần mềm hệ thống gồm hai loại chính là hệ điều hành và các chương trình tiện ích. Hệ điều hành là hệ thống phần mềm điều khiển mọi hoạt động cơ bản của máy tính và các thiết bị ngoại vi. Nhờ vào hệ điều hành mà các tài nguyên hệ thống (chẳng hạn như CPU, bộ nhớ, thiết bị xuất/nhập,) được sử dụng hiệu quả. Một số hệ điều hành thông dụng cần phải kể đến như Windows, Linux, Unix, Mac OS, Chương trình tiện ích được sử dụng để phân tích, cấu hình, tối ưu, và bảo trì hệ thống máy tính. 1.5.2 Phần mềm ứng dụng Là các chương trình được thiết kế nhằm phục vụ nhu cầu sử dụng của con người để hoàn thành một hoặc nhiều công việc nào đó. Nó sử dụng những dịch vụ mà phần mềm hệ thống cung cấp để tương tác với phần cứng. Những loại phần mềm ứng dụng phổ biến như: - Phần mềm văn phòng nổi tiếng nhất hiện nay là Microsoft Office. Trong bộ phần mềm này gồm có Word, Excel, PowerPoint, Access, One Note, InfoPath, Outlook, Publisher, - Phần mềm hỗ trợ học tập : Matlab, MathType, các phần mềm từ điển, - Phần mềm thiết kế đồ họa: AutoCAD, Adobe Photoshop, MS Paint - Phần mềm hỗ trợ trao đổi thông tin: trình duyệt web(IE, Firefox Chrome, Safari, Opera), Yahoo Messenger, Skype,... - Phần mềm giải trí: game, windows media player,... 21 CÂU HỎI CHƯƠNG 1 Câu 1: Máy tính được chia ra làm bao nhiêu loại? Hãy kể tên từng loại. Câu 2: Phân biệt hai khái niệm thông tin và dữ liệu. Câu 3: Hãy liệt kê các đơn vị đo thông tin. Câu 4: Thực hiện chuyển đổi sau: 15GB = ?MB = ?KB Câu 5: Giả sử mỗi bài hát MP3 có dung lượng 3.5MB. Hỏi một ổ đĩa cứng có dung lượng 500GB chứa được khoảng bao nhiêu bài hát trên? Câu 6: Chuyển đổi các giá trị sau từ hệ đếm cơ số b1 sang hệ đếm cơ số b2: a. (48.125)10  ?2 b. (1100011)2  ?10 c. (FB7)16  ?10 d. (382)10  ?16 e. (1101011001110)2  ?16 f. (11000010111100)2  ?8 g. (A5)16  ?2 h. (2E4)16  ?8 Câu 7: Kể tên các thiết bị nhập, thiết bị xuất, thiết bị nhập xuất. Câu 8: Bộ nhớ là gì? Có bao nhiêu loại bộ nhớ? Câu 9: Các thành phần chính của CPU là gì? Câu 10: Phân biệt phần mềm hệ thống và phần mềm ứng dụng. 22 Chương 2 HỆ ĐIỀU HÀNH VÀ CÁC CHƯƠNG TRÌNH TIỆN ÍCH 2.1 Khái niệm và các chức năng chính của hệ điều hành Hệ điều hành (HĐH) là hệ thống phần mềm chạy trên máy tính, dùng để điều hành, quản lí các thiết bị phần cứng và các tài nguyên hệ thống. HĐH tạo ra môi trường giao tiếp giữa người sử dụng và phần cứng máy tính, cho phép họ có thể phát triển và sử dụng các ứng dụng một cách dễ dàng. Chính vì thế, bất cứ máy tính nào cũng cần phải cài đặt HĐH, nếu thiếu nó thì máy tính sẽ trở nên vô dụng. HĐH thường được cài đặt và lưu trữ trên đĩa cứng của máy tính. Đối với các thiết bị cầm tay như điện thoại thông minh thì nó thường được cài đặt ở bộ nhớ trong. Mỗi loại máy tính sẽ sử dụng một loại HĐH riêng. Chẳng hạn như, máy tính lớn sẽ không sử dụng HĐH giống như máy tính cá nhân, và thậm chí các loại máy tính để bàn cũng có thể sử dụng những HĐH khác nhau. Và một số loại khác lại có thể cài đặt đồng thời nhiều HĐH. Hiện nay có rất nhiều HĐH cho nhiều loại máy khác nhau. Nhưng đa số các HĐH đều có các chức năng chính như khởi động và tắt máy tính, hỗ trợ giao diện người dùng, quản lí các chương trình, quản lí bộ nhớ, điều phối các tác vụ, cấu hình thiết bị, thiết lập các kết nối internet, giám sát hiệu năng máy tính, quản lí tập tin, tự động cập nhật, bảo mật, quản lí mạng và một số tiện ích khác. 2.1.1 Khởi động và tắt máy tính Quá trình khởi động một máy tính được thực hiện dựa trên hai cách là khởi động nguội và khởi động nóng. Khởi động nguội tức là bắt đầu bật máy tính đã được tắt hoàn toàn bằng cách nhấn vào nút “ON”. Ngược lại, khi ta khởi động lại máy tính bằng cách sử dụng HĐH hoặc là nhấn nút “RESET” gọi là khởi động nóng. Quá trình khởi động nóng thường xảy ra sau khi cài đặt phần mềm mới, hoặc khi một chương trình nào đó bị treo. Ở hầu hết các máy tính thường có 3 chế độ tắt máy là Shutdown, Sleep, Hibernate. Đối với máy tính để bàn thì ba chế độ này hầu như không khác nhau, nhưng với máy tính xách tay thì vấn đề tiết kiệm điện năng luôn được quan tâm. Nên cần phải lựa chọn chế độ tắt hiệu quả nhất và phù hợp với nhu cầu sử dụng. - Shutdown: là chế độ tắt toàn bộ các chương trình đang được mở và máy tính sẽ không tiêu tốn điện năng nữa. - Sleep: còn được gọi là chế độ standby. Khi sử dụng chế độ này, máy tính sẽ lưu lại trạng thái hiện tại gồm tất cả các chương trình đang được mở và dữ liệu đang xử lí vào bộ nhớ RAM. Máy tính lúc này sẽ chỉ cần một lượng điện năng nhỏ để duy trì hoạt động của bộ nhớ, còn các bộ phận khác sẽ được tắt hoàn toàn. Khi bật máy tính trở lại từ chế độ Sleep, hệ thống sẽ khởi động nhanh chóng và chúng ta có thể làm việc được ngay. Tuy nhiên, chế độ này vẫn có nhược điểm là nếu nguồn điện bị ngắt đột ngột thì toàn bộ dữ liệu đang xử lí và chương trình đang mở sẽ bị mất. - Hibernate: là chế độ ngủ đông và gần giống với chế độ sleep. Tuy nhiên, ở chế độ này thì trạng thái làm việc hiện tại sẽ được lưu vào ổ cứng và không 23 cần duy trì lượng điện năng để lưu trữ dữ liệu trên ổ cứng. Khi bật máy trở lại, máy tính sẽ khởi động lâu hơn chế độ Sleep. Hình 2.1 – Các chức năng của hệ điều hành 2.1.2 Hỗ trợ giao diện người dùng Giống như các loại phần mềm khác, HĐH cũng hỗ trợ giao diện người dùng, cho phép người dùng tương tác với phần mềm. Giao diện người dùng được chia làm hai loại là giao diện dòng lệnh và giao diện đồ họa. HĐH thường sử dụng kết hợp cả hai loại trên. Với giao diện dòng lệnh, người dùng phải sử dụng bàn phím để nhập dữ liệu và các lệnh. Nó gây khó khăn khi sử dụng với những người ít kinh nghiệm vì họ phải nhớ tất cả các lệnh. Hình 2.2 – Giao diện dòng lệnh 24 Ngược lại, với giao diện đồ họa, người dùng có thể tương tác với phần mềm thông qua hệ thống thực đơn (menu), và các biểu tượng hình ảnh trực quan. Loại giao diện này phù hợp với nhiều đối tượng người sử dụng, kể cả những người ít kinh nghiệm hoặc không hiểu nhiều về máy tính. Hình 2.3 – Giao diện đồ họa 2.1.3 Quản lí chương trình Một chức năng quan trọng của HĐH đó là quản lí dữ liệu và chương trình chạy trên nó. Khi người dùng mở một ứng dụng, thì CPU sẽ tải ứng dụng đó từ thiết bị lưu trữ vào bộ nhớ trong. Trước đây, máy tính cá nhân thường hay sử dụng các HĐH đơn nhiệm, cho phép người dùng chạy một ứng dụng tại một thời điểm. Hầu hết các loại điện thoại di động đều sử dụng HĐH đơn nhiệm. Chẳng hạn như, người dùng đang làm việc với chương trình chụp ảnh và muốn nhắn tin cho một người bạn thì họ phải tắt chương trình chụp ảnh trước. Để khắc phục nhược điểm đó, rất nhiều HĐH đa nhiệm ra đời, cho phép người dùng làm việc với nhiều ứng dụng cùng lúc. Khi máy tính đang chạy nhiều ứng dụng đồng thời, thì sẽ có một ứng dụng ở trạng thái kích hoạt và đang được sử dụng còn các ứng dụng còn lại ở trạng thái chạy nền. Trạng thái chạy nền là mức mà các ứng dụng không hiển thị ở màn hình chính nhưng vẫn tiếp tục thực thi các lệnh. 25 Hình 2.4 – Các chương trình chạy trên HĐH đa nhiệm 2.1.4 Quản lí bộ nhớ HĐH chịu trách nhiệm quản lí bộ nhớ để tối ưu hóa việc sử dụng bộ nhớ RAM. Cụ thể là HĐH sẽ tổ chức cấp phát và thu hồi vùng nhớ lưu trữ dữ liệu và các chỉ thị khi chúng đang được xử lí. Nếu máy tính chạy nhiều ứng dụng đồng thời, sẽ có lúc xảy ra tình trạng thiếu bộ nhớ. Ví dụ như: một trình duyệt web cần 128MB RAM, chương trình diệt virus cần 256MB RAM, chương trình chỉnh sửa hình ảnh cần 256MB RAM. Vậy tổng dung lượng cần thiết cho tất cả các ứng dụng là 640MB. Nhưng nếu, máy tính chỉ có 512MB bộ nhớ RAM thì HĐH phải sử dụng bộ nhớ ảo để giải quyết vấn đề này. Bộ nhớ ảo thực ra chính là một phần không gian của thiết bị lưu trữ, thường là ổ cứng, được HĐH phân bổ, có chức năng giống như RAM. Bên cạnh đó, người sử dụng HĐH Windows có thể sử dụng thẻ nhớ ngoài, hoặc USB làm bộ nhớ ảo vì tốc độ truy xuất thông tin nhanh hơn so với ổ cứng. 2.1.5 Điều phối tác vụ Mỗi tác vụ bao gồm các hoạt động như nhận dữ liệu từ thiết bị nhập, xử lí các chỉ thị, gửi thông tin ra thiết bị xuất, truyền dữ liệu từ thiết bị lưu trữ vào bộ nhớ trong và ngược lại. Nhiệm vụ của HĐH chính là xác định thứ tự thực hiện cho mỗi tác vụ dựa trên độ ưu tiên của nó. Tại mỗi thời điểm, một thiết bị chỉ có thể xử lí một tác vụ duy nhất nên nếu có nhiều tác vụ cần xử lí thì HĐH sẽ đưa toàn bộ chúng vào trong hàng đợi, và chờ tới lượt xử lí. Ta xét một ví dụ sau, máy in đang in một tài liệu A, sau đó ta cần in thêm 3 tài liệu khác. Lúc này, HĐH vẫn xử lí và thay vì gửi tới máy in ngay lập tức thì nó sẽ đưa 3 tài liệu này vào trong bộ đệm để chờ được chuyển tới máy in. 26 2.1.6 Cấu hình thiết bị Như đã giới thiệu ở chương trước, một máy tính là sự kết hợp của nhiều thiết bị khác nhau. Mỗi thiết bị đều có những đặc điểm, tính năng và một driver riêng biệt. Driver là một chương trình cung cấp các thông số của thiết bị, để giúp cho HĐH có thể nhận diện và giao tiếp với thiết bị đó. Khi bắt đầu khởi động máy tính, HĐH sẽ tải lên driver của từng thiết bị. Các thiết bị sẽ không hoạt động được nếu không có driver chính xác. Trong trường hợp, ta gắn một thiết bị mới vào máy tính, chẳng hạn như máy in hoặc máy quét thì driver của nó phải được cài đặt trước khi sử dụng. Ngày nay, rất nhiều HĐH đã tích hợp driver của các thiết bị khác nhau. HĐH sẽ tự động cấu hình thiết bị mới khi cài đặt nó và kiểm tra xung đột với các thiết bị khác. 2.1.7 Thiết lập kết nối internet Ngày nay, máy tính sẽ kém hữu dụng nếu không có kết nối internet. Vì vậy, HĐH cung cấp phương thức để một máy tính giao tiếp được với máy tính khác. Chẳng hạn như trong HĐH Windows 7, để thiết lập kết nối mạng ta có thể vào Control Panel  Network and Internet  Network and Sharing Center, rồi chọn “Set up a new connection or network”. Sau đó, dựa trên hướng dẫn của wizard ta có thể thiết lập kết nối thành công. 2.1.8 Giám sát hiệu năng máy tính HĐH thường tích hợp một chương trình giám sát hiệu năng. Chương trình này sẽ thực hiện đánh giá và báo cáo thông tin liên quan đến những tài nguyên và thiết bị khác nhau của máy tính. Ví dụ như, người dùng có thể theo dõi được bộ vi xử lí, ổ đĩa, mạng, và bộ nhớ đang được sử dụng như thế nào. Những thông tin trong báo cáo hiệu năng sẽ giúp cho người dùng hoặc người quản trị xác định được và giải quyết các vấn đề liên quan đến tài nguyên máy tính. Một vấn đề thường gặp là máy tính chạy cực chậm, nhờ vào chương trình giám sát hiệu năng, ta có thể xác định được bộ nhớ đang được sử dụng tối đa. Khi đó người dùng có thể nâng cấp bộ nhớ RAM cho máy tính. Hình 2.5 – Chương trình giám sát hiệu năng máy tính 27 2.1.9 Quản lí tập tin Một chức năng khá quan trọng của HĐH là tổ chức, quản lí tập tin (file) và thư mục (folder). Tập tin: là một tập hợp các thông tin được tổ chức lưu trữ thành một đơn vị độc lập. Mỗi tập tin gồm có 2 phần là tên và phần mở rộng được cách nhau bởi dấu (.). Đây là đơn vị nhỏ nhất được lưu trữ ở bộ nhớ ngoài. Dữ liệu sẽ không thể lưu ở bộ nhớ ngoài được nếu nó không nằm trong dạng tập tin. Tập tin có các thuộc tính như vị trí lưu trữ, kích thước, loại tập tin, thời gian được tạo ra, thời gian chỉnh sửa cuối cùng,... Hình 2.6 – Hiển thị các thuộc tính của các tập tin HĐH luôn theo dõi vị trí lưu trữ các tập tin trên bộ nhớ ngoài thông qua các loại hệ thống tập tin. Có hai loại hệ thống tập tin là FAT và NTFS. Đa số các HĐH hiện nay đều sử dụng loại NTFS vì những tính năng của nó mang lại độ tin cậy và bảo mật cao như khả năng chịu lỗi, cung cấp khả năng phục hồi tập tin nếu ổ cứng bị lỗi, cho phép thiết lập quyền truy cập đối với tập tin hoặc thư mục, Thư mục: HĐH cho phép tổ chức các tập tin thành từng nhóm, được gọi là thư mục để dễ dàng quản lí và truy xuất. Một thư mục có thể chứa một hoặc nhiều thư mục con. Các thư mục trên ổ đĩa được tổ chức một cách logic dưới dạng cây gọi là cây thư mục. Hệ thống quản lí tập tin cho phép người dùng thực hiện các thao tác trên tập tin và thư mục gồm tạo, sao chép, di chuyển, xóa, sắp xếp và chỉnh sửa tên, tìm kiếm. 2.1.10 Tự động cập nhật Ở hầu hết các HĐH hiện nay đều có tính năng tự động cập nhật bao gồm phiên bản mới của các phần mềm sau khi sửa lỗi hoặc bổ sung thêm chức năng mới, những thay đổi về driver của các thiết bị. Chẳng hạn như, cập nhật các phiên bản mới của trình duyệt web, chương trình diệt virus, Nhiều nhà cung cấp phần mềm cho phép tải miễn phí các phiên bản mới đối với những người dùng đã mua bản quyền. Tính năng tự động cập nhật sẽ đưa ra thông báo khi các bản cập nhật đã sẵn sàng, nếu người dùng đồng ý thi nó sẽ tự động tải về và cài đặt. 28 Hình 2.7 – Cài đặt cập nhật cho máy tính 2.1.11 Cung cấp cơ chế bảo vệ máy tính Cơ chế bảo vệ máy tính sẽ đảm bảo cho các tài nguyên của máy tính được sử dụng một cách nhất quán, ngăn chặn sự truy cập trái phép đến máy tính. Mỗi người dùng sẽ có một tài khoản riêng gồm tên và mật khẩu. HĐH thường cung cấp hai loại tài khoản là “administrator” và “guest”. Với tài khoản “administrator”, người dùng có tất cả các quyền gồm truy cập toàn bộ các tập tin và chương trình có trên máy tính, cài đặt phần mềm, tạo tài khoản mới, thực hiện các thiết lập trên máy tính. Ngược lại, với tài khoản “guest”, người dùng bị hạn chế quyền sử dụng các tài nguyên máy tính. Hình 2.8 – Quản lí tài khoản Bên cạnh cơ chế tài khoản người dùng, để bảo vệ dữ liệu khi truyền qua mạng internet, người quản trị có thể chỉ định cho HĐH mã hóa chúng thành dạng không thể đọc được. Người nhận dữ liệu muốn đọc được, cần phải biết cách giải mã dữ liệu đó. 29 2.2 Phân loại hệ điều hành Dựa trên nhiều tiêu chí khác nhau, HĐH có thể được phân loại như bảng sau: Tiêu chí phân loại Phân loại HĐH Số lượng người dùng (truy xuất tài nguyên) • HĐH đơn người dùng: chỉ cho phép một người dùng truy xuất đến tài nguyên máy tính tại một thời điểm. • HĐH đa người dùng: tài nguyên của máy tính có thể được chia sẻ cho nhiều người dùng khác nhau tại cùng một thời điểm. Loại máy tính • HĐH dành cho máy chủ • HĐH dành cho máy tính cá nhân • HĐH nhúng: dành cho các thiết bị di động hoặc hệ thống nhúng. Tác vụ • HĐH đơn nhiệm: mỗi lần chỉ thực hiện được một chương trình. • HĐH đa nhiệm: có thể thực hiện đồng thời nhiều chương trình. Bảng 2.1 – Phân loại hệ điều hành 2.3 Một số hệ điều hành phổ biến 2.3.1 Hệ điều hành Windows HĐH Windows của hãng Microsoft là HĐH được sử dụng phổ biến nhất trên thế giới cũng như ở Việt Nam. Windows đã có một quá trình phát triển khá dài từ những năm 80 cho tới nay. Những phiên bản đã và đang được sử dụng rộng rãi như Windows 98, Windows 2000, Windows XP, Windows Vista, Windows 7, Windows Server 2003, Windows Server 2008. Bên cạnh đó, những phiên bản mới nhất của Windows dành cho máy tính cá nhân, thiết bị di động và máy chủ cũng đã được phát hành như Windows 8, Windows Phone 8, Windows Server 2012 R2. HĐH Windows có khá nhiều ưu điểm nổi trội như giao diện trực quan, dễ sử dụng, phù hợp cho tất cả mọi người, có một số lượng lớn các phần mềm được viết cho Windows, hỗ trợ hầu hết các thiết bị phần cứng,... Tuy nhiên, nó cũng có những nhược điểm nhất định như người dùng cần phải trả phí khá cao khi sử dụng, độ tin cậy và bảo mật chưa cao, không phải là hệ thống mã nguồn mở 2.3.2 Hệ điều hành Linux Linux là HĐH mã nguồn mở khá nổi tiếng cho phép người dùng có thể xem và thay đổi mã nguồn của nó. Ngoài ra, nó còn có rất nhiều những ưu điểm khác như hỗ trợ một số phiên bản miễn phí hoặc giá thành thấp hơn nhiều so với Windows, phần lớn các phiên bản đều hoạt động ổn định trong thời gian dài mà không cần phải khởi động lại máy, khả năng bảo mật cao, phù hợp với nhiều người sử dụng khác nhau, Tuy nhiên, số lượng phần cứng được hỗ trở bởi Linux vẫn còn rất khiêm tốn so với Windows. Linux đầu tiên do Linus Torvalds viết vào năm 1991 dựa trên HĐH Unix. Linux gồm có một nhân kernel và bộ các ứng dụng của người dùng. Nhân Linux được 30 sử dụng trong nhiều bản phân phối phổ biến như Ubuntu, Debian, Google’s Android, Red Hat. 2.3.3 Hệ điều hành dành cho các thiết bị di động Đây là loại HĐH được cài đặt trên các thiết bị như điện thoại thông minh, máy tính bảng, PDA. Một số tính năng phổ biến của chúng là hỗ trợ đa tác vụ, duyệt Web, gửi và nhận email, đồng bộ hóa dữ liệu với máy tính cá nhân, hỗ trợ đọc các loại file khác nhau (.doc, .xls, .pdf,), cho phép người dùng cài đặt ứng dụng mới, Các HĐH dành cho thiết bị di động phổ biến nhất hiện nay là Android, iOS, Windows Phone, BlackBerry. 2.4 Các chương trình tiện ích của hệ điều hành Windows Chương trình tiện ích là một loại phần mềm thực hiện một tác vụ cụ thể, thường liên quan đến quản lí và bảo trì hệ thống máy tính. Hầu hết các HĐH đều tích hợp nhiều chương trình tiện ích khác nhau. Những chức năng mà chúng cung cấp như quản lí tập tin, tìm kiếm tập tin, xem ảnh, gỡ bỏ chương trình, dọn dẹp ổ đĩa, chống phân mảnh ổ đĩa, sao lưu dữ liệu, thiết lập chế độ lưu màn hình, nén tập tin, 2.4.1 Windows Explorer Windows Explorer là một chương trình quản lí tập tin trong HĐH Windows cho phép hiển thị các tập tin/thư mục và thực hiện các thao tác cơ bản trên chúng như tạo mới, sao chép, đổi tên, xóa, di chuyển, sắp xếp, tìm kiếm, Hình 2.9 – Tiện ích Windows Explorer 2.4.2 Tiện ích tìm kiếm dữ liệu Đây là một tiện ích hỗ trợ cho người dùng tìm kiếm các tập tin được lưu trữ ở những vị trí khác nhau trong máy tính. Nó sẽ tìm kiếm một hoặc nhiều tập tin dựa trên những tiêu chí do người dùng đưa ra. Những tiêu chí đó có thể là một từ hoặc một câu nào đó chứa trong tập tin, các thuộc tính của tập tin như ngày tạo, kích thước, tên và loại tập tin. 31 Hình 2.10 – Tiện ích dọn dẹp ổ đĩa 2.4.3 Chương trình dọn dẹp ổ đĩa Tiện ích này sẽ thực hiện tìm kiếm và xóa tất cả các tập tin không cần thiết khỏi ổ đĩa, chẳng hạn như tập tin đã bị xóa, tập tin chương trình không được sử dụng, Hình 2.11 – Tiện ích dọn dẹp ổ đĩa 2.4.4 Chương trình sao lưu và phục hồi dữ liệu Tiện ích sao lưu dữ liệu trong cho phép người dùng sao chép các tập tin hoặc toàn bộ đĩa cứng và lưu trữ ở một vị trí khác như đĩa cứng ngoài, CD/DVD, USB,Trong quá trình sao lưu, các tập tin có thể được nén lại để giúp thu nhỏ kích cỡ của chúng. Vì vậy, người dùng thường không thể sử dụng trực tiếp các tập tin ở dạng sao lưu. Trong trường hợp này, tiện ích phục hồi dữ liệu sẽ giúp giải nén và trả về dạng ban đầu cho chúng. Người dùng có thể đặt lịch biểu cho máy tính tự động sao lưu thường xuyên, tránh mất mát dữ liệu. 32 Hình 2.12 – Tiện ích sao lưu và phục hồi dữ liệu 2.4.5 Chương trình nén dữ liệu Nén dữ liệu là một phương pháp loại bỏ bớt một số thông tin dư thừa, cho phép giảm dung lượng của tập tin, giúp cải thiện tốc độ truyền tập tin qua mạng internet và chiếm ít không gian bộ nhớ hơn so với ban đầu. Nén dữ liệu được chia ra làm 2 loại là nén mất dữ liệu và nén không mất dữ liệu. Với kiểu nén mất dữ liệu thì dung lượng của các tập tin được giảm đáng kể, nhưng chất lượng của chúng cũng sẽ giảm và không thể khôi phục lại trạng thái như ban đầu. Kiểu nén này thường sử dụng để nén những tập tin hình ảnh hoặc video vì sự giảm sút nhỏ về chất lượng khó có thể nhận ra hoặc vẫn sử dụng được. Ngược lại, với kiểu nén không làm mất dữ liệu, người dùng có thể nhận lại được tập tin nguyên gốc sau khi giải nén. Với các loại tập tin văn bản thì việc ứng dụng kiểu nén này là hoàn toàn phù hợp. WinZip hoặc WinRAR là hai tiện ích nén dữ liệu thường được sử dụng trong HĐH Windows. 33 CÂU HỎI CHƯƠNG 2 Câu 1: Nêu khái niệm hệ điều hành? Có bao nhiêu loại HĐH? Hãy kể tên một số hệ điều hành được dùng phổ biến hiện nay? Câu 2: Hãy cho biết những chức năng chính của hệ điều hành là gì? Câu 3: Phân biệt các chế độ tắt máy tính? Câu 4: Phân biệt giao diện dòng lệnh và giao diện đồ họa? Câu 5: Nêu khái niệm tập tin và thư mục? Câu 6: Chương trình nào sau đây dùng để quản lí thư mục và tập tin? a. Windows Explorer b. Windows Accessories c. Microsoft Office d. Windows Control Panel Câu 7: Cho biết ưu và nhược điểm của HĐH Windows là gì? Câu 8: Những điểm vượt trội của HĐH Linux so với HĐH Windows là gì? Câu 9: Những chương trình tiện ích thường được tích hợp trong các HĐH là gì? Câu 10: Hãy cho biết cách thức tìm kiếm một tập tin bất kì được lưu trên ổ cứng của máy tính? 34 Chương 3 THUẬT TOÁN 3.1 Giới thiệu Trước hết, chúng ta hãy cùng xem xét bài toán thường gặp là tìm đường đi ngắn nhất từ địa điểm A đến địa điểm B. - Dữ kiện: Địa điểm A, B và bản đồ. - Yêu cầu: Tìm ra một đường đi ngắn nhất giữa hai địa điểm trên. Dễ thấy rằng, mỗi bài toán đặt ra luôn có hai thành phần cơ bản là các dữ kiện của bài toán và yêu cầu phải làm gì. Việc giải quyết bài toán nghĩa là từ các dữ kiện đã cho dùng một số hữu hạn các thao tác thích hợp để tìm ra kết quả theo yêu cầu của bài toán. Từ khi máy tính ra đời, với tốc độ và tính chính xác của mình, nó đã trở thành một công cụ hữu dụng trong việc giải quyết nhiều bài toán phức tạp. Tuy nhiên, bản thân máy tính chỉ là một thiết bị vật lí vô tri vô giác chỉ có khả năng thực hiện chính xác từng bước các chỉ thị được viết trong chương trình. Vì thế, bước đầu tiên quan trọng nhất mà con người cần phải làm đó là đưa ra cách giải quyết bài toán mà có thể “giao cho máy làm được”. Như vậy, trình tự các bước thực hiện để giải quyết một bài toán được gọi là một thuật toán. Thuật toán là sự thể hiện của phương pháp giải quyết tường minh một bài toán và là cơ sở để chuyển giao công việc cho máy tính. Lập trình chính là quá trình mã hóa thuật toán bằng cách sử dụng các ngôn ngữ lập trình để máy tính có thể hiểu và thực thi được. Không có thuật toán thì không thể có chương trình. Do đó, việc nghiên cứu các thuật toán hiệu quả đóng vai trò rất quan trọng đối với lĩnh vực khoa học máy tính. 3.2 Khái niệm thuật toán Thuật toán là thủ tục gồm một tập hợp hữu hạn các qui tắc, nhằm xác định một dãy hữu hạn các thao tác thực hiện trên các đối tượng dữ liệu đầu vào (input) để giải quyết một hoặc một lớp bài toán và thu được kết quả xác định (output). Ví dụ 1: Thuật toán Euclid là thuật toán tìm ước số chung lớn nhất (USCLN) của hai số nguyên dương a và b. - Input: a, b là số nguyên dương - Output: USCLN của a và b Thuật toán có thể được mô tả như sau:  Bước 1: Nếu a < b thì hoán vị hai số a, b cho nhau  Bước 2: Nếu b = 0 thì USCLN là a 35  Bước 3: Ngược lại, thì thực hiện o Tìm số dư r của phép chia a cho b o Gán a = b, b = r, rồi quay trở lại bước 2. Ví dụ 2: Thuật toán tìm phần tử lớn nhất trong một dãy hữu hạn các số nguyên. - Input: một dãy hữu hạn các số nguyên - Output: giá trị lớn nhất trong dãy Ta có thể mô tả thuật toán như sau:  Bước 1: Đặt giá trị lớn nhất max bằng số nguyên đầu tiên.  Bước 2: So sánh số nguyên kế tiếp trong dãy với giá trị max, nếu nó lớn hơn max thì ta gán max bằng số nguyên này.  Bước 3: Nếu trong dãy còn số nguyên chưa xét tới thì tiếp tục lặp lại bước 2.  Bước 4: Ngược lại thì dừng. Giá trị lớn nhất trong dãy chính là giá trị max. Các tính chất đặc trưng của thuật toán:  Dữ liệu đầu vào(Input): Mỗi thuật toán cần phải có một hoặc nhiều dữ liệu đầu vào.  Dữ liệu đầu ra(Output): Từ dữ liệu đầu vào, thuật toán xử lí và sẽ cho ra kết quả xác định thể hiện lời giải của bài toán.  Tính tổng quát: Thuật toán phải áp dụng để giải một lớp bài toán có dạng tương tự, chứ không phải chỉ áp dụng những bài toán cụ thể riêng lẻ.  Tính xác định: Các bước trong thuật toán phải rõ ràng, trật tự thực hiện phải xác định và là duy nhất. Như vậy, khi dùng thuật toán với cùng một dữ liệu đầu vào phải cho ra cùng một kết quả.  Tính dừng: Thuật toán phải cho ra kết quả sau một số hữu hạn các bước.  Tính hiệu quả: Một thuật toán được gọi là hiệu quả nếu nó đơn giản, dễ hiểu, thời gian thực hiện nhanh và chiếm ít bộ nhớ. 3.3 Các phương pháp biểu diễn thuật toán Mỗi thuật toán cần được biểu diễn sao cho người khác hoặc máy tính có thể hiểu và thực hiện được. Người ta thường diễn tả thuật toán sử dụng một trong các ngôn ngữ sau: - Ngôn ngữ tự nhiên (Liệt kê các bước thực hiện) - Ngôn ngữ lưu đồ (Sơ đồ khối) - Mã giả 36 3.3.1 Ngôn ngữ tự nhiên Với cách biểu diễn này, người ta sử dụng một loại ngôn ngữ tự nhiên (tiếng việt, tiếng anh, ) để liệt kê từng bước thực hiện của thuật toán. Cách biểu diễn này đơn giản, không đòi hỏi người viết và người đọc thuật toán phải nắm các kí hiệu và qui tắc. Tuy vậy, phương pháp này thường dài dòng, không thể hiện rõ cấu trúc của thuật toán, câu chữ mang nhiều ý nghĩa khác nhau nên dễ gây hiểu lầm. 3.3.2 Ngôn ngữ lưu đồ (Sơ đồ khối) Ngôn ngữ lưu đồ là một dạng sơ đồ biểu diễn trực quan luồng dữ liệu được xử lí trong hệ thống. Khi người đọc nhìn vào sơ đồ có thể thấy rõ các thao tác được thực hiện như thế nào và trình tự của chúng trong một hệ thống. Chính vì vậy, sơ đồ khối là một công cụ rất hữu dụng để diễn đạt thuật toán. Sơ đồ khối sử dụng một số ký hiệu hình học sau để diễn đạt: Bảng 3.1 – Các ký hiệu hình học trong sơ đồ khối Ví dụ: Biểu diễn thuật toán tìm giá trị lớn nhất của một dãy số nguyên a gồm N số: a0, a1, a2,, aN-1 37 Người ta thường sử dụng sơ đồ khối trong giai đoạn đầu của việc xây dựng giải pháp để giải quyết bài toán. Nó giúp cho lập trình viên hiểu được tính logic của những bài toán phức tạp, cũng như giúp họ phân tích vấn đề hiệu quả hơn. Ngoài ra, nó còn được sử dụng để gỡ lỗi chương trình. Tuy vậy, nó cũng có một số nhược điểm là phải vẽ nhiều làm mất thời gian, và nó sẽ trở nên quá cồng kềnh với các bài toán phức tạp. Đôi khi, một chút thay đổi trong các giải pháp có thể yêu cầu vẽ lại toàn bộ sơ đồ. 3.3.3 Mã giả Mã giả là một ngôn ngữ gần giống với ngôn ngữ lập trình. Nó sử dụng kết hợp ngôn ngữ tự nhiên, các ký hiệu toán học, và vay mượn một số cấu trúc của một ngôn ngữ lập trình nào đó để thể hiện thuật toán. Mã giả giúp cho người thiết kế và lập trình viên tập trung vào logic của thuật toán mà không cần quan tâm đến các chi tiết của cú pháp ngôn ngữ. Vì là mã giả nên nó không thể được thực thi trên máy tính và không có tiêu chuẩn chung trong việc viết mã giả. Mỗi tác giả có phong cách viết cho riêng mình, miễn là trình bày rõ ràng và họ thường kèm theo chú thích về cú pháp được sử dụng. Các cấu trúc thường gặp trong mã giả như: - Cấu trúc lựa chọn if (điều kiện) then (hành động) else (hành động) - Cấu trúc lặp while (điều kiện) do (hành động) 38 Ví dụ 1: Tìm số lớn nhất trong hai số a và b Ví dụ 2: In ra các số từ 1 đến 5 Nhập giá trị a, b; if (a ≥ b) then Xuất kết quả: số lớn nhất là a; else Xuất kết quả: số lớn nhất là b; a = 1; while (a != 6) do Xuất giá trị a; a = a + 1; 3.4 Các cấu trúc cơ bản Các nhà khoa học máy tính đã đưa ra 3 cấu trúc cơ bản để xây dựng thuật toán và chương trình có cấu trúc gồm: cấu trúc tuần tự, cấu trúc rẽ nhánh và cấu trúc lặp. Việc sử dụng các cấu trúc này sẽ làm cho chương trình hoặc thuật toán trở nên dễ hiểu, dễ gỡ lỗi và dễ thay đổi. 3.4.1 Cấu trúc tuần tự Cấu trúc tuần tự là một cấu trúc cơ bản nhất. Trong cấu trúc tuần tự, các bước được thực hiện theo một trình tự tuyến tính từ trên xuống, hết bước này đến bước khác. Mỗi bước thường thực hiện một trong số các thao tác cơ bản như: nhập dữ liệu, xuất kết quả, thực hiện các phép toán số học và phép gán. Sơ đồ khối thể hiện cấu trúc tuần tự: Ví dụ 1: Tính S = 22 yx CByAx   , trong đó x, y ≠ 0. - Input: A, B, C, x, y - Output: giá trị S 39 Ví dụ 2: Tính tổng trung bình của 3 số nguyên a, b, c. - Input: 3 số nguyên a, b, c - Output: tổng trung bình của 3 số 3.4.2 Cấu trúc rẽ nhánh Trong một số thuật toán, việc thực hiện các bước cần phải được chọn lựa dựa vào một điều kiện xác định. Điều kiện ở đây là một biểu thức logic, có hai giá trị là true (T) và false (F). Tùy thuộc vào kết quả kiểm tra điều kiện mà việc thực hiện thuật toán có thể rẽ theo một trong hai nhánh khác nhau. Trong cấu trúc rẽ nhánh, ngoài các thao tác cơ bản như trong cấu trúc tuần tự, nó còn thực hiện thao tác so sánh hai giá trị. 40 Cấu trúc rẽ nhánh có thể được biểu diễn bằng sơ đồ khối trong hai trường hợp sau: Ví dụ 1: Vẽ sơ đồ thuật toán để giải phương trình ax + b = 0 - Input: hệ số a, b - Output: nghiệm x của phương trình Ví dụ 2: Vẽ sơ đồ thuật toán kiểm tra một số nguyên a là số chẵn hay là số lẻ. 41 3.4.3 Cấu trúc lặp Cấu trúc lặp là cấu trúc cho phép một hoặc một chuỗi các tác vụ/hành động được thực hiện lặp lại nhiều lần. Trong đó, số lần lặp phải là hữu hạn và có thể xác định hoặc không xác định trước. Vòng lặp với số lần lặp không xác định sẽ dừng khi điều kiện kết thúc thỏa mãn. Nhưng người thiết kế thuật toán phải chắc chắn rằng điều kiện kết thúc sẽ được thỏa mãn sau một số hữu hạn lần lặp, nếu không sẽ gây ra vòng lặp chạy vô hạn và thuật toán không kết thúc được. Điều kiện kết thúc có thể được xét trước hoặc sau khi thực hiện mỗi vòng lặp để quyết định có tiếp tục vòng lặp tiếp theo hay không. Cấu trúc lặp có thể được biểu diễn bằng sơ đồ khối như sau: 42 Ví dụ 1: Tính tổng S = 1 + 2 + + N. - Input: giá trị N - Output: tổng S Mô tả thuật toán:  Bước 1: Nhập giá trị cho N  Bước 2: Kiểm tra giá trị N > 0 o Nếu điều kiện sai thì quay lại bước 1 o Nếu điều kiện đúng thì chuyển sang bước 3  Bước 3: o Khởi tạo biến S = 0 o Sử dụng biến chạy i để điều khiển vòng lặp. Giá trị của nó sẽ thay đổi qua mỗi vòng lặp và thường được dùng để quyết định kết thúc vòng lặp. Vì tổng S được tính từ 1 đến N nên ta sẽ khởi tạo i = 1  Bước 4: Kiểm tra điều kiện i <= N o Nếu điều kiện đúng thì thực hiện gán S = S + i, và tăng giá trị của i: i = i + 1, rồi quay về đầu bước 4. o Nếu điều kiện sai: chuyển sang bước 5  Bước 5: xuất giá trị tổng S Sơ đồ khối thể hiện thuật toán: 43 Ví dụ 2: Cho số tự nhiên N. Tính N!. - Input: giá trị N - Output: giai thừa của N Mô tả thuật toán:  Bước 1: Nhập giá trị cho N  Bước 2: Kiểm tra điều kiện N < 0 o Nếu điều kiện sai thì chuyển sang bước 3 o Ngược lại, xuất “N phải là một số không âm”, rồi kết thúc thuật toán  Bước 3: GT = 1, i = N  Bước 4: Kiểm tra điều kiện i > 1 o Nếu điều kiện đúng thì thực hiện gán GT = GT*i, và giảm giá trị của i: i = i - 1, rồi quay về đầu bước 4. o Nếu điều kiện sai: chuyển sang bước 5  Bước 5: Xuất giá trị GT Sơ đồ khối thể hiện thuật toán: 44 BÀI TẬP CHƯƠNG 3 Hãy vẽ sơ đồ khối để biểu diễn thuật toán giải quyết các bài tập sau đây: Bài 1. Tính P(n) = 1.3.5(2n+1), với n ≥ 0 Bài 2. Cho n là số nguyên dương, x là số thực. Tính tổng: a. S(n) = ix i x in i sin 12 12 1     b. S(n) = 12 1... 5 1 3 11   n Bài 3. Cho một năm bất kỳ nào đó. Kiểm tra xem năm này có phải là năm nhuận hay không? Biết rằng, năm nhuận là năm chia hết cho 4 nhưng không chia hết cho 100 hoặc là chia hết cho 400. Bài 4. Cho 3 cạnh a, b, c. Kiểm tra xem có tồn tại tam giác được tạo thành từ 3 cạnh này không? Nếu có, hãy tính diện tích của tam giác. Bài 5. Tìm tất cả các số lẻ nằm trong đoạn từ 0 đến 1000. Bài 6. Cho một dãy số nguyên a0, a1, a2,, an-1. Tính trung bình cộng các số chia hết cho 3. Bài 7. Cho số nguyên n. Tính trị tuyệt đối của n. Bài 8. Trong trang trại của một nông dân có nuôi một số gà và dê. Biết rằng, có tất cả 43 đầu và 108 chân. Hỏi trang trại có bao nhiêu con gà và bao nhiêu con dê? Bài 9. Tính lương của nhân viên dựa vào lương_theo_ngày và số_ngày_công như sau: lương = lương_ theo_ngày * số_ngày_công Nếu số_ngày_công > 25, thì số ngày làm dư sẽ được tính lương gấp đôi. Bài 10. Nhân viên của một siêu thị thực hiện sắp xếp N quả trứng (N > 0) vào trong từng hộp, mỗi hộp có 12 quả trứng. Hỏi có bao nhiêu hộp trứng và bao nhiêu trứng còn dư? Ví dụ: với 43 quả trứng, nhân viên sẽ sắp xếp được 3 hộp trứng và còn thừa lại 7 quả trứng. 45 PHẦN 2 NGÔN NGỮ LẬP TRÌNH C 46 MỞ ĐẦU Máy tính là một công cụ hỗ trợ cho con người để giải quyết các bài toán một cách nhanh chóng và chính xác. Quá trình giải quyết một bài toán bất kì nào đó trên máy tính đều phải trải qua những bước cơ bản như phân tích và xác định vấn đề, thiết kế thuật toán, lập trình, kiểm thử kết quả. Trong đó, lập trình là khâu chuyển đổi các bước trong thuật toán thành những chỉ thị (lệnh) mà máy tính có thể hiểu và thực thi được. Khi lập trình, lập trình viên sẽ biên soạn mã nguồn, biên dịch mã nguồn thành chương trình, thực thi (chạy) chương trình. Mã nguồn của chương trình phải được viết bằng các ngôn ngữ lập trình. Giống như tất cả các ngôn ngữ mà con người sử dụng, ngôn ngữ lập trình cũng bao gồm một tập hợp các kí tự, các từ và các quy tắc về cú pháp. Ngôn ngữ lập trình thường được chia làm 3 loại:  Ngôn ngữ máy/mã máy (machine language): là một loại ngôn ngữ lập trình mà mọi chỉ thị đều được biểu diễn bằng chuỗi số nhị phân 0 và 1. Đây là ngôn ngữ thế hệ đầu tiên. Tuy khó đọc, khó sử dụng, và phụ thuộc nhiều vào phần cứng của máy tính, tuy nhiên ưu điểm của ngôn ngữ máy là được máy tính thực thi một cách trực tiếp.  Ngôn ngữ bậc thấp (assembly language): là ngôn ngữ thuộc thế hệ thứ hai, được thiết kế gần gũi hơn với con người bằng cách sử dụng các kí tự và từ có tính gợi nhớ để thay thế các chữ số nhị phân. Tuy nhiên, chương trình được viết bằng ngôn ngữ bậc thấp vẫn còn liên quan chặt chẽ đến kiến trúc của máy tính nên chỉ thường được sử dụng để viết những chương trình nhỏ, cần tối ưu bộ nhớ và thời gian xử lí.  Ngôn ngữ bậc cao (high-level language): gần với ngôn ngữ tự nhiên nhất, giúp cho việc lập trình trở nên đơn giản hơn nhiều. Khác với ngôn ngữ máy và ngôn ngữ bậc thấp, chương trình viết bằng ngôn ngữ bậc cao có thể chạy được trên nhiều máy tính khác nhau. Hiện nay, có rất nhiều ngôn ngữ bậc cao đã được phát triển và sử dụng phổ biến như Pascal, C/C++/C#, Visual Basic, Java, Python, Trong ba loại ngôn ngữ trên, chỉ có ngôn ngữ máy là ngôn ngữ duy nhất mà máy tính có thể hiểu được. Vì thế, một chương trình được viết bằng ngôn ngữ bậc thấp hoặc bậc cao đều phải được biên dịch sang ngôn ngữ máy. Công cụ thực hiện biên dịch được gọi là chương trình dịch. Trong môn học này, C được chọn làm ngôn ngữ thể hiện. Đây là ngôn ngữ cơ bản, được sử dụng rộng rãi ở khắp nơi và là nền tảng cho người học tiếp tục tìm hiểu những ngôn ngữ khác. 47 Chương 1 TỔNG QUAN VỀ NGÔN NGỮ LẬP TRÌNH C 1.1 Giới thiệu ngôn ngữ C 1.1.1 Lịch sử phát triển C là một ngôn ngữ lập trình cấu trúc do Brian W.Kernighan và Dennis Ritchie phát triển từ đầu những năm 1970 và hoàn thành vào năm 1972. Nó có nguồn gốc từ ngôn ngữ BCPL và ngôn ngữ B. Ban đầu, ngôn ngữ C được phát triển để viết HĐH, sau đó nó đã được sử dụng rộng rãi để viết nhiều ứng dụng như xử lí văn bản, xử lí dữ liệu, đồ họa. Năm 1978, cuốn sách “The C Programming Language” được xuất bản lần đầu tiên để giới thiệu ngôn ngữ C. Trong những năm 1980, việc sử dụng C lan truyền rộng rãi, trình biên dịch C đã có sẵn ở hầu hết các máy tính và HĐH. Tuy nhiên, với sự lan truyền mạnh mẽ thì ngôn ngữ C bắt đầu bị thay đổi, bổ sung một số tính năng mới và bỏ đi một số tính năng cũ sao cho phù hợp với từng nền tảng riêng. Vì thế, ngôn ngữ C tồn tại dưới nhiều phiên bản khác nhau. Mùa hè năm 1983, việc chuẩn hóa ngôn ngữ C đã bắt đầu được phát triển dưới sự điều hành của Viện tiêu chuẩn quốc gia Hoa Kỳ (American National Standards Institute -ANSI). Đến năm 1989, phiên bản chuẩn hóa ANSI C đã được hoàn thành và công bố trong lần xuất bản thứ hai của cuốn “The C Programming Language”. Trong phiên bản chuẩn hóa quy định các thư viện chuẩn cho ngôn ngữ C với đầy đủ các hàm dùng để thực hiện chức năng xuất/nhập dữ liệu, quản lý bộ nhớ, xử lí chuỗi, Tất cả các phiên bản của ngôn ngữ C hiện nay đều tuân theo các mô tả trong chuẩn ANSI C, sự khác biệt chủ yếu giữa chúng là nằm ở việc đưa vào một số thư viện bổ sung vào thư viện chuẩn của C. C không phải là một ngôn ngữ mạnh, nhưng nó có tầm ảnh hưởng rất lớn đến các ngôn ngữ hiện đại khác như C++, C#, Objective-C, Java, Perl, Python, Những ngôn ngữ này đều kế thừa hoặc vay mượn nhiều tính năng từ ngôn ngữ C. Chẳng hạn như, C++ bao gồm tất cả các tính năng của ngôn ngữ C và bổ sung thêm một số tính năng khác để hỗ trợ lập trình hướng đối tượng. Vì vậy, C được xem như là một ngôn ngữ cơ bản mà tất cả các lập trình viên đều nên biết. 1.1.2 Đặc điểm của ngôn ngữ C Ngôn ngữ C có những đặc điểm cơ bản sau: - Là một ngôn ngữ lập trình đa dụng, bậc cao nhưng hỗ trợ khả năng lập trình bậc thấp, ví dụ như thao tác trên bit và trên địa chỉ. Vì thế, nó là một ngôn ngữ phù hợp cho lập trình hệ thống. - C là một ngôn ngữ lập trình cấu trúc, cho phép lập trình viên có thể chia chương trình C ra làm nhiều module và hàm, hỗ trợ tái sử dụng mã nguồn. Cấu trúc module làm cho chương trình dễ gỡ lỗi, dễ kiểm tra, và dễ bảo trì hơn. 48 - Ngôn ngữ C chỉ có 32 từ khóa chuẩn, nhưng lại có một số lượng lớn các toán tử logic và số học. - Một trong những thế mạnh của ngôn ngữ C là tính khả chuyển cao. Với bộ thư viện chuẩn và có sẵn trình biên dịch cho hầu hết các hệ điều hành và nền tảng phần cứng giúp cho các chương trình viết bằng ngôn ngữ C ít thay đổi trên các hệ thống máy tính khác nhau. - Ngôn ngữ C rất linh động về ngữ pháp, nó có thể chấp nhận nhiều cách thể hiện khác nhau cũng như những thao tác mà có thể không hợp lệ ở các ngôn ngữ khác. Chẳng hạn như, C cho phép cộng một ký tự với một số nguyên. - Quá trình dịch và thực thi chương trình C khá nhanh so với những ngôn ngữ khác. Ngoài ra, trong ngôn ngữ C có sẵn các hàm quản lí bộ nhớ giúp tiết kiệm bộ nhớ, nâng cao hiệu quả của chương trình. - Ngôn ngữ C có phân biệt chữ hoa và chữ thường. 1.2 Các thành phần cơ bản của ngôn ngữ C 1.2.1 Bộ ký tự Một chương trình bất kỳ của mọi ngôn ngữ lập trình đều được tạo nên từ tập hợp các câu lệnh. Mỗi câu lệnh là sự kết hợp của các từ theo qui tắc cấu trúc ngữ pháp xác định, trong đó mỗi từ được cấu thành từ bộ ký tự riêng của mỗi ngôn ngữ. Bộ ký tự trong ngôn ngữ C được chia thành các loại sau: - Chữ cái: AZ và az - Chữ số: 09 - Các ký hiệu toán học: + - * / = > < - Các dấu ngăn cách: , . ; : space tab - Các dấu ngoặc: ( ) [ ] { } - Các ký tự đặc biệt: # % ? $ & ^ ! ~ _ ‘ “ | \ / @ Lưu ý: Trình biên dịch sẽ bỏ qua kí tự khoảng trắng (space) nếu nó không nằm trong một hằng chuỗi. Người ta thường dùng khoảng trắng để tách từ nhưng không được phép dùng nó chen giữa các kí tự trong từ khóa hoặc định danh. 1.2.2 Từ khóa Từ khóa (Keyword) là những từ đã được định nghĩa sẵn trong mỗi ngôn ngữ. Mỗi từ khóa có một ý nghĩa xác định và chúng ta không thể thay đổi nó. Từ khóa thường được sử dụng dành riêng cho mục đích xác định như đặt tên cho các kiểu dữ liệu, mô tả lệnh và các cấu trúc điều khiển. 49 Dưới đây là bộ từ khóa của ngôn ngữ C: auto const double float int short struct unsigned break continue else for long signed switch void case default enum goto register sizeof typedef volatile char do extern if return static union while Bảng 1.1 – Bộ từ khóa trong C Khi sử dụng các từ khóa trong C cần phải chú ý những điểm sau: - Các từ khóa trong C phải được viết bằng chữ thường - Không thể sử dụng từ khóa cho mục đích khác như đặt tên cho biến, hằng, mảng, hàm,... 1.2.3 Định danh(tên) Định danh là một dãy kí tự dùng để gọi tên các đối tượng trong chương trình như biến, hằng, hàm, mảng, Khi đặt tên cho một đối tượng, người lập trình cần đặt sao cho phù hợp với ý nghĩa sử dụng của nó, làm cho chương trình dễ hiểu hơn. Một số qui tắc cần tuân theo khi đặt tên trong C: - Chỉ được sử dụng các ký tự gồm chữ cái (A..Z,a..z), chữ số (0..9) và dấu gạch dưới ‘_’. - Không được bắt đầu bằng chữ số, không được trùng với từ khóa. - Ngôn ngữ C phân biệt chữ hoa và chữ thường nên sum và SUM là hai định danh khác nhau hoàn toàn. Mặc dù không bắt buộc, nhưng thông thường thì chữ thường được dùng cho tên biến, tên hàm, tên mảng còn chữ hoa dùng cho tên hằng số. Ví dụ về các định danh hợp lệ:  Biến: i, j, count, top_of_page, name, emp_number, temp1  Hàm: sort, getValue, addition, isContain  Hằng: PI, MAX, MIN Ví dụ về các định danh không hợp lệ:  for : định danh trùng với từ khóa  3g, 9PI: định danh bắt đầu bằng chữ số  search elem, tong#le: định danh chứa ký tự không hợp lệ (khoảng trắng, #). 50 1.2.4 Các kiểu dữ liệu cơ sở Một kiểu dữ liệu được xác định bởi một tập hợp hữu hạn các giá trị mà mỗi dữ liệu thuộc kiểu đó có thể nhận được cùng với một số phép toán có thể thực hiện được trên kiểu dữ liệu đó. Kiểu dữ liệu gắn liền với biến hoặc hằng số để xác định số lượng byte cần cấp phát cho chúng. Các kiểu dữ liệu cơ sở trong ngôn ngữ C gồm: kiểu số nguyên, kiểu số thực, kiểu kí tự, kiểu luận lý và kiểu void. a. Kiểu số nguyên Kiểu số nguyên bao gồm số nguyên có dấu và số nguyên không dấu. Kích thước của biến số nguyên phụ thuộc vào phần cứng và hệ điều hành của máy. Ví dụ, kiểu số nguyên int trên hệ điều hành 16-bit có kích thước là 2 bytes, còn trong hệ điều hành 32-bit có kích thước 4 bytes. Như vậy, dựa vào kích thước của mỗi kiểu số nguyên, ta có thể xác định được miền giá trị mà dữ liệu thuộc kiểu đó có thể nhận được. Các kiểu số nguyên có dấu trong hệ thống 16-bit: Kiểu (Type) Kích thước (Byte) Miền giá trị (Range) char 1 –128  +127 int 2 –32.768  +32.767 short 2 –32.768  +32.767 long 4 –2.147.483.648  +2.147.483.647 Bảng 1.2 – Các kiểu số nguyên có dấu trong hệ thống 16-bit Các kiểu số nguyên không dấu trong hệ thống 16-bit: Kiểu (Type) Kích thước (Byte) Miền giá trị (Range) unsigned char 1 0  255 unsigned int 2 0  65.535 unsigned short 2 0  65.535 unsigned long 4 0  4.294.967.295 Bảng 1.3 – Các kiểu số nguyên không dấu trong hệ thống 16-bit Với kích thước n bits, nếu là kiểu số nguyên có dấu thì miền giá trị sẽ nằm trong khoảng từ 2n-1  2n-1 – 1, còn nếu là kiểu số nguyên không dấu thì miền giá trị sẽ nằm trong khoảng từ 0  2n – 1. b. Kiểu số thực Kiểu số thực (kiểu dấu phẩy động) là kiểu dữ liệu dùng để lưu trữ các giá trị thực. Ngôn ngữ C hỗ trợ 2 kiểu dấu phẩy động là float và double. Trong đó, kiểu double có độ chính xác cao hơn so với kiểu float. 51 Bảng dưới đây thể hiện mối quan hệ giữa độ chính xác xấp xỉ, kích thước và miền giá trị của các kiểu số thực: Kiểu (Type) Độ chính xác (Decimal digits) Kích thước (Byte) Miền giá trị (Range) float 6 – 7 4 3.4*10 –38  3.4*10 38 double 15 – 16 8 1.7*10 –308 1.7*10 308 Bảng 1.4 – Các kiểu số thực Như vậy, nếu độ chính xác không quan trọng bằng kích thước lưu trữ thì ta nên sử dụng kiểu float. Ngược lại, nếu độ chính xác là tiêu chí quan trọng nhất, thì nên sử dụng kiểu double. c. Kiểu kí tự Kiểu kí tự char cho phép lưu trữ một kí tự đơn. Mỗi kí tự sẽ được biểu diễn bằng một giá trị số nguyên 8 bit trong máy tính. Giá trị số nguyên này chính là mã ASCII của kí tự đó. Vì vậy, ta có thể xem kiểu kí tự chính là một kiểu số nguyên. Ví dụ, lưu giá trị 65 tương ứng với kí tự ‘A’, giá trị 97 tương ứng với kí tự ‘a’. d. Kiểu luận lý Ngôn ngữ C không hỗ trợ kiểu logic (boolean của Pascal) mà chỉ quan niệm ngầm định rằng giá trị 0 tương ứng là false (sai), ngược lại giá trị khác 0 tương ứng là true (đúng). Kiểu luận lý được áp dụng khi xét giá trị của các biểu thức logic. Ví dụ: (1 > 2) có giá trị là false (0). e. Kiểu void Kiểu dữ liệu void là kiểu dữ liệu đặc biệt không lưu trữ giá trị nào cả. Nên người ta thường không sử dụng nó để khai báo biến giống như các kiểu số nguyên hay số thực. Kiểu dữ liệu này thường được sử dụng làm kiểu trả về cho hàm hoặc để khai báo con trỏ. Chẳng hạn như, trong chương trình C ta có thể khai báo hàm main() với kiểu trả về là void vì nó không cần trả về giá trị nào cả. 1.2.5 Biến Biến là một đại lượng dùng để lưu trữ giá trị dữ liệu trong bộ nhớ. Biến cho phép cung cấp một tên có ý nghĩa cho mỗi vị trí ô nhớ. Thông qua tên biến, ta có thể truy cập đến các giá trị cụ thể trong ô nhớ mà không cần biết địa chỉ của chúng. HĐH sẽ đảm nhận việc cấp phát ô nhớ còn trống cho mỗi biến. Biến có thể lưu trữ dữ liệu thuộc nhiều kiểu khác nhau như số thực, số nguyên, kí tự, Giá trị của biến có thể thay đổi trong chương trình, nhưng tại mỗi thời điểm một vị trí ô nhớ chỉ có thể lưu trữ một giá trị duy nhất. Cú pháp khai báo biến: kiểu_dữ _liệu tên_biến; 52 Ví dụ: int n; float phi; Trong trường hợp cần khai báo nhiều biến có cùng kiểu, ta có thể sử dụng cú pháp sau: kiểu_dữ _liệu tên_biến1, tên_biến2,; Ví dụ: float delta, result; Cần lưu ý rằng, việc khai báo biến chỉ mới báo cho trình biên dịch biết được kích thước của giá trị mà biến có thể lưu trữ, chứ lúc này bộ nhớ vẫn chưa được cấp phát. Vì vậy, cần phải khởi tạo giá trị ban đầu cho biến: kiểu_dữ _liệu tên_biến = giá_trị_khởi_tạo; Ví dụ: int x = 5, y; /* Khởi tạo giá trị ban đầu cho biến x */ x = 6; /* Gán giá trị khác cho biến x */ y = 7; /* Gán giá trị cho biến y sau khi khai báo */ Sau khi biến có giá trị xác định, thì nó sẽ được cấp phát một vùng nhớ có kích thước tương ứng với kiểu của biến. Mỗi biến có một địa chỉ là địa chỉ của vùng nhớ chứa biến đó. Để lấy ra địa chỉ của biến ta sử dụng toán tử lấy địa chỉ ‘&’ đặt trước tên biến: &tên_biến Lưu ý: - Biến phải được khai báo trước khi sử dụng. - Kiểu dữ liệu của biến không được thay đổi trong toàn bộ chương trình. - Tên biến nên đặt có ý nghĩa, phù hợp với mục đích sử dụng và tuân theo các qui tắc đặt tên định danh đã nêu ở mục trước. - Theo chuẩn ANSI C, vị trí khai báo các biến phải được đặt ngay sau dấu ‘{‘ đầu tiên của thân hàm hoặc của khối lệnh. 1.2.6 Hằng Hằng là cũng đại lượng giống như biến, chỉ khác là giá trị của nó không thay đổi trong quá trình chương trình thực hiện. Hằng thường được dùng để thay thế cho một giá trị lặp lại nhiều lần trong chương trình, giúp dễ dàng thay đổi mã nguồn cũng như cung cấp một cái tên có ý nghĩa cho giá trị đó. Hằng được chia ra làm 4 loại gồm hằng số nguyên, hằng số thực, hằng kí tự, và hằng chuỗi. a. Hằng số nguyên Trong ngôn ngữ C, hằng số nguyên có thể được biểu diễn dưới 3 dạng sau: - Dạng thập phân: số nguyên được biểu diễn bởi tập hợp các chữ số từ 0 đến 9, trong đó chữ số đầu tiên phải khác 0. 53 - Dạng bát phân: số nguyên được biểu diễn bởi tập hợp các chữ số từ 0 đến 7 và thêm tiền tố 0 ở đầu. - Dạng thập lục phân: số nguyên được biểu diễn bởi tập hợp các chữ số từ 0 đến 9, và các chữ cái A đến F hoặc a đến f. Ngoài ra, bổ sung thêm tiền tố 0x hoặc 0X ở đầu. Ví dụ: Dạng thập phân Dạng bát phân Dạng thập lục phân 10 012 0xa or 0xA 132 0204 0x84 32179 076663 0x7dB3 or 0X7DB3 Ngoài ra, để biểu diễn các hằng kiểu long, unsigned, hoặc unsigned long người ta thường thêm hậu tố L hoặc l, U hoặc u, UL hoặc ul vào cuối giá trị nguyên. Ví dụ: - Hằng số nguyên kiểu unsigned int: 5000u, 1000U - Hằng số nguyên kiểu long: -300L, 32767L b. Hằng số thực Hằng số thực có thể được viết theo hai dạng: - Dấu phẩy tĩnh (dạng thập phân): [dấu] [phần nguyên] . [phần thập phân] Trong đó, phần nguyên hoặc phần thập phân có thể vắng. - Dấu phẩy động (dạng số mũ): số thực gồm phần định trị và phần bậc. Hai phần này cách nhau bởi ký tự e hoặc E. Dạng này được sử dụng khi hằng số thực quá nhỏ hoặc quá lớn. Ví dụ: Số thực dấu phẩy tĩnh Số thực dấu phẩy động 15.75 1.575E1 hoặc 1575e-2 -0.0025 -2.5e-3 .75 .0075e2 hoặc 75e-2 Hằng số thực có thể thuộc các kiểu float, double. Để phân biệt giữa các kiểu, người ta thường thêm các hậu tố f, F vào cuối của giá trị thực. Ví dụ: Hằng số thực float: 100F 54 c. Hằng kí tự Hằng kí tự là kí tự đơn nằm trong cặp dấu nháy đơn. Mỗi hằng kí tự sẽ có giá trị là mã ASCII của nó, ví dụ như kí tự ‘A’ có mã là 65. Một hằng kí tự không được có độ dài lớn hơn 1. Đối với một số hằng kí tự đặc biệt, ta có thể biểu diễn ở dạng ‘\c’. Những kí tự này sẽ không được in ra hoặc hiển thị trực tiếp. Dưới đây là một số những kí tự đặc biệt trong C: Kí tự Cách biểu diễn Mã ASCII Kí tự kết thúc chuỗi ‘\0’ 0 Kí tự xuống dòng ‘\n’ 10 Kí tự về đầu dòng ‘\r’ 13 Kí tự tab ‘\t’ 9 Dấu gạch chéo \ ‘\\’ 92 Dấu nháy đơn ‘ ‘\’’ 39 Dấu nháy kép “ ‘\”’ 34 Hằng kí tự có thể tham gia vào các phép toán số học như mọi số nguyên khác. Chẳng hạn như: ‘8’ - ’6’ = 56 – 54 = 2. d. Hằng chuỗi Hằng chuỗi là một chuỗi các kí tự nằm trong cặp dấu nháy kép. Những kí tự trong một chuỗi có thể là chữ cái, chữ số, dấu cách trắng, và các kí tự đặc biệt. Ví dụ: “Hello ! World” , “C programming language”, “1987”, Đối với một chuỗi quá dài, nó có thể được viết trên nhiều dòng sử dụng kí tự ‘\’. Ví dụ: “This is a very long\ string\n”; Chuỗi kí tự được lưu trữ thành một mảng các kí tự đơn trong bộ nhớ và được kết thúc bởi kí tự NUL (‘\0’). Lưu ý: hằng chuỗi “A” khác với hằng kí tự ‘A’. Kí tự ‘A’ có giá trị tương ứng là 65, nhưng chuỗi “A” không có giá trị gì cả. Ở dạng lưu trữ, ta thấy tận cùng của hằng chuỗi có ký tự NUL mà hằng kí tự không có , nên tồn tại chuỗi rỗng “”, chứ không có ký tự rỗng ‘’. Ngôn ngữ C hỗ trợ hai cách khai báo hằng đó là dùng từ khóa const hoặc chỉ thị tiền xử lí #define. Khai báo với từ khóa const: const kiểu_dữ _liệu tên_hằng = giá_trị; Trong khai báo ở trên, giá_trị của đối tượng tên_hằng phải luôn luôn được xác định ngay tại thời điểm khai báo. 55 Ví dụ: const double PI = 3.14159; Chỉ thị tiền xử lí #define là một cách khác linh động hơn để định nghĩa hằng trong chương trình: #define tên_hằng giá_trị Lưu ý: Không có dấu chấm phẩy ở cuối chỉ thị #define. Cách khai báo hằng này thường đặt ở đầu chương trình, nhưng chúng ta có thể đặt nó ở bất kì vị trí nào miễn là trước khi nó được sử dụng. Khi thực hiện biên dịch chương trình, tất cả các vị trí sử dụng tên_hằng sẽ được thay thể bởi giá_trị. Vì vậy, tên_hằng được xem như là hằng kí hiệu thay cho một giá trị hằng. Kiểu dữ liệu của hằng sẽ được trình biên dịch xác định dựa vào giá_trị. Ví dụ: #define PI 3.14159 1.2.7 Hàm Hàm là một đơn vị độc lập của chương trình, được thiết kế để thực hiện một tác vụ cụ thể. Mỗi hàm chứa các khai báo và nhóm các câu lệnh theo một trình tự logic. Tất cả các chương trình C đều sử dụng hàm để tăng khả năng tái sử dụng, tính dễ hiểu, dễ theo dõi cho chương trình. Trong thư viện của C đã định nghĩa sẵn một số lượng lớn các hàm thực hiện chức năng khác nhau. Các hàm thư viện này đều được khai báo trong các tập tin tiêu đề. Để sử dụng chúng, ta chỉ cần khai báo tập tin tiêu đề ở đầu chương trình. Ví dụ, để sử dụng các hàm toán học thì ta khai báo: #include . Một số hàm toán học thường được sử dụng trong C: Hàm Kiểu tham số Kiểu trả về Ý nghĩa Ví dụ sqrt(x) double double Căn bậc 2 của x sqrt(9.0) = 3.0 pow(x,y) double double x mũ y pow(2.0 , 3.0) = 8.0 abs(x) double double Trị tuyệt đối của x abs(-9) = 9 exp(x) double double e mũ x exp(1.0) = 2.718282 log(x) double double Logarithm tự nhiên cơ số e của x log(2.718282) = 1.0 log10(x) double double Logarithm tự nhiên cơ số 10 của x log10(100.0) = 2.0 sin(x) double double sine của x sin(1.0) = 0.841471 cos(x) double double cosine của x cos(1.0) = 0.540302 ceil(x) double double Phần nguyên nhỏ nhất không nhỏ hơn x ceil(2.3) = 3.0 ceil(-2.3) = -2.0 floor(x) double double Phần nguyên lớn nhất không lớn hơn x floor(2.3) = 2.0 floor(-2.3) = -3.0 56 1.2.8 Biểu thức Biểu thức là một chuỗi gồm các toán hạng và toán tử được kết hợp với nhau. Cần chú ý rằng, đối với các biểu thức phức gồm sự kết hợp của nhiều toán tử và toán hạng với nhau thì nên sử dụng dấu ngoặc đơn để đảm bảo trình tự của các phép toán trong biểu thức được thực hiện đúng. Mỗi toán hạng có thể là hằng, biến, lời gọi hàm, hoặc biểu thức con. Toán tử tác động lên giá trị của toán hạng và cho ra một giá trị có kiểu nhất định. Vì vậy, mỗi biểu thức sẽ có một giá trị xác định. Giá trị đó có thể là giá trị nguyên, giá trị thực, hoặc giá trị logic: true (1), false (0). Tùy thuộc vào giá trị của biểu thức và các toán tử nằm trong nó, ta có thể phân loại biểu thức như sau: biểu thức số học, biểu thức quan hệ và biểu thức logic. a. Biểu thức số học Một biểu thức số học gồm các toán tử là các phép toán số học ( +, -, *, /,) và các toán hạng là các đại lượng số học. Do đó, giá trị của biểu thức số học cũng là một đại lượng số học. Ví dụ: 3*((i % 4)*(5 +(j – 2)/(k+3))) b. Biểu thức quan hệ (biểu thức điều kiện) Là biểu thức mà các toán tử nằm trong nó là các phép toán so sánh ( >, <, ==, !=,...). Giá trị của biểu thức quan hệ là giá trị logic. Ví dụ: x >= y hoặc a != 0 c. Biểu thức logic Biểu thức được tạo nên từ hai hay nhiều biểu thức quan hệ và các phép toán logic ( &&, ||, !) được gọi là biểu thức logic. Giá trị của nó là giá trị logic. Trong C, các giá trị nguyên khác 0 có giá trị là true, ngược lại giá trị 0 có giá trị là false. 1.2.9 Toán tử Toán tử là một trong những thành phần cơ bản của một ngôn ngữ, giúp cho người dùng thực hiện các phép tính toán. Ngôn ngữ C hỗ trợ rất đa dạng các toán tử và chúng được phân chia làm các nhóm như sau: - Toán tử số học - Toán tử quan hệ - Toán tử logic - Toán tử gán - Toán tử tăng, giảm - Toán tử điều kiện - Toán tử trên bit - Toán tử phẩy - Toán tử sizeof 57 a. Toán tử số học Bảng dưới đây liệt kê các toán tử số học được sử dụng trong các biểu thức số học: Toán tử Ý nghĩa Kiểu toán hạng Kiểu kết quả Ví dụ + Phép cộng Số nguyên hoặc số thực Kiểu của toán hạng có kiểu cao nhất x = 3 + 2; - Phép trừ Số nguyên hoặc số thực Kiểu của toán hạng có kiểu cao nhất x = y – z; * Phép nhân Số nguyên hoặc số thực Kiểu của toán hạng có kiểu cao nhất x = y * z; / Phép chia Số nguyên / số nguyên Kiểu số nguyên x = 3 / 2; (x = 1) Số thực (số nguyên) / số thực (số nguyên) Kiểu số thực x = 3.0 / 2; (x = 1.5) % Phép chia lấy phần dư Giữa 2 số nguyên Kiểu số nguyên x = 7 % 3; (x = 4) Bảng 1.5 – Các toán tử số học cơ bản b. Toán tử quan hệ Các toán tử quan hệ được sử dụng để thực hiện các phép so sánh giữa hai toán hạng. Nếu điều kiện đúng nhận được giá trị là true (1), ngược là false (0). Các toán tử quan hệ thường được sử dụng trong các biểu thức điều kiện (biểu thức quan hệ) nằm trong các lệnh điều khiển if, while, dowhile, for để đưa ra lựa chọn phù hợp. Các phép toán quan hệ gồm có: Toán tử Ý nghĩa Ví dụ > So sánh lớn hơn 7 > 9 /*cho giá trị 0*/ < So sánh nhỏ hơn 3 < 5 /*cho giá trị 1*/ >= So sánh lớn hơn hoặc bằng 100 >= 100 /*cho giá trị 1*/ <= So sánh nhỏ hơn hoặc bằng 100 <= 50 /*cho giá trị 0*/ == So sánh bằng 3 == 4 /*cho giá trị 0*/ ‘A’ == ‘a’ /*cho giá trị 0*/ != So sánh không bằng 3 != 3 /*cho giá trị 0*/ Bảng 1.6 – Các toán tử quan hệ 58 c. Toán tử logic Các toán tử logic thường được dùng để kết hợp các biểu thức quan hệ lại với nhau tạo thành biểu thức logic. C hỗ trợ 3 toán tử logic gồm: Toán tử Ý nghĩa Ví dụ ! Phép PHỦ ĐỊNH !(3==3) /∗cho giá trị 0 ∗/ && Phép VÀ ((9/3 == 3) && (2∗3==6) ) /*cho giá trị 1*/ ((’A’==’a’) && (3==3)) /∗cho giá trị 0 ∗/ || Phép HOẶC ((2==3) || (’A’==’A’)) /*cho giá trị 1*/ (6 || 0 ) /*cho giá trị 1*/ Bảng 1.7 – Các toán tử logic Dưới đây là bảng chân trị của các toán tử logic, với A và B là biểu thức quan hệ. A ! A 0 1 1 0 A B A &&B A || B 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 1 Bảng 1.8 – Bảng chân trị của các toán tử logic d. Toán tử gán Toán tử gán là toán tử phổ biến nhất trong các ngôn ngữ lập trình. Toán tử gán có kí hiệu là ‘=’ và được dùng để gán giá trị cho biến. Cần phân biệt giữa toán tử so sánh bằng ‘==’ với toán tử gán ‘=’. Biểu thức sử dụng phép toán gán được gọi là biểu thức gán. Cú pháp của biểu thức gán: tên_biến = biểu_thức Biểu thức gán gồm hai vế, trong đó vế trái luôn luôn là biến. Giá trị của biểu thức gán chính là giá trị của biến, do đó ta có thể thực hiện liên tiếp các phép gán. Ví dụ: c = 2; a = b = c; /* a và b có giá trị là 2 */ Bên cạnh toán tử gán đơn ‘=’ thì ngôn ngữ C còn hỗ trợ một số toán tử gán thu gọn có dạng như sau: tên_biến toán_tử= biểu_thức Dạng phép gán thu gọn này được áp dụng với nhiều toán tử khác nhau. 59 Toán tử Lệnh gán thu gọn Lệnh gán đơn += a += b a = a + b -= a -= b a = a - b *= a *= b a = a * b /= a /= b a = a / b %= a %= b a = a % b &= a &= b a = a & b ^= a ^= b a = a ^ b <<= a <<= b a = a << b >>= a >>= b a = a >> b Bảng 1.9 – Các phép gán thu gọn Ví dụ: x = x + 1; viết gọn hơn là: x += 1; x = x + (y + 1); viết gọn hơn là: x += y + 1; e. Toán tử tăng, giảm Phép tăng, giảm một đơn vị là những phép toán số học phổ biến. C hỗ trợ cho người dùng hai toán tử một ngôi ++ và -- để thực hiện điều này. Có hai dạng sử dụng toán tử tăng (giảm) là dạng hậu tố và tiền tố. a++ hoặc ++a  a = a + 1 a-- hoặc --a  a = a – 1 Tuy nhiên, hai dạng này sẽ khác nhau khi nó đứng trong một biểu thức. Đối với dạng hậu tố a++ (a--), giá trị của biểu thức sẽ được tính toán sử dụng giá trị ban đầu của biến a rồi mới tăng (giảm) giá trị của biến a. Ngược lại, với dạng tiền tố ++a (--a), giá trị của biến a sẽ tăng (giảm) trước khi sử dụng nó để tính toán giá trị của biểu thức. Ví dụ: int x = 10, y; y = x++; (1) Câu lệnh (1) sẽ tương đương với 2 câu lệnh: y = x; /* y = 10 */ x = x + 1; /* x = 11 */ trong khi đó: y = ++x; (2) Câu lệnh (2) sẽ tương đương với 2 câu lệnh: x = x + 1; /* x = 11 */ y = x; /* y = 11 */ 60 f. Toán tử điều kiện Toán tử điều kiện ‘?:’ thường được dùng như là cách viết tắt của cấu trúc lệnh ifelse (lệnh ifelse sẽ được thảo luận ở chương sau). Đây là toán tử 3 ngôi gồm 3 toán hạng cấu thành nên biểu thức điều kiện ở dạng như sau: biểu_thức_1 ? biểu_thức_2 : biểu_thức_3 Trong đó, biểu_thức_1 là biểu thức điều kiện. Nếu nó nhận giá trị là true thì giá trị của biểu thức điều kiện sẽ là giá trị của biểu_thức_2, ngược lại là giá trị của biểu_thức_3. Ví dụ: sign = (x > 0) ? 1 : -1; isodd = (x % 2 == 1) ? 1 : 0; Biểu thức điều kiện giúp cho chương trình trở nên nhỏ gọn hơn, dễ đọc hơn, và an toàn khi sử dụng. g. Toán tử trên bit Các toán tử trên bit sẽ tác động lên từng bit riêng lẻ của các toán hạng (toán hạng có giá trị nguyên). Mỗi toán tử thường được sử dụng cho mục đích riêng. Ví dụ như, toán tử ‘&’ thường được dùng để kiểm tra một bit cụ thể của một số nguyên là bit 0 hay bit 1 bằng cách sử dụng mặt nạ với bit cần quan tâm là 1, còn các bit khác bằng 0. Các toán tử bit trong C bao gồm: Toán tử Ý nghĩa & Phép giao (AND bit) | Phép hội (OR bit) ~ Phép lấy bù 1 (NOT bit) ^ Phép hội loại trừ (XOR bit) << Phép dịch trái >> Phép dịch phải Bit A Bit B A &B A | B ~ A A ^ B 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 Bảng 1.10 – Các toán tử trên bit và bảng chân trị 61 Cần chú ý rằng, đối với các toán tử hai ngôi như &, | , ^ thì hai toán hạng cần phải có cùng kiểu và cùng độ rộng với nhau. Hai toán tử ‘>’ thực hiện chức năng dịch chuyển các bit sang trái và sang phải. Đây cũng là toán tử hai ngôi và yêu cầu hai toán hạng phải là số nguyên. Phép toán dịch chuyển sẽ thực hiện tác động lên toán hạng bên trái dựa vào giá trị của toán hạng bên phải. Sau khi dịch chuyển, kết quả thu được sẽ có cùng kiểu và cùng độ rộng với toán hạng bên trái. Với phép dịch sang trái, biểu_thức_1 << biểu_thức_2 thì giá trị của biểu_thức_2 là số bit 0 tương ứng sẽ được chèn vào bên phải. Kết quả thu được có giá trị bằng biểu_thức_1 nhân với 2biểu_thức_2. Trong một số trường hợp, vấn đề tràn số sẽ xảy ra sau khi dịch chuyển. Vì thế, người dùng cần phải chọn lựa kiểu dữ liệu phù hợp để lưu trữ giá trị của biểu_thức_1 và kết quả. Ví dụ: int num, res; num = 6; /* num = 0000 0000 0000 0110 */ res = num << 2; /* res = 0000 0000 0001 1000 = 24 */ Với phép dịch sang phải, biểu_thức_1 >> biểu_thức_2 thì số bít tương ứng được chèn vào bên trái sẽ phụ thuộc vào kiểu dữ liệu của biểu_thức_1. Nếu biểu_thức_1 có kiểu là unsigned thì phép dịch sẽ chèn các bit 0 vào bên trái, ngược lại sẽ chèn bit dấu vào bên trái. Kết quả thu được có giá trị bằng biểu_thức_1 chia cho 2biểu_thức_2. Ví dụ: unsigned int a, res_a; a = 192; /* a = 0000 0000 1100 0000*/ res_a = a >> 2; /* res_a = 0000 0000 0011 0000 = 48*/ int b, res_b; b = -26066; /* b = 1001 1010 0010 1110 */ res_b = b << 2;/*res_b = 1110 0110 1000 1011=-6517 */ h. Toán tử phẩy Toán tử phẩy được sử dụng để liên kết các biểu thức liên quan với nhau. Cú pháp của biểu thức sử dụng toán tử phẩy: T = (biểu_thức_1, biểu_thức_2, biểu_thức_3, ) Các biểu thức con lần lượt được tính giá trị từ trái sang phải. Giá trị của biểu thức kết hợp T chính là giá trị của biểu thức nằm bên phải nhất. Trong tất cả các toán tử thì toán tử phẩy là toán tử có độ ưu tiên thấp nhất. 62 Ví dụ: int a = 2, b = 3, x = 0; x = (++a, b += a); /* x = 6 */ i. Toán tử sizeof sizeof là toán tử một ngôi trả về số lượng bytes mà một toán hạng chiếm trong bộ nhớ. Toán hạng ở đây có thể là biến, biểu thức, hoặc kiểu dữ liệu. Toán tử này được áp dụng với tất cả các kiểu dữ liệu khác nhau. Ví dụ: int a = 10; unsigned int result; result = sizeof(a); /* result = 2 */ j. Chuyển kiểu dữ liệu Chuyển kiểu dữ liệu là phép chuyển đổi biến từ kiểu dữ liệu này sang kiểu dữ liệu khác. C hỗ trợ hai cách chuyển kiểu đó là chuyển kiểu tự động và chuyển kiểu bắt buộc hay còn gọi là ép kiểu. Chuyển kiểu tự động do trình biên dịch thực hiện khi các biến trong một biểu thức có kiểu dữ liệu khác nhau hoặc gán một biến kiểu này cho một biến kiểu kia . Vì thế, để tính toán giá trị của biểu thức thì các biến có kiểu dữ liệu thấp được chuyển sang kiểu dữ liệu cao hơn mà dữ liệu vẫn được bảo toàn. Các kiểu dữ liệu được phân cấp từ thấp đến cao như sau: char hoặc short  int  long  float  double Ví dụ: int i; float f = i + 3.14; /* i được chuyển sang kiểu float */ Tuy nhiên, việc chuyển từ kiểu dữ liệu cao sang kiểu dữ liệu thấp hơn thì có thể gây mất dữ liệu hoặc nhận giá trị xa lạ. Ngoài ra, còn gặp các cảnh báo từ trình biên dịch. Ví dụ: short int a; long b = 35289049; float f = 4.5; a = b; /* a = 30681 */ a = f; /* a = 4 */ Trong một số trường hợp chúng ta muốn ép kiểu theo ý muốn thì có thể sử dụng cú pháp chuyển kiểu tường minh như sau: (kiểu_dữ_liệu) biểu_thức Cú pháp này cũng giúp tránh được những cảnh báo của trình biên dịch khi chuyển từ kiểu dữ liệu cao sang kiểu dữ liệu thấp hơn. 63 Ví dụ: int a = 10, b = 3; float f; f = a / b; /* f = 3.0 */ f = (float)a / b; /* f = 3.33333 */ Độ ưu tiên của các toán tử Độ ưu tiên và trình tự kết hợp của các toán tử sẽ ảnh hưởng đến việc nhóm các toán hạng và các toán tử với nhau khi tính toán giá trị của biểu thức. Độ ưu tiên của một toán tử chỉ có nghĩa khi một toán tử khác có độ ưu tiên cao hơn hoặc thấp hơn nó tồn tại trong cùng một biểu thức. Nguyên tắc thực hiện: - Thực hiện biểu thức trong ngoặc ( ) sâu nhất trước. - Toán tử có độ ưu tiên cao hơn sẽ được thực hiện trước. Nếu hai toán tử có độ ưu tiên bằng nhau thì dựa vào trình tự kết hợp để thực hiện. - Nên sử dụng cặp dấu ngoặc ( ) cho các biểu thức con để đảm bảo thứ tự thực hiện chính xác theo mong muốn. Bảng dưới đây liệt kê độ ưu tiên của các toán tử từ cao đến thấp: Độ ưu tiên Toán tử Trình tự kết hợp 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 () [] -> . ! ~ ++ -- - + * (type) & sizeof * / % + - > >= == != & ^ | && || ?: = += -= *= /= %= &=                Bảng 1.11 – Độ ưu tiên của các toán tử Ví dụ:  int y = x*3 + 2;  y = (x*3) + 2;  x != 0 && y == 0  (x != 0) && ( y == 0)  int a = 3/4*6; /* a = 0 */ khác với int a =