Dành cho Quảng cáo

Chào mừng quý vị đến với .

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 4. Bài toán và thuật toán

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: Hoàng Dũng
Ngày gửi: 19h:06' 27-09-2009
Dung lượng: 3.0 MB
Số lượt tải: 215
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