Giáo án Tin học lớp 10 Bài 3: Bài toán và Thuật Toán

Bài 3 $4. Bài toán và Thuật Toán Giải thích một số khái niệm trong Sách giáo khoa 1.- Khái niệm bài toán tin học Vì tin học là một ngành khoa học chuyên nghiên cứu về việc xử lý thông tin bằng máy tính điện tử, nên bài toán tin học cũng không ngoài mục tiêu đó. Có như vậy, nó mới phục vụ đắc lực cho ngành công nghệ thông tin. Mà dã gọi là công nghệ thì nó vận hành như một nhà máy, mỗi chương trình ví như một cỗ máy: chế biến nguyên liệu thành sản phẩm tiêu dùng Chẳng hạn như nhà máy bánh kẹo, cứ đưa bột, đường, sữa, vào một đầu, thì qua một quá trình biến đổi nó cho ra đầu kia là bánh, là kẹo Còn về bài toán tin học thì nó nhận lấy thông tin vào, người lập trình phải bày mưu tính kế vạch ra cho máy cách làm thế nào để đưa thông tin ra theo đúng yêu cầu của khách hàng! 2. Chương trình và Thuật toán Chương trình chính là dãy hữu hạn các thao tác mà máy có thể thực hiện được để hoàn thành một công việc lớn nào đó. Thuật toán cũng như chương trình, có thể là một phần của chương trình, nêu bật lên được phương pháp, mưu mẹo, thủ thuật để giải quyết vấn đề. Ví dụ: Tính trung bình cộng của n số tự nhiên đầu tiên, n>0 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 dơn vị. Bước 4. Nều k>n thì thu lấy giá tị 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, theo Gauss, với n tự nhiên tùy ý s = 1+2++n = (1+n)*n/2. Chỉ cần một bước! 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. 3.- Một số ví dụ 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ố nguyên dương. Ở đây, ta chỉ xét trường hợp gay cấn: số n lẻ > 10. 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 đến trong khoảng từ 2 đế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 nêu trong SGK, trang 36 vẫn chưa là tốt nhất. Thật vậy: Sau bước 3, cần có Bước 3’ nữa là nều N>=4 thì: Nếu N chẵn sẽ không là số nguyên tố, kết thúc. Rồi Bước 4: Không cho i = 2 mà cho i = 3. Rồi Bước 7 Không cho i = i+1, mà là cho i = i+2, để chỉ xét chia cho số lẻ thôi. Với phân tích trên đây: Để ý [ n ] =9. N = 97 được xét thử chia cho 3,5,7,9 không lúc nào chia hết, nên N là số nguyên tố. N = 91 đượ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ố. Khi làm việc với máy tính, bạn không nên chủ quan vào “tài” tính toán nhanh của mình được, mà phải giả sử là mình gặp bài toán với con số rất lớn, không thể nhẩm một chốc một lát được. Do đó mới nhờ đến máy chứ! Tuy nhiên, cần phải thử (test) với những số nhỏ đã. Dễ mà sai thì còn nói gì đến khó! Bạn hãy thử xét với N = 32449 xem nó có là số nguyên tố không nhé! Thử theo thuật toán sau đây: Bước 1. Nhập N lể và > 10. Bước 2. k = 3. Cho mốc = [ n ], phần nguyên của n. Bước 3. 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 4. Khi không còn thỏa mãn điều kiện để tăng k lên nữa, tức là khi (N chia hết cho k) hoặc là (k>mốc), thì dựa vào đó mà phán quyết: Nếu k>mốc thì N là số nguyên tố, trái lại N không là số nguyên tố. OK 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 va SBT. Nếu ham mê nũa thì tìm thêm các bài tập khác! Chú ý: Không chỉ con người biết lập trình cho máy tính mà còn cho các thiết bị điện tử khác. Rồi Thượng đế còn giỏi hơn ta, vì Người đã lập trình cho mọi loài động/thực vật OK 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 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, ko 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ếu trùng với mùi người quen thì không sủa nữa, mà đổi thái độ sang vẫy đuôi mừng rỡ. 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. Hãng www.mail.yahoo.com khi thấy người sử dụng tạo tài khoán, đặt username 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 mấ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ả 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 dược Đó cũng là một thuật toán! Hãy xem: m-video-clip--David-Copperfield.html 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: Giai đoạn nào làm gì? Làm như thế nào? Để thi tốt nghiệp và đại học với kết quả tốt nhất, hay để đi du học, và rồi để thành đạt trong cuộc đời đầy sóng gió này! Chúc các bạn thành công! www.khoia0.com lightsmok@yahoo.com