Bài giảng Tin học lớp 10 - Bài 3, Tiết 4: Bài toán và thuật toán

Nội dung text: Bài giảng Tin học lớp 10 - Bài 3, Tiết 4: Bài toán và thuật toán

1. Bài 3 $4. Bài toán và thuật toán 1.- Khái niệm bài toán 2.- Khái niệm thuật toán 3.- Một số ví dụ về thuật toán
2. 1.- Khái niệm bài toán • Trong phạm vi Tin học, bài toán là một việc nào đó ta muốn máy thực hiện. Như vậy, ta cần quan tâm 2 yếu tố: Đầu vào và đầu ra: Đưa cho máy cái gì để thu được cái gì? • Đầu vào (Input) là các thông tin đã có. • Đầu ra (output) là các thông tin cần có từ đầu vào.
3. 2.- Khái niệm thuật toán • Chương trình là dãy hữu hạn các công việc có thể làm được để đạt được mục đích đề ra. • Làm thế nào để từ Input lần tìm ra Output là cả một vấn đề mưu mẹo, chiến lược, khôn khéo • Việc chỉ ra tường minh cách lần tìm ra Output của bài toán dược gọi là thuật toán. • Tuy nhiên, thuật toán cũng là một phần hoặc cả chương trình. • Do vậy, có thể nói: Thuật toán là một dãy hữu hạn các thao tác xác định để từ Input ta nhận được Output.
4. Định nghĩa này không chỉ dùng trong Tin học, mà còn trong hầu hết các lĩnh vực của cuộc sống, chẳng hạn: • Thuật toán quay Rubic. • Thuật toán Gauss để giải hệ n phương trình bậc nhất n ẩn. • Thuật toán khai căn tay. • Thuật toán Horner để tính nhanh giá trị của một đa thức
5. Bài toán: Tính trung bình cộng của n số tự nhiên đầu tiên, n>1 Chương trình: • Bước 1. Nhập n từ bàn phím. • Bước 2. Tính tổng s = 1+2+ +n. • Bước 3. Tính kết quả = s/n. • Bước 4. Đáp số: kq. Thuật toán thì có nhiều:
6. Thuật toán ở bước 2: Tính tổng s = 1+2+ +n? • Thuật toán 1. (Cơ bắp – cộng dồn): Bước 1. Cho S = 0 và k = 1. Bước 2. Cho S = S + k, tức tăng S thêm k đơn vị. Bước 3. Cho k = k+1, tức là tăng k lên 1 đơn vị. Bước 4. Nều k>n thì dược s và kết thúc! Trái lại thì quay về thực hiện bước 2. Cách làm trên, phải mất n-1 phép cộng, vô cùng vất vả khi n rất lớn!
7. Thuật toán 2. (Gauss – nhà toán học Đức): • Hồi học lớp 4, gặp bài toán 1+2+3+ +100 = ? Gauss trả lời ngay đáp số là 5050. • Thầy giáo vô cùng ngạc nhiên hỏi: “Em làm ở nhà rồi à?”. Gauss bảo là không phải như vậy, mà nhận xét: 1+100 = 2+99 = 3+98 = đều bằng 101 cả, mà có 50 cặp, nên tổng = 5050 • Vậy theo Gauss, với n tự nhiên tùy ý > 1, s = 1+2+ +n = (1+n)*n/2. Chỉ cần 3 phép tính!
8. 3.- Một số ví dụ về thuật toán • Ví dụ 1: Kiểm tra tính nguyên tố của một số tự nhiên n>10. • Chẳng hạn n= 97. Phân tích: • Thuật toán 1. • Thử các phép chia 97 cho 2,3,4,5 ,96. Nếu không khi nào chia hết thì 97 là số nguyên tố, trái lại 97 không là số Tổng quát hết n-2 phép thử.
9. Thuật toán 2. • Thử các phép chia 97 cho 3, 5, 7, , 95. • Cách này mất [(n-2)/2] phép thử và ít hơn Thuật toán 1. Thuật toán 3. • Thử các phép chia 97 cho 3,5,7, ,47 thôi, vì 97 lẻ không cần thử chia cho số chẵn và không chia hết cho các số lớn hơn n/2. • Cách này mất [(n-2)/4] phép thử và ít hơn Thuật toán 2.
10. • Thuật toán 4. • Thử các phép chia 97 cho 3,5,7,9 thôi, vì 97 lẻ không cần thử chia cho số chẵn và không cần xét thử chia các số lớn hơn sqrt(n), vì nếu n chia hết cho số a > sqrt(n), thì n = a*b, b sẽ <= sqrt(n), đã được xét trong khoảng từ 3 đến sqrt(n) rồi. • Cách này mất [sqrt(n)/2] phép thử và ít hơn Thuật toán 3. Và có lẽ ngắn hơn cả! Thuật toán trong SGK, trang 36 chưa là tốt nhất vì họ phải mất [sqrt(n)] phép chia thử.
11. • Ví dụ ở thuật toán 4. • n = 97, [sqrt(n)] = 9, chỉ xét thử chia cho 3,5,7,9. Ta thấy không lúc nào chia hết, nên n là số nguyên tố. • n = 91, [sqrt(n)] = 9 được lần lượt xét thử chia cho 3,5,7,9 thấy nó chia hết cho 7, n không là số nguyên tố. • n = 32749 xem nó có là số nguyên tố không nhé!
12. Cách trình bày một thuật toán • Cách 1. Nêu ra từng bước cụ thể. Cách này rất hay dùng để trình bày nhanh phương án giải bài toán. • Cách 2. Vẽ sơ đồ khối, công phu hơn, nhưng trực quan hơn, hiện đại hơn. Các nhà khoa học, các nhà quản lý và các nhà doanh nghiệp rất hay làm theo cách này.
13. Ví dụ: Giải phương trình: ax + b = 0. Cách 1. • Bước 1. Nhập a, b là 2 số thực. • Bước 2. Xét a: Nếu a 0 thì cho x = -b/a, đáp số rồi hết. Trái lại, trong bối cảnh đó: Nếu b 0 thì trả lời Vô nghiệm và hết. Trái lại trả lời mọi x thức đều là nghiệm
14. • Cách 2.
15. Một số thuật toán thông dụng trong kỹ thuật • Ví dụ: Thuật toán cho cái máy giặt: Bước 1. Hút nước vào. Bước 2. Đun nước nóng lên. Bước 3. Quay vật vã cho bật ghét bẩn thôi ra. Bước 4. Xả nước ra và đo độ đục của nước. Bước 5. Xét độ đục: Nếu còn đục thì quay về Bước 1. Bước 6. Lúc này hết đục rồi thì mà quay ly tâm để vắt nước ra và kết thúc.
16. • Ví dụ: Thượng để lập trình cho con chó: • Bước 1. Sủa và ngửi mùi khách. • Bước 2. So sánh mùi đó với các mùi trong cơ sở dữ liệu lưu từ trước: Nếu là mùi người quen thì không sủa nữa, mà đổi thái độ sang mừng rỡ và hết. Trái lại, thì sửa tiếp và chờ “ý kiến” của chủ nhà. • Bước 3. Nếu chủ nhà bảo “Thôi im đi, không sửa nữa” thì nó mới thôi và lưu mùi đó vào cơ sở dữ liệu để dùng về sau. Trái lại thì tiếp tục sủa/cắn cho đến khi người lạ bỏ đi và hết.
17. Trên Internet? • Ví dụ: Tìm kiếm trên mạng Hãng www.google.com khi nhận được từ khóa thì đi tìm trong hàng triệu trang web xem có trang nào có từ khóa đó thì thu thập lại, và hiện ra kết quả tóm tắt tên của các đường link, từng 10 cái một mỗi lần
18. • Ví dụ: Hãng yahoo khi thấy người sử dụng tạo tài khoán thư diện tử xin đăng ký một user name nào đó, thì lập tức tìm lục trong hàng triệu tài khoản email để xem name đó có trùng với ai không. Nếu trùng thì báo cho người sử dụng rằng đã có người đặt rồi, và người sử dụng đó phải đặt cái tên khác, cho đến khi không trùng với ai cả hoặc bỏ cuộc! Vấn đề ở chỗ họ có thủ thuật tìm kiếm thế nào mà nhanh như vậy! Chỉ trong giây lát
19. • Học thuật toán, rèn luyện thuật toán, không chỉ cho máy tính, mà hãy lập trình cho chính công việc mình: Từng giai đoạn nào làm gì? Làm như thế nào? • Cuối cùng là để trở thành người có ích cho xã hội và thành đạt trong cuộc đời đầy sóng gió này! • Chúc các bạn thành công! lightsmok@gmail.com www.lightsmok.wordpress.com