Khái niệm thuật toán: - HOẠT ĐỘNG DẠY HỌC: 1.Ổn định: (1') - 123docz.net

Mục Lục

III. HOẠT ĐỘNG DẠY HỌC: 1.Ổn định: (1′)

2. Khái niệm thuật toán:

– Thuật toán để giải một bài
toán là một dãy hữu hạn các
thao tác được sắp xếp theo
một trình tự xác định sao cho
sau khi thực hiện dãy thao tác
ấy, từ Input của bài toán, ta
nhận được Output cần tìm.

– Ví dụ: Tìm giá trị lớn nhất
của một dãy số nguyên.

Giải

• Xác định bài toán:

+ Input: Số nguyên dương N
và dãy N số nguyên a1,…,aN.
+ Output: Giá trị lớn nhất Max
của dãy số.

• Ý tưởng:

+ Khởi tạo giá trị Max = a1.
+ Lần lượt với i từ 2 đến N,
so sánh giá trị số hạng ai với
giá trị Max, nếu ai > Max thì
Max nhận giá trị mới là ai.
• Thuật toán:

Có thể mô tả theo hai cách:
cách liệt kê và theo sơ đồ khối.
+ Cách liệt kê:

5′

chơi tìm một người cao
nhất trong một nhóm
nguời mà ta không nhìn
thấy những người ấy.
– Chú ý trong thuật toán i
là biến chỉ số có giá trị
nguyên thay đổi từ 2 đến
N+1.

– Hướng dẫn cách viết
phép gán “

←

”

– Theo em ta có thể vẽ tuỳ
tiện các hình khối trong sơ
đồ được không?

– Gọi HS đọc phần quy định
các hình khối trong SGK.

– Để hiểu rõ ta xét sơ đồ
khối của thuật toán nói trên.
– Gọi HS nhắc lại input và

output của bài toán.

– Như vậy phần nhập và
xuất dữ liệu được biểu
diễn bơi hình ô van.

– Các phép so sánh biến I
và biến N, phần tử ai và
biến Max được biểu diễn
bởi các hình thoi.

– Theo em thuật toán có
những tính chất nào?

– 3 HS lên tham gia trò
chơi.

– HS trả lời: không, mà
phải tuân theo một số
quy định cụ thể.
– HS đọc SGK.
– HS trả lời:
+ Input: Số nguyên
dương N và dãy N số
nguyên a1,…,aN.
+ Output: Giá trị lớn
nhất Max của dãy số.
– HS quan sát.

– HS đọc các tính chất
…,aN

Bước 2: Max

←

a1, i

←

Bước 3: Nếu i >N thì đưa ra
giá trị Max rối kết thúc

Bước 4: Nếu ai > Max thì
Max

←

Bước 5: i

←

i+1 rồi quay lại

bước 3.

+ Theo sơ đồ khối:

Người ta dùng một số khối,
đường mũi tên với quy định:
 Hình thoi thể hiện

thao tác so sánh.

 Hình chữ nhật thể
hiện các phép tính toán.
 Hình ô van thể hiện

thao tác nhập xuất dữ liệu.
 Các mũi tên quy định

trình tự thực hiện các
thao tác.

+ Với bài toán trên ta có sơ
đồ khối như sau:

* Các tính chất của thuật toán:

– Tính dừng: Thuật toán phải

Nhập N và dãy a1,.., aN
Maxa1, i2
i > N
Đưa ra
Max rồi
kết thúc
ai >
Max
ii +1
Maxai
Đ
S
Đ
S

3′

5′

10′

– Sau một số hữu hạn bước
thuật toán phải xác định
được các thông tin cần
tìm.

– Sau một bước của thuật
toán là bước tiếp theo hoặc
là thuật toán dừng.

– Em hiểu như thế nào về
tính đúng đắn?

– Đúng vậy sau khi thuật
toán dừng phải xác định
đúng các thông tin cần tìm.
– Xét các tính chất với
thuật toán tìm Max trên.
– Để hiểu rõ hơn về các
thuật toán ta lần lượt xét
một số ví dụ.

– Xác định Input và Output
của bài toán.

– Trình bày ý tưởng

– Gọi HS đọc ý tưởng
trong SGK.

– Mô phỏng việc thực hiện
thuật toán với N = 29

– Theo em bước 1 ta phải
làm gì?

trong SGK.

– HS trả lời: thuật toán
phải tìm đúng output
cần tìm.
– HS trả lời: input là số
nguyên dương N.
– HS bổ sung: output là
trả lời N có phải là số
nguyên tố không
– HS suy nghĩ.
– HS đọc SGK:
+ 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ố.
– HS trả lời: Nhập số
kết thúc sau một số hữu hạn
lần thực hiện các thao tác.
– Tính xác định: Sau khi thực
hiện một thao tác thì hoặc là
thuật toán kết thúc hoặc là có
đúng một thao tác xác định để
được thực hiện tiếp theo.

– Tính đúng đắn: Sau khi thuật
toán kết thúc, ta phải nhận
được Output cần tìm.

3. Một số ví dụ về thuật toánVí dụ 1: Kiểm tra tính nguyên

(Trang 29 -29 )

Một phần của tài liệu
TIN 10 HK I