Banner-baigiang-1090_logo1
Banner-baigiang-1090_logo2

MUỐN TẮT QUẢNG CÁO?

Thư mục

Quảng cáo

Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Tìm kiếm theo tiêu đề

    Tìm kiếm Google

    Quảng cáo

    Quảng cáo

  • Quảng cáo

    Hướng dẫn sử dụng thư viện

    Hỗ trợ kĩ thuật

    Liên hệ quảng cáo

    • (04) 66 745 632
    • 0166 286 0000
    • contact@bachkim.vn

    Bài 9. Tin học và xã hội

    Tham khảo cùng nội dung: Bài giảng, Giáo án, E-learning, Bài mẫu, Sách giáo khoa, ...
    Nhấn vào đây để tải về
    Báo tài liệu có sai sót
    Nhắn tin cho tác giả
    (Tài liệu chưa được thẩm định)
    Nguồn:
    Người gửi: Nguyễn Thanh Vũ
    Ngày gửi: 18h:30' 12-10-2017
    Dung lượng: 3.0 MB
    Số lượt tải: 7
    Số lượt thích: 0 người
    1
    Bài 4: Bài toán và Thuật toán(tt)
    TIẾT 13+14: THUẬT TOÁN TÌM KIẾM TUẦN TỰ VÀ TÌM KIẾM NHỊ PHÂN
    2
    Tớ là một chú cá . Hãy tìm tớ trong đám bạn này nhé!!
    1
    2
    3
    4
    5
    Không phải rồi!
    Ồ! Không phải nữa rồi!

    Ồ! Lại sai nữa rồi!
    Hi! Hi! Chưa đúng đâu nghen!
    A! Ha! Tìm ra rồi!
    3
    XÁC ĐỊNH BÀI TOÁN
    OUPUT
    INPUT
    Dãy A gồm N số nguyên khác nhau a1,a2,…,aN và số nguyên k
    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 TUẦN TỰ
    (Sequential Search)
    4
    TÌM KIẾM TUẦN TỰ
    (Sequential Search)
    Ý tưởng:
    Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đó với khóa cho đến khi gặp một số hạng bằng khóa thì số hạng đó là số hạng cần tìm.
    Trong trường hợp thứ hai, dãy không có số hạng nào bằng khóa.
    5
    TÌM KIẾM TUẦN TỰ
    Ví dụ:
    Dãy A gồm các số
    1
    4
    2
    9
    8
    11
    5
    7
    a1 a2 a3 a4 a5 a6 a7 a8
    N=8
    K=9





    ||
    Tìm thấy
    , có a6=k, vậy chỉ số cần tìm là i=6
    K=6
    , không có giá trị nào



    Không tìm thấy
    6
    Ví dụ thuật toán tìm kiếm tuần tự
    2
    3
    4
    5
    6
    SAI
    ĐÚNG
    VẬY i = 6
    7
    Thuật toán tìm kiếm tuần tự
    SƠ ĐỒ KHỐI
    B1. Nhập N, a1,a2,…aN, khóa 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 3.
    LIỆT KÊ
    Nhập N, a1,a2….,aN,k
    i1
    ai=k
    Đưa ra i rồi
    kết thúc
    ii+1
    i>N?
    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
    Đúng
    Sai
    Đúng
    Sai
    8
    Nhập N, a1,…,aN,k
    ai = k
    i > N
    Đưa ra i rồi kềt thúc
    SAI
    ĐÚNG
    i  i + 1
    i  1
    i = 2
    i = 3
    i = 4
    i = 1
    SAI
    Với i = 4 thì a4 = 2
    THUẬT TOÁN TÌM KIẾM TUẦN TỰ
    (Sequentinal Search)
    N = 6; k = 2
    a1 = 5
    i = 2 < N
    a2 = 7
    i = 3 < N
    a3 = 1
    i = 4 < N
    a4 = 2
    Ví dụ
    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
    9
    Em có suy nhận xét gì sau khi xem xong?
    Người đọc sách muốn tìm trang 30 của quyển sách.
    Người ấy bắt đầu mở chính giữa quyển sách
    Số trang vừa mở được là trang 44.(chưa tìm đúng số trang cần tìm)
    Như vậy người ấy chỉ tìm trong phạm vi từ số trang từ đầu cho đến trang 44 (không cần tìm phần sau trang 44 )
    Tiếp tục phân đôi số trang từ trang đầu cho đến trang 44. Trang tìm được là trang 22, cứ tiếp tục như vậy cho đến khi tìm được trang 30.
    10
    Thuật toán tìm kiếm nhị phân
    (dãy A tăng)
    OUPUT
    INPUT
    Dãy A tăng gồm N số nguyên khác nhau a1,a2,…,aN và số nguyên k
    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
    Xác định bài toán
    11
    Ý tưởng
    aGiữa=k
    aGiữaChọn aGiữa ở giữa dãy để so
    sánh với k, trong đó Giữa=
    Giữa là chỉ số cần
    tìm. Kết thúc
    Tìm kiến trên dãy
    aGiữa+1,,,aN
    aGiữa>k
    Việc tìm kiếm
    chỉ xét trên dãy
    a1,…,aGiữa-1
    Quá trình lặp lại cho đến khi hoặc tìm thấy k hoặc vi phạm tìm kiếm bằng rỗng
    12
    150
    84
    6
    75
    9
    8
    7
    5
    4
    3
    2
    1
    i
    38
    15
    7
    2
    A
    Biểu diễn thuật toán :
    k = 150
    Lượt thứ nhất: aGiữa là a5 = 75; 75 < 150
     vùng tìm kiếm thu hẹp trong phạm vi từ a6 a9
    151
    90
     vùng tìm kiếm thu hẹp trong phạm vi từ a8 a9
    13
    50
    39
    75
    11
    30
    6
    9
    10
    9
    8
    7
    5
    4
    3
    2
    1
    i
    8
    6
    5
    1
    A
    k = 14
    Lượt thứ nhất: agiữa là a5 = 9; 9 < 14
     vùng tìm kiếm thu hẹp trong phạm vi từ a6 a10
    Lượt thứ hai: agiữa là a8 = 39; 39 > 14
     vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7;
    Lượt thứ ba: agiữa là a6 = 11; 11 < 14
     vùng tìm kiếm thu hẹp chỉ còn a7;
    Lượt thứ tư: agiữa là a 7 = 30 > 14
     Cuối=Giửa - 1 = 6 > đầu = 7
     Thông báo không tìm thấy số hạng có giá trị bằng 14.
    14
    Thuật toán liệt kê
    B1. Nhập N, a1,a2,…aN, khóa k;
    B2. Dau1, CuoiN;

    B3. Giữa 

    B4. Nếu aGiữa=k thì thông báo chỉ số Giữa rồi kết thúc;
    B5.Nếu aGiữa>k thì đặt Cuoi=Giua-1, rồi chuyển đến bước 7
    B6. DauGiua+1;
    B7. Nếu Dau>Cuoi thì thông báo dãy A không có số hạng có gíá trị bằng k rồi kết thúc
    B8. Quay lại B3
    LIỆT KÊ
    Chọn aGiữa ở giữa dãy để so
    sánh với k, trong đó Giữa=
    aGiữa=k
    Giữa là chỉ số cần
    tìm. Kết thúc
    aGiữa>k
    Việc tìm kiếm
    chỉ xét trên dãy
    a1,a2,…,aGiữa-1
    aGiữaTìm kiến trên dãy
    aGiữa+1,aGiữa+2,
    …,aN
    Quá trình lặp lại cho đến khi hoặc tìm thấy
    k hoặc vi phạm tìm kiếm bằng rỗng
    15
    SƠ ĐỒ KHỐI
    Nhập N và a1,a2,..,aN;k
    Dau1;Cuoi1
    Giua[(Dau+Cuoi)]/2
    aGiua=k?
    Dua ra Giua roi
    ket thuc
    aGiua>k
    CuoiGiua-1
    DauGiua+1
    Dau>Cuoi?
    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
    Đúng
    Đúng
    Đúng
    Sai
    Sai
    Sai
    B1. Nhập N, a1,a2,…aN, khóa k;
    B2. Dau1, CuoiN;
    B3. Giữa [(Dau+Cuoi)]/2
    B4. Nếu aGiữa=k thì thông báo chỉ số Giữa rồi kết thúc;
    B5.Nếu aGiữa>k thì đặt Cuoi=Giua-1, rồi chuyển đến bước 7
    B6. DauGiua+1;
    B7. Nếu Dau>Cuoi thì thông báo dãy A không có số hạng có gíá trị bằng k rồi kết thúc
    B8. Quay lại B3
    16
    Nhập N và a1,a2,..,aN;k
    Dau1;CuoiN
    Giua[(Dau+Cuoi)]/2
    aGiua=k?
    Dua ra Giua roi
    ket thuc
    aGiua>k
    CuoiGiua-1
    DauGiua+1
    Dau>Cuoi?
    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
    Đúng
    Đúng
    Đúng
    Sai
    Sai
    Sai
    SƠ ĐỒ KHỐI
    K=21, N=9
    1
    9
    5
    9
    6
    7
    9
    22
    6
    6
    6
    21
    Chỉ số cần tìm i=Giua=6
    1
    2
    3
     
    Gửi ý kiến