Thuật toán
Ví dụ
+ Thuật toán giải phương trình bậc 1, giải phương trình bậc 2
+ Thuật toán tìm số lớn nhất trong 3 số a, b, c
+ Thuật toán tính trung bình cộng của 4 số a, b, c, d
+ Thuật toán tìm đường đi ngắn nhất
Khái niệm
Thuật ngữ "thuật toán" (Algorithm) xuất phát từ tên của nhà toán học thế kỷ IX, Abu Ja’fa Mohammed ibn Musa al-Khowarizmi Ban đầu, thuật toán được hiểu là các quy tắc thực hiện phép toán số học với số trong hệ thập phân Tuy nhiên, với sự phát triển của máy tính, khái niệm thuật toán đã được mở rộng Vào năm 1936, nhà toán học người Anh Alan Turing đã đưa ra một định nghĩa hình thức về thuật toán thông qua máy Turing, từ đó lý thuyết thuật toán đã được hình thành.
Lý thuyết thuật toán liên quan đến vấn đề sau:
+ Giải được bằng thuật toán: Thay những thuật toán chưa tốt bằng những thuật toán tốt hơn
+ Triển khai thuật toán: Xây dựng những ngôn ngữ thực hiện trên máy tính để mã hóa thuật toán
Thuật toán là một chuỗi các thao tác hữu hạn được sắp xếp theo một trình tự xác định, nhằm mục đích giải quyết một vấn đề cụ thể.
An operation, also referred to as a task, command, or instruction, is an action that must be executed by the algorithm's execution mechanism.
Mỗi thao tác trong bài toán chuyển đổi từ trạng thái nhập sang trạng thái xuất sử dụng các đối tượng trong trạng thái nhập và tạo ra các đối tượng mới trong trạng thái xuất Mối quan hệ giữa hai trạng thái này phản ánh tác động của thao tác Chuỗi các thao tác của thuật toán diễn ra liên tiếp, nhằm biến đổi bài toán từ trạng thái ban đầu đến trạng thái kết quả.
Mỗi thao tác có thể phân tích thành các thao tác đơn giản hơn
Trong thuật toán, việc xác định rõ ràng trình tự thực hiện các thao tác là rất quan trọng Một tập hợp thao tác nếu được sắp xếp theo thứ tự khác nhau sẽ dẫn đến những kết quả khác nhau.
Các đặc trưng của thuật toán
Tính xác định trong thuật toán yêu cầu các thao tác, đối tượng và phương tiện phải rõ ràng và không gây nhầm lẫn Điều này có nghĩa là khi hai cơ chế khác nhau thực hiện cùng một thuật toán và sử dụng các đối tượng, phương tiện đầu vào giống nhau, thì kết quả đầu ra phải đồng nhất.
+ Tính dừng: Đòi hỏi thuật toán phải dừng và cho kết quả sau một số hữu hạn các bước
Thuật toán được coi là đúng khi nó cung cấp kết quả phù hợp với đặc tả của thuật toán trong mọi tình huống và với tất cả các đối tượng, phương tiện nhập.
Thuật toán có tính phổ dụng cao, cho phép giải quyết một tập hợp bài toán cụ thể được xác định bởi đặc tả Trong trường hợp lớp bài toán chỉ có một bài, thuật toán sẽ không cần sử dụng đối tượng hay phương tiện nhập nào.
Phương pháp biểu diễn
Thuật toán có thể được diễn đạt qua nhiều hình thức như lưu đồ, ngôn ngữ tự nhiên, mã giả, hoặc ngôn ngữ lập trình Đầu tiên, thuật toán có thể trình bày dưới dạng ngôn ngữ tự nhiên, mô tả các bước thực hiện một cách tuần tự Thứ hai, khi sử dụng ngôn ngữ lập trình, thuật toán sẽ được mô tả bằng cấu trúc lệnh và dữ liệu của ngôn ngữ đó Tiếp theo, mã giả là hình thức trình bày thuật toán bằng văn bản tự nhiên, dễ hiểu nhưng khó cài đặt, trong khi việc sử dụng ngôn ngữ lập trình có thể phức tạp và khó nắm bắt Cuối cùng, dạng lưu đồ là phương pháp biểu diễn chính mà chúng ta sẽ tập trung nghiên cứu, giúp hình dung rõ ràng hơn về quy trình thực hiện thuật toán.
Lưu đồ là công cụ sử dụng hình vẽ theo quy ước để biểu diễn thuật toán, mang đến hình ảnh trực quan và tổng thể về quy trình Do đó, lưu đồ thường được ưa chuộng trong việc trình bày các thuật toán.
Các ký hiệu sử dụng trong phương pháp biểu diễn thuật toán bằng lưu đồ:
STT Ký hiệu Giải thích
1 Bắt đầu và kết thúc chương trình
2 Điểm nối, đường đi (luồng xử lý)
5 Thao tác xử lý hoặc tính toán
6 Trả về giá trị (return)
7 Điểm nối liên kết tiếp theo (sử dụng khi lưu đồ vượt quá trang)
Ví dụ 1: Đọc các thông tin như tên, tuối và lưu lại những người có tuổi trên
Ví dụ 2: dụ: Nhập vào 3 số nguyên a, b, c và xuất ra màn hình với giá trị của mỗi số tăng lên 1
Là người cuối cùng? Đọc tên, tuổi Bắt đầu
Chú ý khi vẽ lưu đồ:
+ Trước tiên hãy tập trung vẽ một số đường đi chính của lưu đồ
+ Thêm vào tất cả các nhánh và vòng lặp
+ Một lưu đồ chỉ có một điểm Bắt đầu và một điểm kết thúc
+ Mỗi bước trong chương trình không cần thể hiện trong lưu đồ
+ Lưu đồ cần phải đáp ứng được yêu cầu: những người lập trình khác có thể hiểu lưu đồ một cách dễ dàng
Vẽ lưu đồ thuật toán cho các bài toán sau:
Bài 1: Tìm số lớn nhất trong 3 số a, b, c
Bài 2: Giải phương trình bậc 1: ax + b = 0 (a ≠ 0)
Bài 3: Giải phương trình bậc 2: ax 2 + bx + c = 0 (a ≠ 0)
Bài 4: Nhập vào hai số x, y Xuất ra màn hình tổng, hiệu, tích, thương của hai số trên
Bài 5: Nhập vào số nguyên n, kiểm tra xem n chẵn hay lẻ và xuất ra màn hình
Bài 6: Nhập vào ba cạnh a, b, c của tam giác Xuất ra màn hình tam giác đó thuộc loại tam giác gì? (Thường, cân, vuông, đều hay vuông cân)
Giới thiệu ngôn ngữ lập trình C++
Lịch sử hình thành
Ngôn ngữ lập trình C được Dennis Ritchie phát triển vào năm 1972 tại AT&T Bell Laboratories trong bối cảnh ông và các đồng nghiệp đang thiết kế hệ điều hành UNIX Nhận thấy rằng không có ngôn ngữ lập trình nào phù hợp với yêu cầu của dự án, Ritchie quyết định tạo ra một ngôn ngữ mới để giải quyết các vấn đề gặp phải Ông đã tham khảo nhiều ngôn ngữ trước đó, đặc biệt là ngôn ngữ B do Ken Thompson phát triển tại Bell Labs, và đã tích hợp nhiều phần của ngôn ngữ này vào C.
C Chính vì vậy mà Dennis Ritchie đã chọn ngay chữ cái tiếp theo của B (tức là C) để đặt tên cho ngôn ngữ mới này
Ngôn ngữ lập trình C, với sức mạnh và tính linh hoạt của mình, đã nhanh chóng trở nên phổ biến vượt ra ngoài Bell Labs, được các lập trình viên trên toàn thế giới sử dụng để phát triển nhiều loại chương trình Tuy nhiên, sự xuất hiện của các phiên bản C khác nhau từ nhiều tổ chức đã tạo ra những khác biệt tinh tế, gây khó khăn cho các lập trình viên Để giải quyết vấn đề này, vào năm 1983, Viện tiêu chuẩn Quốc gia Hoa Kỳ (ANSI) đã thành lập một ủy ban nhằm thiết lập tiêu chuẩn cho ngôn ngữ C, được gọi là ANSI C, và hầu hết các trình biên dịch C hiện đại đều tuân theo tiêu chuẩn này với một số ngoại lệ.
C++ là ngôn ngữ lập trình được Bjarne Stroustrup phát triển vào năm 1980 tại phòng thí nghiệm Bell, New Jersey, Mỹ Ban đầu, ngôn ngữ này được gọi là "C with classes" (C với các lớp), nhưng đến năm 1983, Stroustrup đã đổi tên thành C++, với ký hiệu ++ biểu thị cho toán tử tăng 1 trong ngôn ngữ C.
Mặc dù C là một ngôn ngữ lập trình được ưa chuộng trong cộng đồng lập trình viên chuyên nghiệp, nhưng nó vẫn tồn tại một số hạn chế Khi số lượng dòng lệnh vượt quá một mức nhất định, việc quản lý mã nguồn trở nên khó khăn hơn.
C++ được phát triển nhằm đơn giản hóa việc quản lý các chương trình lớn và phức tạp, giúp người lập trình dễ dàng hiểu và điều khiển chúng.
C++ được biết đến như là ngôn ngữ lập trình hướng sự vật hay hướng đối tượng - OOP (Object Oriented Programming).
Đặc điểm
C là một ngôn ngữ lập trình mạnh mẽ và linh hoạt, cho phép người dùng thỏa sức sáng tạo mà không bị ràng buộc Ngôn ngữ này được ứng dụng rộng rãi trong nhiều lĩnh vực, bao gồm phát triển hệ điều hành, phần mềm xử lý văn bản, đồ họa, bảng tính, và cả các chương trình biên dịch cho các ngôn ngữ khác.
Ngôn ngữ lập trình C được ưa chuộng nhất bởi các lập trình viên chuyên nghiệp, nhờ vào sự phong phú của các trình biên dịch và thư viện đã được phát triển sẵn.
Ngôn ngữ C là một ngôn ngữ khả chuyển, cho phép chương trình được viết trên một hệ máy tính, như IBM PC, có thể dễ dàng được dịch và chạy trên các hệ máy tính khác, chẳng hạn như DEC VAX, với rất ít thay đổi Tính khả chuyển này đã được công nhận và chuẩn hóa bởi ANSI cho ngôn ngữ C.
Ngôn ngữ lập trình C chỉ bao gồm một số ít từ khoá cơ bản, nhưng điều này không làm giảm sức mạnh của nó Nhiều từ khoá không đồng nghĩa với việc một ngôn ngữ mạnh hơn; ngược lại, C có khả năng giải quyết mọi bài toán lập trình.
Ngôn ngữ lập trình C được thiết kế theo mô-đun, cho phép mã chương trình được tổ chức thành các thủ tục gọi là hàm (function) Những hàm này có thể được tái sử dụng trong nhiều ứng dụng và chương trình khác nhau, giúp tối ưu hóa quy trình lập trình.
Trong ngôn ngữ lập trình C, không cho phép khai báo hàm bên trong hàm, đây là một trong những đặc điểm nổi bật của C Do C++ phát triển dựa trên C, nên tất cả các đặc điểm của C đều được C++ kế thừa Bên cạnh đó, C++ còn sở hữu một số đặc điểm bổ sung khác.
+ C++ là ngôn ngữ hướng đối tượng
+ C++ là ngôn ngữ định kiểu rất mạnh
+ C++ cung cấp cách truyền tham số bằng tham chiếu cho hàm
+ C++ cung cấp cơ cấu thư viện để người lập trình có thể tự tạo thêm hàm thông dụng vào thư viện và có thể tái sử dụng sau này
C++ hỗ trợ cơ chế đa dạng hóa tên hàm và toán tử, cho phép sử dụng cùng một tên hoặc ký hiệu để định nghĩa các chương trình con thực hiện nhiệm vụ tương tự với các kiểu dữ liệu tham số khác nhau.
C++ giới thiệu các lớp (class) như một cấu trúc mới, cho phép đóng gói dữ liệu và hàm trong một thực thể với mức độ bảo vệ cao.
C++ hỗ trợ tính kế thừa thông qua việc cho phép một lớp con kế thừa dữ liệu và hàm từ lớp cha, tạo ra sự di truyền trong lập trình.
Cấu trúc của một chương trình C++
Một chương trình C++ nói chung có dạng như sau:
(2): [Khai báo các nguyên mẫu hàm của người dùng]
(5): [Các định nghĩa biến, hằng]
(6): main ([khai báo tham số])
(10): Các định nghĩa hàm của người dùng
Chú ý: Các thành phần trong cặp ngoặc vuông [] có thể có hoặc không trong chương trình
(1): Cú pháp để khai báo thư viện: #include
Ví dụ: #include; #include;…
(2): Cung cấp tên hàm, kiểu hàm, số đối số và kiểu của từng đối số của hàm
Cú pháp khai báo nguyên mẫu hàm: ([Khai báo các đối số]);
Ví dụ: int chanle (int x); Trong đó, kiểu hàm là int, tên hàm là chanle, đối số là x và kiểu của đối số là int
Người lập trình có thể tạo ra các kiểu dữ liệu mới bằng cách sử dụng từ khóa typedef, ngoài những kiểu chuẩn có sẵn trong ngôn ngữ lập trình.
Macro là một khái niệm cho phép bạn gán một giá trị hoặc nội dung nào đó một cái tên, giúp sử dụng nhiều lần trong chương trình mà không cần viết trực tiếp Điều này làm cho chương trình trở nên dễ đọc và dễ hiểu hơn, đồng thời thuận tiện khi cần thay đổi nội dung Khi biên dịch, chương trình sẽ tự động thay thế tên đã gán vào đúng vị trí cần thiết trong mã nguồn.
Phép thế macro là một thao tác trong đó 'tên' được sử dụng để đại diện cho nội dung của macro 'Tên' này đóng vai trò quan trọng trong việc xác định và sử dụng macro trong các ứng dụng Nội dung của macro chính là những thông tin hoặc lệnh được thực hiện khi macro được gọi.
Một macro được định nghĩa như sau:
#define tên_macro nội_dung
Tên macro là một tên hợp lệ, với nội dung (giá trị) của macro được xem như một chuỗi cần thay thế cho tên macro tương ứng Giữa tên và nội dung có thể có một hoặc nhiều khoảng trống Nội dung của macro bắt đầu từ ký tự không phải dấu trống đầu tiên sau tên macro và kéo dài đến hết dòng.
Các biến và hằng được định nghĩa trong bài viết này sẽ trở thành biến và hằng toàn cục Ý nghĩa cũng như cú pháp định nghĩa của chúng đã được trình bày chi tiết trong phần về biến và hằng.
Hàm main() là thành phần bắt buộc trong chương trình C++, với phần thân hàm bắt đầu từ dấu mở móc { ở dòng 7 và kết thúc ở dấu đóng móc } ở dòng 9.
(10): Các định nghĩa hàm của người dùng: Một định nghĩa hàm bao gồm tiêu đề của hàm, thân hàm với cú pháp như sau:
([Khai báo các đối])
Khi định nghĩa hàm, tiêu đề phải phù hợp với nguyên mẫu hàm Nếu trong chương trình, định nghĩa hàm xuất hiện trước lời gọi hàm, thì không bắt buộc phải có dòng khai báo nguyên mẫu hàm.
Một số ví dụ mẫu
Ví dụ 1: Chương trình nhập vào điểm 3 môn: Toán, Lý, Hóa và tính điểm trung bình của 3 môn đó
//Bắt đầu hàm main int main()
//Khai báo 3 biến double dtb,dt,dl,dh;
Để tính điểm trung bình của ba môn Toán, Lý và Hóa, bạn cần nhập vào điểm số cho từng môn Sau khi nhập điểm, chương trình sẽ tính điểm trung bình (dtb) bằng cách cộng ba điểm và chia cho 3 Kết quả sẽ được hiển thị, cùng với đánh giá học lực: nếu dtb dưới 5, học lực sẽ được xếp loại yếu; từ 5 đến dưới 7 là trung bình; từ 7 đến dưới 8 là khá; và từ 8 trở lên là giỏi.
Ví dụ 2: Viết chương trình có sử dụng hàm tìm số lớn nhất trong 3 số x, y, z;
//Khai báo hàm có tên là maxabc float maxabc (float a, float b, float c)
{ float max; max = a>b?a:b; return (max>c?max:c);
//Bắt đầu hàm main main()
//Nhập giá trị cho các biến coutx; couty; coutz; t = maxabc (x,y,z); cout
