tailieunhanh - Bài toán và thuật toán - Nguyễn Thế Vinh

Tài liệu "Bài toán và thuật toán" cung cấp kiến thức cơ bản về bài toán, thuật toán, cấu trúc dữ liệu, hi vọng tài liệu này sẽ giúp ích cho các bạn sinh viên ngành công nghệ thông tin trong việc học. . | Bài toán và thu t toán Nguy n Th Vinh - ĐHKH CHƯƠNG II BÀI TOÁN VÀ THUẬT TOÁN . KHÁI NIỆM BÀI TOÁN . Bài toán Trong phạm vi Tin học, ta có thể quan niệm bài toán là việc nào đó ta muốn máy tính thực hiện. Viết một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí điểm trong trường học Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: đưa vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output). Do đó để phát biểu một bài toán ta cần phải chỉ rõ Input và Output của bài toán đó. Ví dụ 1: Giải phương trình bậc nhất ax+b=0 Input: Các giá trị thực a,b Output: Nghiệm là giá trị x hoặc thông báo không có nghiệm Ví dụ 2: Quản lí điểm trong trường học Input: Thông tin cá nhân của từng học sinh Output: Thông tin cần khai thác về một học sinh, một lớp học sinh, một khối hay toàn trường. . Các bước giải bài toán bằng máy tính điện tử Học sử dụng máy tính thực chất là học cách giao cho máy tính việc mà ta muốn nó làm. Khả năng khai thác máy tính phụ thuộc rất nhiều vào sự hiểu biết của người sử giải bài toán trên máy tính được tiến hành qua các bước sau: Bước 1: Xác định bài toán Như đã trình bày, mỗi bài toán được đặc tả bởi hai thành phần: Input và Output. Việc xác định bài toán chính là xác định rõ hai thành phần này. Các thông tin đó cần được nghiên cứu cẩn thận để có thể lựa chọn thuật toán, cách thể hiện các đại lượng đã cho và các đại lượng phát sinh trong quá trình giải bài toán và ngôn ngữ lập trình thích hợp. 20 Bài toán và thu t toán Nguy n Th Vinh - ĐHKH Ví dụ, trong một bài toán Tin học khi đề cập đến một số nguyên dương N ta phải biết rõ phạm vi giá trị của nó, để lựa chọn cách thể hiện N bằng kiểu dữ liệu thích hợp. Bước 2: Lựa chọn hoặc thiết kế thuật toán Bước lựa chọn và thiết kế thuật toán là bước quan trọng nhất để giải một bài toán. Mỗi thuật toán chỉ giải một bài toán nào đó, nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. Cần chọn một thuật toán phù hợp để giải bài toán .