Đăng ký Đăng nhập
Trang chủ Skkn một số phương pháp giải toán trong bdhsg tin học...

Tài liệu Skkn một số phương pháp giải toán trong bdhsg tin học

.DOC
12
792
99

Mô tả:

Së GD&§T QU¶NG B×NH TRêng thpt sè 1 bè tr¹ch ĐỀ TÀI: MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN TRONG BỒI DƯỠNG HỌC SINH GIỎI Ở TRƯỜNG PT Gv: NguyÔn H÷u §øc Tæ: Tin Häc N¨m häc 2012-2013 Mục lục I. Lý do chọn đề tài Tr 3 II. Phần nội dung đề tài Tr 4 1. Cơ sở lý luận của đề tài Tr 4 2. Thực trạng của vấn đề Tr 4 3. Các biện pháp giải quyết vấn đề Tr 4 a. Giới thiệu phương pháp đánh dấu Tr 4 b. Giới thiệu phương pháp sinh Tr 6 c. Xây dựng công thức truy hồi Tr 9 4. Hiệu quả của sáng kiến kinh nghiệm Tr 10 III. Tr 11 Kết luận Tài liệu tham khảo Tr 12 2 Tên đề tài : MỘT SỐ PHƯƠNG PHÁP GIẢI TOÁN TRONG BỒI DƯỠNG HỌC SINH GIỎI Ở TRƯỜNG PT I. LÝ DO CHỌN ĐỀ TÀI Bồi dưỡng học sinh giỏi là một nhiệm vụ rất cần thiết và quan trọng đối với mỗi giáo viên, việc tìm tòi, sưu tầm, biên tập và tích lũy các dạng toán, các phương pháp giải là công việc thường nhật của mỗi giáo viên nhằm nâng cao trình độ chuyên môn nghiệp vụ, tích lũy kinh nghiệm cho bản thân. Trong quá trình giảng dạy môn Tin học 11, các vấn đề đã được đề cập theo kiến thức kỹ năng của chương trình Tin học phổ thông và áp dụng vào giải một số bài tập thực tế có hiệu quả, tuy nhiên các vấn đề đó mới được giới thiệu ở mức độ cơ bản, giải các bào toán đơn giản với dữ liệu vào nhỏ, chưa nghiên cứu ở mức độ sâu rộng hơn, việc giải các bài toán trong các đề thi học sinh giỏi gặp rất nhiều khó khăn, chính vì vậy, để phục vụ cho quá trình giảng dạy và đặc biệt là công tác bồi dưỡng học sinh giỏi cấp THPT, tôi đã tổng hợp được một số phương pháp giải toán cơ bản nhằm phục vụ cho công tác bồi dưỡng học sinh giỏi bộ môn Tin học ở trường PT. Mục đích là giới thiệu một số phương pháp cùng thuật toán giải các bài toán tiêu biểu cho phương pháp đó. Dưới đây là một số phương pháp: - Tìm hiểu thuật toán phương pháp đánh dấu. - Tìm hiểu thuật toán phương pháp sinh. - Xây dựng công thức truy hồi. - Giới thiệu một số thuật toán và cài đặt chương trình thể hiện các thuật toán đó. 3 II. PHẦN NỘI DUNG 1. CƠ SỞ LÝ LUẬN CỦA ĐỀ TÀI Việc bồi dưỡng học sinh giỏi là việc làm thường nhật hằng năm của giáo viên, nếu chỉ sử dụng những kiến thức được trang bị theo yêu cầu của chương trình phổ thông sẽ gặp rất nhiều khó khăn, thậm chí có nhiều bài toán không giải được theo yêu cầu với dữ liệu vào lớn và thời gian thực hiện ngắn. Mặt khác việc phân loại các phương pháp giải toán trong công tác bồi dưỡng học sinh giỏi hiện nay chưa nhiều. Dựa vào cấu trúc đề ra môn Tin học qua các kì thi học sinh giỏi Tỉnh Dựa vào các kiến thức cơ bản mà học sinh đã được học trong chương trình Tin học phổ thông 2. THỰC TRẠNG CỦA VẤN ĐỀ - Những kiến thức trong chương trình Tin học phổ thông còn hạn chế hoặc không đủ đáp ứng cho việc giải một số bài toán trong các kì thi học sinh giỏi Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian thực hiện ngắn. - Việc tổng hợp các phương pháp giải nhằm giúp học sinh có thể so sánh các cách giải, các kết quả còn ít. 3. CÁC BIỆN PHÁP GIẢI QUYẾT VẤN ĐỀ Từ thực trạng trên, tôi xin tổng hợp một số phương pháp để giải một số dạng toán cơ bản trong công tác bồi dưỡng học sinh giỏi Tỉnh như sau: a. Giới thiệu phương pháp đánh dấu Kỹ thuật đánh dấu phần tử thường được sử dụng khi giải các bài toán cần đến chọn những phần tử theo yêu cầu nào đó. Để chọn phần tử ta thực hiện đánh dấu phần tử đó bằng cách: sử dụng một mảng M, đánh dấu M[i]:=true để chọn phần tử i, M[i] := false để không chọn phần tử i. Bài toán ví dụ: Viết chương trình in ra tệp NT.OUT tất cả các số nguyên tố <=60000. (Yêu cầu chương trình chạy không quá 2 giây) Với bài toán này, chúng ta có thể sử dụng phương pháp thông thường để giải: Var i,d: word; F: text; function nguyento(n: word): boolean; var j: byte;kt:boolean; begin if n<=1 then nguyento:=false else 4 begin j:=2; kt:=true; while (j<=sqrt(n)) and (kt=true) do if n mod j =0 then kt:=false else j:=j+1; if kt=true then nguyento:=true else nguyento:=false; end; end; Begin Assign(f, ‘NT.OUT’); Rewrite(f); for i:=2 to 60000 do if nguyento(i)=true then write(f,i,' '); close(f); readln end. Tuy nhiên khi viết chương trình như ở trên, sẽ không đảm bảo yêu cầu về mặt thời gian. Ta có thể sử dụng phương pháp đánh dấu để giải bài toán trên như sau. Ta thấy với bất kỳ số nguyên N (N>1) thì bội của N (khác N) đều không phải nguyên tố. Giả sử N là nguyên tố, khi đó ta đánh dấu tất cả các số là bội của N đều bằng false. Như vậy ta không cần kiểm tra đối với các số đã được đánh dấu đó nữa. Để đánh dấu ta sử dụng một mảng gồm 60000 phần tử kiểu Boolean. Thuật toán được mô tả như sau: B1: Khởi tạo mảng A[]=true; B2: Lặp: với mỗi n ⒂[2..60000] ta thực hiện: Nếu A[n]=true thì Đánh dấu tất cả các bội của n thành false (i:=2 ⅴ60000 div i: A[n*i]:=false) B3: Duyệt mảng A, nếu A[i]=true thì in i Chương trình: uses crt; type mm= array[1..60000] of boolean; var a: mm; n,i,j,d: word; 5 begin clrscr; for i:=1 to 60000 do a[i]:=true;a[1]:=false; for i:=2 to 60000 do if a[i]=true then for j:=2 to 60000 div i do a[i*j]:=false; for i:=2 to 60000 do if a[i]=true then write(i,' '); readln end. Với cách giải này, thời gian máy thực hiện không quá 2 giấy. b. Giới thiệu về phương pháp sinh Phương pháp sinh có thể áp dụng để giải bài toán liệt kê tổ hợp đặt ra nếu như hai điều kiện sau thoả mãn: - Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê. Từ đó có thể xác định được cấu hình đầu tiên và cấu hình cuối cùng trong thứ tự đã xác định - Xây dựng được thuật toán từ cấu hình chưa phải cấu hình cuối, sinh ra được cấu hình kế tiếp nó. Phương pháp sinh có thể mô tả như sau: ; Repeat <Đưa ra cấu hình đang có>; ; Until ; * Bài toán ví dụ: LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N Một dãy nhị phân độ dài n là một dãy x = x 1x2...xn trong đó xi � {0, 1} (  i : 1 ≤ i ≤ n). Dễ thấy: một dãy nhị phân x độ dài n là biểu diễn nhị phân của một giá trị nguyên p(x) nào đó nằm trong đoạn [0, 2n - 1]. Số các dãy nhị phân độ dài n = số các số nguyên � [0, 2n- 1] = 2n. Ta sẽ lập chương trình liệt kê các dãy nhị phân theo thứ tự từ điển có nghĩa là sẽ liệt kê lần lượt các dãy nhị phân biểu diễn các số nguyên theo thứ tự 0, 1,..., 2n-1. 6 Ví dụ: Khi n = 3, các dãy nhị phân độ dài 3 được liệt kê như sau: p(x) 0 X 000 001 1 2 3 4 5 6 010 011 100 101 110 111 7 Như vậy dãy đầu tiên sẽ là 00...0 và dãy cuối cùng sẽ là 11...1. Nhận xét rằng nếu dãy x = (x1, x2, ..., xn) là dãy đang có và không phải dãy cuối cùng thì dãy kế tiếp sẽ nhận được bằng cách cộng thêm 1 ( theo cơ số 2 có nhớ) vào dãy hiện tại. Ví dụ khi n = 8: Dãy đang có: 10010000 cộng thêm 1: +1 Dãy mới: 10010001 Dãy đang có: 10010111 cộng thêm 1: Dãy mới: +1 10011000 Như vậy kỹ thuật sinh cấu hình kế tiếp từ cấu hình hiện tại có thể mô tả như sau: Xét từ cuối dãy về đầu (xét từ hàng đơn vị lên), gặp số 0 đầu tiên thì thay nó bằng số 1 và đặt tất cả các phần tử phía sau vị trí đó bằng 0. i := n; While (i > 0) and (xi = 1) do i := i - 1; If i > 0 then Begin xi := 1; For j := i + 1 to n do xj := 0; End; Cụ thể: Dữ liệu vào (Input): nhập từ file văn bản NHIPHAN.INP chứa số nguyên dương n ≤ 100 Kết quả ra (Output): ghi ra file văn bản NHIPHAN.OUT các dãy nhị phân độ dài n. NHIPHAN.INP NHIPHAN.OUT 3 000 001 7 010 011 100 101 110 111 Chương trình thể hiện thuật toán sinh dãy nhị phân Program nhiphan; Const max = 100; fi = ‘Nhiphan.inp’; fo = ‘Nhiphan.out’; type mm= Array[1..max] of Integer; Var A: mm; n, i,j: Integer; f1,f2:text; Begin Assign(f1, fi); Reset(f1); Assign(f2, fo); Rewrite(f2); Readln(f1,n); FillChar(A, SizeOf(A), 0); If n=0 then Write(f2,0) Else Repeat for i := 1 to n do Write(f2,A[i]); Writeln(f2); i := n; While (i > 0) and (x[i] = 1) do Dec(i); if i > 0 then Begin A[i] := 1; for j:=i+1 to n do A[i]:=0; End; 8 until i = 0; Close(f1); Close(f2); End. c. Xây dựng công thức truy hồi. Đây là bước rất quan trọng trong việc giải các bài toán bằng phương pháp quy hoạch động. Cơ sở xây dựng công thức truy hồi: Xét xem bài toán có thể tìm được nghiệm từ các bài toán nhỏ hơn hay không, việc xây dựng công thức tổng quát để tìm nghiệm của bài toán từ các bài toán con gọi là công thức truy hồi. Bài toán ví dụ: Cho số tự nhiên n (n<=100). Hãy cho biết có bao nhiêu cách phân tich số n thành tổng của dãy các số nguyên dương. (Các cách phân tích là hoán vị của nhau chỉ tính một cách. Nếu n=0 cũng có 1 số cách phân tích) (Ví dụ: n=5 có 7 cách: 5=1+1+1+1+1 ) 5=1+1+1+2 5=1+1+3 5=1+2+2 5=1+4 5=2+3 5=5  Phương pháp: Nếu gọi F[m,v] là số cách phân tích số v thành tổng các số nguyên dương <=m. Khi đó số cách phân tích có 2 loại: - Loại 1: Không chứa số m trong phép phân tích, lúc này số cách phân tích loại này chính là số cách phân tích số v thành tổng các số v thì chỉ có loại 1, còn nếu m<=v thì phải cả loại 1 và loại 2, nên ta có công thức: + Nếu m>v thì F[m,v]=F[m-1,v] + Nếu m<=v thì F[m,v]=F[m-1,v] + F[m,v-m] Đây chính là công thức truy hồi tính F[m,v] thông qua F[m’,v’] với dữ liệu bé hơn. Vậy với bài toán trên, ta sẽ lấy kết quả là: F[n,n] chính là số cách phân tích số n thành tổng các số <=n. 9 Theo bài ra ta có F[0,0]=1; F[0,v]=0 vì không có cách nào để phân tích số v nguyên dương thành tổng các số <=0. Như vậy ta cần sử dụng một mảng 2 chiều và khởi tạo giá trị ban đầu như trên, sau đó dùng công thức truy hồi để tính F[n,n] chính là số cách phân tích cần tìm. Chương trình: type mm=array[0..100,0..100] of byte; var f: mm; n,m,v,k: byte; Begin write('n= ');readln(n); fillchar(f[0],sizeof(f[0]),0); f[0,0]:=1; for k:=1 to n do for v:=0 to n do if k>v then f[k,v]:=f[k-1,v] else f[k,v]:=f[k-1,v]+f[k,v-k]; writeln('so cach phan tich la: ',f[n,n]); readln end. 4. HIỆU QUẢ CỦA SÁNG KIẾN KINH NGHIỆM Qua các năm giảng dạy và tham gia bồi dưỡng học sinh giỏi Tỉnh, tôi đã áp dụng các phương pháp trên để thực hiện giảng dạy và đạt được kết quả bước đầu. Trong khi giảng dạy, học sinh có được phương pháp mới để làm bài nên các em rất có hứng thú trong học tập, từ đó mà các em đam mê Tin học hơn. Kết quả bồi dưỡng học sinh giỏi từ những năm gần đây đều đạt giải, cụ thể: năm học 2009-2010 một giải 3, năm 2010-2011 một giải ba, năm 2011-2012: hai giải ba, ba giải KK, năm 2012-2013: một giải ba, một giải KK. 10 III. KẾT LUẬN: Từ thực tế giảng dạy và bồi dưỡng học sinh giỏi, tôi nhận thấy: Với mỗi dạng toán cần có phương pháp giải phù hợp, với mỗi bài toán cần tìm giải thuật tối ưu cùng với việc xây dựng cấu trúc dữ liệu lưu trữ hợp lý. Đồng thời phải phù hợp với sự phát triển tâm sinh lý và trí tuệ của học sinh. Qua các năm giảng dạy, cùng với sự tìm tòi các tài liệu, các bài viết trên mạng Internet cùng với cấu trúc đề ra và kiến thức cơ bản qua các kì thi chọn học sinh giỏi Tỉnh, tôi thấy với ba phương pháp cơ bản trên học sinh có thể tiếp thu để giải nhiều bài toán. Với mỗi phương pháp chúng ta có thể đưa ra rất nhiều ví dụ để học sinh có thể vận dụng, tuy nhiên trong phạm vi của một sáng kiến kinh nghiệm, tôi chỉ đưa ra một ví dụ để trình bày cho một phương pháp. Trên đây là một số phương pháp cơ bản trong bồi dưỡng học sinh giỏi ở trường phổ thông. Vì kinh nghiệm chưa nhiều, không thể tránh khỏi các hạn chế, rất mong sự đóng góp ý kiến của quý thầy cô giáo. Tôi xin chân thành cảm ơn! 11 Tài liệu tham khảo: 1. Sách giáo khoa Tin học 11, sách giáo viên Tin học 11. 2. Ngôn ngữ lập trình Turbo Pascal – Quách Tuấn Ngọc 3. Tài liệu tập huấn bối dưỡng học sinh giỏi – Lê Thủy Thạch 4. Tài liệu tập huấn – Nguyễn Xuân Huy 5. Cấu trúc dữ liệu và giải thuật – Đỗ Xuân Lôi 12
- Xem thêm -

Tài liệu liên quan