Thuaät toaùn
THUẬT TOÁN
I. LÝ DO CHỌN SÁNG KIẾN.
Ngày nay, công nghệ thông tin được ứng dụng rộng rãi trong thực tế ở nhiều
lĩnh vực. Để đáp ứng nhu cầu đó của xã hội, môn Tin học đã được đưa vào
trường trung học phổ thông nhằm bước đầu cung cấp cho các em học sinh những
kiến thức cơ bản. Tuy nhiên, do đặc trưng của môn học có những khái niệm trừu
tượng nên các em gặp nhiều khó khăn trong quá trình tiếp thu bài. Đặc biệt trong
chương trình Tin học 11, khi học phần lập trình đòi hỏi phải tư duy thì khó khăn
nhất đối với các em là bước “Lựa chọn và thiết kế thuật toán”.
Việc lựa chọn và thiết kế thuật toán để giải bài toán trên máy tính là một
bước rất quan trọng. Bởi vì nếu bỏ qua bước này thì đôi khi việc lập trình cho ra
kết quả không tối ưu. Cũng giống như khi giải một bài tập toán, vật lý,... để tìm
ra kết quả chính xác thì buộc học sinh phải xác định công thức cần áp dụng là
công thức nào.
Khi nắm vững cách lựa chọn và thiết kế thuật toán, các em học sinh có thể
dễ dàng viết chương trình để giải bài toán trên máy tính bằng bất kỳ ngôn ngữ
bậc cao nào. Làm được việc này sẽ kích thích sự hứng thú học môn Tin học hơn.
Điều quan trọng hơn, việc lựa chọn và thiết kế thuật toán để giải bài toán
trên máy tính giúp rèn luyện cho học sinh khả năng tư duy, sáng tạo, biết phân
tích và giải quyết tình huống. Đây là những kỹ năng rất cần thiết để sau này các
em hoà nhập vào thực tế cuộc sống.
Từ những lý do nêu trên, qua thực tế giảng dạy bản thân tôi thấy cần đưa ra
một số kinh nghiệm để trao đổi với các đồng nghiệp nhằm giúp học sinh bước
đầu hiểu rõ và tiếp cận với thuật toán giải bài toán để việc lập trình đạt kết quả tốt
hơn. Vì thời gian có hạn, tôi chỉ trình bày cách xây dựng thuật toán để giải bài
toán bằng cách lập sơ đồ khối.
Trong phần trình bày của tôi không tránh khỏi những thiếu sót. Tôi rất
mong sự trao đổi, góp ý của quý thầy cô đồng nghiệp. Tôi xin chân thành cảm
ơn.
GV:
Huøynh Minh Taân
Trang: 1
Thuaät toaùn
II.THỰC TRẠNG TRƯỚC KHI THỰC HIỆN CÁC GIẢI PHÁP CỦA SÁNG
KIẾN
1) Thuận lợi:
Toàn ngành, toàn xã hội đang đề cao việc ứng dụng công nghệ thông
tin vào tất cả các lĩnh vực.
Môn Tin học là môn chính khoá trong trường phổ thông.
Các em học sinh thích được thực hành trên máy tính để nghiên cúu
tìm tòi.
Ngôn ngữ bậc cao trong môn Tin học gần gũi với ngôn ngữ giao tiếp
trong cuộc sống.
2) Khó khăn:
Máy vi tính và các thiết bị hổ trợ còn hạn chế
Phần lập trình hoàn toàn xa lạ với học sinh.
3) Số liệu thống kê
Qua các lớp tôi đang dạy, khi học đến phần lập trình Pascal đa số các em
học sinh còn lúng túng khi viết một chương trình. Đặc biệt là khái niệm
về bài toán và thuật toán, các em chưa nắm vững và hay bỏ quên bước
này. Do đó khi viết chương trình, sản phẩm thu được chưa đảm bảo tính
tối ưu.
III. NỘI DUNG ĐỀ TÀI
1) Cơ sở lý luận
Đa số các câu nói hàng ngày của con người như: “Các bước để vá một
ruột xe bị lủng”, “Nếu….thì…”, “Nếu…thì…ngược lại…”, “Trong khi
….thì làm….” đều có thể diển đạt bằng ngôn ngữ Sơ đồ khối .
Điều quan trọng là khi đã xây dựng được thuật toán bằng sơ đồ khối thì
ta có thể sử dụng bất kỳ một ngôn ngữ bậc cao nào cũng viết được
chương trình một cách rất thuận tiện và đảm bảo tính tối ưu.
2). Noäi dung,biện pháp thực hiện các giải pháp cuûa saùng kieán.
GV:
Huøynh Minh Taân
Trang: 2
Thuaät toaùn
TÓM TẮT LÝ THUYẾT
A) BAØI TOAÙN.
Trong phạm vi tin học, có thể quan niệm bài toán là một việc nào đó mà ta
muốn máy tính thực hiện.
Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố:
o Đưa vào máy thông tin gì (Input)
o Cần lấy ra thông tin gì (Output).
B) THUAÄT TOAÙN
a). 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.
Những đặc trưng cơ bản của thuật toán:
Tính tổng quát: Thuật toán không đề cập chỉ một bài toán riêng lẽ mà
bao hàm một lớp bài toán cùng một kiểu,
Có giới hạn: Quá trình biến đổi từ thông tin ban đầu đến kết quả cuối
cùng qua một số giới hạn các biến đổi.
Tính duy nhất: Toàn bộ quá trình biến đổi, cũng như trình tự thực
hiện phải được xác định và là duy nhất. Như vậy khi dùng thuật toán
cùng một tin tức ban đầu phải có cùng một kết quả.Trong thuật toán ở
mỗi giai đoạn phải nêu chính xác các bước tiếp theo, có nghĩa là thứ
tự thực hiện, các thao tác và quyết định phải được quy định rõ ràng.
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.
Thuật toán có thể phân loại như sau:
Thuật toán không phân nhánh
Thuật toán có phân nhánh
Thuật toán theo chu trình có bước lặp xác định và có bước lặp không
xác định.
GV:
Huøynh Minh Taân
Trang: 3
Thuaät toaùn
Thuật toán không phân nhánh là thuật toán đơn giản nhất. Trong thực
tế thường gặp thuật toán phân nhánh theo các điều kiện so sánh đúng
hoặc sai. Phổ biến nhất trong các bài toán thực tế là thuật toán gồm nhiều
chu trình , theo nhiều nhánh, đó là đặc trưng của thuật toán giaỉ các bài
toán khoa học kỷ thuật
b). Các kí hiệu để diễn tả thuật toán bằng sơ đồ khối.
Thể hiện thao tác so sánh
Thể hiện các phép tính toán
Thể hiện các thao tác nhập, xuất dữ liệu
Quy định trình tự thực hiện các phép toán
Lưu ý:
Với hình ô van thì chỉ có một hướng mũi tên đi ra cho trường hợp
thao tác nhập dữ liệu và chỉ có một hướng đi vào cho thao tác xuất
dữ liệu
Với hình chữ nhật thì có một hướng mũi tên vào và một hướng mũi
tên ra
Với hình thoi thì có một hướng mũi tên vào và hai hướng mũi tên ra
GV:
Huøynh Minh Taân
Trang: 4
Thuaät toaùn
MỘT SỐ VÍ DỤ
VỀ LỰA CHỌN VÀ THIẾT KẾ THUẬT TOÁN
. Thuật toán không phân nhánh
VD1:
Cho A=x2+y2;
B=x+y+3A;
C=xy+A-2B2;
x,y R. Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối để tính C
* Xác định bài toán
Input: x,y
Output: C
Lưu ý: Muốn tính được C thì đầu tiên ta phải tính A và B
Sơ đồ khối
Nhập x, y
Ax*x+y*y
B x+y+3*A
C x*y+A-2*B*B
Thông báo
C rồi kết
thúc
GV:
Huøynh Minh Taân
Trang: 5
Thuaät toaùn
VD2:
Tính vận tốc v khi chạm đất của một vật rơi từ độ cao h, biết rằng v= 2 gh , trong
đó g là gia tốc rơi tự do và g = 9.8 m/s 2. Độ cao h được nhập từ bàn phím. Hãy mô tả
thuật toán giải bài toán bằng sơ đồ khối.
* Xác định bài toán
Input: h
Output: v
Lưu ý: Ta có thể khai báo g là hằng số hoặc không cũng được
Sơ đồ khối
Nhập h
v
Thông báo v
rồi kết thúc
BÀI TẬP ĐỀ NGHỊ
Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối:
Bài 1:
Nhập từ bàn phím độ dài 3 cạnh của tam giác ABC, rồi tính chu vi, diện tích và
các đường cao của tam giác.
Hướng dẫn:
- Input: độ dài 3 cạnh a,b,c
- Output: chuvi, dientich, các đường cao ha,hb,hc
- Sử dụng các công thức:
Chu vi:
2p=a+b+c;
GV:
Huøynh Minh Taân
Trang: 6
Thuaät toaùn
Diện tích:
s = p(p-a)(p-b)(p-c) ;
Các đường cao:
2s
ha= a ;
,
2s
hb= b ;
2s
hc= c ;
Bài 2
Nhập từ bàn phím toạ độ 3 điểm A,B,C. Tính tích vô hướng của hai vectơ AB
và AC .
Hướng dẫn:
- Input: Toạ độ 3 điểm A, B và C;
- Output: Tích vô hướng AB. AC ;
- Sử dụng các công thức: uuur
vectơ:
AB=(x B -x A ;y B -y A ) ;
uuur
AC=(x C -x A ;y C -y A ) ;
uuur uuur
AB.AC=(x
B -x A ).(x C -x A )+(y B -y A ).(y C -y A ) ;
Tích vô hướng:
Bài 3
Nhập từ bàn phím toạ độ 3 điểm A,B,C. Tính độ dài các đoạn thẳng AB,AC và
BC.
Hướng dẫn:
- Input: Toạ độ 3 điểm A, B và C;
- Output: Độ dài các đoạn thẳng AB,AC và BC
- Sử dụng các công thức:
AB=
uuur
AB = (x B -x A ) 2 +(y B -y A ) 2
;
Bài 4
Giải tam giác khi biết góc B, cạnh a và góc C.
Hướng dẫn
- Input: Góc B , C và cạnh a;
- Output: Góc A, cạnh b và c
- Sử dụng các công thức:
.
* Đổi độ ra rad : 180 ;
* A+B+C=1800;
GV:
Huøynh Minh Taân
Trang: 7
Thuaät toaùn
a
b
c
=
=
* sinA sinB sinC ;
GV:
Huøynh Minh Taân
Trang: 8
Thuaät toaùn
. Thuật toán có phân nhánh
Sơ đồ:
Dạng thiếu
Đúng
Điều
kiện
Câu lệnh
Sai
Dạng đủ
Câu lệnh
2
Chú ý:
GV:
Sai
Điều
kiện
Đúng
Câu lệnh
1
Ta có thể sử dụng cấu trúc rẽ nhánh lồng nhau
Huøynh Minh Taân
Trang: 9
Thuaät toaùn
VD3:
Tìm số lớn nhất trong hai số thực A và B
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: A,B
Output: Số lớn nhất trong hai số
Sơ đồ khối
Nhập A,B
A>=B
S
Lớn nhất là B
và kết thúc
Đ
Lớn nhất là A
và kết thúc
GV:
Huøynh Minh Taân
Trang: 10
Thuaät toaùn
VD4:
Tìm số lớn nhất trong ba số thực A , B và C
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: ba số thực A,B,C
Output: Số lớn nhất trong ba số
Sơ đồ khối
Nhập A,B,C
Đ
A> C
A> B
S
S
B>C
Đ
Đ
Max A
S
Max C
Max B
Thông báo Max
và kết thúc
GV:
Huøynh Minh Taân
Trang: 11
Thuaät toaùn
VD5:
Cho phương trình bậc hai ax2+bx+c=0
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: a,b,c (a<>0)
Output: Nghiệm x thoả phương trình ax2+bx+c=0
Sơ đồ khối
Nhập a,b,c
(a<>0)
Db*b-4*a*c
D<0
Thông báo PT
vô nghiệm rồi
kết thúc
Đ
S
D=0
Đ
S
x1 (-b+sqrt(D))/(2*a)
x2 (-b-sqrt(D))/(2*a)
GV:
Huøynh Minh Taân
x-b/(2*a)
Thông báo PT
có nghiệm
kép x rồi kết
thúc
Thông báo PT
có 2 nghiệm x1
và x2 rồi kết
thúc
Trang: 12
Thuaät toaùn
VD6: Cho bài toán
x 2 y 2 ; nếu
x 2 y2 1
z x y; nếu x 2 y 2 1 và y x
0.5; nếu x 2 y 2 1 và y x
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: x,y;
Output: z
Sơ đồ khối
Nhập x, y
x*x+y*y<=
1
Đ
z x*x+y*y
Thông báo z
rồi kết thúc
Đ
z x+y
Thông báo z
rồi kết thúc
S
y>=x
S
z 0.5
GV:
Huøynh Minh Taân
Thông báo z
rồi kết thúc
Trang: 13
Thuaät toaùn
BÀI TẬP ĐỀ NGHỊ
Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối:
Bài 1: Nhập dữ liệu là tháng trong năm
Hướng dẫn
- Tháng trong năm phải từ 1 đến 12
- Nếu thoả thì thông báo là tháng, ngược lại thì thông báo không
phải là tháng trong năm
Bài 2: Nhập vào một năm cho ra số ngày của năm đó
Hướng dẫn
- Có hai loại ngày là 365 ngày và 366 ngày
- Năm nhuận là 365 ngày, không nhuận là 366 ngày
- Năm nhuận là năm chia hết cho 400 hoặc chia hết cho 4 nhưng
không chia hết cho 100
Bài 3: Tính căn bậc hai của một số
Hướng dẫn
- Sử dụng hàm Sqrt(x)
- Nếu nhập vào số âm thì thông báo số đó không có căn bậc hai
Bài 4: Giải bất phương trình ax+b> 0
Hướng dẫn
- Sử dụng thuật toán như các bài đã gặp
Bài 5: Nhập một điểm thi của học sinh và phân loại nếu điểm thấp hơn 5 thì không
đạt, từ 5 đến < 6.5 thì trung bình, từ 6.5 đến <8 thì khá, từ 8 đến < 9 thì giỏi, >=9
đến 10 thì xuất sắc.
Hướng dẫn
- Sử dụng If lồng nhau
GV:
Huøynh Minh Taân
Trang: 14
Thuaät toaùn
. Thuật toán theo chu trình có bước lặp xác định.
Sơ đồ:
Câu lệnh
Đúng
GV:
Huøynh Minh Taân
Điều
kiện
Sai
Trang: 15
Thuaät toaùn
VD7:
n
Tính tổng
S x1 x 2 ... x n ;(S x k )
k 1
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: Số nguyên dương n và x1,x2,…,xn;
Output: Tổng S
Sơ đồ khối
Nhập n và
x1,x2,…,xn
S0
i1
SS+xi
ii+1
Đ
i <= n
S
Thông báo
S rồi kết
thúc
GV:
Huøynh Minh Taân
Trang: 16
Thuaät toaùn
VD8:
Tính giai thừa của một số nguyên dương n (n!=1.2.......(n-1).n.
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: Số nguyên dương n;
Output: Giai thừa của n (GT)
Sơ đồ khối
Nhập n
GT1
i1
GTGT*i
ii+1
Đ
i n
S
Thông báo
GT rồi kết
thúc
GV:
Huøynh Minh Taân
Trang: 17
Thuaät toaùn
VD9:
Tính tồng
S
1
1
1
1
...
a a 1 a 2
a n (a số nguyên và a > 2 )
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: Số nguyên dương n và a;
Output: Tổng S
Sơ đồ khối
Nhập n và a
S0
i0
SS+1/(a+i)
ii+1
Đ
i n
S
Thông báo S
rồi kết thúc
GV:
Huøynh Minh Taân
Trang: 18
Thuaät toaùn
BÀI TẬP ĐỀ NGHỊ
Hãy mô tả thuật toán giải các bài toán sau bằng sơ đồ khối:
Bài 1: Tính tổng
S= 1 + 2 + 3 + ………..+ n
với n nhập từ bàn phím
Bài 2: Tính tổng
S 1
1 1
1
.......
2 3
n
với n nhập từ bàn phím
Bài 3: Tính tổng
S= 12 + 22 + 32 + ………..+ n2
với n nhập từ bàn phím
Bài 4: Tính tổng
S 1
1 1
1
.......
1! 2!
n!
với n nhập từ bàn phím
Bài 5: Tính tích
n
P x 1*x 2 *...* x n ;(P x i )
i 1
với n nhập từ bàn phím
Hướng dẫn
Các bài trên làm tương tự như ví dụ 7, 8, 9
GV:
Huøynh Minh Taân
Trang: 19
Thuaät toaùn
. Thuật toán theo chu trình có bước lặp không xác định.
Sơ đồ:
Điều
kiện
Sai
Đúng
Câu lệnh
VD10:
Tìm ước số chung lớn nhất của hai số nguyên dương a và b
Hãy mô tả thuật toán giải bài toán bằng sơ đồ khối
* Xác định bài toán
Input: Số nguyên dương a,b;
Output: UCLN(a,b)
Sơ đồ khối
Nhập a, b
a <> b
S
Thông báo
UCLN là a, kết
thúc
GV:
Huøynh Minh Taân
Đ
a>b
S
bb - a
Đ
aa - b
Trang: 20
- Xem thêm -