Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
THÔNG TIN CHUNG VỀ SÁNG KIẾN<br />
<br />
<br />
<br />
<br />
1. Tên sáng kiến: <br />
Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình giải <br />
bài toán trên máy tính.<br />
2. Lĩnh vực áp dụng sáng kiến: <br />
Áp dụng trong giảng dạy lập trình môn tin học 11.<br />
3. Thời gian áp dụng sáng kiến: <br />
Từ ngày 20, tháng 09, năm 2014 đến ngày 20, tháng 4, năm 2016.<br />
4. Tác giả: <br />
Họ và tên: Nguyễn Thị Phương Ngân.<br />
Năm sinh: 1986.<br />
Nơi thường trú: Khu Tập thể giáo viên trường THPT Mỹ Tho.<br />
Trình độ chuyên môn: cử nhân sư phạm tin học.<br />
Chức vụ công tác: Giáo viên dạy môn Tin học.<br />
Nơi làm việc: Trường THPT Mỹ Tho.<br />
Điện thoại: 0975061791.<br />
5. Đơn vị áp dụng sáng kiến:<br />
Tên đơn vị: Trường THPT Mỹ Tho.<br />
Địa chỉ: xã Yên Chính – Ý Yên – Nam Định.<br />
<br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 1<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
<br />
<br />
MỤC LỤC<br />
<br />
Trang<br />
Trang..................................................................................................................................2<br />
<br />
<br />
<br />
<br />
Đề tài: Hướng dẫn học sinh lựa chọn thuật toán tối ưu khi lập trình <br />
giải bài toán trên máy tính.<br />
<br />
<br />
I. Điều kiện, hoàn cảnh tạo ra sáng kiến<br />
Hiện nay trên thế giới, tin học ngày càng phát triển mạnh mẽ, có ứng <br />
dụng rộng rãi trong hầu hết các lĩnh vực của xã hội, sự phát triển của tin <br />
học được tính bằng giờ, cứ mỗi giờ lại có thêm phiên bản phần mềm tin <br />
học được nâng cấp hay có những phần mềm mới được tạo ra. Ở Việt Nam <br />
<br />
<br />
Trường THPT Mỹ Tho 2<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
cũng vậy, tin học có mặt trợ giúp trong mọi ngành nghề, ở khắp mọi nơi, <br />
từ thành thị đến nông thôn và phổ biến với tất cả mọi người từ người già <br />
đến trẻ, từ những công nhân viên đến những người nông dân đều rất cần <br />
đến sự trợ giúp của tin học. Ngày nay, tin học đã trở thành một phần không <br />
thể thiếu trong cuộc sống của mỗi chúng ta.<br />
Lịch sử phát triển xã hội loài người đang ở nền văn minh thứ ba. Sự hình <br />
thành và phát triển của mỗi nền văn minh gắn liền với một công cụ lao <br />
động mới, chẳng hạn như máy hơi nước – đối với nền văn minh công <br />
nghiệp, máy tính điện tử đối với nền văn minh thông tin. Máy tính chính <br />
là công cụ trợ giúp cho sự phát triển Tin học, có thể đáp ứng nhu cầu tính <br />
toán, lưu trữ, tìm kiếm,.., và xử lý thông tin một cách có hiệu quả.<br />
Máy tính có tốc độ xử lý nhanh (hàng tỉ lệnh trên 1 giây) nhưng nó cũng <br />
có giới hạn. Tất cả các máy tìm kiếm (ví dụ như google, yahoo hay <br />
gmail…) đều được lập trình bằng các đoạn lệnh của một Ngôn ngữ lập <br />
trình nào đó nhưng máy nào sử dụng thuật toán tối ưu (tốt nhất ) thì tìm <br />
kiếm được nhanh, chính xác và sẽ được đông đảo người dùng lựa chọn sử <br />
dụng.<br />
Với một bài toán cũng vậy, một bài toán có thể có nhiều thuật toán để <br />
giải nhưng ta nên lựa chọn thuật toán tối ưu (có số phép tính ít nhất). Vậy <br />
việc lựa chọn một thuật toán đưa tới kết quả nhanh là một đòi hỏi thực tế <br />
cần được quan tâm đặc biệt. Do đó, trong khi viết chương trình ta nên tìm <br />
cách viết sao cho chương trình thực hiện càng ít phép toán càng tốt. Xuất <br />
phát từ thực tế đó tôi đưa ra đề tài: “Hướng dẫn học sinh lựa chọn <br />
thuật toán tối ưu khi lập trình giải bài toán trên máy tính” nhằm định <br />
<br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 3<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
hướng cho các em học sinh biết phân tích, lựa chọn thuật toán tối ưu trước <br />
khi lập trình giải bài toán trên máy tính.<br />
II. Mô tả giải pháp<br />
1. Thực trạng<br />
Nhận thấy tầm quan trọng của Tin học đối với thực tế cuộc sống, mọi <br />
lĩnh vực, ngành nghề, từ năm học 2007 2008 Bộ giáo dục và đào tạo đã <br />
đưa môn Tin học thành môn học chính thức ở tất cả các trường Trung học <br />
cơ sở, Trung học phổ thông. Mỗi khối lớp được biên soạn chương trình từ <br />
cơ bản đến cụ thể từng vấn đề nhằm giúp học sinh có sự hiểu biết về Tin <br />
học, có sự tư duy, logic giữa Tin học với các môn học khác, từ đó giúp các <br />
em vận dụng vào thực tế. <br />
Trong chương trình Tin học 11 đi sâu vào dạy học lập trình, các em học <br />
sinh đã hiểu được những khái niệm cơ sở, kiến thức về lập trình, đã có thể <br />
vận dụng kiến thức để lập trình giải các bài toán trên máy tính. Tuy nhiên <br />
các em lập trình còn mang tính chất cảm tính, lập trình sao cho chương trình <br />
chạy được chứ chưa biết phân tích, lựa chọn thuật toán tối ưu để giải <br />
quyết bài toán. Trước thực tế đó tôi đưa ra đề tài: “Hướng dẫn học sinh <br />
lựa chọn thuật toán tối ưu khi lập trình giải bài toán trên máy tính” <br />
nhằm định hướng cho các em biết thuật toán tối ưu là gì, vì sao phải lựa <br />
chọn thuật toán tối ưu, để từ đó các em biết phân tích, lựa chọn thuật toán <br />
trước khi lập trình giải bài toán trên máy tính.<br />
2. Các giải pháp trọng tâm<br />
2.1. Mục đích, yêu cầu<br />
Đề tài này đi sâu vào mục đích trao đổi cùng đồng nghiệp, các thầy cô <br />
giáo vai trò của việc lựa chọn được thuật toán tối ưu.<br />
<br />
<br />
Trường THPT Mỹ Tho 4<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
Giúp các em học sinh nhớ lại quy trình khi lập trình giải một bài toán trên <br />
máy tính, đặc biệt là bước lựa chọn thuật toán giải bài toán rất quan trọng.<br />
Giúp các em học sinh hiểu được thuật toán ở đây là cái gì và vì sao nên lựa <br />
chọn thuật toán tối ưu để giải bài toán, từ đó đứng trước một bài toán học <br />
sinh biết nhận xét, phân tích các trường hợp để đề xuất, lựa chọn thuật <br />
toán tối ưu giải bài toán sao cho chương trình chạy nhanh hơn.<br />
Thông qua một số thuật toán cơ bản (như sắp xếp, tìm kiếm,…) học sinh <br />
biết vận dụng để có thể giải quyết những bài toán phức tạp hơn.<br />
2.2. Nội dung<br />
2.2.1. Nhắc lại các bước lập trình giải bài toán trên máy tính <br />
Thông thường khi lập trình giải bài toán trên máy tính học sinh hay bị <br />
mắc sai lầm là viết chương trình luôn mà bỏ qua các bước giải bài toán trên <br />
máy tính, vì vậy có khi chương trình đã chạy nhưng sai kết quả vì hiểu sai <br />
đề, hoặc thuật toán chưa khả thi…<br />
Vì vậy khi dạy lập trình giáo viên nhắc học sinh không nên ngay lập tức <br />
viết chương trình mà nên nhớ lại các bước giải bài toán trên máy tính. Việc <br />
giải bài toán trên máy tính thường được tiến hành qua 5 bước sau:<br />
+ Bước 1: Xác định bài toán;<br />
+ Bước 2: Lựa chọn hoặc thiết kế thuật toán;<br />
+ Bước 3: Viết chương trình;<br />
+ Bước 4: Hiệu chỉnh;<br />
+ Bước 5: Viết tài liệu.<br />
Trong 5 bước giải bài toán trên máy tính thì bước lựa chọn hoặc thiết kế <br />
thuật toán đặc biệt rất quan trọng để các em có thể phân tích đề bài, tìm ra <br />
hướng giải, thuật toán phù hợp.<br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 5<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
2.2.2. Một số khái niệm<br />
2.2.2.1. Khái niệm thuật toán<br />
2.2.2.1.1. Thuật toán là gì<br />
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 <br />
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ừ <br />
Input của bài toán, ta nhận được Output cần tìm.<br />
2.2.2.1.2. Các tính chất của thuật toán<br />
Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện <br />
các thao tác.<br />
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 <br />
thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo.<br />
Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output <br />
cần tìm.<br />
2.2.2.1.3. Vì sao phải lựa chọn thuật toán tối ưu<br />
a. Vì sao phải lựa chọn thuật toán tối ưu<br />
Sau khi đã xây dựng được một thuật toán và một chương trình tương <br />
ứng, mặc dù đã được cài đặt theo một thuật toán đúng và đáp ứng được các <br />
tính chất của thuật toán nhưng có thể không cho kết quả mong muốn đối <br />
với một bộ dữ liệu nào đó vì hoặc là nó đòi hỏi quá nhiều thời gian, hoặc là <br />
không có đủ bộ nhớ để lưu giữ dữ liệu và các biến của chương trình. Vì <br />
vậy ta cần phân tích thuật toán để đưa ra thuật toán tối ưu.<br />
b. Căn cứ vào đâu để xác định thuật toán là tối ưu<br />
Với một bài toán, không chỉ có một thuật toán, vậy căn cứ vào đâu để có <br />
thể nói được thuật toán này nhanh hơn thuật toán kia? Ta có thể căn cứ vào <br />
thời gian và bộ nhớ cần thiết để thực hiện thuật toán. Trong đề tài này ta <br />
<br />
<br />
Trường THPT Mỹ Tho 6<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
sẽ quan tâm đến thời gian thực hiện thuật toán. Việc đánh giá thời gian <br />
thực hiện của thuật toán dẫn tới một khái niệm “độ phức tạp về thời gian <br />
của thuật toán” đã được chứng minh và thường được gọi tắt là độ phức tạp <br />
của thuật toán, kí hiệu là O(..). Độ phức tạp của thuật toán càng nhỏ thì <br />
thuật toán càng chạy nhanh và khả thi.<br />
Thời gian thực hiện một thuật toán phụ thuộc vào rất nhiều yếu tố như: <br />
kích thước của dữ liệu đưa vào, lựa chọn, bố trí kiểu dữ liệu có hợp lý <br />
không… <br />
Vậy để tính toán thời gian thực hiện thuật toán ta sẽ đếm số câu lệnh mà <br />
nó thực hiện, hoặc trong một số trường hợp có thể đếm cụ thể phép tính <br />
số học, so sánh, gán…mà thuật toán đòi hỏi thực hiện hoặc có thể chạy <br />
trực tiếp chương trình bằng một ngôn ngữ lập trình cụ thể và thử nghiệm <br />
nó nhờ một số bộ dữ liệu nào đấy rồi so sánh kết quả thử nghiệm với kết <br />
quả mà ta đã biết. <br />
c. Ngôn ngữ thuật toán<br />
Ngôn ngữ dùng để miêu tả thuật toán gọi là ngôn ngữ thuật toán.<br />
Thuật toán thường được mô tả bằng một dãy các lệnh. Bộ xử lý sẽ thực <br />
hiện các lệnh đó theo một trật tự nhất định cho đến khi gặp lệnh dừng thì <br />
kết thúc.<br />
Ngôn ngữ thuật toán bao gồm:<br />
+ Ngôn ngữ liệt kê từng bước;<br />
+ Sơ đồ khối;<br />
+ Ngôn ngữ lập trình <br />
Trong đề tài này tôi ưu tiên sử dụng ngôn ngữ liệt kê từng bước và <br />
ngôn ngữ lập trình Pascal.<br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 7<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
2.2.3. Một số thuật toán cơ bản thường dùng<br />
2.2.3.1. Thuật toán sắp xếp<br />
2.2.3.1.1. Bài toán<br />
* Bài toán: Cho số nguyên dương N và dãy A gồm N số nguyên: a1, a2,…, <br />
aN. Sắp xếp dãy A thành dãy không giảm (tức là số hạng trước không lớn <br />
hơn số hạng sau).<br />
* Ví dụ: Cho N=6, dãy A: 3 2 1 4 6 3<br />
=> Dãy sau khi sắp xếp: 1 2 3 3 4 6<br />
2.2.3.1.2. Thuật toán<br />
Trong quá trình học tập và giảng dạy tôi đã được học và biết có rất <br />
nhiều phương pháp sắp xếp (chẳng hạn như sắp xếp kiểu lựa chọn, sắp <br />
xếp kiểu thêm dần, sắp xếp kiểu phân đoạn, sắp xếp kiểu vun đống, sắp <br />
xếp kiểu hòa nhập hai đường trực tiếp, sắp xếp tuần tự, tráo đổi, sắp xếp <br />
nhanh Quick sort…). Tuy nhiên trong chương trình tin học phổ thông tôi ưu <br />
tiên sử dụng phương pháp sắp xếp bằng tráo đổi và sắp xếp nhanh Quick<br />
sort. Tôi nhận thấy: phương pháp sắp xếp bằng tráo đổi đơn giản dễ hiểu <br />
với học sinh, số lượng phép tính toán, chi phí thời gian thực hiện cũng <br />
không quá cao, tuy nhiên nếu tập dữ liệu đưa vào lớn thì phương pháp này <br />
bộc lộ hạn chế; còn phương pháp sắp xếp nhanh Quick sort thì quả là một <br />
thuật toán sắp xếp tuyệt vời, có chi phí thời gian thấp.<br />
Trong đề tài này tôi đưa ra hai thuật toán sắp xếp đó là: sắp xếp bằng <br />
tráo đổi và sắp xếp nhanh Quick sort để độc giả có sự so sánh và sử dụng <br />
linh hoạt trong trường hợp cụ thể.<br />
2.2.3.1.2.1. Thuật toán sắp xếp bằng tráo đổi <br />
<br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 8<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
* Ý tưởng phương pháp: Với mỗi cặp số hạng đứng liền kề trong dãy, <br />
nếu số trước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp <br />
lại cho đến khi không có sự đổi chỗ nào nữa.<br />
* Thuật toán:<br />
Procedure sapxeptraodoi;<br />
Var i, j, tg: integer;<br />
begin<br />
For i:=1 to n1 do<br />
For j:= n downto i+1 do<br />
If a[j] mỗi lần duyệt i <br />
phải thực hiện n1 phép so sánh để tìm ra giá trị lớn nhất đẩy về cuối dãy. <br />
<br />
n * (n 1)<br />
Vậy số phép toán cần thiết là: (n1)+(n2)+…+1= => Độ phức tạp <br />
2<br />
<br />
của thuật toán xấp xỉ cỡ O(n2).<br />
2.2.3.1.2.2. Thuật toán sắp xếp nhanh Qicksort<br />
* Ý tưởng phương pháp: <br />
Để sắp xếp dãy trước tiên ta chọn một phần tử ngẫu nhiên trong dãy làm <br />
“chốt”. Mọi phần tử có giá trị nhỏ hơn “chốt” phải được xếp vào vị trí <br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 9<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
trước “chốt” (đầu dãy); mọi phần tử có giá trị lớn hơn “chốt” phải được <br />
xếp vào vị trí sau “chốt” (cuối dãy). Khi đó dãy cần sắp xếp được phân <br />
thành hai đoạn: một đoạn gồm các phần tử có giá trị nhỏ hơn “chốt”, một <br />
đoạn gồm các phần tử có giá trị lớn hơn “chốt”. Cứ tiếp tục sắp xếp lặp đi <br />
lặp lại như vậy với các đoạn con cuối cùng ta sẽ thu được dãy đã được sắp <br />
xếp theo chiều tăng dần.<br />
* Thuật toán:<br />
procedure qs(l,h:longint);<br />
var i,j,k:longint;<br />
begin<br />
if l>=h then exit;<br />
i:=l; j:=h;<br />
k:=a[random(hl+1)+l];<br />
repeat<br />
while a[i]k do dec(j);<br />
if i25. Cách này <br />
sẽ tối ưu hơn. <br />
Chương trình minh họa:<br />
Program bai_toan_co_2;<br />
uses crt;<br />
var g,c: integer;<br />
begin<br />
clrscr;<br />
for c:=9 to 25 do<br />
begin<br />
g:=36c;<br />
if ((4*c+2*g)=100) then<br />
write('So ga la: ',g,' So cho la: ',c);<br />
end;<br />
end. <br />
2.2.4.2. Ví dụ 2<br />
Cho mảng A gồm n phần tử. Hãy viết chương trình tạo mảng B[1..n], <br />
trong đó b[i] là tổng của i phần tử đầu tiên của A. ( Bài 2 Bài tập và thực <br />
hành 4 SGK trang 66)<br />
* Xác định bài toán:<br />
+ Input: mảng A gồm n phần tử;<br />
<br />
<br />
<br />
Trường THPT Mỹ Tho 16<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
+ Output: tạo mảng b[1..n], trong đó b[i] là tổng của i phần tử đầu tiên của <br />
a;<br />
* Để giải quyết 1 bài toán có thể có rất nhiều thuật toán để giải. Giả sử <br />
thoạt đầu có thể sử dụng chương trình sau (có trong SGK) để giải quyết <br />
bài toán này:<br />
program subsum1;<br />
const nmax=100;<br />
type myarray= array[1..nmax] of integer;<br />
var a,b:myarray;<br />
n,i,j:integer;<br />
begin<br />
randomize;<br />
write ('nhap n');<br />
readln(n);<br />
{ Tao ngau nhien mang gom n so nguyen}<br />
for i:=1 to n do a[i]:=random(300)random(300);<br />
for i:=1 to n do write(a[i]:5);<br />
writeln;<br />
{ Bat dau tao b}<br />
for i:=1 to n do<br />
begin<br />
b[i]:=0;<br />
for j:=1 to i do b[i]:=a[i]+a[j];<br />
end;<br />
{ Ket thuc tao b}<br />
<br />
<br />
Trường THPT Mỹ Tho 17<br />
Giáo viên: Nguyễn Thị Phương Ngân Tổ: Lý – Tin KTCN<br />
<br />
<br />
for i:=1 to n do write(b[i]:6);<br />
readln<br />
end.<br />
Chạy thử chương trình với một số bộ test ngẫu nhiên ta có:<br />
<br />
n Mảng a Mảng b<br />
3 103 226 37 103 329 292<br />
<br />
<br />
<br />
4 106 47 212 48 106 153 365 317<br />
<br />
<br />
<br />
9 136 122 207 63 95 152 60 55 156 136 258 465 528 433 281 221 166 322<br />
<br />
<br />
<br />
<br />
* Quan sát từ đoạn{ Bat dau tao b} ta thấy phải sử dụng 2 vòng lặp for lồng <br />
nhau for i:=1 to n do<br />
begin<br />
b[i]:=0;<br />
for j:=1 to i do b[i]:=a[i]+a[j];<br />
end;<br />
* Nếu sử dụng thuật toán trên thì máy tính phải thực hiện n(n+1)/2phép <br />
cộng.<br />
* Trong bài toán này ta thấy:<br />
b[1]=a[1]<br />
b[i]=b[i1]+a[i] , 1
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
