Bài giảng môn Tin học 7 - Bài 4: Bài toán và thuật toán

TRẦN ĐẠI NGHIà TIN HỌC 7Ñaëng Höõu HoaøngBÀI 4 BÀI TOÁN VÀ THUẬT TOÁNThời gian 5 tiếtKIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNG@ Xác định bài toán * INPUT : Số nguyên dương N;* OUTPUT : “ N là số nguyên tố “ hoặc “ N không là số nguyên tố “ @ Ý tưởng * Nếu N = 1 thì N không là số nguyên tố;* Nếu 1 thì thông báo N là nguyên tố rồi kết thúc; B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết  thúc; B7: i  i + 1 rồi quay lại bước 5;Nhập NN =1 ?N [N ] ?N có chia hết cho i ?i  i +1Thông báo N là số nguyên tố rồi kết thúc.Thông báo N không là số nguyên tố rồi kết thúc. §SS§SS§§SƠ ĐỒ THUẬT TOÁN KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNGi2345N/i29/229/329/429/5Chia hết không ?KhôngKhôngKhôngKhôngChia hếtKhôngChia hết không ?45/345/2N/i32i45 không là số nguyên tố. 29 là số nguyên tố Trường hợp 2: N = 29 ([ 29 ] = 5) Trường hợp 1: N = 45 ([ 45 ] = 6)MÔ PHỎNG THUẬT TOÁN KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNGTHUẬT TOÁN SẮP XẾPHãy tìm cách sắp xếp học sinh đứng chào cờ (hình a) theo thứ tự thấp trước cao sau (hình b)H×nh aH×nh bSẮP XẾP BẰNG TRÁO ĐỔI@ Xác định bài toán * INPUT : Dãy A gồm N số nguyên a1, a2,,aN.* OUTPUT : Dãy A được sắp xếp thành một dãy không giảm @ Ý tưởng Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa .THUẬT TOÁN B1: Nhập N, các số hạng a1, a2, , aN; B2: M  N; B3: Nếu M M thì quay lại bước 3; B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; B8: Quay lại bước 5.Nhập N và a1, a2,..., aN M  NM M ?ai > ai+1 ?Tráo đổi ai và ai+1Đưa ra A đã sắp xếpRồi kết thúc§§§SSSSƠ ĐỒ THUẬT TOÁN SẮP XẾP TRÁO ĐỔIVới N = 6 và dãy A gồm 6 số hạng sau : 359817Lượt thứ nhất 359817358917358197358179Lượt thứ hai358179351879351789Lượt thứ ba 351789315789315789135789Lượt thứ tư MÔ PHỎNG THUẬT TOÁN SẮP XẾP TRÁO ĐỔIHai bạn chó (Bi và Bo) chơi trốn tìm, Bo đã trốn vào trong những chiếc mũ của ông già Noel trên. Hãy chỉ ra cách tìm chiếc mũ mà Bo đang trốn ? Cho biết có những cách nào ?Bo trốn đâu nhỉ ?C1: Tìm kiếm tuần tự (mở từng mũ )C2: Do các mũ đã sắp xếp lớn dần, hai mũ đầu nhỏ hơn người của Bo nên chỉ tìm hai mũ sau thôi !THUẬT TOÁN TÌM KIẾMTÌM KIẾM TUẦN TỰ@ Xác định bài toán * INPUT : Dãy A gồm N số nguyên khác nhau a1, a2,,aN và số nguyên k;* OUTPUT : Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.@ Ý tưởng Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá k cho đến khi có sự trùng nhau, nếu đã xét tới cuối cùng mà không có sự trùng nhau thì có nghĩa là dãy A không có số hạng nào có giá trị k . B1: Nhập N, các số hạng a1, a2,, aN và giá trị khoá k; B2: i  1; B3: Nếu ai = k thì thông báo chỉ số i, rồi kết thúc; B4: i  i+1; B5: Nếu i > N 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; B6: Quay lại bước B3.THUẬT TOÁN Cách 1 : Liệt kê các bướcTÌM KIẾM TUẦN TỰNhập N, a1, a2,..., aN và ki  1ai = k ?Đưa ra irồi kết thúcĐSĐi i + 1i > N ?Thông báo dãy A không có số hạng có giá trị bằng dãy k, rồi kết thúcSSƠ ĐỒ THUẬT TOÁN TÌM KIẾM TUẦN TỰ54321I5125118924175A* Với k = 2 và dãy A gồm 10 số hạng như sau: tại vị trí i = 5 có a5 = 2 = k* Với k = 6 và dãy A gồm 10 số hạng như sau: A5714298112551I1234567891011 Với mọi i từ 1 10 không có ai có giá trị bằng 6 5MÔ PHỎNG THUẬT TOÁN TÌM KIẾM TUẦN TỰTÌM KIẾM NHỊ PHÂN@ Xác định bài toán INPUT : Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2,,aN và số nguyên k;* OUTPUT : Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.TÌM KIẾM NHỊ PHÂN@ Ý tưởng Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm bằng cách so sánh k với số hạng ở giữa dãy ( agiua), khi đó chỉ xảy ra một trong ba trường hợp :Nếu agiua = k tìm được chỉ số, kết thúc;Nếu agiua > k do dãy A đã được sắp xếp tăng nên việc tìm kiếm thu hẹp chỉ xét từ a1 agiua-1;Nếu agiua k thì đặt Cuoi = Giua – 1, rồi chuyển đến B7; B6: Dau  Giua +1;THUẬT TOÁN Cách 1 : Liệt kê các bướcTÌM KIẾM NHỊ PHÂN B7: Nếu Dau > Cuoi thì thông báo dãy A không có số hạng  có giá trị bằng k, rồi kết thúc; B8: Quay lại B3;SƠ ĐỒ THUẬT TOÁN TÌM KIẾM NHỊ PHÂN10987654321i333130222196542AVới k = 21 và dãy A gồm 10 số hạng như sau: Lượt thứ nhất: agiua là a5 = 9; 9 21 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7;Lượt thứ ba: agiua là a6 = 21; 21= 21   Vậy số cần tìm là i = 6.22216621MÔ PHỎNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂNDẶN DÒ1. Trả lời các câu hỏi 1, 2, 3, 4, 5, 6, 7 _ trang 44 _ sách giáo khoa .2. Thực hiện phần B “ Câu hỏi và bài tập “ _ trang 6 và trang 18, 19, 20, 21 _ Sách bài tập 3. Tuần sau : bài tập và kiểm tra 1 tiết. Thöïc hieän thaùng 8 naêm 2006Baøi hoïc ñaõ KEÁT THUÙCThaân AÙi Chaøo Caùc Em