Giáo án Tin học 10 Bài 3: 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 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. 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. Nhưng 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. Đị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 Ngoài ví dụ trong sách giáo khoa (học sinh tụ dọc), ta xét bài toán sau: Tính trung bình cộng của n số tự nhiên đầu tiên, n>1 nhập từ bàn phím. 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. Sau đây, ta đề cập một phần chương trình trê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 là cho S mới = S trước đó + k. 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ì thu lấy giá trị của 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! Thuật toán 2. (Gauss – nhà toán học Đức): Hồi học lớp 4, thầy giáo cho bài toán 1+2+3++100 = ? Gauss trả lời ngay đáp số: 5050. Thầy giáo vô cùng ngạc nhiên, hỏi Gauss: “Em làm ở nhà rồi à?”. Gauss bảo là không phải như vậy, mà 1+100 = 2+99= 3+98 = đều bằng 101 cả, mà có 50 cặp số có tổng như vậy, nên jết quả phải là 5050 Vậy, khi tính theo Gauss, với n tự nhiên tùy ý s = 1+2++n = (1+n)*n/2 thì chỉ cần 3 phép tính! Rõ ràng là thuật toán nêu bật phương pháp, mưu mẹo còn chương trình thì nêu lên trình tự là chính. 2 3.- Một số ví dụ về thuật toán (Học sinh tự dọc trong SGK) Tuy nhiên ta hãy phân tích thêm ví dụ 1. (trang 36): Kiểm tra tính nguyên tố của một số tự nhiên. Ở đây, ta chỉ xét trường hợp gay cấn: số n lẻ > 10. Kinh nghiệm mới đầu lấy số bé để thử đã, sau nâng lên thành tổng quát. Chẳng hạn n= 97. 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ố nguyên tố. Cách này cần 95 phép thử chia. Tổng quát hết n-2 phép thử. Thuật toán 2. Thử các phép chia 97 cho 3,5,7,,95 thôi, vì 97 lẻ không cần thử chia cho số chẵn! 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. 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 n , vì nếu n chia hết cho số a > n thì n = a*b, b sẽ <= n , đã được xét trong khoảng từ 3 đến n rồi. Cách này mất [ n /2] phép thử và ít hơn Thuật toán 3. Vậy thì tìm lời giải cho một bài toán tin học tức là thiết kế ra trình tự các bước cụ thể bắt máy giúp ta đạt mục tiêu hiệu quả nhất tức là tốn kém ít thời gian và bộ nhớ nhất. Do vậy phải nghĩ mưu mẹo, vận dụng toán học để có một thuật toán tối ưu! Thuật toán trong SGK, trang 36 chưa là tốt nhất vì họ phải mất [ n ] phép thử chia, vì khi tăng k họ phải tăng 1 đơn vị và nếu N là số chẵn họ vẫn bắt máy thử chia Ví dụ: Để ý. N = 97, [ 97 ] =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, [ 91 ] =9 được 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é! Thuật toán đầy đủ sẽ như sau: Cách 1. (Viết theo ngông ngữ giả lập trình) Bước 1. Nhập N tự nhiên. Bước 2. Nếu N < 2 thì thông báo N không là SNT và Kết thúc. Bước 3. Nếu N < 4 thì thông báo N là SNT và Kết thúc. Bước 4. Nếu N chắn thì thông báo N không là SNT và Kết thúc. Bước 5. k ← 3. Cho mốc ← [ n ], phần nguyên của n. (k ← 3 đọc là cho k bằng 3) Bước 6. Chừng nào (N không chia hết cho k) và (k ≤ mốc) thì còn tăng k lên 2 đơn vị. Bước 7. Nếu k>mốc thì thông báo N là SNT và Kết thúc, trái lại N không là SNT và Kết thúc. Cách 3. (Sơ đồ khối). Nhập số tự nhiên N 3 Sau đó bạn hãy đọc và suy ngẫm các ví dụ còn lại trong sách giáo khoa, làm hết các bài tập trong SGK và SBT. Nếu ham mê nũa thì tìm thêm các bài tập khác! Một số thuật toán thông dụng trong kỹ thuật và đời sống: 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, không về Bước 1, mà quay ly tâm để vắt nước ra và kết thúc. Ví dụ: Thượng để lập trình cho con chó khi thấy khác đến nhà: Bước 1. Sủa và ngửi mùi khách. Bước 2. Xét mùi người khách, so sánh với các mùi trong cơ sở dữ liệu mùi đã lưu từ trước: N<2 N không là SNT N<4 N có là SNT N chắn N không là SNT k ← 3, mốc ← [ n ] N không chia hết cho k và k < mốc k ← k+ 2 K > mốc N không là SNT + - + - + - + - - + N không là SNT 4 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, người quen đấy” thì nó mới thôi và lưu mùi người khách đó vào cơ sở dữ liệu để dùng về sau. Trái lại thi tiếp tục sủa/cắn cho đến khi người lạ bỏ đi Ví dụ: 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 đó không thì thu thập lại, và hiện ra kết quả tóm tắt từng 10 cái một. Ví dụ: Hãng Yahoo khi thấy người sử dụng tạo tài khoán thư điện tử xin đặt 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 có trùng với ai không. Nếu trùng thì thông 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 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 Rồi tại sao David Copperfield lại cưa đôi người ra được Đó cũng là một thuật toán! Học thuật toán, rèn luyện thuật toán, không chỉ để lập trình 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. (còn nữa) lightsmok@gmail.com www.lightsmok.wordpress.com Bài tập: Bạn hãy vẽ sơ đồ khối cho các thuật toán đã nêu ở trên như các mẫu ở sách giáo khoa đã làm!