Tài liệu Phát triển tư duy thuật toán qua một số bài toán lập trình

SỞ GD & ĐT THANH HÓA TRƯỜNG THPT YÊN ĐỊNH 2 -------------------- SÁNG KIẾN KINH NGHIỆM Tên đề tài: PHÁT TRIỂN TƯ DUY THUẬT TOÁN QUA MỘT SỐ BÀI TOÁN LẬP TRÌNH. Họ và tên: Lương Trung Dũng Chức vụ: TTCM Đơn vị công tác: Trường THPT Yên Định 2 SKKN thuộc môn: Tin học THANH HOÁ, NĂM 2013 0 A. ĐẶT VẤN ĐỀ I. CƠ SỞ LÝ LUẬN Trong các bài toán có những lúc chúng ta tỏ ra bế tắc trước những hướng đi để tìm lời giải cho bài toán, vấn đề tìm ra một hướng đi đúng đắn cho bài toán thực sự là một vấn đề khó đối với học sinh nói chung và đối với học sinh học môn tin học THPT nói riêng. Khi đứng trước một bài toán lạ, không chỉ học sinh thường tỏ ra lúng túng, mà đối với các giáo viên cũng tỏ ra rất lúng túng không biết lựa chọn phương pháp nào để đưa ra lời giải cho bài toán. Có nhiều lúc những bài toán hết sức đơn giản nhưng chúng ta chưa khôn khéo đưa bài toán đó về dạng quen thuộc để giải bài toán, cuối cùng dẫn tới con đường bế tắc không tìm ra được lời giải hay thuật toán đúng đắn. Nhìn chung chính học sinh và cả chúng ta nữa, chúng ta chưa có phương pháp đúng để đưa một bài toán đó từ bài toán mà chúng ta chưa hề hay biết về bài toán chúng ta đã biết. Với những bài toán ta luôn hướng tới sự hoàn thiện tư duy và phát triển khả năng thuật toán cho học sinh. Đặc biệt đối với học sinh khá giỏi ta cần phát triển sự tư duy cho học sinh để các em có thể phát triển khả năng thuật toán và kỷ thuật lập trình. Chính vỳ lý do đó mà tôi chọn đề tài “Phát triển tư duy thuật toán qua một số bài toán lập trình” nhằm xây dựng cho các em kỷ năng tư duy và phát triển tốt nhất. II. CƠ SỞ THỰC TIỄN. Qua 8 năm giảng dạy bộ môn tin học trong một trường phổ thông, qua các kỳ thi học sinh giỏi tin học trong những năm vừa qua với một số vấn đề khi đưa ra một số bài toán khó trong tin học, yêu cầu học sinh tìm lời giải cho bài toán thì học sinh thường không tìm ra được thuật toán một cách nhanh chóng, có chăng các em cũng đưa ra được một vài ý tưởng cho thuật toán nhưng chưa thực sự sát để mang lại kết quả. Thêm vào đó trong chương trình tin học 11 chỉ dừng lại ở một số kỷ năng cơ bản và đơn giản qua các bài toán. Do đó sử dụng phương pháp xây dựng kỷ năng và kỷ thuật lật trình để đi tìm lời giải cho các bài toán. Bài toán 1: Cho dãy gồm N phần tử a1, a2,...an. Sắp xếp dãy theo trật tự không giảm (hoặc không giảm). Dữ liệu: Vào từ tệp SAPXEP.INP gồm; - Dòng đầu ghi số N là số phần tử của mảng. - Dòng tiếp theo ghi các phần tử của mảng từ a 1 đến an, các phần tử cách nhau bởi 1 dấu cách. Kết quả: Ghi ra tệp SAPXEP.OUT 1 Ghi dãy đã sắp xếp trên dòng và các số cách nhau 1 dấu cách SAPXEP.INP SAPXEP.OUT 4 3458 3854 Cơ sở sắp xếp: Với dãy N phần tử ta có thể có nhiều cách để xếp. Thuật toán tráo đổi dễ hiểu đối với học sinh tuy nhiên chưa tối ưu. Ta có thể sử dụng thuật toán Quicksort để tăng hiệu quả sắp xếp lên nhiều và ta kết hợp sử dụng nó bằng đề qui. Đây là một bài toán quen thuộc đối với học sinh trong khi giải bài toán tìm kiếm. Ta có thể nâng lên sắp xếp chỉ mục để tăng khả năng xắp sếp cho mục tin lớn Chúng ta vận dụng bài toán này để giải các bài toán sau: Bài toán 2: Dãy FAREY. Ứng với số tự nhiên N>0, ta có dãy Farey gồm các phân số tối giản có giá trị lớn hơn 0 và nhỏ hơn 1 theo thứ tự tăng dần. Ví dụ: Với N=4 ta có dãy phân số 1 1 1 2 3 ; ; ; ; 4 3 2 3 4 Yêu cầu: Cho số tự nhiên N (0a[j] then Begin Tg:=a[i];A[i]:=a[j];A[j]:=tg; End; End; 5 Thuật toán sắp xếp bằng Quicksort: Var a:array[1..1000] of integer; N:integer; Procedure quicksort(d,c:integer); Var i,j,tg,m:integer; Begin I:=d; j:=c; M:= a[(i+j) div 2]; While i<=j do Begin While a[i]m do dec(j); If i<=j then Begin Tg:=a[i];A[i]:=a[j];A[j]:=tg; Inc(i); dec(j); End; End; If di then quicksort(i,c); End; Sau khi giới thiệu thuật toán Quicksort học sinh đã năm được cách thức sử dụng thuật toán. Ta hướng tới việc dùng chỉ mục để sắp xếp mảng. ở đây ta sử dụng mảng b để lưu vị trí (chỉ số) của phần tử trong mảng a. Ta tiến hành cài đặt thuật toán như sau: Sắp xếp chỉ mục bằng Quicksort: Ta khởi tạo chỉ mục cho mảng b là vị trí của chính nó ban đầu của mảng a. Dùng thủ tục Procedure Init; Var a:array[1..1000] of integer; b:array[1.1000] of word; N:integer; Procedure Init; Var i:word; Begin For i:=1 to n do b[i]:=i; End; Procedure quicksort(d,c:integer); Var i,j,tg,m:integer; 6 Begin I:=d; j:=c; M:= a[b[(i+j) div 2]]; While i<=j do Begin While a[b[i]]m do dec(j); If i<=j then Begin Tg:=b[i];b[i]:=b[j];b[j]:=tg; Inc(i);dec(j); End; End; If di then quicksort(i,c); End; Toàn văn chương trình sắp xếp chỉ mục bằng Quicksort Var a:array[1..1000] of integer; b:array[1.1000] of word; N:integer; f:text; Procedure Init; Var i:word; Begin Assign(f,’Sapxep.inp’); Reset(f); Readln(f,N); For i:=1 to n do Begin Read(f,a[i]); b[i]:=i; End; Close(f); End; Procedure ghikq; Var i:word; Begin Assign(f,’Sapxep.out’); Rewrite(f); For i:=1 to n do write(f,a[b[i]],’ ’); Close(f); End; 7 Procedure quicksort(d,c:integer); Var i,j,tg,m:integer; Begin I:=d; j:=c; M:= a[b[(i+j) div 2]]; While i<=j do Begin While a[b[i]]m do dec(j); If i<=j then Begin Tg:=b[i];b[i]:=b[j];b[j]:=tg; Inc(i);dec(j); End; End; If di then quicksort(i,c); End; Begin Init; Quicksort(1,N); Ghikq; End. Nhận xét: - Đối với bài toán gốc này ta không thấy có gì đáng kể giữa 2 phương pháp sắp xếp là tráo đổi thông thường xếp theo khoá và xếp bằng chỉ mục. Điểm ta cần nhận ra ở đây là việc thay đổi của quá trình sắp xếp các phần tử là vị trí của các phần tử trong mảng a vẫn được giữ nguyên so với ban đầu, cấu trúc mảng a không bị thay đổi, việc thay đổi chỉ diễn ra trên chỉ mục của nó. Tức là, nó chỉ thay đổi về mặt chỉ số của các bản ghi bằng một mảng phụ b, do đó khi ta thay đổi kích thước của các mẫu tin thì chỉ số của các phần tử trong mảng vẫn không bị thay đổi (không tăng). - Chúng ta hoàn toàn có thể áp dụng việc sắp xếp này cho mảng có các phần tử phức hợp. Ta xét các bài toán tiếp theo để là rõ thêm việc sắp xếp chỉ mục và ứng dụng của nó. II. GIẢI QUYẾT CÁC BÀI TOÁN Bài toán 2: Dãy FAREY. 8 Ứng với số tự nhiên N>0, ta có dãy Farey gồm các phân số tối giản có giá trị lớn hơn 0 và nhỏ hơn 1 theo thứ tự tăng dần. Ví dụ: Với N=4 ta có dãy phân số 1 1 1 2 3 ; ; ; ; 4 3 2 3 4 Yêu cầu: Cho số tự nhiên N (0b do If a>b then a:=a-b Else b:=b-a; 10 UCLN:=a; End; Procedure Toigian; Var i:word; Begin For i:=1 to k do Begin A[i].t:=a[i].t div UCLN(a[i].t,a[i].m); A[i].m:=a[i].m div UCLN(a[i].t,a[i].m); End; Procedure quicksort(d,c:integer); Var i,j,tg,m:integer; Begin I:=d; j:=c; M:= a[b[(i+j) div 2]].th; While i<=j do Begin While a[b[i]].thm do dec(j); If i<=j then Begin Tg:=b[i];b[i]:=b[j];b[j]:=tg; Inc(i);dec(j); End; End; If di then quicksort(i,c); End; Procedure ghikq; Var i:word; Begin Assign(f,’Farey’.out’); Rewrite(f); { ghi tử số lên dòng thứ nhất và loại phần tử trùng nhau } For i:=1 to k-1 do If a[b[i]].th<>a[b[i+1]].th then write(f,a[b[i]].t,’ ’); write(f,a[b[k]].t); writeln(f); { Ghi mẫu số lên dòng thứ 2 có loại phần tử trùng nhau} 11 For i:=1 to k-1 do If a[b[i]].th<>a[b[i+1]].th then write(f,a[b[i]].m,’ ’); write(f,a[b[k]].m); Close(f); End; Begin Init; Quicksort; Ghikq; End. Nhận xét: - Thuật toán đã cho ta thấy rõ việc sắp xếp bằng chỉ mục Index sort có thể làm được trên dãy có các mục tin lớn rất nhiều mà không bị ảnh hưởng tới giá trị và cấu trúc của các phần tử gốc. - Từ đây học sinh có thể vận dụng để sắp xếp cho các bài toán khác có mẫu tin lớn hơn rất nhiều và hiểu rõ thêm về sắp xếp bằng chỉ mục. - Việc sắp xếp bài toán mang lại phương án tìm ra kết quả dễ dàng. Bài toán 2: BĂNG NHẠC. Người ta cần ghi N bài hát, được mã số từ 1 đến N, vào một băng nhạc có thời lượng tính theo phút đủ chứa toàn bộ các bài đã cho. Với mỗi bài hát ta biết thời lượng phát của bài đó. Băng sẽ được lắp vào một máy phát nhạc đặt trong một siêu thị. Khách hàng muốn nghe bài hát bào chỉ việc nhấn phím ứng với bài đó. Để tìm và phát bài thứ i trên băng, máy xuất phát từ đầu cuộn băng, quay băng để bỏ đi i-1 bài ghi trước bài đó. Thời gian quay băng bỏ qua mỗi bài và thời gian phát bài đó được tính là như nhau. Tính trung bình, các bài hát trong một ngày được khách hàng lựa chọn với số lần như nhau. Hãy tìm cách ghi các bài hát trên băng sao cho tổng thời gian quay băng trong mỗi ngày là ít nhất. Dữ liệu : Vào từ file BANGNHAC.INP - Dòng đầu ghi số N. - Dòng tiếp theo ghi thời lượng các bài hát tương ứng mỗi số cách nhau 1 dấu cách. Kết quả : Ghi ra tệp BANGNHAC.OUT - Các dòng trên ghi 2 số j và d là mã số bài hát và thời gian tìm phát bài. - Dòng cuối ghi tổng thời gian quay băng nếu mối bài phát một lần. Ví dụ : 12 BANGNHAC.INP 3 723 BANGNHAC.OUT 22 35 1 12 19 BANGNHAC.INP : 3 bài Bài 1 : phát 7 phút Bài 2 : phát 2 phút Bài 3 : phát 3 phút BANGNHAC.OUT Tìm và phát bài 2 cần 2 phút Tìm và phát bài 3 cần 5 phút Tìm và phát bài 1 cần 12 phút Tổng thời gian phát mỗi bài 1 lần : 19 phút Phân tích: Với bài toán này, ta dễ dàng nhận thấy một điều để xếp các bài hát vào trong băng nhạc ta có nhiều các x ếp. Gi ả s ử ta có ba b ài hát với số phút lần lượt như sau: Mã số bài hát Thời gian phát 1 7 2 2 3 3 Ta xét vài tình huống ghi băng để rút ra kết luận cần thiết. Trật tự ghi trên băng (x, y, z) (1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1) Thời gian phát T(x) +t(y)+ t(z): thời gian tìm và phát bài i (7) + (7+2) + (7+2+3) = 28 phút (7) + (7+3) + (7+3+2) = 29 phút (2) + (2+7) + (2+7+3) = 23 phút (2) + (2+3) + (2+3+7) = 19 phút (PA tối ưu) (3) + (3+7) + (3+7+2) = 25 phút (3) + (3+2) + (3+2+7) = 20 phút Vậy phương án tối ưu sẽ là (2, 3, 1): ghi bài 2 rồi đến bài 3, cuối cùng là bài 1. Tổng thời gian theo phương án này là 19 phút. Để có phương án tối ưu ta chỉ cần ghi băng theo trật tự tăng dần của thời lượng bài hát. Bài toán được cho với giả thiết băng đủ lớn để ghhi được toàn bộ các bài hát. Việc lựa chọn phương án theo cơ chế này được gọi là “phương pháp tham lam” . Thuật toán: - Thủ tục Procedure Init; dùng để đọc dữ liệu và khởi tạo chỉ mục. - Thủ tục Procedure Quicksort sắp xếp dữ liệu mảng theo chỉ mục. - Thủ tục Procedure ghikq; Thực hiện tính thời gian tổng và ghi kết quả. Toàn văn chương trình: Var a,b:array[1..200] of integer; 13 F:text; N:integer; Procedure Init; Var i,j:word; Begin Assign(f,’Bangnhac.inp’);Reset(f);Readln(f,N); For i:=1 to n do Begin Read(f,a[i]);b[i]:=i; End; Close(f); End; Procedure ghikq; Var i,t,tg:word; Begin Assign(f,’Bangnhac.out’); Rewrite(f); T:=0; tg:=0; For i:=1 to n do Begin T:=t+a[b[i]]; tg:=tg+t; writeln(f,b[i],’ ’,t); End; Write(f,tg); Close(f); End; Procedure quicksort(d,c:integer); Var i,j,tg,m:integer; Begin I:=d; j:=c; M:= a[b[(i+j) div 2]]; While i<=j do Begin While a[b[i]]m do dec(j); If i<=j then Begin Tg:=b[i];b[i]:=b[j];b[j]:=tg; Inc(i);dec(j); End; 14 End; If di then quicksort(i,c); End; Begin Init; Quicksort; Ghikq; End. Nhận xét: - Với phương pháp sắp xếp theo chỉ mục và tìm được phương án tối ưu, đưa ra lời giải cho việc tìm kiếm phương án. Ta có thể thấy việc sắp xếp không chỉ dừng lại cho việc tìm kiếm mà còn lựa chọn được phương án tối ưu. Chính vì vậy trong cùng một phương pháp mà xử lý được nhiều công việc nên ta dùng phương pháp “tham lam”. Ta có thể xét thêm một bài toán nữa để thấy rõ cách thức chọn lựa và tư duy. Bài toán 4: CHỌN VIỆC. Có N công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi 1 giời thực hiện trên máy tính. Với mỗi việc ta biết thời hạn phải nộp kết quả thực hiện sau khi hoàn thành việc đó và tiền thưởng thu được nếu nộp kết quả trước hoặc đúng thời điểm quy định. Chỉ có một máy tính trong tay, hãy lập lịch thực hiện đủ N công việc trên máy tính sao cho tổng số tiền thưởng thu được là lớn nhất và thời gian hoạt động của máy là nhỏ nhất. Giả thiết rằng máy được khởi động vào đầu ca, thời điểm t=0 và chỉ tắt máy sau khi đã hoàn thành đủ N công việc. Dữ liệu : Vào từ tệp VIEC.INP - Dòng đầu ghi số N - N dòng tiếp theo gồm 2 số t và th, t là thời hạn nộp, th là mức thưởng. Kết quả : Ghi ra tệp VIEC.OUT - i dòng đầu ghi thời gian việc i được làm. - Dòng cuối ghi tổng tiền thưởng thu được. Ví dụ VIEC.INP Ý nghĩa : Cho biết 4 việc 4 1 15 3 10 5 100 1 27 - Việc thứ nhất nộp không muộn hơn 1 giờ thưởng 15 ngàn - Việc thứ hai nộp không muộn hơn 3 giờ thưởng 10 ngàn - Việc thứ ba nộp không muộn hơn 5 giờ thưởng 100 ngàn - Việc thứ tư nộp không muộn hơn 1 giờ thưởng 27 ngàn 15 Ý nghĩa : VIEC.OUT 4 2 3 1 137 - Giờ thứ 1 thực hiện công việc 4 nộp đúng hạn nên được thưởng 27 ngàn. - Giờ thứ 2 thực hiện công việc 2 nộp đúng hạn nên được thưởng 10 ngàn. - Giờ thứ 3 thực hiện công việc 3 nộp đúng hạn nên được thưởng 100 ngàn. - Giờ thứ 4 thực hiện công việc 1 nộp không đúng hạn nên không được thưởng nhưng vẫn phải hoàn tất. Phân tích : Ta ưu tiên cho những công việc có tiền thưởng cao, do đó sắp xếp các việc giảm dần theo tiền thưởng. Với mỗi việc k ta đã biết giới hạn thời gian nộp việc đó là h=t[k]. Ta xét trục thời gian b. Nếu giờ h trên trục đó đã bận do công việc khác thì ta tìm thời điểm h trở về trước một thời điểm có thể thực hiện được việc k đó. Nếu tìm được một thời điểm m như vậy, ta đánh dấu bằng mã số của việc đó trên trục thời gian b, b[m] :=k. Sau khi xếp việc xong, có thể trên trục thời gian còn những thời điểm rỗi, ta dồn các việc đã xếp về phía trước nhằm thu được một lịch làm việc trù mật, tức là không có giờ trống. Cuối cùng ta xếp tiếp những việc trước đó xét nhưng không xếp được. Đây là những việc phải làm nhưng không thể nộp đúng hạn nên sẽ không có tiền thưởng. Với thí dụ đã cho, N = 4, thời gian giao nộp t=(1, 3, 5, 1) và tiền thưởng a = (15, 10, 100, 27) ta tính toán như sau : - Khởi trị : trục thời gian b = (0, 0, 0, 0, 0,…). - Chọn việc 3 có tiền thưởng lớn nhất là 100. Xếp việc 3 với thời hạn t[3]=5 vào h : h[5]=3. Ta thu được h = (0, 0, 0, 0, 3). - Chọn tiếp việc 4 có tiền thưởng 27. Xếp việc 4 với thời hạn t[4]=1 vào h : h[1]=4. Ta thu được h = (4, 0, 0, 0, 3). - Chọn tiếp việc 1 có tiền thưởng 15. Xếp việc 1 với thời hạn t[1]=1 vào h: Không xếp được vì thời điểm 1 trở về trước trục thời gian h[1..1]ư đã kín. Ta thu được h = (4, 0, 0, 0, 3). - Chọn nốt việc 2 có tiền thưởng 10. Xếp việc 2 với thời hạn t[2]=3 vào h: h[3]=2. Ta thu được h = (4, 0, 2, 0, 3). - Dồn việc trên trục thời gian h, ta thu được h=(4, 2, 3, 0, 0). - Xếp nốt việc phải làm mà không có thưởng, ta thu được h=(4, 2, 3, 1). - Ca làm việc đúng N giờ. 16 - Chỉ mục b[i]= v>0 cho biết v đứng thứ i trong dãy được sắp giảm theo giá trị tiền thưởng và việc v chưa được xếp. B[i]=v<0 cho biết việc v đã xếp xong trong lần duyệt đầu tiên. Thuật toán : - Các biến mảng a: tiền thưởng, t: thời gian giao nộp, b: chỉ mục, h: trục thời gian ; các biến m: số việc đã xếp, tg: tổng số tiền thưởng. - Thủ tục Procedure Init để khởi tạo các giá trị ban đầu và đọc dữ liệu đầu vào. - Thủ tục Procedure quicksort để sắp xếp mảng a theo chỉ mục dựa trên tiền thưởng. - Thủ tục Procedure xepviec để chọn và ưu tiên xếp các công việc thưởng cao vào vị trí theo ý tưởng đã phân tích. - Thủ tục Procedure donviec để dồn các việc đã xếp về đầu, vị trí trống sẽ thực hiện xếp các công việc không có thưởng cho hoàn thành N công việc. - Thủ tục Procedure xeptiep xếp các công việc còn lại cho hết và hoàn thành. - Thủ tục Procedure Ghikq để ghi kết quả bài toán theo yêu cầu của bài toán đặt ra. Toàn văn chương trình : Var a,b,t, h :array[1..200] of integer ; m, n, tg :integer ; Procedure Init; Var i,j:word; Begin Assign(f,’Viec.inp’); Reset(f);Readln(f,N); For i:=1 to n do Begin Read(f,t[i],a[i]); b[i]:=i; End; Close(f); End; Procedure quicksort(d,c:integer); Var i,j,tg,m:integer; Begin i:=d; j:=c; m:= a[b[(i+j) div 2]]; While i<=j do Begin While a[b[i]]>m do inc(i); While a[b[j]]i then quicksort(i,c); End; Procedure xepviec ; Var i,k,v :integer ; Begin Fillchar(h,sizeof(h),0) ; For i :=1 to N do Begin v:=b[i] ; {việc nào} For k :=t[v] downto 1 do If h[k]= 0 then Begin h[k] :=v ; b[i] :=-v ; Break ; End ; End ; End ; Procedure Donviec ; Var i :integer ; Begin tg :=0 ; {Tìm giờ trống đầu tiên trong h} For i :=1 to 200 do If h[i]= 0 then Begin m :=i ; break ; End ; Else tg :=tg+a[h[i]] ; If M>N then exit ; For i :=m+1 to 200 do If h[i]>0 then Begin h[m] :=h[i]; tg :=tg+a[h[i]] ; Inc(m) ; If m>n then exit ; End ; End ; Procedure xeptiep ; Var i :integer ; Begin For i := 1 to n do If b[i]>0 then Begin h[m] :=b[i] ; Inc(m) ; End ; 18 End ; Procedure ghikq; Var i,t,tg:word; Begin Assign(f,’Viec.out’); For i:=1 to n do writeln(f,h[i]); Write(f,tg); Close(f); End; Begin Init; Quicksort; Xepviec; Donviec; Xeptiep; Ghikq; End. Rewrite(f); III. KẾT LUẬN BÀI TOÁN - Qua bài toán ta thấy rằng với mức độ thông thường để nhìn nhận ra bài toán thực sự là khó khăn đối với học sinh, khi mẫu tin trở nên lớn, ta phải biết khéo léo nhìn nhận bài toán, nhìn nhận bài toán qua việc sắp xếp dữ liệu không còn là đơn giản. - Để đánh giá và rút bài toán sắp xếp cho những bài toán này thì giải thuật tham lam cho chúng ta cách thức để hiểu được vấn đề - Không chỉ là sắp xếp đơn thuần cho các bài toán với kích thước lớn như trên, các bài toán này cho ta thấy được ý nghĩa to lớn của sắp xếp bằng chỉ mục là rất cần thiết. - Ta hoàn toàn có thể tăng kích thước mục tin trong việc sắp xếp, lợi dụng phương pháp tham lam này để giải quyết các bài toán phức tạp hơn như bài toán xếp ba lô, cây bao trùm,… - Thông qua các bài toán ta tăng dần kỷ năng tư duy của học sinh. Việc phát triển bài toán được nâng lên rõ rệt . 19