tailieunhanh - Tin học đại cương - Phần 1 Đại cương về tin học - Chương 6

Tài liệu tham khảo giáo trình Tin học đại cương dùng cho khối A do Đỗ Thị Mơ chủ biên - Bộ môn công nghệ phần mềm gồm 2 phần chia làm 13 chương - Phần 1 Đại cương về tin học - Chương 6 Giải thuật | CHƯƠNG VI GIẢI THUẬT 1. Khái niệm giải thuật Algorithms - Khi cần giải quyết một bài toán trong thực tế với sự trợ giúp của máy tính điện tử ta thường phải biết dữ liệu vào của bài toán Input là gì và bài toán yêu cầu dữ liệu ra Output là gì . Bước tiếp theo ta phải thiết lập được các bước thao tác cụ thể để từ Input ta có được Output. Công việc đó trong tin học được gọi là xây dựng giải thuật. - Giải thuật của 1 bài toán là một dãy các câu lệnh Statements chặt chẽ và rõ ràng xác định một trình tự các thao tác trên một số đối tượng nào đó sao cho sau một số bước hữu hạn thực hiện ta thu được kết quả mong muốn. - Với định nghĩa như vậy ta thấy rằng đối với một bài toán cụ thể có thể có nhiều giải thuật khác nhau nhưng tất nhiên là các giải thuật đó phải cho cùng một kết quả theo đúng yêu cầu của bài toán. - Khi nghiên cứu về giải thuật thường ta phải biết được giải thuật đó tác động lên dữ liệu nào. Việc lựa chọn cấu trúc dữ liệu Data structures phù hợp và việc thiết lập được các giải thuật đúng đắn có cấu trúc tốt và hiệu quả là những vấn đề mấu chốt của công việc thiết lập phần mềm. Chính vì vậy mà Niklaus Wirth người sáng lập ra ngôn ngữ lập trình Pascal đã tổng kết Giải thuật Cấu trúc dữ liệu Chương trình Ví dụ Xây dựng giải thuật tìm UCLN của 2 số nguyên dương a và b ký hiệu a b Đối với bài toán này ta có Input 2 số nguyên dương a b Output a b Giải thuật được xây dựng dựa trên tính chất Nếu a b thì a b a Nếu a b thì a b a-b b Nếu a b thì a b a b-a Cụ thể giải thuật của bài toán như sau Bước 1 So sánh a và b Nếu a b thì dừng giải thuật và thông báo a b a. Nếu a b thì chuyển sang bước 2 Bước 2 Nếu a b thì thay thế a bởi a-b nếu a b thì thay thế b bởi b-a. Quay lại thực hiện bước 1 Minh hoạ a 20 b 32 Bước thực hiện a b Kiểm tra điều kiện a b Bước 1 20 32 Sai Bước 2 20 12 Bước 1 20 12 Sai Bước 2 8 12 Bước 1 8 12 Sai Bước 2 8 4 Bước 1 8 4 Sai Bước 2 4 4 Bước 1 4 4 Đúng Kết quả là 20 32 4 102 Trường Đai hoc. Nông nghiên 1 - Giáo trình Tin hoc. đai cương 102 2. Các .