tailieunhanh - Bài giảng Tin học cơ sở: Bài 7 - Đào Kiến Quốc
Bài giảng Tin học cơ sở: Bài 7 - Thuật toán có nội dung trình bày về bài toán và thuật toán, các phương pháp biểu diễn thuật toán, các đặc trưng của thuật toán và một số nội dung liên quan khác. | BÀI GIẢNG TIN HỌC CƠ SỞ Giảng viên: ĐÀO KIẾN QUỐC Mobile Email: dkquoc@ BÀI 7 . THUẬT TOÁN ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NỘI DUNG Bài toán và thuật toán Các phương pháp biểu diễn thuật toán Các đặc trưng của thuật toán KHÁI NIỆM BÀI TOÁN Cho số tự nhiên n n có phải số nguyên tố hay không “có” hay “không” Cho hồ sơ điểm sinh viên Tìm tất cả các sinh viên có điểm trung bình trên 8 Danh sách sv thoả mãn Thiết kế hình học, tải trọng Tính sức bền Độ bền Input Yêu cầu Output Cho một bài toán nghĩa là cho input, và yêu cầu để tìm (tính) ra output KHÁI NIỆM THUẬT TOÁN Thuật toán (algorithm) là một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để giải một bài toán Ví dụ : thuật toán Euclid tìm ước số chung lớn nhất của hai số tự nhiên. USCLN(a,b) = USCLN (b,a)) Nếu a> b, USCLN(a,b) = USCLN (a-b,b) USCLN(a,a)= a THUẬT TOÁN EUCLID TIM USCLN CỦA HAI SỐ TỰ NHIÊN Bài toán: Cho hai số m, n tìm d = USCLN(m,n) Bước 1: Kiểm tra nếu m= n thì về bước 5, nếu không thực hiện tiếp bước 2 Bước 2: Nếu m> n thì về bước 4 nếu không thực hiện tiếp bước 3 Bước 3: m n m>n m n thì về bước 4, nếu không thực hiện tiếp bước 3 Bước 3: m NỘI DUNG Bài toán và thuật toán Các phương pháp biểu diễn thuật toán Các đặc trưng của thuật toán KHÁI NIỆM BÀI TOÁN Cho số tự nhiên n n có phải số nguyên tố hay không “có” hay “không” Cho hồ sơ điểm sinh viên Tìm tất cả các sinh viên có điểm trung bình trên 8 Danh sách sv thoả mãn Thiết kế hình học, tải trọng Tính sức bền Độ bền Input Yêu cầu Output Cho một bài toán nghĩa là cho input, và yêu cầu để tìm (tính) ra output KHÁI NIỆM THUẬT TOÁN Thuật toán (algorithm) là một quá trình gồm một dãy hữu hạn các thao tác có thể thực hiện được sắp xếp theo một trình tự xác định dùng để giải một bài toán Ví dụ : thuật toán Euclid tìm ước số chung lớn nhất của hai số tự nhiên. USCLN(a,b) = USCLN (b,a)) Nếu a> b, USCLN(a,b) = USCLN (a-b,b) USCLN(a,a)= a THUẬT TOÁN EUCLID TIM USCLN CỦA HAI SỐ TỰ NHIÊN Bài toán: Cho hai số m, n .
đang nạp các trang xem trước
