Bài 4: Bài toán và thuật toán

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

Thêm vào BST

Báo xấu

137
lượt xem 9
download

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

Bài toán là một việc nào đó ta muốn máy tính thực hiện. Bài toán được cấu tạo từ hai thành phần cơ bản: Input: Các thông tin đã có Output: Các thông tin cần tìm từ Input. Ví dụ 1: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương: Xác định bài toán:   Input: Hai số nguyên dương M và N; Output: Ước chung lớn nhất của M và N; Khái niệm thuật toán. Khái niệm: Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho...

Chủ đề:

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

Lưu

Nội dung Text: Bài 4: Bài toán và thuật toán

Bài 4: Bài toán và thuật toán Giảng viên hướng dẫn: Thầy Trần Doãn Vinh Sinh viên thực hiện: Mai Văn Quý – K56A CNTT
Khái niệm bài toán. Bài toán là một việc nào đó ta muốn máy tính  thực hiện. Bài toán được cấu tạo từ hai thành phần cơ bản:  Input: Các thông tin đã có Output: Các thông tin cần tìm từ Input.
Ví dụ 1: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương: Xác định bài toán: Input: Hai số nguyên dương M và N;  Output: Ước chung lớn nhất của M và N; 
Khái niệm thuật toán. Khái niệm: Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên. Xác định bài toán: Input: Số nguyên dương N và dãy N số nguyên a1,a2,…,aN. Output: Giá trị lớn nhất (Max) của dãy số. Ý tưởng: Khởi tạo Max =a1; Với i chạy từ 2 đến N, so sanh ai với Max, nếu ai > Max thì Max nhận giá trị mới là ai. Thuật toán: Bước 1: Nhập N và dãy a1,a2,…,aN Bước 2: Max := a1; i=2  N; Bước 3: Nếu i > N; đưa ra giá trị Max rồi kết thúc; Ngược lại sang b4; Bước 4: Nếu ai > Max thì Max := ai; Bước 5: i := i+1; Quay lại bước 3
Sơ đồ khối:
Tính chất của thuật toán Tính dừng: Thuật toán phải kết thúc sau một số  hữu hạn lần thực hiện các thao tác Tính xác định: Sau khi thực hiện một thao tác thì  hoặc là thuật toán kết thúc hoặc có đúng một thao tác xác định để thực hiện tiếp theo. Tính đúng đắn: Sau khi thuật toán kết thúc phải  nhận được output cần tìm.
Bài tập về nhà Xác định và viết thuật toán cho các bài toán (biểu diễn  bằng 2 phương pháp liệt kê và sơ đồ khối) Giải phương trình bậc 2 Kiểm tra tính chính phương của một số nguyên dương. Kiểm tra tính nguyên tố của một số nguyên dương. Nghiên cứu trước nội dung tiếp theo: Cách mô tả thuật  toán bằng sơ đồ khối. Một số ví dụ về Thuật toán.