Thư mục

Hỗ trợ kỹ thuật

  • (Hotline:
    - (04) 66 745 632
    - 0982 124 899
    Email: hotro@violet.vn
    )

Thống kê

  • lượt truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Chào mừng quý vị đến với Thư viện Bài giảng điện tử.

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
    Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

    BÀI TOÁN VÀ THUẬT TOÁN

    (Tài liệu chưa được thẩm định)
    Nguồn:
    Người gửi: Hoàng Dũng
    Ngày gửi: 19h:06' 27-09-2009
    Dung lượng: 3.0 MB
    Số lượt tải: 210
    Số lượt thích: 0 người
    TRẦN HỮU TRANG
    TRU?NG TRUNG H?C PH? THƠNG

    TIN HỌC 10
    Đặng Hữu Hoàng
    BÀI 4
    BÀI TOÁN VÀ THUẬT TOÁN
    Thời gian 5 tiết
    KIỂ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 < N < 4 thì N là số nguyên tố;
    * Nếu N ≥ 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố;
    THUẬT TOÁN
    B1: Nhập số nguyên dương N;
    B2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc ;
    B3: Nếu N < 4 thì thông báo N là nguyên tố rồi kết thúc;
    B4: i  2;
    Cách 1 : Liệt kê các bước
    KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNG
    B5: Nếu i > 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 N
    N =1 ?
    N < 4 ?
    i  2
    i>[N ] ?
    N có chia hết cho i ?
    i  i +1
    Thô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.
    Đ
    S
    S
    Đ
    S
    S
    Đ
    Đ
    SƠ ĐỒ THUẬT TOÁN
    KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNG
    45 không là số nguyên tố.
    29 là số nguyên tố
    MÔ PHỎNG THUẬT TOÁN
    KIỂM TRA TÍNH NGUYÊN TỐ CỦA MỘT SỐ NGUYÊN DƯƠNG
    THUẬT TOÁN SẮP XẾP
    Hã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 a
    Hình b
    SẮ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 < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
    B4: M  M – 1, i  0;
    Cách 1 : Liệt kê các bước
    SẮP XẾP TRÁO ĐỔI
    B5: i  i + 1;
    B6: Nếu i > 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  N
    M < 2 ?
    M  M - 1; i 0
    i  i + 1
    i > M ?
    ai > ai+1 ?
    Tráo đổi
    ai và ai+1
    Đưa ra A đã sắp xếp
    Rồi kết thúc
    Đ
    Đ
    Đ
    S
    S
    S
    SƠ ĐỒ THUẬT TOÁN
    SẮP XẾP TRÁO ĐỔI
    Với N = 6 và dãy A gồm 6 số hạng sau :
    Lượt thứ nhất
    Lượt thứ hai
    Lượt thứ ba
    Lượt thứ tư
    MÔ PHỎNG THUẬT TOÁN
    SẮP XẾP TRÁO ĐỔI
    Hai 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ẾM
    TÌ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ước
    TÌM KIẾM TUẦN TỰ
    Nhập N, a1, a2,..., aN
    và k
    i  1
    ai = k ?
    Đưa ra i
    rồi kết thúc
    Đ
    S
    Đ
    i i + 1
    i > 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úc
    S
    SƠ ĐỒ THUẬT TOÁN
    TÌM KIẾM TUẦN TỰ
    5
    4
    3
    2
    1
    I
    51
    25
    11
    8
    9
    2
    4
    1
    7
    5
    A
    * 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:
    Với mọi i từ 1 10 không có ai có giá trị bằng 6
    5
    MÔ 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 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ừ agiua+1  an;
    Quá trình trên được lặp đi lặp lại cho đến khi tìm được Output .
    B1: Nhập N, các số hạng a1, a2,…, aN và giá trị khoá k;
    B2: Dau  1, Cuoi  N;
    B3: Giua ;
    B4: Nếu agiua = k thì thông báo chỉ số Giua, rồi kết thúc;
    B5: 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ước
    TÌ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ÂN
    10
    9
    8
    7
    6
    5
    4
    3
    2
    1
    i
    33
    31
    30
    22
    21
    9
    6
    5
    4
    2
    A
    Vớ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 a10;
    33
    31
    30
    22
    21
    Lượt thứ hai: agiua là a8 = 30; 30 > 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.
    22
    21
    6
    6
    21
    MÔ PHỎNG THUẬT TOÁN
    TÌM KIẾM NHỊ PHÂN
    DẶ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 hiện tháng 8 năm 2006
    Bài học đã
    KẾT THÚC
    Thân Ái Chào Các Em
    No_avatar
    thay` DANG HUU HOANG oi . khong biet thi` lam` chi cho met , lam con` thua xa cac truong dom~ , co lam thi` phai cho nhieu bai tap len chu lam` nhu thay chi to tui no' mat thoi gian len mang thoi ...... Dep me di cho roi`. do` khon nanThè&nbsp;lưỡi
     
    Gửi ý kiến
    print