Ngôn ngữ C/C++ và kỹ thuật lập trình cơ sở: Phần 1

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:95

Thêm vào BST

Báo xấu

22
lượt xem 11
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cuốn sách "Kỹ thuật lập trình cơ sở với ngôn ngữ C/C++" phần 1 cung cấp cho người đọc những kiến thức như: tổng quan về kỹ thuật lập trình; ngôn ngữ lập trình C/C++; cấu trúc lệnh trong lập trình. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Ngôn ngữ C/C++ và kỹ thuật lập trình cơ sở: Phần 1

LP R H ATi N V . A W| V IN Ồ O GN 0 - 7 NHÀ XUẤT BẢN KHOA HỌC VÀ KỸ THUẬT
DƯƠNG THẢNG LONG (CHỦ BIÊN) TRƯƠNG TIÉN TÙNG KỸ THUẬT LẬP TRÌNH c v s ở VỐI NGỔN NGỮ C/C++ V~T~1 NHÀ XUẤT BẢN KHOA HỌC VÀ KỸ THUẬT
Chịu trách nhiệm xuất bản GIÁM ĐỐC - TỔNG BIÊN TẬP PHẠM NGỌC KHÔI Biên tập và sửa bản in: TS. NGUYEN h u y t i ế n Họa sỹ bìa : XUÂN DŨNG NHÀ XUẤT BẢN KHOA HỌC VÀ KỸ THUẬT 70 Trần Hưng Đạo - Hoàn Kiếm - Hà Nội ĐT: 04 3942 2443 Fax: 04 3822 0658 Website: http://www.nxbkhkt.com.vn Email: nxbkhkt@hn.vnn.vn CHI NHÁNH NHÀ XUẤT ÉvÍN KHOA HỌC VÀ KỸ THUẬT 28 Đồng KHqri?-*Quận 1 - TP Hồ Chí Minh Ể >t:t8 3822 5062 ’ ' f In 300 bản, khổ 16 X 24cm, tại Xí nghiệp In NXB Văn hóa Dân tộc Địa chỉ: 128C/22 Đại La, Hà Nội SỐĐKXB: 1455 - 2014/CXB/l - 93/KHKT. Quyết định XB số: 245/QĐXB - NXBKHKT, ngày 30/12/2014. ISBN: 978-604-67-0312-9 In xong và nộp lưu chiểu Quý I năm 2015.
LỜI NÓI ĐẦU Để đáp ứng nhu cầu đào tạo kỹ sư tin học của các ngành Công nghệ thông tin và Tin học trong các trường đại học, tăng cường thêm một lựa chọn cho người học tiếp cận đa dạng đến những vấn đề cơ sở của ngành, chúng tôi biên soạn cuốn sách “K ỹ thuật lập trình cơ sở với ngôn ngữ C /C + + ”. Tài liệu này mong muốn cung cấp các kiến thức cơ sở về lập trình nói chung và các kỹ thuật xử lý trong ngôn ngữ C/C++ nói riêng, qua đó nhàm giúp sinh viên có thêm tài liệu học tập, tham khảo và đặc biệt là kỹ năng thực hành giải quyết các bài tập lập trình. Nội dung tài liệu gồm 06 chương, sắp xếp theo trật tự logic từ đon giản đến phức, đảm bảo tính hệ thống và liên thông từ đầu đến cuối. Chương 1 trình bày các khái niệm cơ bản về lập trình, ngôn ngữ lập trình và các vấn đề liên quan đến lập trình như giải thuật, độ phức tạp của giải thuật. Chương 2 giới thiệu về ngôn ngữ lập trình C/C++ gồm các khái niệm và các thành phân cơ bản cân có của ngôn ngữ lập trình như tập ký tự, tên, từ khóa, kiểu dữ liệu, các toán tử, cấu trúc chương trình, câu lệnh, khối lệnh,... Chương 3 trình bày các cấu trúc lệnh điều khiển trong lập trình bao gồm tuần tự, rẽ nhánh và lặp. Chúng được thể hiện bởi các lệnh như if, switch, for, while,... Chương 4 trình bày về lập trình cấu trúc. Trong đó gồm các khái niệm liên quan, phương pháp xây dựng chương trình theo mô-đun (dưới dạng các hàm), các vấn đề liên quan đến hàm như vấn đề trao đổi dữ liệu giữa các hàm, kỹ thuật hàm đệ quy, hàm nạp chồng, hàm m ẫu,...
4 KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGÓN NGỮ C/C++ Chương 5 trình bày phương pháp tổ chức dữ liệu theo mảng, các bài toán và thuật toán liên quan đến mảng. Trong đó bao gồm mảng một chiều, mảng hai chiều, mảng biểu diễn xâu ký tự và cách xử lý,... và đặc biệt là phương pháp khai thác sử dụng cơ chế bộ nhớ động với con trỏ. Chương 6 trình bày phương pháp tổ chức dữ liệu theo gói (hay cấu trúc - struct), phương pháp tổ chức dữ liệu dạng danh sách, dạng cây... đổi với các cấu trúc dữ liệu cơ bản và các vấn đề liên quan. Cũng trong chương này, phần cuối sẽ cung cấp phương pháp xử lý vào/ra tệp tin phục vụ cho việc lưu dữ liệu trên bộ nhớ ngoài (ổ đĩa). Mỗi chương được chia làm ba phần: phần thứ nhất trình bày lý thuyết các vấn đề, mỗi vấn đề đều có các ví dụ minh họa, giải thích chi tiết hoặc/và các hình vẽ minh họa trực quan giúp cho người đọc dễ tiếp nhận. Phần thứ hai gồm các bài tập có hướng dẫn thực hiện và lời giải theo hướng dẫn đó và phần thứ ba là các bài tập chưa có lời giải. Các ví dụ mẫu cũng như bài giải của các bài tập đã được viết bằng ngôn ngữ C/C++ và chạy thử cho kết quả đúng trên môi trường Dev-C++. Hướng dẫn: Bạn đọc nên đọc các phần lý thuyết trước mỗi chương và xem các ví dụ minh họa, tiếp theo tìm hiểu các bài tập đã nêu phương pháp giải để nắm rõ việc vận dụng phần lý thuyết vào mỗi bài toán cụ thể. Cuối cùng bạn hãy tự làm các bài tập yêu cầu để nâng cao kỹ năng lập trình cũng như giải quyết các bài toán bàng máy tính. Nhóm tác giả mong nhận được những đóng góp để hoàn thiện hơn cho tài liệu này qua địa chỉ email: duongthanglong@ gm ail.com. Hà Nội ngày 19 thảng 05 năm 2014 Nhóm tác giả
Chương 1 TỔNG QUAN VỀ KỸ THUẬT LẬP TRÌNH 1.1. Lập trình và ngôn ngữ lập trình 1.1.1. Khái niệm về lập trình Thuật ngữ lập trình (programming) nhằm nói đến quá trình xây dựng - sản xuất một chương trình phần mềm cho máy tính, qua đó khi chương trình phần được thực thi trên máy tính, chúng ta ứng dụng để giải quyết bài toán thực tế. Khái niệm bài toán ở đây được hiểu theo nghĩa rộng, tức là bất kỳ vấn đề nào trong thực tế mà con người cần ứng dụng máy tính để giải quyết. Quá trình này gồm nhiều giai đoạn như khảo sát, phân tích và thiết kế, mã hóa chương trình, kiểm thử chương trình, bảo trì nâng cấp,... (xem hình vẽ sau). Các giai đoạn chính trong quá trình xây dựng một chương trình phần mềm như sau. Chương \ Khảo Phân tích & Mã hóa Kiểm trình phần I sát thiêt kê chương trình tra mềm Giai đoạn khảo sát nhàm làm rõ các yêu cầu của bài toán, giới hạn hay xác định phạm vi bài toán cần giải quyết, tiếp theo phân tích các yêu cầu của bài toán thật chi tiết về các quy trình nghiệp vụ, cách thức xử lý các vấn đề có trong phạm vi bài toán để từ đó thiết kế các
6 KỸ THUẬT LẠP TRÌNH c ơ s ở VỚI NGÔN NGỮ C/C++ thành phần cho chương trình phần mềm. Giai đoạn mã hóa chương trình (hay coding) là một giai đoạn quan trọng, ở đó, các thiết kế về phần mềm sẽ được chuyển hóa thành nội dung các thành phần của một chương trình máy tính. Người thực hiện ở giai đoàn này hay được gọi là lập trình viên (programmer). Như vậy, kết quả của lập trình là chương trình phần mềm (software), chương trình này sẽ được thực hiện trên máy tính và qua đó giúp con người giải quyết bài toán đặt ra ban đầu. Chúng ta không đi sâu tìm hiểu chi tiết về các giai đoạn ở đây. Trong khuôn khổ tài liệu này, sẽ đề cập đến giai đoạn mã hóa chương trình hay còn gọi là viết mã lệnh. Giai đoạn này được thực hiện dựa trên những phân tích và thiết kế về chương trình đó. Các thiết kế của chương trình gồm nhiều thành phần khác nhau như việc phân chia các rtìô-đun xử lý, các giao diện người dùng của chương trình... nhưng quan trọng là quy trình xử lý và tính toán cho các vấn đề của bài toán bằng máy tính, hay còn gọi là thuật toán. Phần thuật toán này sẽ cho thấy cấu trúc trình tự mà người lập trình sẽ viết mã lệnh cho chương trình. Khái niệm và các vấn đề về thuật toán được trình bày ở phần sau. Thực tiễn đặt ra nhiều bài toán cho việc xây dựng các chương trình phần mềm ứng dụng. Có một số bài toán có thể đang được giải quyết bằng sức lao động của con người, tuy nhiên có những bài toán chúng ta không thể giải quyết vì khối lượng tính toán khổng lồ hoặc diễn ra trong những môi trường đặc biệt. Chẳng hạn, bài toán giải phương trình bậc hai là đơn giản và chúng ta có thể tính toán trong thời gian ngắn, trong khi bài toán phân tích một số nguyên khoảng 50 chữ số thành các thừa số nguyên tố sẽ cần một khối lượng tính toán lớn và con người không dễ gì có thể tính toán ngay được. Hoặc bài toán điều khiển các thiết bị rô-bốt được phóng vào vũ trụ thì rõ ràng con người chưa thể tham gia điều khiển trực tiếp mà cần có sự tự động hóa việc điều khiển bàng máy tính. Những điều này cho thấy sự cần
KỸ THUẬT LẬP TRÌNH c ơ s ở VỚI NGÔN NGỮ C/C++ thiết đến việc ứng dụng máy tính thông qua các chương trình phầr mềm ứng dụng. Mặt khác, với đặc trưng như tính trung thực, không bị phụ thuộc vào điều kiện ngoại cảnh khi tính toán và xử lý... nên việc ứng dụng máy tính giải quyết các bài toán giúp con người sẽ hiệu quả cao vè đảm bảo tính ổn định hon. 1.1.2. Ngôn ngữ lập trình Chương trình phần mềm của máy tính là tập hợp các câu lệnh C C thứ tự để điều khiển máy tính xử lý và tính toán giải quyết bài toán đ< đặt ra. Các câu lệnh (hay còn gọi mã lệnh) được viết trong chươnị trình về bản chất chỉ sử dụng 2 ký hiệu 0 và 1, bởi vì máy tính điện tì hiện nay chỉ xử lý tín hiệu dạng nhị phân (tương ứng với trạng thá ON/OFF). Các lệnh biểu diễn ở dạng này gọi là mã máy. Tuy nhiêi chúng ta không phải và cũng rất khó lập trình bằng các lệnh m ã máy mà sẽ sử dụng các lệnh dưới dạng tương tự ngôn ngữ tự nhiên (chi yếu bằng tiếng Anh) để dễ dàng hơn, đó chính là nhờ sự cung cấp củi ngôn ngữ lập trình. Như vậy, ngôn ngữ lập trình có thể hiểu là tập các ký pháp, qir tắc, quy ước để viết mã lệnh cho chương trình. Hiện nay có rất nhiềi loại ngôn ngữ lập trình được chia thành từng nhóm sau: - Ngôn ngữ máy: sử dụng các ký hiệu nhị phân cùng với quy tắ của máy nên rất khó áp dụng và hầu như không được dùng để viể chương trình. - Nhóm ngôn ngữ bậc thấp: sử dụng các ký hiệu là chữ cái, chi số, dấu... hay còn gọi là các ký tự cùng với quy tắc gần với quy tắ của máy nên cũng khá khó khi áp dụng. Chẳng hạn, như ngôn ng Assembler. Các ngôn ngữ thuộc nhóm này thường áp dụng để vi( chương trình phần mềm dạng hệ thống, can thiệp sâu bên trong cá thiết bị vật lý để điều khiển.
8 KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGỐN NGỮ C/C++ - Nhóm ngôn ngữ bậc cao: sử dụng các ký hiệu là các ký tự của ngôn ngữ tự nhiên (tiếng Anh) để viết lệnh với quy tắc gần với quy tắc của ngôn ngữ tự nhiên nên dễ áp dụng. Chẳng hạn như Pascal, C/C++, Java,... Ngôn ngữ lập trình về bản chất cung cấp cho người lập trình hai yếu tố chính thứ nhất, cung cấp các ký hiệu và quy tắc viết mã lệnh để sao cho đơn giản và dễ triển khai; thứ hai, cung cấp cơ chế để các chương trình sau khi viết bàng ngôn ngữ này sẽ được chuyển về dạng mã máy để thực hiện trên máy tính. Quá trình chuyển đổi này được gọi là biên dịch (compile) chương trình. Chương trình được viết ra sử dụng một ngôn ngữ lập trình nào đó được gọi là chương trình nguồn (source programs), sau khi biên dịch sẽ tạo thành chương trình gồm các lệnh mã máy được gọi chương trình thực thi (executive programs). Hình vẽ sau minh họa quá trình lập trình phần mềm và biên dịch, chạy thử chương trình trên máy tính. 1.2. Thuật toán 1.2.1. Khái niệm thuật toán (algorithms) Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy có thứ tự các thao tác trên những đối tượng, sao cho
KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGÔN NGỮ C/C++ 9 sau một số hữu hạn bước thực hiện các thao tác này, ta thu được kết quả mong muốn. Thuật toán là khái niệm cơ bản trong tin học để diễn tả cách thức máy tính xử lý thông tin nhằm giải quyết một bài toán nào đó. Vì vậy để lập trình cho máy tính, trước hết, chúng ta phải thiết kế một thuật toán thích hợp mà các bước tính toán trong đó là thực hiện được bởi máy tính. Sự thích hợp của một thuật toán được thể hiện ở các đặc trưng cần có và chúng ta sẽ xem xét chi tiết ở phần tiếp theo. Chẳng hạn, để thực hiện bài toán giải phương trình bậc hai dạng a.x2+b.x+c = 0 chúng ta cần phải thực hiện theo thứ tự các bước như sau: Bước 1) Xác định các hệ số của phương trình là ba số a, b và c. Bước 2) Kiểm tra, nếu a bằng 0 thì trả lời đây không phải là phương trình bậc hai và kết thúc. Ngược lại thực hiện tiếp bước 3. Bước 3) Tính giá trị của delta = b2- 4a.c Bước 4) Nếu delta < 0 thì trả lời phương trình không có nghiệm thực và kết thúc. Ngược lại sang bước 5. Bước 5) Nếu delta = 0 thì trả lời phương trình có nghiệm kép là Xi = x2 = -b/(2.a) và kết thúc. Ngược lại sang bước 6. Bước 6) Nếu delta > 0 thì trả lời phương trình có hai nghiệm phân biệt là X] = (-b+delta1/2)/(2.a) và x2 = (-b-delta1/2)/(2.a) và kết thúc. Quá trình thực hiện bài toán trên có 6 bước, nội dung thực hiện các bước là rõ ràng, chính xác và đơn nghĩa. Nếu chúng ta đảo lộn trật tự của các bước thì có thể dẫn đến sai, tức là không giải quyết được bài toán đã đặt ra. Đây là đặc điểm có tính thứ tự của các thao tác trong bất kỳ một thuật nào. Để tìm hiểu kỹ các đặc trưng của thuật toán, chúng ta sẽ tiếp tục ở phần sau.
10 KỸ THUẬT LẬP TRÌNH c ơ s ở VỚI NGÔN NGỮ C/C++ 1.2.2. Phương pháp trình bày thuật tuán Vấn đề biểu diễn thuật toán cũng rất quan trọng, nhàm mục đích truyền đạt nội dung phương cách tính toán và xử lý cho một bài toán từ người thiết kế đến người lập trình một cách chính-xác. Dễ nhất là sử dụng hệ thống các ký hiệu hình thức hóa, tuy nhiên với những thuật toán lớn và để gần gũi với ngôn ngữ tự nhiên của con người, chúng ta thường sử dụng ngôn ngữ giả lập trình với mô tả từng bước. Như vậy, chúng ta có hai cách để biểu diễn thuật toán: - Cách thứ nhất là nêu trình tự các bước từ bước 1 đến bước cuối cùng, ở mỗi bước sử dụng ngôn ngữ giả lập trình cùng với ngôn ngữ tự nhiên để trình bày thao tác cần tính toán hoặc xử lý. Các mô tả này phải chính xác, rõ ràng, đom nghĩa và dễ hiểu. Cấu trúc mô tả một thuật toán theo cách này thường gồm các 3hần như sau: A lgorithm : tên_thuật_toán Input: các_tham_số_đầu_vào O utput: các_kết_quả_tính_toán_đầu_ra Actions: B 1) Mô _tả_thao_tác_xử_lý_cho_bước_ 1 B2) Mô_tả_thao_tác_xử_lý_cho_bước_2 Bn) M ô_tả_thao_tác_xử_lý_cho_bước_« E nd. (kết thúc thuật toán) Trong đó, chúng ta có thể dịch chuyển từ bước sau lên bước trước để cho lặp lại việc thực hiện một số thao tác nào đó. Tuy nhiên điều này cần được thiết kế chặt chẽ để tránh việc lặp lại vô tận, tức không có điểm dừng cho thuật toán.
KỸ THUẬT LẬP TRỈNH c ơ s ở VỚI NGÔN NGỮ C/C++ 11 Chúng ta xem ví dụ sau về tìm số lớn nhất trong ba số nguyên để nắm rõ hơn về phương pháp trình bày : A lgorithm : TM3S In p u t: a, b, c (là 3 số nguyên) O u tp u t: m (là số lớn nhất) Actions: B l) Nếu a>b thì đặt m = a; Ngược lại, đặt m = b; B2) Nếu m
12 KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGÔN NGỮ C/C++ Trong đó, một thuật toán thường chỉ có hai hình e-líp thể hiện một điểm bắt đầu và một điểm kết thúc của thuật toán. Các mũi tên nổi các hình (thao tác) lại với nhau tạo nên tính thứ tự cần phải xem xét cẩn trọng. Nếu một thao tác nào đó trong một hình vẽ mà quá lớn và chưa cụ thể để dễ dàng lập trình thì có thể được thiết kế chi tiết thành một thuật toán con khác với một sơ đồ khác tương ứng. Chẳng hạn, với thuật toán giải phương trình bậc hai ở trên chúng ta có thể biểu diễn bằng sơ đồ sau: (^ B ắ t đ ầ ^ ) (1) Ị Nhập hệ số a,b,c Ị (2 ) Trả lời không , (9) phải phương «— a*0^> trình bậc hai - b + VÃ -ố -V Ã _ ~b X, = , X, = X, =*, « (7) (6) 2a 2 2a 2a T .(10) ► (^K ẻtth u c^) M ột thuật toán được trình bày dưới dạng sơ đồ thường là rõ ràng, tường minh và trực quan với cách tư duy lập luận của con người hom. Người lập trình sẽ dễ dàng triển khai chương trình từ thuật toán ở dạng này. Tuy nhiên nếu thuật toán quá lớn thì việc trình bày bằng mô tả các bước sẽ đơn giản hơn, khi đó các bước phải được trình bày rõ
KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGÔN NGỮ C/C++ 13 chi tiết từng thao tác để người lập trình có thể nắm bắt được và mã hóa thành các câu lệnh xử lý, tính toán trong chương trình được dễ dàng. Để hiểu rõ và chắc chắn chính xác chi tiết từng thao tác trong một thuật toán, thông thường, trước hết chúng ta hãy làm thử từng bước của thuật toán đã cho với các trường hợp khác nhau của dữ liệu đầu vào (input). Ở đây chúng ta sẽ làm thử một trường hợp của thuật toán giải phương trình bậc hai ở trên. Cụ thể với sơ đồ của ví dụ trên ta có như sau: Sau khi bắt đầu, chúng ta nhập các hệ số tại hình vẽ thứ (2) (hình bình hành), giả sử là a = 2, b = 5, c = 2. Tiếp theo tại hình (3) kiểm tra a * 0 là đúng nên sang hình (4) và tính A = 5 - 4 x 2 x 2 = 9. Tiếp tục kiểm tra A > 0 tại hình (5) là đúng nên sang hình (6) để tính giá trị nghiệm: = -5 + V 9_ . _ , = -5 -V 9 _ . Xi = — — ■ = -0 ,5 và x2 = —— —;—- = - 2 2x2 2x2 sau đó kết thức thuật toán. 1.2.3. Các đặc trưng của thuật toán Thông thường, để cho biết một thuật toán là tốt hay không chúng ta cần đưa ra các tiêu chí đánh giá. Sau đây là những tiêu chí thường được đề cập, có những tiêu chí là bắt buộc, có những tiêu chí cần đạt ở mức độ càng cao càng tốt. - Tính kết thúc: thuật toán phải được kết thúc sau một số hữu hạn thao tác. Đây là tính bắt buộc của bất kỳ một thuật toán nào. Ví dụ sau đây là một thuật toán để tìm ước số chung lớn nhất của hai số nguyên dương mà không có tính kết thúc vì các bước trong đó được lặp lại vô hạn lần (thuật toán bên dưới). Thực vậy, khi hai số bàng nhau (a=b) thì tại bước 2 thuật toán sẽ trừ bớt của b và do đó giá trị b sẽ bằng 0 (a khác 0), tiếp theo bước 3 sẽ không kết thúc vì sau bước 2 thì giá trị a khác b. Bước 4 sẽ lặp lại bước 1, bây giờ sẽ lặp vô hạn lần
14 KỸ THUẬT LẬP TRÌNH c ơ s ở VỚ! NGỒN NGỮ C/C++ VÌ b = 0 nên tại bước 1 giá trị a luôn không đổi dẫn đến không bao giờ đạt được kết quả a = b ở bước 3 để dừng thuật toán. A lgorithm : USCLN (thuật toán không có tính dừng) Input: a, b (là 2 số nguyên dương) Output: u (là ước số chung lớn nhất) Actions: B l) Nếu a>b thì đặt a = a-b; (giảm bớt của a đi b đom vị) B2) Nếu a
KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGỐN NGỮ C/C++ 15 - Tính phổ dụng: thuật toán có thể mở rộng, áp dụng được cho lớp các bài toán tương tự nhau, không chỉ giải quyết duy nhất một bài toán đã đặt ra. Ví dụ: bài toán đặt ra là lập trình để giải hệ 3 phương trình với 3 ẩn số (x, y, z) như sau: 'au .x + an .y + aìĩ.z = bì
16 KỸ THUẬT LẬP TRÌNH c ơ s ở VỚI NGÔN NGỮ C/C++ giá độ phức tạp của thuật toán, và chúng ta chỉ quan tâm đến yếu tố này trong tài liệu. Thông thường, độ phức tạp (xét yếu tố thời gian) của thuật toán được đánh giá dựa trên kích thước dữ liệu đầu vào của bài toán, đó là vì khi dữ liệu đầu vào có kích thước lớn sẽ dẫn đến số các thao tác xử lý nhiều hơn. Thật vậy, chẳng hạn với bài toán tính tổng của dãy các số nguyên, khi sổ lượng số nguyên là 2 (a, b) thì chỉ cần một phép tính cộng (a+b), khi số lượng dãy là 3 (a, b, c) thì cần 2 phép tính cộng (a+b+c),... tổng quát với dãy n số thì cần n-1 phép tính cộng. Tuy nhiên, số các thao tác xử lý tính toán của một thuật toán thường không xác định một cách tuyệt đối mà sẽ ước lượng ở mức trung bình. Và chúng ta dùng khái niệm bậc o để thể hiện con số ước lượng này. Sau đây là một số ước lượng hay được dùng trong việc đánh giá các thuật toán (được sắp xếp theo độ phức tạp tăng dần): Ký hiệu Ý nghĩa 0(log2n) Độ phức tạp logarit của kích thước dữ liệu (n). Độ phức tạp tuyến tính, tức là số thao tác xử lý tính toán 0(n) sẽ tăng lên một cách tuyến tính cùng với kích thước của dữ liệu đầu vào. 0 (n.log2n) Độ phức tạp n nhân với logarit của n. 0(na) Độ phức tạp đa thức bậc a của n (a là một hằng số). 0(a") Độ phức tạp lũy thừa. Chẳng hạn, với thuật toán tính tổng của một dãy n số nguyên theo cách mô tả như trên thì có độ phức tạp là O(n). Một quy ước trong việc đánh giá là nếu số ước lượng là m ột biểu thức theo n thì chúng ta sẽ lấy giá trị cao nhất, hoặc biểu thức theo n mà nhân với một hàng số thì không tính hàng số đó. Ví dụ, một thuật toán có ước lượng là 5+n+3.n thì ta lấy 3.n và suy ra lấy n, vậy ta có bậc O(n). M ột thuật toán có ước lượng là n+n2+2" thì ta lấy là 2n và có bậc 0(2").
KỸ THUẬT LẬP TRỈNH c ơ s ở VỚI NGÔN NGỮ C/C++ 17 1.2.5. Một số ví dụ về thuật toán ■ Ví dụ 1.1: Thuật toán “đổi chỗ”, có hai thùng A và B, thùng A đựng thóc và thùng B đựng ngô, hãy đổi chỗ thóc và ngô cho nhau. A B (thóc) (ngô) Để thực hiện thuật toán này chúng ta phải sử dụng thêm một thùng trung gian thứ 3, ký hiệu là c và thuật toán được trình bày theo cách 1 như sau: Bước 1) Chuyển thóc ở thùng A vào thùng c Bước 2) Chuyển ngô ở thùng B vào thùng A Bước 3) Chuyển thóc ở thùng c vào thùng B Hình minh họa như sau: (trung gian) ■ Ví dụ 1.2: Thuật toán “nấu cơm” : “Nấu cơm ” là một công việc rất quen thuộc trong cuộc sống, tuy nhiên nếu có ai đó chưa một lần thực hiện trong thực tế thì không thể làm được và chúng ta phải đưa ra một thuật toán cho người đó thực hiện, thuật toán được trình bày như sau: Bước 1) Thu thập nguyên liệu như gạo, nước và xác định các công cụ sử dụng để nấu cơm như nồi (giả sử nồi điện), nguồn điện. Bước 2) Nếu nguyên liệu không có hoặc thiếu công cụ thì thông báo không thể nấu cơm và chuyển đến bước 6.
18 KỸ THUẬT LẬP TRÌNH c ơ s ở VỚI NGÔN NGỮ C/C++ Bước 3) Lấy gạo cho vào nồi Bước 4) Vo gạo và đổ nước, đóng nắp nồi Bước 5) Cắm điện và bật công tắc sang chế độ nấu Bước 6) Kết thúc ■ Ví dụ 1.3: Thuật toán giải phương trình bậc 2 có dạng sau ax2 +bx + c = 0 Thuật toán trình bày dưới dạng sơ đồ như sau:
KỸ THUẬT LẬP TRÌNH c ơ SỞ VỚI NGÔN NGỮ C/C++ 19 ■ Ví dụ í .4: Thuật toán tìm số nhỏ nhất trong một dãy số. Cho một dãy số như sau: Xi, x2, x3 x4, x5 xn , ,..., . Hãy tìm số nhỏ nhất trong dãy số trên. Ta ký hiệu X j là số thứ i trong dãy trên với i = 1,2,3,— n và sử , dụng Min để lưu số nhỏ nhất, thuật toán được trình bày (bằng cả mô tả từng bước và sơ đồ khối) như sau: Thuật toán trên (dạng sơ đồ) được mô tả từng bước như sau: Bước 1) Xác định n và các giá trị X |, x 2,..., Xn Bước 2) Nếu n < 1 thì thông báo không có các số và kết thúc