CHƯƠNG 02 – THUẬT TOÁN

 

VD:

+ 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) là từ viết tắt của tên một nhà toán học ở thế kỷ IX: Abu Ja’fa Mohammed ibn Musa al-Khowarizmi.
Thuật toán là một dãy hữu hạn các thao tác được bố trí theo một trình tự xác định, được đề ra trước, nhằm giải quyết một bài toán nhất định.
Thao tác hay còn gọi là tác vụ, phép toán (Operation) hay lệnh (Command), chỉ thị (Instruction)… là một hành động cần được thực hiện bởi cơ chế thực hiện thuật toán.
Mỗi thao tác biến đổi bài toán từ một trạng thái trước (hay trạng thái nhập) sang trạng thái sau (hay trạng thái xuất). Thực tế mỗi thao tác thường sử dụng một số đối tượng trong trạng thái nhập (các đối tượng nhập) và sản sinh ra các đối tượng mới trong trạng thái xuất (các đối tượng xuất). Quan hệ giữa 2 trạng thái xuất và nhập cho thấy tác động của thao tác. Dãy các thao tác của thuật toán nối tiếp nhau nhằm biến đổi bài toán từ trạng thái ban đầu đến trạng thái kết quả.
Các đặc trưng của thuật toán
Tính xác định: Các thao tác, các đối tượng, phương tiện trong thuật toán phải có ý nghĩa rõ ràng, không được gây nhầm lẫn. Nói cách khác, hai cơ chế hoạt động khác nhau cùng thực hiện một thuật toán, sử dụng các đối tượng, phương tiện nhập phải cho cùng một kết quả.
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.
Tính đúng của thuật toán: Thuật toán đúng là thuật toán cho kết quả thỏa mãn đặc tả thuật toán với mọi trường hợp của các đối tượng, phương tiện nhập.
Tính phổ dụng: Thuật toán để giải một lớp bài toán gồm nhiều bài cụ thể, lớp đó được xác định bởi đặc tả. Dĩ nhiên là có lớp bài toán chỉ gồm 1 bài. Thuật toán khi đó sẽ không cần sử dụng đối tượng, phương tiện nhập nào cả.
Phương pháp biểu diễn
Thuật toán có thể diễn đạt dưới nhiều hình thức, chẳng hạn dưới dạng lưu đồ, dạng ngôn ngữ tự nhiên, dạng mã giả hoặc một ngôn ngữ lập trình nào khác.
Dạng ngôn ngữ tự nhiên: Thuật toán có thể trình bày dưới dạng ngôn ngữ tự nhiên theo trình tự các bước thực hiện trong thuật toán.
Dạng ngôn ngữ lập trình: Dùng cấu trúc lệnh, dữ liệu của một ngôn ngữ lập trình nào đó để mô tả.
Dạng mã giả: Thuật toán trình bày trong dạng văn bản bằng ngôn ngữ tự nhiên tuy dễ hiểu nhưng khó cài đặt. Dùng một ngôn ngữ lập trình nào đó để diễn tả thì phức tạp, khó hiểu. Thông thường thuật toán cũng được trao đổi dưới dạng văn bản – tuy không ràng buộc nhiều vào cú pháp xác định như các ngôn ngữ lập trình, nhưng cũng tuân theo một số quy ước ban đầu – ta gọi là dạng mã giả. Tùy theo việc định hướng cài đặt thuật toán theo ngôn ngữ lập trình nào ta diễn đạt thuật toán gần với ngôn ngữ ấy.
Dạng lưu đồ: Trong các phương pháp biểu diễn, chúng ta sẽ chủ yếu nghiên cứu phương pháp biểu diễn theo dạng này. Dạng lưu đồ dùng các hình vẽ (có quy ước) để diễn đạt thuật toán. Lưu đồ cho hình ảnh trực quan và tổng thể của thuật toán, cho nên thường được sử dụng nhiều nhất.
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 đồ:

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.
VD: Đọ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 50
 
Advertisements
By dungkcna113 Posted in C/C++

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s