Giáo án Tin - Bài toán và thuật toán

CHƯƠNG 4 BÀI TOÁN VÀ THUẬT TOÁN Giáo viên hƣớng dẫn: Thầy Trần DoãnVinh Sinh viên thực hiện: Phan Thị Hồng Nhƣ Lớp: K56 A- CNTT 1. 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. 1. Khái niệm bài toán.   Ví dụ 1: Bài toán tìm ƣớc chung lớn nhất của 2 số nguyên dƣơng:   Input: Hai số nguyên dƣơng M và N;   Output: Ƣớc chung lớn nhất của M và N; 2. Khái niệm thuật toán.   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. 2.Khái niệm thuật toán. Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên. Trƣớc hết ta 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ố. 2.Khái niệm thuật toán.   Ý 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. 2.Khái niệm thuật toán.   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; CẢM ƠN CÁC EM ĐÃ THEO DÕI! CHÚC CÁC EM HỌC TỐT!