Toán - Bài toán và thuật toán

Thửùc hieọn thaựng 10 naờm 2010Chaứo mửứng quyự Thaày coõ veà dửù giụ,ứ thaờm lụựp 10C7VD1: Cho dãy số A có: 1, 2, 9, 4, 10, 5; k=4VD2: Cho dãy số B có: 1, 2, 4, 5, 9, 12; k=5 Bài toán: Dãy A được xếp thứ tự gồm N số nguyên khác nhau từ a1 .. aN ; và số nguyên k. Cần biết có hay không chỉ số i (1≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số đó.Bài toán trên có gỡ khác so với bài toán tỡm kiếm theo thuật toán tỡm kiếm tuần tự?BÀI TOÁN VÀ THUẬT TOÁN THUẬT TOÁN TèM KiẾM NHỊ PHÂNBài toán: Cho dãy A gồm N số nguyên khác nhau và dãy tăng có a1 .. aN ; và số nguyên k.Cần biết có hay không chỉ số i (1≤ i ≤ N) mà ai = k. Nếucó hãy cho biết chỉ số đó.Xác định bài toán:Input: Số nguyên dương N, dãy A được sắp xếp tăng a1 .. aN ; số nguyên k Output: + Chỉ số i khi ai = k + Thông báo không có số nào trong dãy A bằng kHãy xác định bài toán trên?BÀI TOÁN VÀ THUẬT TOÁN THUẬT TOÁN TèM KiẾM NHỊ PHÂNNhận xét: Vỡ dãy A là dãy tăng nên sau mỗi lần so sánh với khóa k đã cho ta sẽ thu hẹp được phạm vi tỡm kiếm + Nếu aGiua = k thỡ giua là chỉ số cần tỡm rồi kết thúc thuật toán. + Nếu aGiua > k việc tỡm kiếm chỉ thực hiện trên dãy a1 , a2 ,  aGiua -1. + Nếu aGiua k thỡ đặt Cuoi  Giua-1, rồi chuyển đến bước 7- Bước 6: Dau  Giua+1;- Bước 7: Nếu Dau > Cuoi thỡ thông báo dãy A không có số hạng nào có giá trị bằng k, rồi kết thúc.- Bước 8: Quay lại bước 3BÀI TOÁN VÀ THUẬT TOÁN THUẬT TOÁN TèM KiẾM NHỊ PHÂNDiễn tả thuật toán theo sơ đồ khốiNhập N, dãy a1 .. aN , số kDau 1, Cuoi  NGiua  [(Dau + Cuoi)/2]aGiua = k ?aGiua > k ?saiđúngđưa ra Giua rồi kết thúcCuoi Giua - 1Dau  Giua + 1Dau > Cuoi?đúngsaiđúngDãy A không có số hạng nào bằng krồi kết thúcsai* Mô phỏng thuật toán tỡm kiếm nhị phânVí dụ 1:Cho N = 6 và dãy A sắp xếp tăng dần: 1, 2, 4, 5 , 9 , 12 ; số k = 5i123456Dóy A1245912DauCuoiGiuaaGiuaLần duyệt12316344591225161449223464544Kết luận: ở lần duyệt thứ 3 thỡ aGiua = k = 5. Vậy chỉ số cần tỡm là : i = Giua = 4* Mô phỏng thuật toán tỡm kiếm nhị phânVí dụ 1:Cho N = 6 và dãy A sắp xếp tăng dần: 1, 2, 4, 5 , 9 , 12 ; số k = 10i123456Dóy A1245912DauCuoiGiuaaGiuaLần duyệt123163441291225161469223664564Kết luận: Tại lần duyệt thứ 4 Dau > Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị bằng 10Củng cố và hướng dẫn về nhà Chú ý: dãy số sau khi sắp xếp thứ tự, ta dùng thuật toán tim kiếm nhị phân Hoàn thành các bài tập ở Sgk và một số bài tập ở SBT để chuẩn bị cho giờ bài tập tiết sau Cho N = 6 và dãy A được sắp xếp giảm dần: 12, 9, 5, 4, 2, 1; số k = 4Mô phỏng thuật toán nhị phân Thửùc hieọn thaựng 10 naờm 2010Baứi hoùc ủaừ KEÁT THUÙCThaõn AÙi Chaứo Thaày coõ vaứ caực Em