Bài 4: Bài toán và thuật toán
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (184.22 KB, 8 trang )
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 tốn.
Bài tốn là một việc nào đó ta muốn máy tính
thực hiện.
Bài tố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 tố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 tố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 tốn
Tính dừng: Thuật tố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 tố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
tốn bằng sơ đồ khối. Một số ví dụ về Thuật tốn.
